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.
However, unexpected correlations have been found in several such ostensibly independent processes.
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.
CSPRNG requirements fall into two groups: 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.
First, while most PRNGs' outputs appear random to assorted statistical tests, they do not resist determined reverse engineering.
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 (
, G is a PRNG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.
[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.
A number of such schemes have been defined, including: Obviously, the technique is easily generalized to any block cipher; AES has been suggested.
[18] If the key k 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.
For example: 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.
[24] 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.
[24] 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.
[24] It is noted in the next revision that the 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.
[26] There are also standards for statistical testing of new CSPRNG designs: The Guardian and The New York Times 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 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 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".
[32] 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, 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 or virtual private network (VPN) connections.
"[33][34] During World War II, Japan used a cipher machine for diplomatic communications; the United States was able to crack it and read its messages, mostly because the "key values" used were insufficiently random.