Cryptographically secure pseudorandom number generator

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search


Most cryptographic applications require random numbers, for example:

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, 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 pseudo-random number generator is insufficient.




  • 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%.[2] Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.[3]


CSPRNGs are designed explicitly to resist this type of cryptanalysis.


In the asymptotic setting, a family of deterministic polynomial time computable functions for some polynomial p, is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input ( 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,

for some negligible function .[4] (The notation means that x is chosen uniformly at random from the set X.)

There is an equivalent characterization: For any function family , G is a PRNG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.[5]

A forward-secure PRNG with block length is a PRNG , where the input string with length k is the current state at period i, and the output (, ) consists of the next state and the pseudorandom output block of period i, such that it withstands state compromise extensions in the following sense. If the initial state is chosen uniformly at random from , then for any i, the sequence must be computationally indistinguishable from , in which the are chosen uniformly at random from .[6]

Any PRNG can be turned into a forward secure PRNG with block length by splitting its output into the next state and the actual output. This is done by setting , in which and ; then G is a forward secure PRNG with as the next state and as the pseudorandom output block of the current period.

Entropy extraction[edit]

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



  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.


Designs based on cryptographic primitives[edit]

  • A secure block cipher can be converted into a CSPRNG by running it in counter mode. This is done by choosing a random key and encrypting a 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Assuming an n-bit block cipher the output can be distinguished from random data after around 2n/2 blocks since, following the birthday problem, colliding blocks should become likely at that point, whereas a block cipher in CTR mode will never output identical blocks. For 64-bit block ciphers this limits the safe output size to a few gigabytes, with 128-bit blocks the limitation is large enough not to impact typical applications.

Number-theoretic designs[edit]

  • The Blum Blum Shub algorithm has a security proof based on the difficulty of the quadratic residuosity problem. Since the only known way to solve that problem is to factor the modulus, it is generally regarded that the difficulty of integer factorization provides a conditional security proof for the Blum Blum Shub algorithm. However the algorithm is very inefficient and therefore impractical unless extreme security is needed.
  • The Blum–Micali algorithm has an unconditional security proof based on the difficulty of the discrete logarithm problem but is also very inefficient.

Special designs[edit]




Several CSPRNGs have been standardized. For example,

This withdrawn standard has four PRNGs. Two of them are uncontroversial and proven: CSPRNGs named Hash_DRBG[18] and HMAC_DRBG.[19]
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.[20]
When the maximum number of bits output from this PRNG is equal to the 2blocksize, 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.[20] 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.[20]
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.[21]
  • 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

A good reference is maintained by NIST.

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

NSA kleptographic backdoor in the Dual_EC_DRBG PRNG[edit]

The Guardian and The New York Times have reported that the National Security Agency (NSA) inserted a backdoor into a 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[22][23] that, as independent security experts long suspected,[24] 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.[25] RSA Security received a $10 million payment from the NSA to do so.[26]

Security flaws[edit]

DUHK attack[edit]

On October 23, 2017, Shaanan Cohney, Matthew Green, and Nadia Heninger, cryptographers at The University of Pennsylvania and Johns Hopkins University released details of the DUHK (Don't Use Hard-coded Keys) attack on WPA2 where hardware vendors use a hardcoded "seed key" for the ANSI X9.31 RNG algorithm in conjunction with the usage of the ANSI X9.31 Random Number Generator, "an attacker can brute-force encrypted data to discover the rest of the encryption parameters and deduce the master encryption key used to encrypt web sessions or VPN connections."[27][28]


  2. ^ Katz, Jonathan; Lindell, Yehuda (2008). Introduction to Modern Cryptography. CRC press. p. 70. ISBN 978-1584885511.
  4. ^ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, def 3.3.1.
  6. ^ Dodis, Yevgeniy, Lecture 5 Notes of Introduction to Cryptography (PDF), retrieved 3 January 2016, def 4.
  10. ^ CVS. CVS log of arc4random.c October 1, 2013
  11. ^ CVS. CVS log of arc4random.c November 16, 2014
  12. ^ Github. Github commit of random.c July 2, 2016
  18. ^ Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016.
  19. ^ Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016.
  20. ^ a b c Campagna, Matthew J. (November 1, 2006). "Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator" (PDF). Retrieved November 19, 2016.
  21. ^ Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Retrieved November 19, 2016.
  25. ^ Matthew Green. "RSA warns developers not to use RSA products".
  27. ^ Shaanan Cohney; Matthew D. Green; Nadia Heninger. "Practical state recovery attacks against legacy RNG implementations" (PDF).
  28. ^ "DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections". Retrieved 25 October 2017.

External links[edit]