14

In the news, there are several articles (here, here, and the technical point of view) which have to do with a weakness in a random number generator.

The question is somewhat twofold. What symptoms do weak RNGs exhibit? Does this mean, for instance, that several different seeds give the same result? Or am I missing what they mean by "weak"?

And, How does one go from figuring out there's a weak RNG to completely deciphering the encrypted traffic?

Rubber Duck
  • 516
  • 1
  • 5
  • 16

2 Answers2

17

When you generate a private key, you do so with a source of randomness. If that source of randomness can output N different streams of bits, then, at most, you may get N different private key. This is where we like to talk of entropy, which is a measure of how big that N is. When the source of randomness is said to offer "100 bits of entropy", then it means that (roughly) N = 2100.

The attacker will want to obtain your private key. If he knows that you use a weak source with a low N (say, only 40 bits of entropy), then he can, on his own machine, enumerate all possible outputs from the random source and work out the corresponding private key.

For instance, suppose that you used a PRNG seeded with the current time, expressed in microseconds. This is the time as known by your machine. The attacker assumes that your machine is reasonably well set with the current time, say within 10 seconds. So, from the point of view of the attacker, the seed for your PRNG is known within a 10 seconds range; since the PRNG use the time in microseconds, that leaves him with N = 10000000 possible seeds. The attacker then says to himself: "IF that guy used as seed value x, THEN his code produced private key value Kx; let's see if that matches his public key... nope. So he did not use x. Let's try again with x+1 (and so on)."

So a weak PRNG is deadly in such situations.

How can you detect a weak PRNG ? Well, most of the time, you cannot. A very poor PRNG may look poor from start; for instance, if you generate two private keys and get twice the same, then there is probably something wrong... but, as the "time as seed" example shows, this is not always easy to detect: time flows continuously, so you never reuse a seed. And yet this is weak. Because weakness comes from how hard it is to guess the internal state of the random source, which is not the same as being statistically biased.

A big statistical bias is detectable and is an obvious weakness; but a PRNG can be weak without being detectable as such.

If you are a bad guy and want to make an undetectable weak PRNG, then you can take a good block cipher (say, the AES), choose some key value K, and encrypt the successive values of a counter, starting at 0. This will produce a very long stream of pseudorandom bytes which nobody will be able to prove non-random, precisely because AES is good at encrypting things. But you, as the bad guy, know K, so you can easily predict the whole stream yourself.

The only reliable way to detect a weak PRNG is to inspect the exact method by which the PRNG works, down to the low details: what physical events it gather, why can these events be considered "random", how they are mixed together with cryptographic algorithms to produce pseudorandom bytes. You cannot do that with an opaque hardware RNG, hence the current crop of rumours.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 2
    And in the case of Intel's RDRand, for instance, we *know* that they're using AES as the last step to whiten the output. What we don't know is whether or not Intel has given the AES key to the NSA. If they did, and RDRand's raw output isn't truly random (like a counter) then despite the fact that it appear random to us and we have no way of knowing otherwise, the NSA could potentially decrypt the output and find the non or not-optimally random value and predict previous or future values. – Xander Sep 12 '13 at 21:16
  • Can weak PRNGs affect other aspects of a cryptosystem besides key generation? – Steve Sep 12 '13 at 22:02
  • A software RNG may be slower but you can audit it. Since good software RNGs rely on a hardware noise input (i.e. some sensor to the outside analog world) - that hardware input should be an off-the-shelf commodity product not intended for security but with a decent level of incidental natural noise. – LateralFractal Sep 12 '13 at 23:07
  • As an added bonus -- do you have any pointers on RNG that you think are nicely/badly written? –  Sep 20 '13 at 02:15
3

Weak RNGs are, by definition, difficult to detect (in a random stream, all sequences are equally probable so it would take an infinite stream to prove non randomness), but a good definition is whether you can (apparently) reliably predict the next digit in the random stream better than 'chance'. Again, this is only provable if you have an infinite stream, but for the breaking of crypto, this isn't as important as assuming a weak RNG from observation and using the assumption to actually break the encryption (i.e. using your assumption of how a (pseudo) random pattern is generated this is a better way to prove a weak RNG than waiting for an infinite stream to be generated and testing it for distribution).

Once you have determined/guessed how to predict the pattern in a random stream, if that stream has been used for generating keys, or one time pads, you have a way of using the predicted distribution as a way of reducing the search space for (secret) key guessing or looking for distribution in a transposition cipher etc. For one time pads, it's especially a problem as you have a way in to reversing the pad (which is trivial if you know any significant amount of the key).

All cryptographic algorithms are susceptible to poor randomness to a different degree of course and sometimes 'pseudo' is enough.

David Scholefield
  • 1,824
  • 12
  • 21