3

Its always been said that to get strong cryptographic numbers in computing, a good random number generator is needed. Without a good source of randomness, it could be possible for an attacker to determine the state of the random number generator and predict the next random numbers. Obviously this means they then either have or could have your encryption keys and things like that.

I know this must be a very real attack, but I've always considered it a theoretical one because I have no idea how this would be done. What would be a good real world scenario would be able to exploit the predictability of a not so good random number generator (but better than "the amount of time since you've opened the command prompt")?

Also, would it be possible to generate a key with said generator, and then have an attacker re-create that key using only an approximate knowledge of the system the generator was run on?

Or, am I completely misunderstanding the vulnerability in a poorer random number generator?

3

A large number of secure protocols depend on random or secure pseudo-random numbers. Even the session ids created by most web applications for keeping track of which web request belongs to which user depends on random strings which are generated using random numbers.

If, for example, I could predict the next session id generated by a web application, I could hijack this session.

Random numbers are used to create session keys in various protocols (ssl, ssh, ...). If I could predict these keys, I could decrypt the data sent in these sessions. They are also used as nonce values, and if I can predict these, I can break a number of protocols that depend on nonces not being predictable.

how to get at the state

To guess the state of a random number generator, you usually need to observe a lot of numbers generated by the RNG.

This doesn't mean that you have to observe the application that requests these numbers. If you have access to the same RNG (which is possible if you have access to the physical server where your victim application resides), you can simply request a million or ten million numbers yourself, using another program. But usuallly you don't have direct access to the RNG, so you'd either need to passively observe ommunications for a long time or trick the server side into providing more of these numbers (for example, by connecting as a regular user and requesting encryption key rotation 100 times a second in a badly designed protocol that allows for this).

One quality of good random number generators is that they have very long periods, e.g. it takes a huge number of invocations before they start repeating themselves.

Assume for example that you have a really bad generator that starts repeating its sequence of numbers after only 256 invocations. Now if you can observe a few of these random numbers, you can easily pinpoint at which point in the sequence the random number generator is, and correctly predict all future numbers generated.

A good generator should also output numbers that pass various statistical tests. That means that for example all numbers in the output space should be generated with roughly the same frequency, that there shouldn't be detectable patterns (e.g. the RNG always alternating between even and odd numbers) etc.

If you do manage to detect a specific pattern in a RNG, apart from being able to predict parts of a future "random" number, you might figure out that this pattern always occurs when the least important 8 bits in the RNG are in a certain configuration. If you managed to identify a few such patterns that let you infer parts of the RNG's state, you could combine these observations to yield a larger part of the whole state.

Good RNGs should take into account the whole state for each output bit they produce. But say you have one that doesn't do this. For example, assume that you have an RNG that produces numbers whose lowest bit only depends on a single bit of RNG state. This means that the RNG leaks part of its internal state with every number it produces. And if the lowest bit depended on two bits of internal state instead, the RNG would still leak important probabilistic information about the state of these two bits with every number produced.

  • So with these factors in mind, is it feasible to retroactively 'predict' a number that was already generated? If I used a bad generator to make say, an SSL cert, would I actually be in any danger of someone attempting to predict my numbers and get my private key in a practical amount of time (say, one year or less for a 2048 bit key)? – Nicholas Dechert Nov 4 '16 at 15:43
  • Theoretically, yes, because you can always run the RNG until you reach the current state, recording the last x numbers generated. In practice, I'd doubt such a "brute force" technique would always be feasible. It would depend very much on the actual RNG. The same goes for finding an inverse function that yields the sequence in reverse given a current state - depending on the RNG, this might be fairly easy or almost impossible. If you look at a RNG as a special kind of hash function that hashes its own state to get the next state, you see this isn't designed to be reversible. – Out of Band Nov 4 '16 at 17:33
  • Also, most cryptographically secure RNGs have an entropy pool which is periodically refreshed by system events and mixed into the RNG state, so a real-life attack on the forward secrecy of an RNG would necessarily involve recording the entropy pool. – Out of Band Nov 4 '16 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.