Cryptographically secure pseudorandom number generator

Most cryptographic applications require random numbers, for example:

• key generation
• nonces
• salts in certain signature schemes, including ECDSA, RSASSA-PSS

The "quality" of the randomness required for these applications varies. For example, creating a nonce in some protocols needs only uniqueness. On the other hand, the generation of a master key requires a higher quality, such as more entropy. And in the case of one-time pads, the information-theoretic guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy, and thus any kind of pseudorandom number generator is insufficient.

Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high-quality source, generally the operating system's randomness API. However, unexpected correlations have been found in several such ostensibly independent processes. From an information-theoretic point of view, the amount of randomness, the entropy that can be generated, is equal to the entropy provided by the system. But sometimes, in practical situations, more random numbers are needed than there is entropy available. Also, the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can "stretch" the available entropy over more bits.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG)[1] is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG),[2][3] which can be compared to "true" vs. pseudo-random numbers.

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 they pass statistical randomness tests; and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.[4]

• Every CSPRNG should satisfy the next-bit test. That is, given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success non-negligibly better than 50%.[5] Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.[6]
• Every CSPRNG should withstand "state compromise extension attacks".[7] In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.

Example: If the CSPRNG under consideration produces output by computing bits of π in sequence, starting from some unknown point in the binary expansion, it may well satisfy the next-bit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if π is a normal number, for example.) However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi (i.e. the state of the algorithm) is currently in use will be able to calculate all preceding bits as well.

Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, while most PRNGs outputs appear random to assorted statistical tests, they do not resist determined reverse engineering. Specialized statistical tests may be found specially tuned to such a PRNG that shows the random numbers not to be truly random. Second, for most PRNGs, when their state has been revealed, all past random numbers can be retrodicted, allowing an attacker to read all past messages, as well as future ones.

CSPRNGs are designed explicitly to resist this type of cryptanalysis.

