View source for Cryptographically secure pseudorandom number generator

<amp/>
A '''cryptographically secure pseudo-random number generator''' ('''CSPRNG''') or '''cryptographic pseudo-random number generator''' ('''CPRNG''') is a [[pseudo-random number generator]] (PRNG) with properties that make it suitable for use in [[cryptography]].

Many aspects of cryptography require [[random]] numbers, for example:

* [[key generation]]
* [[cryptographic nonce|nonces]]
* [[one-time pad]]s
* [[salt (cryptography)|salts]] in certain signature schemes, including [[ECDSA]], [[RSASSA-PSS]]

The "quality" of the randomness required for these applications varies.
For example, creating a [[Cryptographic nonce|nonce]] in some [[Cryptographic protocol|protocols]] needs only uniqueness.
On the other hand, generation of a master [[key (cryptography)|key]] requires a higher quality, such as more [[information entropy|entropy]]. And in the case of [[one-time pad]]s, the [[information theory|information-theoretic]] guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy.

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.

==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: 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.

*Every CSPRNG should satisfy the [[next-bit test]]. That is, given the first <var>k</var> bits of a random sequence, there is no polynomial-time algorithm that can predict the (<var>k</var>+1)th bit with probability of success non-negligibly better than 50%. [[Andrew Yao]] proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.
*Every CSPRNG should withstand "state compromise extensions". 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 [[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 π 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]].

==Definitions==
In the [[Asymptotic security|asymptotic setting]], a family of deterministic polynomial time computable functions <math>G_k\colon\{0,1\}^k\to\{0,1\}^{p(k)}</math> for some polynomial , is a '''pseudorandom number generator''' ('''PRG'''), if it stretches the length of its input (<math>p(k) > k</math> for any ), and if its output is [[Computational indistinguishability|computationally indistinguishable]] from true randomess, i.e. for any probabilistic polynomial time algorithm , which outputs 1 or 0 as a distinguisher,

: <math>\left|\Pr_{x\gets\{0,1\}^k}[A(G(x))=1] - \Pr_{r\gets\{0,1\}^{p(k)}}[A(r)=1]\right| < \mu(k)</math>

for some [[negligible function]] <math>\mu</math>. (The notation <math>x\gets X</math> means that is chosen [[Uniform distribution (discrete)|uniformly]] at random from the set .)

There is an equivalent characterization: For any function family <math>G_k\colon\{0,1\}^k\to\{0,1\}^{p(k)}</math>, is a PRG if and only if the next output bit of cannot be predicted by a polynomial time algorithm.

A '''forward-secure''' PRG with block length <math>t(k)</math> is a PRG <math>G_k\colon\{0,1\}^k\to\{0,1\}^k\times\{0,1\}^{t(k)}</math>, where the input string <math>s_i</math> with length is the current state at period , and the output (<math>s_{i+1}</math>, <math>y_i</math>) consists of the next state <math>s_{i+1}</math> and the pseudorandom output block <math>y_i</math> of period , such that it withstands state compromise extensions in the following sense. If the initial state <math>s_1</math> is chosen uniformly at random from <math>\{0,1\}^k</math>, then for any , the sequence <math>(y_1,y_2,\dots,y_i,s_{i+1})</math> must be computationally indistinguishable from <math>(r_1,r_2,\dots,r_i,s_{i+1})</math>, in which the <math>r_i</math> are chosen uniformly at random from <math>\{0,1\}^{t(k)}</math>.

