6 ms·

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 th

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.
  - john_alan 6y ago
    So you agree with me, uniformity is important?
    - rurban 6y ago
      Yes, but I don't like the abbrevated term that much. I prefer the Kolmogorov complexity, precisely a discrete uniform distribution. It's not only important, it's the only factor.
  - Taek 6y ago
    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.
HexagonalKitten 6y ago
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.
- john_alan 6y ago
  > 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?
  - HexagonalKitten 6y ago
    > 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.
0cVlTeIATBs 6y ago
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.
Taek 6y ago
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 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.
- john_alan 6y ago
  Ok thanks for advice. Will aim for non uniform key material going forward.
GoblinSlayer 6y ago
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.

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.
- john_alan 6y ago
  So you agree with me, uniformity is important?
  - rurban 6y ago
    Yes, but I don't like the abbrevated term that much. I prefer the Kolmogorov complexity, precisely a discrete uniform distribution. It's not only important, it's the only factor.
- Taek 6y ago
  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.

HexagonalKitten 6y ago

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.

john_alan 6y ago
> 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?
- HexagonalKitten 6y ago
  > 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.

0cVlTeIATBs 6y ago

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.

Taek 6y ago

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

john_alan 6y ago
Ok thanks for advice. Will aim for non uniform key material going forward.

GoblinSlayer 6y ago

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.