Generating Cryptographically Secure Random Numbers with Coins and a Cup(blog.sia.tech)
blog.sia.tech
Generating Cryptographically Secure Random Numbers with Coins and a Cup
https://blog.sia.tech/generating-cryptographically-secure-random-numbers-with-coins-and-a-cup-4e223899509e
52 comments
With the important caveat that you catch it, rather than letting it bounce and land.
Just like you do with dice.
If I catch a quarter, I can often feel the heads or tails side and flip it without most people noticing.
I'm not quite perfect at it, but I'd say I'm at 90% heads / 10% tails, as long as its an old-school quarter and not any of these newer ones with crazy designs on the back. (I can feel the Eagle vs Washington's Head pretty well. But the 50-states and stuff are too much for my fingers to memorize. Give me a few minutes with the coin beforehand, maybe I can learn on the spot... if the back is distinct enough from Washington's head).
Its a fun party trick, to remind people that you need to let the coin bounce on the ground if you want a fair toss. If you let someone "catch" the coin, you're prone to all sorts of shennanigans.
I'm not quite perfect at it, but I'd say I'm at 90% heads / 10% tails, as long as its an old-school quarter and not any of these newer ones with crazy designs on the back. (I can feel the Eagle vs Washington's Head pretty well. But the 50-states and stuff are too much for my fingers to memorize. Give me a few minutes with the coin beforehand, maybe I can learn on the spot... if the back is distinct enough from Washington's head).
Its a fun party trick, to remind people that you need to let the coin bounce on the ground if you want a fair toss. If you let someone "catch" the coin, you're prone to all sorts of shennanigans.
Its actually quite easy to toss a coin into the air so that it's rotating while not perpendicular to the ground, but not flipping over. It will land with the same orientation it was tossed into the air with. However, to an observer, it looks like it's flipping.
I used to do that in grade school to win coin flips. Flip the coin, catch it, feel for heads or tails, and depending on what you want present it by either simply opening your fist, or revealing it by flipping it onto the back of your other palm.
Ah, that sounds like a different exploit.
Above, you can fiddle the result of a coin toss by sleight of hand.
Here, you're not dexterous enough for that, but you can fiddle the result anyway by alternating between two processes. This is a more powerful approach!
There was an example of this that stuck with me in the (fantasy) book Another Fine Myth, in which the narrator must perform magic for a king, but lacks the ability to do magic. He has a single gimmick device and needs to pass it off as more than it is.
So he asks the king to choose one of two horses, and, when the king picks the real horse, says "by your word shall that creature be spared". Then the narration remarks that if the king had picked the other (fake) horse, the trick would have been performed on "the creature he [the king] had doomed with a word".
The lesson is, if you're offered a choice, you need to know what it is you're choosing before you make the choice. Participating in a process without knowing what the process consists of is another way to say "being scammed".
Above, you can fiddle the result of a coin toss by sleight of hand.
Here, you're not dexterous enough for that, but you can fiddle the result anyway by alternating between two processes. This is a more powerful approach!
There was an example of this that stuck with me in the (fantasy) book Another Fine Myth, in which the narrator must perform magic for a king, but lacks the ability to do magic. He has a single gimmick device and needs to pass it off as more than it is.
So he asks the king to choose one of two horses, and, when the king picks the real horse, says "by your word shall that creature be spared". Then the narration remarks that if the king had picked the other (fake) horse, the trick would have been performed on "the creature he [the king] had doomed with a word".
The lesson is, if you're offered a choice, you need to know what it is you're choosing before you make the choice. Participating in a process without knowing what the process consists of is another way to say "being scammed".
> Here, you're not dexterous enough for that, but you can fiddle the result anyway by alternating between two processes. This is a more powerful approach!
What you're describing is called "Magician's Force", and its certainly a powerful component of many tricks. But a lot of people are wise to that, so you need to have a backup plan.
Or, you can rely purely on slight of hand / dexterity to get things done.
--------
Really, a good magician uses all the tricks in combination with each other.
If you "lead" with Magician's force, some members of the audience think you're just doing psychological tricks. If you "lead" with dexterity tricks, then by the time you pull out Magician's force, you can trick them into thinking your magician's force was another dexterity trick.
What you're describing is called "Magician's Force", and its certainly a powerful component of many tricks. But a lot of people are wise to that, so you need to have a backup plan.
Or, you can rely purely on slight of hand / dexterity to get things done.
--------
Really, a good magician uses all the tricks in combination with each other.
If you "lead" with Magician's force, some members of the audience think you're just doing psychological tricks. If you "lead" with dexterity tricks, then by the time you pull out Magician's force, you can trick them into thinking your magician's force was another dexterity trick.
[deleted]
Reminds me of the Dice-O-Matic: https://www.youtube.com/watch?v=7n8LNxGbZbs
So basically a senary (base-6) RNG:
* https://en.wikipedia.org/wiki/Senary
* https://en.wikipedia.org/wiki/Senary
I was expecting the author to use polyhedral dice as in the leader image. For example, a d100 can be composed from two 10-sided dice, both read from 1 to 0, side-by-side, the first being the "tens" and the second the "ones". e.g. "3" and "4" reads as "34", "0" and "5" reads as "5" etc. Two "0"s read as "100" so the range of the composite die is 01 to 100. Alternatively, the dice can be read from 0 to 9, yielding a range from 00 to 99. More ten-siders can be added for higher base-10's, for example 6 ten-siders can be read as a number from 000001 to 000000 = 100,000.
The problem with that of course is that polyhedral dice are normally made for gaming and are not, shall we say, entirely fair. I remember someone making an exhaustive evaluation with a machine made with Legos (obviously) and there was a lot of bias especially for some brands of polyhdrals than others.
Edit: One can also generate numbers in, e.g., base-16, etc. in a similar way, composing a d10 and a d6, although this is more cumbersome because each digit now needs two die rolls. I think it's possible to find actual 16-siders though.
The problem with that of course is that polyhedral dice are normally made for gaming and are not, shall we say, entirely fair. I remember someone making an exhaustive evaluation with a machine made with Legos (obviously) and there was a lot of bias especially for some brands of polyhdrals than others.
Edit: One can also generate numbers in, e.g., base-16, etc. in a similar way, composing a d10 and a d6, although this is more cumbersome because each digit now needs two die rolls. I think it's possible to find actual 16-siders though.
The Von Neumann extractor mentioned in the article is interesting.
There are other approaches too. I once implemented an algorithm to remove unknown bias from a bitstream in a streaming fashion. According to the paper I used their result was theoretically optimal. Check it out: https://github.com/tdons/deskew-bernoulli
There are other approaches too. I once implemented an algorithm to remove unknown bias from a bitstream in a streaming fashion. According to the paper I used their result was theoretically optimal. Check it out: https://github.com/tdons/deskew-bernoulli
Can someone help me understand what "entropy" is? In physics, my understanding is that the entropy of a collection of dice in a cup is decreasing over time: the entropy of 5 dice in a row is high, and 5 dice in a messy pile is low. In cryptography we say that this has "generated" entropy, implying that the entropy is increasing over time. Are these actually two separate definitions of the same word, or am I misunderstanding something? Is this a "credit"/"debit" type situation?
[append] A brief internet search indicates that I'm mistaken about the physical definition of entropy and that it does increase over time, never (universally) decrease. That does clarify the confusion I have here but highlights that I clearly don't have a very good mental picture of what "entropy" is.
[append] A brief internet search indicates that I'm mistaken about the physical definition of entropy and that it does increase over time, never (universally) decrease. That does clarify the confusion I have here but highlights that I clearly don't have a very good mental picture of what "entropy" is.
The word entropy can refer to 2 separate things, but they are somewhat related:
https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_...
>My greatest concern was what to call it. I thought of calling it 'information,' but the word was overly used, so I decided to call it 'uncertainty.' When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, 'You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, no one really knows what entropy really is, so in a debate you will always have the advantage.'
https://en.wikiquote.org/wiki/Claude_Elwood_Shannon
https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_...
>My greatest concern was what to call it. I thought of calling it 'information,' but the word was overly used, so I decided to call it 'uncertainty.' When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, 'You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, no one really knows what entropy really is, so in a debate you will always have the advantage.'
https://en.wikiquote.org/wiki/Claude_Elwood_Shannon
Entropy of the universe as a whole is increasing. Localized entropy can go up or down as energy is added/removed or reorganized in the system. Water can freeze or thaw. Dice can be random or in a pattern. But eventually all the suns will go out. It is only the overall temperature of the universe, the largest system, that is always increasing. (Sorry, mixed up my increasings and decreasings. How one discusses entropy can change by context.)
In cryptography, entropy is randomness. The higher degree of randomness something has the more entropy it has. You'll often see entropy expressed in bits.
Here's an XKCD comic that uses entropy. It may give you more context: https://xkcd.com/936/
Here's an XKCD comic that uses entropy. It may give you more context: https://xkcd.com/936/
> As an example, let’s take 2 coins that each have a bias of 75%. The ‘distance from unbiased’ for each coin is 0.25. We double that for each coin to get 0.5, then we multiply them together to get 0.125. Finally, we add 0.5 to get 62.5%. The full equation would be (0.5 + (2x0.25)x(2x0.25)) = 62.5%.
I think the answer here would be 75%, no? 0.5 x 0.5 = .25 not .125, or am I missing something? Maybe the example was supposed to have 3 coins -- then the math would work.
Does that result somehow make sense in that each coin is halfway to being completely biased?
The strange thing in that formula is seen with 2 80% biased coins. You end up with a total bias of 86%. Which goes counter to the idea that mixing biased coins is always an improvement.
I think the answer here would be 75%, no? 0.5 x 0.5 = .25 not .125, or am I missing something? Maybe the example was supposed to have 3 coins -- then the math would work.
Does that result somehow make sense in that each coin is halfway to being completely biased?
The strange thing in that formula is seen with 2 80% biased coins. You end up with a total bias of 86%. Which goes counter to the idea that mixing biased coins is always an improvement.
Something strange is going on in that paragraph for sure. Its not very rigorous.
Lets start with a more rigorous approach: E(heads) == .75 on a biased coin.
Maybe with 100-coin flips, with an average of 75-heads. We have a normalish-distribution centered around 75 where we can still draw a good random number from. It probably wouldn't be too hard to "subtract 25" after 75-flips and get something less biased as a result. That's the idea anyway.
Variance of a single coin flip, or variance(heads) == .75 * .25 == 0.1875. Honestly, I'm not sure where that 62.5% figure comes from at all.
Lets start with a more rigorous approach: E(heads) == .75 on a biased coin.
Maybe with 100-coin flips, with an average of 75-heads. We have a normalish-distribution centered around 75 where we can still draw a good random number from. It probably wouldn't be too hard to "subtract 25" after 75-flips and get something less biased as a result. That's the idea anyway.
Variance of a single coin flip, or variance(heads) == .75 * .25 == 0.1875. Honestly, I'm not sure where that 62.5% figure comes from at all.
edit: Math mistake in the blog post, now fixed and updated. I was missing a '1/2' that you have to multiply the entire product of the coins by.
-------- old comment enumerating all possibilities:
You can see the example is correct by enumerating all possibilities. For coins with a 75% bias, you can represent the possible outcomes by "HHHT". Which means the set of possible outcomes for 2 such coins is:
HHHT x HHHT =
HH HH HH HT
HH HH HH HT
HH HH HH HT
TH TH TH TT
That's 10 instances of HH/TT and 6 instances of HT/TH, or a simulated coin with a 10/16 chance of heads = 0.625 bias.
Two 80% coins looks like:
HHHHT x HHHHT
HH HH HH HH HT
HH HH HH HH HT
HH HH HH HH HT
HH HH HH HH HT
TH TH TH TH TT
Which results in 17/25 outcomes as 'heads', or 68% bias for the simulated coin. Which supports the statement that mixing biased coins is always an improvement.
-------- old comment enumerating all possibilities:
You can see the example is correct by enumerating all possibilities. For coins with a 75% bias, you can represent the possible outcomes by "HHHT". Which means the set of possible outcomes for 2 such coins is:
HHHT x HHHT =
HH HH HH HT
HH HH HH HT
HH HH HH HT
TH TH TH TT
That's 10 instances of HH/TT and 6 instances of HT/TH, or a simulated coin with a 10/16 chance of heads = 0.625 bias.
Two 80% coins looks like:
HHHHT x HHHHT
HH HH HH HH HT
HH HH HH HH HT
HH HH HH HH HT
HH HH HH HH HT
TH TH TH TH TT
Which results in 17/25 outcomes as 'heads', or 68% bias for the simulated coin. Which supports the statement that mixing biased coins is always an improvement.
> For coins with a 75% bias, you can represent the possible outcomes by "HHHT"
Your method seems to lack rigor.
Lets take a fair D4 (https://en.wikipedia.org/wiki/Four-sided_die), and define "Heads" as 1, 2, 3, and 'Tails" and 4. This gives us a perfectly biased 75% Heads coin.
The possibilities are:
* Heads: 75% of the time (123)
* Tails: 25% of the time (4)
--------
With two "flips" of this D4, we've got:
* HH -- 56.25% (11, 12, 13, 21, 22, 23, 31, 32, 33)
* HT -- 18.75% -- Von Neuman Heads (14, 24, 34)
* TH -- 18.75% -- Von Neuman Tails (41, 42, 43)
* TT -- 6.25% (44)
---------
The Von Neuman Method throws away the TT and HH possibilities, leaving an 18.75% chance of heads and an 18.75% chance of tails. The HH and TT require a "reroll". Thus, we've removed the bias of the dice.
In any case, by giving every state an equal chance and a specific name (11, 12, 13...), we have a more rigorous count of the possibilities. I don't know where your method went wrong... but clearly something is off.
Your method seems to lack rigor.
Lets take a fair D4 (https://en.wikipedia.org/wiki/Four-sided_die), and define "Heads" as 1, 2, 3, and 'Tails" and 4. This gives us a perfectly biased 75% Heads coin.
The possibilities are:
* Heads: 75% of the time (123)
* Tails: 25% of the time (4)
--------
With two "flips" of this D4, we've got:
* HH -- 56.25% (11, 12, 13, 21, 22, 23, 31, 32, 33)
* HT -- 18.75% -- Von Neuman Heads (14, 24, 34)
* TH -- 18.75% -- Von Neuman Tails (41, 42, 43)
* TT -- 6.25% (44)
---------
The Von Neuman Method throws away the TT and HH possibilities, leaving an 18.75% chance of heads and an 18.75% chance of tails. The HH and TT require a "reroll". Thus, we've removed the bias of the dice.
In any case, by giving every state an equal chance and a specific name (11, 12, 13...), we have a more rigorous count of the possibilities. I don't know where your method went wrong... but clearly something is off.
>> For coins with a 75% bias, you can represent the possible outcomes by "HHHT"
> Your method seems to lack rigor.
> Lets take a fair D4 (https://en.wikipedia.org/wiki/Four-sided_die), and define "Heads" as 1, 2, 3, and 'Tails" and 4. This gives us a perfectly biased 75% Heads coin.
...but that's exactly the same method you just complained lacked rigor. (It doesn't, but what were you complaining about?)
> Your method seems to lack rigor.
> Lets take a fair D4 (https://en.wikipedia.org/wiki/Four-sided_die), and define "Heads" as 1, 2, 3, and 'Tails" and 4. This gives us a perfectly biased 75% Heads coin.
...but that's exactly the same method you just complained lacked rigor. (It doesn't, but what were you complaining about?)
I think you've misunderstood my method. We aren't using the Von Neumann extractor here, we're counting the total number of heads and saying "heads" for the result if the count is even, and "tails" of the result is odd.
With your D4, that means the HH and TT both count as heads - 62.5% total, which is consistent with everything else.
With your D4, that means the HH and TT both count as heads - 62.5% total, which is consistent with everything else.
Well yes, but actually no
(0.5 + (2x0.25)x(2x0.25)) != 62.5%
Your math there doesn't add up... quite literally
Your math there doesn't add up... quite literally
Great article.
Don’t agree here though:
> If you generate a random string that is 128 bits in length, you are highly likely to find a run of zeroes or ones that is at least 8 long, and finding a run that is 15 long or longer is uncommon but still very possible and not something to be worried about.
In crypto we want the key material to be unpredictable AND uniform.
This uniformity requirement is why we pass the shared secret from an elliptic curve Diffie Hellman interaction through a digest like SHA-2.
Not because the shared curve co-ordinate isn’t random. But because we need to remove any non-uniformity.
Don’t agree here though:
> If you generate a random string that is 128 bits in length, you are highly likely to find a run of zeroes or ones that is at least 8 long, and finding a run that is 15 long or longer is uncommon but still very possible and not something to be worried about.
In crypto we want the key material to be unpredictable AND uniform.
This uniformity requirement is why we pass the shared secret from an elliptic curve Diffie Hellman interaction through a digest like SHA-2.
Not because the shared curve co-ordinate isn’t random. But because we need to remove any non-uniformity.
That is a conflation of two things. The first is an bitstream from a hwrng, and you're right that if it was non-uniform this would probably mean that it was biased and would be a weak key. Not because it has a bunch of zeros in a row, but because the attacker could assume that it did and guess it more easily.
The other issue is the key itself, and in AES for example, there are (believed to be) no 'weak' keys. All zeros is just as secure at mixing the plaintext as anything else. If you reject keys with too many zeros in a row all you're doing is lowering the keyspace you have to work with.
So no, uniformity is not a goal for keys.
The other issue is the key itself, and in AES for example, there are (believed to be) no 'weak' keys. All zeros is just as secure at mixing the plaintext as anything else. If you reject keys with too many zeros in a row all you're doing is lowering the keyspace you have to work with.
So no, uniformity is not a goal for keys.
> So no, uniformity is not a goal for keys.
> you're right that if it was non-uniform this would probably mean that it was biased and would be a weak key
This seems contradictory.
Interesting. Why do you hash the ECDH secret then?
> you're right that if it was non-uniform this would probably mean that it was biased and would be a weak key
This seems contradictory.
Interesting. Why do you hash the ECDH secret then?
> This seems contradictory.
Because there are two entirely different things - one is producing an unbiased bitstream from a potentially biased one (the topic of the article) and the other is keying an individual encryption.
When you're trying to generate a bitstream and you expect uniformity (ie, a prng) then seeing obvious non-uniformity over time is a sign that it's biased. You need the type of algorithms from the article to unbias it while preserving the actual entropy. This is what a system's designer should be doing to produce useful output from a hwrng in the first place.
But, looking at an individual piece of randomness, a key, you shouldn't be looking for uniformity at all. Here you want all zeros, all 1s, and any mix, to be equally possible.
> Interesting. Why do you hash the ECDH secret then?
Well, EC is a bit magical and I don't know. Wikipedia says that it prevents 'weak bits' from the handshake. That means correlations, but I don't know why this is true. At any rate uniformity here means what you think, that it's not a random bitstream and should not be used as such.
Because there are two entirely different things - one is producing an unbiased bitstream from a potentially biased one (the topic of the article) and the other is keying an individual encryption.
When you're trying to generate a bitstream and you expect uniformity (ie, a prng) then seeing obvious non-uniformity over time is a sign that it's biased. You need the type of algorithms from the article to unbias it while preserving the actual entropy. This is what a system's designer should be doing to produce useful output from a hwrng in the first place.
But, looking at an individual piece of randomness, a key, you shouldn't be looking for uniformity at all. Here you want all zeros, all 1s, and any mix, to be equally possible.
> Interesting. Why do you hash the ECDH secret then?
Well, EC is a bit magical and I don't know. Wikipedia says that it prevents 'weak bits' from the handshake. That means correlations, but I don't know why this is true. At any rate uniformity here means what you think, that it's not a random bitstream and should not be used as such.
This is the exact type of bad intuition that the article is trying to warn against. A purely random number - including the output of SHA2 - is going to have long consecutive strings of 1's or 0's.
Here's a simulation: https://play.golang.org/p/_eNAI3inGyQ
The results show that ~0.35% of all SHA2 outputs have >=15 zeroes in a row! Which means that ~0.7% of all SHA2 outputs have >=15 runs of the same binary digit in a row. As stated in the blog post, it's uncommon but it's not so uncommon that it should serve as a red flag.
If you change the code to look for runs of 9 in a row or greater, you'll see that ~40% of all SHA2 outputs have runs of ones or zeros that are greater than 9 in length.
Uniform randomness means that you will get long strings of ones or zeros on occasion. And it's more common than most human intuition would suggest.
Here's a simulation: https://play.golang.org/p/_eNAI3inGyQ
The results show that ~0.35% of all SHA2 outputs have >=15 zeroes in a row! Which means that ~0.7% of all SHA2 outputs have >=15 runs of the same binary digit in a row. As stated in the blog post, it's uncommon but it's not so uncommon that it should serve as a red flag.
If you change the code to look for runs of 9 in a row or greater, you'll see that ~40% of all SHA2 outputs have runs of ones or zeros that are greater than 9 in length.
Uniform randomness means that you will get long strings of ones or zeros on occasion. And it's more common than most human intuition would suggest.
Ok thanks for advice. Will aim for non uniform key material going forward.
Can you explain what you mean by uniformity? I am having a hard time understanding your point; a long random bit string which is sampled from a uniform distribution will, indeed, have a pretty high likelihood of a short run of zeros or ones. You could reject runs (not sure why), but that would make the distribution less uniform, right?
An analogy: True randomness is uncompressable. If there are patterns, which could lead to compression tricks, it's not random anymore.
Primitive runs like 0000000 are compressible patterns. Other patterns similarly, like 01010101, or 00110001110011. That's why you check generators visually by printing out bitmaps, and ideally by running it through a couple of compressors. Afaik this is not yet done by the 4 most common PRNG testsuites yet, but I'm working on it.
Primitive runs like 0000000 are compressible patterns. Other patterns similarly, like 01010101, or 00110001110011. That's why you check generators visually by printing out bitmaps, and ideally by running it through a couple of compressors. Afaik this is not yet done by the 4 most common PRNG testsuites yet, but I'm working on it.
A run like 0000000 is only compressible if it appears more often than it would in a fully random output. And in a fully random output, we would expect the run '0000000' to appear about once every 16 bytes.
When you compress 0000000 to something smaller, you have to replace '0000000' in the plaintext with a smaller symbol in the squash text. Which means if that smaller symbol appears in the plaintext, you have to replace it with a larger symbol in the squash text. And if your smaller symbol appears more frequently than '0000000', you are going to end up with a "squash" text that is larger than the plaintext.
When you compress 0000000 to something smaller, you have to replace '0000000' in the plaintext with a smaller symbol in the squash text. Which means if that smaller symbol appears in the plaintext, you have to replace it with a larger symbol in the squash text. And if your smaller symbol appears more frequently than '0000000', you are going to end up with a "squash" text that is larger than the plaintext.
I’m not saying short runs of 1 or 0 is not suitable for cryptographic use. I’m saying we always strive to remove any non-uniformity. Ie. Output of good CSPRNG will not have runs of one or the other.
True hardware random generators regularly have runs or non-uniformity. That’s why we use them to seed a CSPRNG not use the output directly.
Example https://crypto.stackexchange.com/questions/38053/what-should...
True hardware random generators regularly have runs or non-uniformity. That’s why we use them to seed a CSPRNG not use the output directly.
Example https://crypto.stackexchange.com/questions/38053/what-should...
[deleted]
The probability of 8 consecutive heads in 128 coin flips is about 1 in 5. I checked a SHA-2 256-bit hash in binary and indeed saw 8 consecutive 0s in the output. If what you are saying were true than one could expect the probability of one bit in the key to depend on the previous bit.
There's no single structure that all random strings fit, but most random strings have an accidental structure. You can abuse this property to remember strong password simply streamed from a CSPRNG.
> When we say that a random number has 78 bits of entropy, what we really mean is that an attacker has a 1 in 2⁷⁸ chance of guessing the random number.
I don't have any experience with cryptographically secure randomness, I'm just curious. Assuming an attacker knows that a biased coin has been used and that a random number has 78 bits of entropy instead of 128; how in practice would the attacker use this knowledge to guess the random number?
I don't have any experience with cryptographically secure randomness, I'm just curious. Assuming an attacker knows that a biased coin has been used and that a random number has 78 bits of entropy instead of 128; how in practice would the attacker use this knowledge to guess the random number?
If you know a coin is biased towards heads, the most likely outcome is all heads. So you'd start by guessing all heads, then guess all combinations with one head, all combinations with 2 heads, etc
If you don't know the bias you can start with all heads, then do all tails, etc.
Basically, anything you know about a bias allows you to sort the possible outcomes by how likely they are in your model and then try them in order from most likely to least likely.
If you don't know the bias you can start with all heads, then do all tails, etc.
Basically, anything you know about a bias allows you to sort the possible outcomes by how likely they are in your model and then try them in order from most likely to least likely.
While not technically related, this reminds me of Keybase's cryptographic coin flip:
https://keybase.io/blog/cryptographic-coin-flipping
https://keybase.io/blog/cryptographic-coin-flipping
Can't you just use the cloudflare trick and take a photo of boiling water, clouds or a tree in the wind?
An interesting startup story, and links to measures of atmospheric radio-generated randomness at https://www.random.org/history/
The title should be changed to say, generating cryptographically insecure random numbers with coins and a cup.
Apply the von Neumann trick on top of the results and now we're talking. The real benefit here is the cup-based flipping technique creating independent trials.
Apply the von Neumann trick on top of the results and now we're talking. The real benefit here is the cup-based flipping technique creating independent trials.
I'm guessing you didn't read the post? It covers the Von Neumann trick, why that doesn't work in practice, and then it also explains why using biased coins to generate random numbers results in real security when done correctly.
The tornado trick doesn't work if you don't combine it with the Von Neumann trick, though.
> What we’re going to do is take 5 coins, ideally all of different shapes and sizes, and put them into a large cup. You want the cup to be large so that as you shake the coins around, the coins get jumbled in a highly random way. Give the cup 5 good shakes where the coins are tumbling around, and then dump the coins out and count the number of heads. If there are an even number of heads, record a ‘0’ for the random bit. If there are an odd number of heads, record a ‘1’ for the random bit.
Consider the extreme case where all of the coins have a 0.1% chance of coming up heads: you have a 99.501% chance of getting 5 heads (odd), 0.498% chance of getting 4 heads and 1 tails (even), a 0.001% chance of getting 3 heads and 2 tails (odd), and a vanishingly small chance of getting 3 or more tails.
So if you use the tornado trick with 5 coins that biased, your "random" bitstring is going to look something like "11111111111111...".
> What we’re going to do is take 5 coins, ideally all of different shapes and sizes, and put them into a large cup. You want the cup to be large so that as you shake the coins around, the coins get jumbled in a highly random way. Give the cup 5 good shakes where the coins are tumbling around, and then dump the coins out and count the number of heads. If there are an even number of heads, record a ‘0’ for the random bit. If there are an odd number of heads, record a ‘1’ for the random bit.
Consider the extreme case where all of the coins have a 0.1% chance of coming up heads: you have a 99.501% chance of getting 5 heads (odd), 0.498% chance of getting 4 heads and 1 tails (even), a 0.001% chance of getting 3 heads and 2 tails (odd), and a vanishingly small chance of getting 3 or more tails.
So if you use the tornado trick with 5 coins that biased, your "random" bitstring is going to look something like "11111111111111...".
If your coins are 99.9% biased it means you are going to need more than 5 coins. Bias approaches zero exponentially fast as you add more coins, and in this case it means you'd need 1151 coins at 99.9% bias per coin to have a simulated coin with a bias of less than 55%. At 99% bias per coin you only need 114 coins, and at 90% bias you only need 11 coins.
The main difference between the tornado trick and the von Neumann trick is how well they work in practice. In practice, coin tosses have at least a small amount of correlation, which breaks the von Neumann trick and gives you sloppy entropy. In the degenerate case, you might end up with almost no randomness despite using the von Neumann trick.
In practice, coin flips in the tornado have a bias that is around 55% per coin, which means that 5 coins is more than enough to give you reliable entropy. The tornado trick is about trying to fit into the real world well, which means discarding fears of using coins that are 99.9% biased towards a particular outcome, since coins like that don't exist in common contexts.
The main difference between the tornado trick and the von Neumann trick is how well they work in practice. In practice, coin tosses have at least a small amount of correlation, which breaks the von Neumann trick and gives you sloppy entropy. In the degenerate case, you might end up with almost no randomness despite using the von Neumann trick.
In practice, coin flips in the tornado have a bias that is around 55% per coin, which means that 5 coins is more than enough to give you reliable entropy. The tornado trick is about trying to fit into the real world well, which means discarding fears of using coins that are 99.9% biased towards a particular outcome, since coins like that don't exist in common contexts.
I did read the post.
A 5-coin Taek's Tornado is simply an insecure RNG if given biased coins. A one-time pad generated with it would not suffice. Not even if it has 127.6 bits of entropy in every 128 bits.
If you take the 128-bit chunks they reference, and throw that through a cryptographic hash function, then you'd be safe (don't ask me to prove it).
But they don't quite get there. They talk about using one as a way to avoid throwing away entropy, but not as a means of scrambling up the 128 biased bits into a suitable PRNG.
A 5-coin Taek's Tornado is simply an insecure RNG if given biased coins. A one-time pad generated with it would not suffice. Not even if it has 127.6 bits of entropy in every 128 bits.
If you take the 128-bit chunks they reference, and throw that through a cryptographic hash function, then you'd be safe (don't ask me to prove it).
But they don't quite get there. They talk about using one as a way to avoid throwing away entropy, but not as a means of scrambling up the 128 biased bits into a suitable PRNG.
http://www.stat.columbia.edu/~gelman/research/published/dice...