Generating Cryptographically Secure Random Numbers with Coins and a Cup
blog.sia.tech
blog.sia.tech
http://www.stat.columbia.edu/~gelman/research/published/dice...
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.
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".
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.
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.
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
[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.
Here's an XKCD comic that uses entropy. It may give you more context: https://xkcd.com/936/
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.'
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.
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.
-------- 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.
Your math there doesn't add up... quite literally
(0.5 + 1/2 * (coin product)) not (0.5 + (coin product))
Thanks for pointing out the mistake. I've edited the blog post accordingly.
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.
With your D4, that means the HH and TT both count as heads - 62.5% total, which is consistent with everything else.
> 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?)
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.
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...
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.
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.
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.
> 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?
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.
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.
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 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.
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.
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.
> 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...".
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.