Acryptographically secure pseudorandom number generator (CSPRNG) orcryptographic pseudorandom number generator (CPRNG) is apseudorandom number generator (PRNG) with properties that make it suitable for use incryptography. It is also referred to as acryptographic random number generator (CRNG).

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(June 2024) (Learn how and when to remove this message)

Mostcryptographic applications requirerandom numbers, for example:

• key generation
• initialization vectors
• nonces
• salts in certain signature schemes, includingECDSA andRSASSA-PSS
• token generation

The "quality" of the randomness required for these applications varies. For example, creating anonce in someprotocols needs only uniqueness. On the other hand, the generation of a masterkey requires a higher quality, such as moreentropy. And in the case ofone-time pads, theinformation-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 randomnessAPI. 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.

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 statisticalrandomness tests:
   • Every CSPRNG should satisfy thenext-bit test. That is, given the firstk bits of a random sequence, there is nopolynomial-time algorithm that can predict the (k+1)th bit with probability of success non-negligibly better than 50%.^[1]Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.^[2]
2. They hold up well under serious attack, even when part of their initial or running state becomes available to an attacker:^[3]
   • Every CSPRNG should withstand "state compromise extension attacks".^[3]: 4 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.

For instance, if the PRNG under consideration produces output by computing bits ofpi 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 anormal number. However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi is currently in use (i.e. the state of the algorithm) 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 ofcryptanalysis.

In theasymptotic setting, a family of deterministic polynomial time computable functions${\displaystyle G_k:\{0,1{\}}^k\to \{0,1{\}}^{p(k)}}$ for some polynomialp, is apseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input (${\displaystyle p(k)>k}$ for anyk), and if its output iscomputationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithmA, which outputs 1 or 0 as a distinguisher,

for somenegligible function${\displaystyle \mu }$.^[4] (The notation${\displaystyle x\leftarrow X}$ means thatx is chosenuniformly at random from the setX.)

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

Aforward-secure PRNG with block length${\displaystyle t(k)}$ is a PRNG${\displaystyle G_k:\{0,1{\}}^k\to \{0,1{\}}^k\times \{0,1{\}}^{t(k)}}$, where the input string${\displaystyle s_i}$ with lengthk is the current state at periodi, 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 periodi, 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 anyi, 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)}}$.^[6]

Any PRNG${\displaystyle G:\{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}$; thenG 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.^[7]Even earlier,John von Neumann proved that asimple 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.

CSPRNG designs are divided into two classes:

1. Designs based on cryptographic primitives such asciphers andcryptographic hashes
2. Designs based on mathematical problems thought to behard

• A secureblock cipher can be converted into a CSPRNG by running it incounter mode using, for example, a special construct that theNIST in SP 800-90A callsCTR DRBG. CTR_DBRG typically usesAdvanced Encryption Standard (AES).
  • AES-CTR_DRBG is often used as a random number generator in systems that use AES encryption.^[9][10]
  • The NIST CTR_DRBG scheme erases the keyafter 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 itsPost-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.^[11]
• A stream cipher can be converted into a CSPRNG. This has been done with RC4,ISAAC, andChaCha20, to name a few.
• A cryptographically securehash might also be a base of a good CSPRNG, using, for example, a construct that NIST callsHash DRBG.
• AnHMAC primitive can be used as a base of a CSPRNG, for example, as part of the construct that NIST callsHMAC DRBG.

• TheBlum Blum Shub algorithm has a security proof based on the difficulty of thequadratic residuosity problem. Since the only known way to solve that problem is to factor the modulus, it is generally regarded that the difficulty ofinteger 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.
• TheBlum–Micali algorithm has a security proof based on the difficulty of thediscrete logarithm problem but is also very inefficient.
• Daniel Brown ofCerticom wrote a 2006 security proof forDual EC DRBG, based on the assumed hardness of theDecisional Diffie–Hellman assumption, thex-logarithm problem, and thetruncated point problem. The 2006 proof explicitly assumes a loweroutlen (amount of bits provided per iteration) than in the Dual_EC_DRBG standard, and that theP andQ in the Dual_EC_DRBG standard (which were revealed in 2013 to be probably backdoored by NSA) are replaced with non-backdoored values.

"Practical" CSPRNG schemes not only include an CSPRNG algorithm, but also a way to initialize ("seed") 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 inmacOS 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,^[12] andBLAKE2s to ingest entropy.^[13]
• arc4random, a CSPRNG in Unix-like systems that seeds from/dev/random. It originally is based onRC4, but all main implementations now useChaCha20.^[14][15][16]
• CryptGenRandom, part ofMicrosoft'sCryptoAPI, offered on Windows. Different versions of Windows use different implementations.
• ANSI X9.17 standard (Financial Institution Key Management (wholesale)), which has been adopted as aFIPS standard as well. It takes as input aTDEA (keying option 2) key bundlek and (the initial value of) a 64-bitrandom seeds.^[17] Each time a random number is required, it executes the following steps:
  1. Obtain the current date/timeD to the maximum resolution possible.
  2. Compute a temporary valuet = TDEA_k(D).
  3. Compute the random valuex = TDEA_k(s ⊕t), where ⊕ denotes bitwiseexclusive or.
  4. Update the seeds = TDEA_k(x ⊕t).

Obviously, the technique is easily generalized to any block cipher;AES has been suggested.^[18] If the keyk is leaked, the entire X9.17 stream can be predicted; this weakness is cited as a reason for creating Yarrow.^[19]

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.^[a]

Several CSPRNGs have been standardized. For example:

• FIPS 186-4^[21]
• NIST SP 800-90A

• NIST SP 800-90A Rev.1

• 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 byNIST.^[26]

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.^[27]

The Guardian andThe New York Times reported in 2013 that theNational Security Agency (NSA) inserted abackdoor into apseudorandom number generator (PRNG) ofNIST SP 800-90A, which allows the NSA to readily decrypt material that was encrypted with the aid ofDual EC DRBG. Both papers reported^[28][29] that, as independent security experts long suspected,^[30] the NSA had been introducing weaknesses into CSPRNG standard 800-90; this being confirmed for the first time by one of the top-secret documents leaked toThe Guardian byEdward 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 akleptographic backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such asRSA Security continued using Dual_EC_DRBG until the backdoor was confirmed in 2013.^[31] RSA Security received a $10 million payment from the NSA to do so.^[32]

On October 23, 2017,Shaanan Cohney,Matthew Green, andNadia Heninger,cryptographers at theUniversity of Pennsylvania andJohns Hopkins University, released details of the DUHK (Don't Use Hard-coded Keys) attack onWPA2 where hardware vendors use a hardcoded seed key for the ANSI X9.31 RNG algorithm, stating "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 orvirtual private network (VPN) connections."^[33][34]

DuringWorld War II, Japan used a cipher machine for diplomatic communications; the United States was able tocrack it and read its messages, mostly because the "key values" used were insufficiently random.

The WikibookCryptography 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 theWayback 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.

• Cryptographic algorithms
• Cryptographically secure pseudorandom number generators
• Cryptographic primitives

• CS1 errors: ISBN date
• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from June 2024
• All articles needing additional references
• Webarchive template wayback links