Cryptographically secure pseudo-random number generator

A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography.

Many aspects of cryptography require random numbers, for example:

• Key generation
• Nonces
• Salts in certain signature schemes, including ECDSA, RSASSA-PSS.
• One-time pads

The "quality" of the randomness required for these applications varies. For the generation of a nonce, only uniqueness might be required. For the generation of a master key, a higher quality is needed. And in the case of one-time pads, the information-theoretic guarantee of unbreakable cryptography only holds if the random stream is obtained from a true random source.

Ideally, the generation of these random numbers uses entropy obtained from another source, which might be a hardware random number generator or perhaps unpredictable system processes — though unexpected correlations have been found in several such ostensible processes. From an information theoretic point of view the amount of randomness, the entropy, that can be generated is equal to the entropy that went in to the system. But sometimes, in practical situations, more random numbers are needed than there is entropy available. In such instances a CSPRNG can be used. A CSPRNG can "stretch" the available entropy over more bits.

When all the entropy we have is available when algorithm execution begins, we really have a stream cipher. However some crypto system designs allow for the addition of entropy during execution, in which case it is not a stream cipher and cannot be used as one. Stream cipher and CSPRNG design is related.

Contents

1 Requirements 2 Designs 2.1 Designs based on cryptographic primitives 2.2 Designs based on number theory 2.3 Special designs 3 Standards

Requirements

The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: first that their statistical properties are good (passing tests of randomness), second that they hold up well in case of attack, even when (part of) their secrets are revealed.

• A CSPRNG should satisfy the "next-bit test". The next-bit test is the following: Given the first <math>l<math> bits of a random sequence there is no polynomial-time algorithm that can predict the (<math>l + 1<math>)st bit with probability of success higher than 1/2. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.

• A CSPRNG should withstand state compromise extensions. That is, in the unfortunate case that part or all of the state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the incident. Also if there is an input of entropy, it should be infeasible (ie, very very hard) to use knowledge of the state to predict future conditions of the state.

Example: If the CSPRNG being considered produces output by computing some function of the next digit of pi, it may well be random, as pi appears to be a random sequence. However, this does not satisfy the next-bit test, and thus is not cryptographically secure. There exists an algorithm that will predict the next bit.

Most PRNGs are not suitable for use as CSPRNGs since, whilst they appear random to statistical tests, they are not designed to resist determined mathematical reverse engineering and usually do not do so. CSPRNGs are designed explicitly to resist this type of cryptanalysis, and if well done, actually do so.

Designs

For our discussion we can divide the designs of CSPRNGs into three classes: 1) those based on block ciphers, 2) those based upon hard mathematical problems, and 3) special-purpose designs.

Designs based on cryptographic primitives

• A secure block cipher can also be converted into a CSPRNG by running it in counter mode. This is done by choosing an arbitrary key and encrypting a zero, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Obviously, the period will be 2ⁿ for an n-bit block cipher; equally obviously, the initial values (i.e. key and "plaintext") must not become known to an attacker lest, however good this CSPRNG construction might be otherwise, all security be lost.

• A cryptographically secure hash of a counter might also act as a good CSPRNG in some cases. In this case it is necessary that the initial value of this counter is random and secret. If the counter is a bignum, then the CSPRNG could have an infinite period.

• Most stream ciphers work by generating a pseudorandom stream of bits that are XORed with the message; this stream can often be used as a good CSPRNG (thought not always: see RC4 cipher).

One design in this class has been described in the standard ANSI X9.17, it works as follows:

• Input: Date/time information D, a 64 bit seed s and a two-key triple DES key k.
• Initialization: Compute I = DES_k (D)
• Output: Each time a random number is required, output x=DES_k(I xor s), and update the seed s to DES_k(x xor I)

Designs based on number theory

• Blum Blum Shub has a strong security proof. But implementations are slow compared to some other designs.

Special designs

• There are PRNGs that have been designed to be cryptographically secure. One example is ISAAC (based on a variant of the RC4 cipher), which is fast and has an expected cycle length of 2⁸²⁹⁵ and for which no successful attack in a reasonable time has yet been found.

• Yarrow algorithm, Fortuna

Standards

A number of designs of CSPRNGs have been standardized. They can be found in:

• FIPS 186-2
• ANSI X9.17-1985 Appendix C
• ANSI X9.31-1998 Appendix A.2.4
• ANSI X9.62-1998 Annex A.4