Cryptographically secure pseudorandom number generator


A cryptographically secure pseudorandom number generator or cryptographic pseudorandom number generator is a pseudorandom number generator with properties that make it suitable for use in cryptography. It is also referred to as a cryptographic random number generator.

Background

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, 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 just 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, numbers are needed with more randomness than the available entropy can provide. 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.

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:
  1. They pass statistical randomness tests:
  2. * 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 th bit with probability of success non-negligibly better than 50%.
  3. * Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness. In other words, no polynomial-time algorithm would be able to distinguish the output of the RNG from true randomness.
  4. * Instead of polynomial-time complexity, another metric considered in practice is the absolute number of operations required for a distinguisher to tell the output from true randomness. From the number of operations one can also define a security level for a particular CSPRNG against distinguishing attacks.
  5. They hold up well under serious attack, even when part of their initial or running state becomes available to an attacker:
  6. * Every CSPRNG should withstand "state compromise extension attacks". In the event that part or all of its state has been revealed, 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.
  7. * For instance, if the PRNG under consideration produces output by computing bits of pi 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 pi is conjectured to be a normal number. However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi 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:
  1. 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. At the same time, because CSPRNGs are designed to resist all statistical tests, a CSPRNG can replace any true random number generator in any non-cryptographic application as well.
  2. 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.

    Definitions

In the asymptotic setting, a family of deterministic polynomial time computable functions for some polynomial, is a pseudorandom number generator, if it stretches the length of its input, and if its output is computationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithm, which outputs or as a distinguisher,
for some negligible function.
There is an equivalent characterization: For any function family, is a PRNG if and only if the next output bit of cannot be predicted by a polynomial time algorithm.
A forward-secure PRNG with block length is a PRNG, where the input string with length is the current state at period, and the output consists of the next state and the pseudorandom output block of period, that withstands state compromise extensions in the following sense. If the initial state is chosen uniformly at random from, then for any, the sequence must be computationally indistinguishable from, in which the are chosen uniformly at random from.
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 is a forward secure PRNG with as the next state and as the pseudorandom output block of the current period.

Entropy extraction

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

Designs

CSPRNG designs are divided into two classes:
  1. Designs based on cryptographic primitives such as ciphers and cryptographic hashes
  2. Designs based on mathematical problems thought to be hard

    Designs based on cryptographic primitives

  • A secure block cipher can be converted into a CSPRNG by running it in counter mode using, for example, a special construct that the NIST in SP 800-90A calls CTR DRBG. CTR_DBRG typically uses Advanced Encryption Standard.
  • * AES-CTR_DRBG is often used as a random number generator in systems that use AES encryption.
  • * The NIST CTR_DRBG scheme erases the key after the requested randomness is output by running additional cycles. This is wasteful from a performance perspective, but does not immediately cause issues with forward secrecy. However, realizing the performance implications, the NIST recommends an "extended AES-CTR-DRBG interface" for its Post-Quantum Cryptography Project submissions. This interface allows multiple sets of randomness to be generated without intervening erasure, only erasing when the user explicitly signals the end of requests. As a result, the key could remain in memory for an extended time if the "extended interface" is misused. Newer "fast-key-erasure" RNGs erase the key with randomness as soon as randomness is requested.
  • A stream cipher can be converted into a CSPRNG. This has been done with RC4, ISAAC, and ChaCha20, to name a few.
  • A cryptographically secure hash might also be a base of a good CSPRNG, using, for example, a construct that NIST calls Hash DRBG.
  • An HMAC primitive can be used as a base of a CSPRNG, for example, as part of the construct that NIST calls HMAC DRBG.

    Number-theoretic designs

  • 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 a security proof based on the difficulty of the discrete logarithm problem but is also very inefficient.
  • Daniel Brown of Certicom wrote a 2006 security proof for Dual EC DRBG, based on the assumed hardness of the Decisional Diffie–Hellman assumption, the x-logarithm problem, and the truncated point problem. The 2006 proof explicitly assumes a lower outlen than in the Dual_EC_DRBG standard, and that the P and Q in the Dual_EC_DRBG standard are replaced with non-backdoored values.

    Practical schemes

"Practical" CSPRNG schemes not only include an CSPRNG algorithm, but also a way to initialize it while keeping the seed secret. A number of such schemes have been defined, including:
  • Implementations of /dev/random in Unix-like systems.
  • * Yarrow, which attempts to evaluate the entropic quality of its seeding inputs, and uses SHA-1 and 3DES internally. Yarrow was used in macOS and other Apple OS' up until about December 2019, after which it switched to Fortuna.
  • * Fortuna, the successor to Yarrow, which does not attempt to evaluate the entropic quality of its inputs; it uses SHA-256 and "any good block cipher". Fortuna is used in FreeBSD. Apple changed to Fortuna for most or all Apple OSs beginning around Dec. 2019.
  • * The Linux kernel CSPRNG, which uses ChaCha20 to generate data, and BLAKE2s to ingest entropy.
  • arc4random, a CSPRNG in Unix-like systems that seeds from. It originally is based on RC4, but all main implementations now use ChaCha20.
  • CryptGenRandom, part of Microsoft's CryptoAPI, offered on Windows. Different versions of Windows use different implementations.
  • ANSI X9.17 standard, which has been adopted as a FIPS standard as well. It takes as input a TDEA key bundle k and a 64-bit random seed s. Each time a random number is required, it executes the following steps:
Obviously, the technique is easily generalized to any block cipher; AES has been suggested. If the key k is leaked, the entire X9.17 stream can be predicted; this weakness is cited as a reason for creating Yarrow.
All these above-mentioned schemes, save for X9.17, also mix the state of a CSPRNG with an additional source of entropy. They are therefore not "pure" pseudorandom number generators, in the sense that the output is not completely determined by their initial state. This addition aims to prevent attacks even if the initial state is compromised.