Skip to main content

Random number generation

This section provides a few words on random numbers, so that discussions elswhere in the documentation make more sense.

Good random numbers are necessary in cryptography. They are used as symmetric keys and in the generation of asymmetric keypairs. Even public items such as initialization vectors and salts must be random and different every instance, even if they are not secret.

There are two kinds of random number generators (RNG):

  • Hardware

    A hardware RNG produces “true” random data because, if the hardware RNG is a good one, the output is not predictable.

  • Pseudo

    A pseudo random number generator (PRNG), sometimes called a deterministic random bit generator (DBRG) or software RNG, produces data that is indistinguishable from true random (meaning it passes tests of randomness) but is predictable. However, it is possible to use a good PRNG such that it is virtually impossible for an attacker to make a correct prediction.

More on PRNGs

There are two components to a PRNG: the algorithm and the seed. The algorithm must be a method of generating bytes that produces output indistinguishable from true random and will not repeat output for a very long time, usually repeating only after 232 bytes of output. The seed is input to the algorithm. If the seed is changed, the output is also changed.

A PRNG is a machine: start it up, ask it to generate output, and it will produce bytes that look random. The next time it is started up, it will generate the same output. This process is predictable.

But if the machine is started and some other seed data is loaded, it will produce different output. If the machine is restarted and the same seed is loaded, it will produce the same output; hence, each time a PRNG is started, new seed data must be loaded. Furthermore, the seed must be unpredictable so that an attacker cannot simply start up a copy of the machine and supply the same seed to produce the same output.

The strength of a seed is measured in “number of bits of entropy”. When seeding a PRNG, ensure that at least 128 bits of entropy is used.

One may ask why a PRNG should be used to generate random output instead of a seed. It is because a seed is generally many bytes long with some non-random bits; that is, there could be 128 bits of entropy in a 256-byte buffer. The PRNG “compresses” the entropy in a seemingly non-random source into a byte array of the appropriate size, a set of bytes that passes tests of randomness. In addition, the PRNG can continue to generate new random bytes even after the entropy of the seed has been matched. For example, if 128 bits of entropy is collected over 300 bytes of seed and fed into a PRNG, it will then generate a 128-bit key, and then another 128-bit key, and a 128-bit salt, and so on.

A PRNG should always be able to accept more seed bytes. That is, adding new seed data to an existing PRNG will not make the algorithm start over; it will just add the new seed data into the internal state.