Random number generators

Hardware entropy generators

Hardware:

Daemons:

  • EGD: Entropy Gathering Daemon
  • PRNGD: Pseudo Random Number Generator Daemon
  • aed: an “additional entropy” daemon for Linux

Other:

Download entropy from websites

Seed collision

Size of the internal state

If the size of the RNG internal state is too small, you may generate duplicate seeds. For example, most LCG RNG uses a 32 bits unsigned integer as state.

Using the birthday problem, we can compute the number of seed that have to be tested to get the first collision with a probability of 50%:

>>> from math import sqrt, log
>>> def n(p, d): return sqrt(2*d*log(1/(1.0-p)))
...
>>> n(0.5, 2.0**32)
77162.743235574148

where 2^32 is the number of different possible seeds.

So with an internal state of 32 bits, you have to try 77163 seeds to create the same RNG with a probability of 50%. If we want to be sure, you can try with a probability of 99%:

>>> n(0.99, 2.0**32)
198892.20870276989

Even if you have a perfect random seed generator, you have a risk to generate duplicate generators if the internal state is too small. If you want to avoid collisions, use a geneartor using larger internal state, eg. at least 128 bits:

>>> n(0.5, 2.0**128)
2.1719381355163562e+19

Quality of the seed generator

In the first section, we supposed that the seed generator was perfect. But in real life, the seed is usually created using predictable informations like process identifier or current time in seconds. Because of a bug introduced in OpenSSL package, the seed was only created using the process identifier, which is -most of the time- a number of... 15 bits.

>>> n(0.5, 2.0**15)
213.13398045637061

Try 213 different keys was enough to break Debian OpenSSL security...

Good entropy sources

  • /dev/random: best entropy source on Linux, but blocks if there is no more entropy. It uses physical events like: keyboard strokes, mouse clicks and moves, hard drive timing, etc.
  • /dev/urandom: non blocking generator
  • (External) Hardware RNG

Cryptographic secure PRNG (CSPRNG)

Properties:

  • Protect against previous / next numbers prediction, even if the attacker knows the last results
  • Protect internal state: even if the attacker knows the RNG output, he shouldn’t be able to guess the internal state. Common trick is to hash the output (eg. MD5, SHA-1, or using a cryptographic hash function)
  • Protect against entropy injection

LCG RNGs don’t feet these requierements because knowing one number is enough to guess all previous and next numbers. Mersenne Twister is not a CSPRNG because it’s not uniform in dimension 624.