In the asymptotic setting, a family of deterministic polynomial time computable functions ${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$ for some polynomial p, is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input (${\displaystyle p(k)>k}$ for any k), and if its output is computationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithm A, which outputs 1 or 0 as a distinguisher,

${\displaystyle \left|\Pr _{x\gets \{0,1\}^{k}}[A(G(x))=1]-\Pr _{r\gets \{0,1\}^{p(k)}}[A(r)=1]\right|<\mu (k)}$

for some negligible function ${\displaystyle \mu }$.[8] (The notation ${\displaystyle x\gets X}$ means that x is chosen uniformly at random from the set X.)

There is an equivalent characterization: For any function family ${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$, G is a PRNG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.[9]

A forward-secure PRNG with block length ${\displaystyle t(k)}$ is a PRNG ${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}}$, where the input string ${\displaystyle s_{i}}$ with length k is the current state at period i, and the output (${\displaystyle s_{i+1}}$, ${\displaystyle y_{i}}$) consists of the next state ${\displaystyle s_{i+1}}$ and the pseudorandom output block ${\displaystyle y_{i}}$ of period i, that withstands state compromise extensions in the following sense. If the initial state ${\displaystyle s_{1}}$ is chosen uniformly at random from ${\displaystyle \{0,1\}^{k}}$, then for any i, the sequence ${\displaystyle (y_{1},y_{2},\dots ,y_{i},s_{i+1})}$ must be computationally indistinguishable from ${\displaystyle (r_{1},r_{2},\dots ,r_{i},s_{i+1})}$, in which the ${\displaystyle r_{i}}$ are chosen uniformly at random from ${\displaystyle \{0,1\}^{t(k)}}$.[10]

Any PRNG ${\displaystyle G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$ can be turned into a forward secure PRNG with block length ${\displaystyle p(k)-k}$ by splitting its output into the next state and the actual output. This is done by setting ${\displaystyle G(s)=G_{0}(s)\Vert G_{1}(s)}$, in which ${\displaystyle |G_{0}(s)|=|s|=k}$ and ${\displaystyle |G_{1}(s)|=p(k)-k}$; then G is a forward secure PRNG with ${\displaystyle G_{0}}$ as the next state and ${\displaystyle G_{1}}$ as the pseudorandom output block of the current period.

Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality quasi-random bit stream.[11] Even earlier, John von Neumann proved that a simple algorithm can remove a considerable amount of the bias in any bit stream,[12] which should be applied to each bit stream before using any variation of the Santha–Vazirani design.

In the discussion below, CSPRNG designs are divided into three classes:

1. those based on cryptographic primitives such as ciphers and cryptographic hashes,
2. those based upon mathematical problems thought to be hard, and
3. special-purpose designs.

The last often introduces additional entropy when available and, strictly speaking, are not "pure" pseudorandom number generators, as their output is not completely determined by their initial state. This addition can prevent attacks even if the initial state is compromised.

Several CSPRNGs have been standardized. For example,

• FIPS 186-4[23]
• NIST SP 800-90A:

This withdrawn standard has four PRNGs. Two of them are uncontroversial and proven: CSPRNGs named Hash_DRBG[24] and HMAC_DRBG.[25]

The third PRNG in this standard, CTR DRBG, is based on a block cipher running in counter mode. It has an uncontroversial design but has been proven to be weaker in terms of distinguishing attack, than the security level of the underlying block cipher when the number of bits output from this PRNG is greater than two to the power of the underlying block cipher's block size in bits.[26]

When the maximum number of bits output from this PRNG is equal to the 2^blocksize, the resulting output delivers the mathematically expected security level that the key size would be expected to generate, but the output is shown to not be indistinguishable from a true random number generator.[26] When the maximum number of bits output from this PRNG is less than it, the expected security level is delivered and the output appears to be indistinguishable from a true random number generator.[26]

It is noted in the next revision that claimed security strength for CTR_DRBG depends on limiting the total number of generate requests and the bits provided per generate request.

The fourth and final PRNG in this standard is named Dual EC DRBG. It has been shown to not be cryptographically secure and is believed to have a kleptographic NSA backdoor.[27]

• NIST SP 800-90A Rev.1: This is essentially NIST SP 800-90A with Dual_EC_DRBG removed, and is the withdrawn standard's replacement.
• ANSI X9.17-1985 Appendix C
• ANSI X9.31-1998 Appendix A.2.4
• ANSI X9.62-1998 Annex A.4, obsoleted by ANSI X9.62-2005, Annex D (HMAC_DRBG)

A good reference is maintained by NIST.[28]

There are also standards for statistical testing of new CSPRNG designs:

• A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 800-22.[29]

The Guardian and The New York Times have reported in 2013 that the National Security Agency (NSA) inserted a backdoor into a pseudorandom number generator (PRNG) of NIST SP 800-90A which allows the NSA to readily decrypt material that was encrypted with the aid of Dual EC DRBG. Both papers report[30][31] that, as independent security experts long suspected,[32] the NSA has been introducing weaknesses into CSPRNG standard 800-90; this being confirmed for the first time by one of the top secret documents leaked to the Guardian by Edward Snowden. The NSA worked covertly to get its own version of the NIST draft security standard approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor." In spite of the known potential for a kleptographic backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such as RSA Security continued using Dual_EC_DRBG until the backdoor was confirmed in 2013.[33] RSA Security received a $10 million payment from the NSA to do so.[34]

• Kelsey, John; Schneier, Bruce; Wagner, David; Hall, Chris (1998). "Cryptanalytic Attacks on Pseudorandom Number Generators". Fast Software Encryption (PDF). Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/3-540-69710-1_12. ISBN 978-3-540-64265-7. ISSN 0302-9743.

The Wikibook Cryptography has a page on the topic of: Random number generation

• RFC 4086, Randomness Requirements for Security
• Java "entropy pool" for cryptographically secure unpredictable random numbers. Archived 2008-12-02 at the Wayback Machine
• Java standard class providing a cryptographically strong pseudo-random number generator (PRNG).
• Cryptographically Secure Random number on Windows without using CryptoAPI
• Conjectured Security of the ANSI-NIST Elliptic Curve RNG, Daniel R. L. Brown, IACR ePrint 2006/117.
• A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, Daniel R. L. Brown and Kristian Gjosteen, IACR ePrint 2007/048. To appear in CRYPTO 2007.
• Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.
• Efficient Pseudorandom Generators Based on the DDH Assumption, Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/321.
• Analysis of the Linux Random Number Generator, Zvi Gutterman and Benny Pinkas and Tzachy Reinman.
• NIST Statistical Test Suite documentation and software download.