6 ms·

I'm a complete noob when it comes to cryptography. I understand that having a PRNG that doesn't return numbers with even distribution across a range is bad. Ext

by txttran 13y ago

I'm a complete noob when it comes to cryptography. I understand that having a PRNG that doesn't return numbers with even distribution across a range is bad. Extreme example would be something like http://xkcd.com/221/ http://xkcd.com/221/. But could someone explain how an attacker can take advantage of the fact that 0 is returned ~1% more often than other digits? It this flaw alone sufficient to break cryptocat? Or does it simply make brute forcing easier when combined with other crypto flaws?

nknighthb 13y ago
> I understand that having a PRNG that doesn't return numbers with even distribution across a range is bad. That's (potentially dangerously) oversimplified. Uniformity is one of the consequences rather than the requirement itself. The core requirement is unpredictability. If the output is non-uniform, it means the output isn't fully unpredictable (which may or may not lead to practical attacks depending on the degree of the problem and how the PRNG is actually being used). Meanwhile, you can also create a uniform PRNG that isn't secure at all (e.g. http://en.wikipedia.org/wiki/Mersenne_twister http://en.wikipedia.org/wiki/Mersenne_twister ).
patio11 13y ago
At a high level of abstraction: If one runs a nuclear power plant, one does not make a practice of tolerating small oil spills. Small oil spills are almost harmless. So are small quantities of sparks. The combination of small oil spills and small quantities of sparks, however, is a severe problem and gets worse in a hurry if it compounds with certain other usually benign properties of nuclear power plants. Unfortunately, the sort of nuclear power plant operators which tolerate oil spills are often sufficiently not on their A game to tolerate sparks. This is a very handwavy explanation. In particular, God doesn't hate nuclear powerplants and try to introduce sparks into them at inopportune moments just to see if they happen to find an oil spill, but The Adversary often can and will do this to your cryptosystem.
EthanHeilman 13y ago
If you are interested this webpage does some really neat stuff with visualizing PRNGs. http://lcamtuf.coredump.cx/oldtcp/ http://lcamtuf.coredump.cx/oldtcp/
Homunculiheaded 13y ago
There's a nice article "Cryptography is a science, not engineering" [0] that gives an overview of cryptography that might help with your question as well. The essence is that in modern cryptography you're creating a provably secure system. One of those proofs is that your prng outputs a uniform distribution. [0] http://www.daemonology.net/blog/2013-06-17-crypto-science-not-engineering.html http://www.daemonology.net/blog/2013-06-17-crypto-science-no...
marshray 13y ago
The small bias described in the article is a pointless and embarrassing flaw, but it's not the bug that made messages decryptable (this most recent time). The recent work on biases in RC4 contains a good example of how small biases can end up being exploitable. http://www.isg.rhul.ac.uk/tls/ http://www.isg.rhul.ac.uk/tls/
thetwiceler 13y ago
If you take this sort-of-stretched case where encryption can be broken, I can explain why this is a problem. Suppose you are using the PRNG to make a stream cipher. Basically, your random key is a seed for the PRNG. You then generate lots of pseudo-random characters from that seed, and XOR them together (character-by-character) with your message to encrypt it. Now, the fact that XOR is linear (it's just addition mod 2) means when you XOR two probability distributions against a constant (i.e., an atomic distribution), you'll get a shifted distribution. Let's say your PRNG disproportionately outputs "0" at each character. Then the distribution of each character of the ciphertext will be centered at p XOR 0, where p is the corresponding character of the plaintext! So by the law of large numbers, if we see the same message encrypted many times, we can determine with high probability exactly what each character of the plaintext is, and completely break encryption!
nikic 13y ago
Yes, the fact that 0 is returned ~1% more often than other digits is very significant. E.g. if the generated random number stream were used for XOR encryption, then you could just collect a large number of encryptions of the same text, for each character look which one occurs most often and then that would be the encrypted character (because 0 has a bias and occurs most often and c XOR 0 == c). Using other encryption methods the advantage is often not so obvious, but it exists. Also it should be noted that 1/250 is a pretty large bias and would probably not even need particularly many ciphertexts.

by txttran 13y ago

nknighthb 13y ago

> I understand that having a PRNG that doesn't return numbers with even distribution across a range is bad. That's (potentially dangerously) oversimplified. Uniformity is one of the consequences rather than the requirement itself. The core requirement is unpredictability. If the output is non-uniform, it means the output isn't fully unpredictable (which may or may not lead to practical attacks depending on the degree of the problem and how the PRNG is actually being used). Meanwhile, you can also create a uniform PRNG that isn't secure at all (e.g. http://en.wikipedia.org/wiki/Mersenne_twister http://en.wikipedia.org/wiki/Mersenne_twister ).

patio11 13y ago

At a high level of abstraction: If one runs a nuclear power plant, one does not make a practice of tolerating small oil spills. Small oil spills are almost harmless. So are small quantities of sparks. The combination of small oil spills and small quantities of sparks, however, is a severe problem and gets worse in a hurry if it compounds with certain other usually benign properties of nuclear power plants. Unfortunately, the sort of nuclear power plant operators which tolerate oil spills are often sufficiently not on their A game to tolerate sparks. This is a very handwavy explanation. In particular, God doesn't hate nuclear powerplants and try to introduce sparks into them at inopportune moments just to see if they happen to find an oil spill, but The Adversary often can and will do this to your cryptosystem.

EthanHeilman 13y ago

If you are interested this webpage does some really neat stuff with visualizing PRNGs. http://lcamtuf.coredump.cx/oldtcp/ http://lcamtuf.coredump.cx/oldtcp/

Homunculiheaded 13y ago

There's a nice article "Cryptography is a science, not engineering" [0] that gives an overview of cryptography that might help with your question as well. The essence is that in modern cryptography you're creating a provably secure system. One of those proofs is that your prng outputs a uniform distribution. [0] http://www.daemonology.net/blog/2013-06-17-crypto-science-not-engineering.html http://www.daemonology.net/blog/2013-06-17-crypto-science-no...

marshray 13y ago

The small bias described in the article is a pointless and embarrassing flaw, but it's not the bug that made messages decryptable (this most recent time). The recent work on biases in RC4 contains a good example of how small biases can end up being exploitable. http://www.isg.rhul.ac.uk/tls/ http://www.isg.rhul.ac.uk/tls/

thetwiceler 13y ago

If you take this sort-of-stretched case where encryption can be broken, I can explain why this is a problem. Suppose you are using the PRNG to make a stream cipher. Basically, your random key is a seed for the PRNG. You then generate lots of pseudo-random characters from that seed, and XOR them together (character-by-character) with your message to encrypt it. Now, the fact that XOR is linear (it's just addition mod 2) means when you XOR two probability distributions against a constant (i.e., an atomic distribution), you'll get a shifted distribution. Let's say your PRNG disproportionately outputs "0" at each character. Then the distribution of each character of the ciphertext will be centered at p XOR 0, where p is the corresponding character of the plaintext! So by the law of large numbers, if we see the same message encrypted many times, we can determine with high probability exactly what each character of the plaintext is, and completely break encryption!

nikic 13y ago

Yes, the fact that 0 is returned ~1% more often than other digits is very significant. E.g. if the generated random number stream were used for XOR encryption, then you could just collect a large number of encryptions of the same text, for each character look which one occurs most often and then that would be the encrypted character (because 0 has a bias and occurs most often and c XOR 0 == c). Using other encryption methods the advantage is often not so obvious, but it exists. Also it should be noted that 1/250 is a pretty large bias and would probably not even need particularly many ciphertexts.