Any PRG <math>G\colon\{0,1\}^k\to\{0,1\}^{p(k)}</math> can be turned into a forward secure PRG with block length <math>p(k)-k</math> by splitting its output into the next state and the actual output. This is done by setting <math>G(s) = G_0(s)\Vert G_1(s)</math>, in which <math>|G_0(s)| = |s| = k</math> and <math>|G_1(s)| = p(k)-k</math>; then is a forward secure PRG with <math>G_0</math> as the next state and <math>G_1</math> 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 [[Randomness extractor#Von Neumann extractor|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==

In the discussion below, CSPRNG designs are divided into three classes:
# those based on cryptographic primitives such as [[cipher]]s and [[cryptographic hash]]es,
# those based upon mathematical problems thought to be hard, and
# 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.

===Designs based on cryptographic primitives===
* A secure [[block cipher]] can be converted into a CSPRNG by running it in [[Block cipher modes of operation|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 2<sup>''n/2''</sup> 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.
* A cryptographically secure [[cryptographic hash function|hash]] of a counter might also act as a good CSPRNG in some cases. In this case, it is also necessary that the initial value of this counter is random and secret. However, there has been little study of these algorithms for use in this manner, and at least some authors warn against this use.

* Most [[stream cipher]]s work by generating a pseudorandom stream of bits that are combined (almost always [[XOR cipher|XOR]]ed) with the [[plaintext]]; running the cipher on a counter will return a new pseudorandom stream, possibly with a longer period. The cipher can only be secure if the original stream is a good CSPRNG, although this is not necessarily the case (see the [[RC4 cipher]]). Again, the initial state must be kept secret.

===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 an unconditional security proof based on the difficulty of the [[discrete logarithm problem]] but is also very inefficient.
* Daniel Brown of [[Certicom]] has written 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 (which were revealed in 2013 to be probably backdoored by NSA) are replaced with non-backdoored values.

===Special designs===
There are a number of practical PRNGs that have been designed to be cryptographically secure, including

*the [[Yarrow algorithm]] which attempts to evaluate the entropic quality of its inputs. Yarrow is used in [[FreeBSD]] and [[Mac OS X]] (also as [[/dev/random]]).
*the [[Salsa20#ChaCha variant|ChaCha20 algorithm]] replaced [[RC4]] in [[OpenBSD]] since version 5.4., replaced RC4 in [[NetBSD]] since version 7.0, and replaced SHA-1 in [[Linux]] since kernel version 4.8.
*the [[Fortuna (PRNG)|Fortuna algorithm]], the successor to Yarrow, which does not attempt to evaluate the entropic quality of its inputs.
*the function [[CryptGenRandom]] provided in [[Microsoft]]'s [[Cryptographic Application Programming Interface]]
*[[ISAAC (cipher)|ISAAC]] based on a variant of the [[RC4 cipher]]
*[[Evolutionary algorithm]] based on [[NIST]] Statistical Test Suite.
* [[Rc4#RC4-based random number generators|arc4random]]
* [[AES-CTR]] DRBG is often used as a random number generator in systems that use AES encryption.
*[[American National Standards Institute|ANSI]] X9.17 standard (''Financial Institution Key Management (wholesale)''), which has been adopted as a [[Federal Information Processing Standard|FIPS]] standard as well. It takes as input a [[TDEA]] ([[Triple DES#Keying options|keying option 2]]) key bundle ''k'' and (the initial value of) a 64-bit [[random seed]] ''s''. Each time a random number is required it:
** Obtains the current date/time ''D'' to the maximum resolution possible.
** Computes a temporary value ''t'' = TDEA<sub>''k''</sub>(''D'')
** Computes the random value ''x'' = TDEA<sub>''k''</sub>(''s'' ⊕ ''t''), where ⊕ denotes bitwise [[exclusive or]].
** Updates the seed ''s'' = TDEA<sub>''k''</sub>(''x'' ⊕ ''t'')

:Obviously, the technique is easily generalized to any block cipher; [[Advanced Encryption Standard|AES]] has been suggested (Young and Yung, op cit, sect 3.5.1).

==Standards==

Several CSPRNGs have been standardized. For example,
* [http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf FIPS 186-4]
* [[NIST SP 800-90A]]:

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

: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.

:When the maximum number of bits output from this PRNG is equal to the 2<sup>blocksize</sup>, 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.
* 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 [http://csrc.nist.gov/groups/ST/toolkit/random_number.html reference] is maintained by [[NIST]].

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

* ''A Statistical Test Suite for Random and Pseudorandom Number Generators'', [http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf NIST Special Publication 800-22].

==NSA [[Kleptography|kleptographic]] backdoor in the Dual_EC_DRBG PRNG==

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

==Security flaws==

===DUHK attack===
On October 23, 2017, [[Matthew_D._Green | Matthew Green]], a [[cryptographer]] at [[Johns Hopkins University]] released details regarding an 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."

==Source==
[http://wikipedia.org/ http://wikipedia.org/]
==See Also on BitcoinWiki==
* [[Bitgirls]]
* [[Bitcoin Marketers]]
* [[BitcoinExchangeGuide]]
* [[Emmares]]
* [[Belkin Marketing]]