8 ms·

Generating Cryptographically Secure Random Numbers with Coins and a Cup

72 points by Taek 6y ago

ballenf 6y ago
> 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.
- dragontamer 6y ago
  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.
- Taek 6y ago
  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.
  - tubbyjr 6y ago
    Well yes, but actually no (0.5 + (2x0.25)x(2x0.25)) != 62.5% Your math there doesn't add up... quite literally
    - deleted 6y ago
      [deleted]
    - Taek 6y ago
      Ah whoops you have to multiply the whole product by 1/2. (0.5 + 1/2 * (coin product)) not (0.5 + (coin product)) Thanks for pointing out the mistake. I've edited the blog post accordingly.
      - tubbyjr 6y ago
        ty, great post other than that little issue
  - dragontamer 6y ago
    > 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 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.
    - Taek 6y ago
      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.
_wldu 6y ago
Reminds me of the Dice-O-Matic: https://www.youtube.com/watch?v=7n8LNxGbZbs https://www.youtube.com/watch?v=7n8LNxGbZbs
- throw0101a 6y ago
  So basically a senary (base-6) RNG: * https://en.wikipedia.org/wiki/Senary https://en.wikipedia.org/wiki/Senary
tdons 6y ago
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 https://github.com/tdons/deskew-bernoulli
fouronnes3 6y ago
On a related note, the biased coin is the unicorn of probability but it's physically impossible: http://www.stat.columbia.edu/~gelman/research/published/diceRev2.pdf http://www.stat.columbia.edu/~gelman/research/published/dice...
- delecti 6y ago
  With the important caveat that you catch it, rather than letting it bounce and land.
  - dragontamer 6y ago
    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.
    - oh_sigh 6y ago
      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.
      - thaumasiotes 6y ago
        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".
SamReidHughes 6y ago
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.
- Taek 6y ago
  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.
  - SamReidHughes 6y ago
    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.
  - JoshuaDavid 6y ago
    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...".
thih9 6y ago
> 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?
- Taek 6y ago
  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.
techbio 6y ago
An interesting startup story, and links to measures of atmospheric radio-generated randomness at https://www.random.org/history/ https://www.random.org/history/
CGamesPlay 6y ago
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.
- sandworm101 6y ago
  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.)
- amingilani 6y ago
  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/ https://xkcd.com/936/
- Thorrez 6y ago
  The word entropy can refer to 2 separate things, but they are somewhat related: https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory 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.wikiquote.org/wiki/Claude_Elwood_Shannon
john_alan 6y ago
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.
- xvedejas 6y ago
  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?
  - john_alan 6y ago
    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-be-used-as-a-source-for-entropy https://crypto.stackexchange.com/questions/38053/what-should...
    - deleted 6y ago
      [deleted]
  - rurban 6y ago
    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.
franky47 6y ago
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
YeGoblynQueenne 6y ago
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.
GoblinSlayer 6y ago
Can't you just use the cloudflare trick and take a photo of boiling water, clouds or a tree in the wind?

72 points by Taek 6y ago

> 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.

dragontamer 6y ago
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.
Taek 6y ago
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.
- tubbyjr 6y ago
  Well yes, but actually no (0.5 + (2x0.25)x(2x0.25)) != 62.5% Your math there doesn't add up... quite literally
  - deleted 6y ago
    [deleted]
  - Taek 6y ago
    Ah whoops you have to multiply the whole product by 1/2. (0.5 + 1/2 * (coin product)) not (0.5 + (coin product)) Thanks for pointing out the mistake. I've edited the blog post accordingly.
    - tubbyjr 6y ago
      ty, great post other than that little issue
- dragontamer 6y ago
  > 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 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.
  - Taek 6y ago
    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.

_wldu 6y ago

Reminds me of the Dice-O-Matic: https://www.youtube.com/watch?v=7n8LNxGbZbs https://www.youtube.com/watch?v=7n8LNxGbZbs

throw0101a 6y ago
So basically a senary (base-6) RNG: * https://en.wikipedia.org/wiki/Senary https://en.wikipedia.org/wiki/Senary

tdons 6y ago

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 https://github.com/tdons/deskew-bernoulli

fouronnes3 6y ago

On a related note, the biased coin is the unicorn of probability but it's physically impossible: http://www.stat.columbia.edu/~gelman/research/published/diceRev2.pdf http://www.stat.columbia.edu/~gelman/research/published/dice...

delecti 6y ago
With the important caveat that you catch it, rather than letting it bounce and land.
- dragontamer 6y ago
  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.
  - oh_sigh 6y ago
    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.
    - thaumasiotes 6y ago
      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".

SamReidHughes 6y ago

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.

Taek 6y ago
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.
- SamReidHughes 6y ago
  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.
- JoshuaDavid 6y ago
  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...".

thih9 6y ago

> 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?

Taek 6y ago
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.

techbio 6y ago

An interesting startup story, and links to measures of atmospheric radio-generated randomness at https://www.random.org/history/ https://www.random.org/history/

CGamesPlay 6y ago

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.

sandworm101 6y ago
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.)
amingilani 6y ago
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/ https://xkcd.com/936/
Thorrez 6y ago
The word entropy can refer to 2 separate things, but they are somewhat related: https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory 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.wikiquote.org/wiki/Claude_Elwood_Shannon

john_alan 6y ago

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.

xvedejas 6y ago
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?
- john_alan 6y ago
  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-be-used-as-a-source-for-entropy https://crypto.stackexchange.com/questions/38053/what-should...
  - deleted 6y ago
    [deleted]
- rurban 6y ago
  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.

franky47 6y ago

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

YeGoblynQueenne 6y ago

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.

GoblinSlayer 6y ago

Can't you just use the cloudflare trick and take a photo of boiling water, clouds or a tree in the wind?