Cryptographically secure pseudorandom number generator: Difference between revisions

Revision as of 17:36, 10 May 2024

Latest revision as of 08:24, 16 April 2025

(19 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Type of functions designed for being unsolvable by root-finding algorithms}}

{{Copy edit|date=April 2024}}

A '''cryptographically secure pseudorandom number generator''' ('''CSPRNG''') or '''cryptographic pseudorandom number generator''' ('''CPRNG''') is a [[pseudorandom number generator]] (PRNG) with properties that make it suitable for use in [[cryptography]]. It is also referred to as a '''cryptographic random number generator''' ('''CRNG''').

== Background ==

{{Unreferenced section|date=June 2024}}

Most [[cryptography|cryptographic applications]] require [[random]] numbers, for example:

* [[key generation]]

* [[initialization vector]]s

* [[cryptographic nonce|nonces]]

* [[salt (cryptography)|salts]] in certain signature schemes, including [[ECDSA]] and [[PKCS 1|RSASSA-PSS]].

* [[tokenization (data security)|token generation]]

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, the generation of a master [[key (cryptography)|key]] requires a higher quality, such as more [[entropy (computing)|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, and thus just any kind of pseudorandom number generator is insufficient.

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, the generation of a master [[key (cryptography)|key]] requires a higher quality, such as more [[entropy (computing)|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, and thus 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, more random numbers are needed with more randomness than therethe isavailable entropy availablecan 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:

# that theyThey pass statistical [[randomness tests]]; and:

#* 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%.<ref name="katz">{{cite book |last1=Katz|first1=Jonathan|last2=Lindell|first2=Yehuda|date=2008|title=Introduction to Modern Cryptography|url=https://archive.org/details/Introduction_to_Modern_Cryptography|publisher=CRC press|page=[https://archive.org/details/Introduction_to_Modern_Cryptography/page/n88 70]|isbn= 978-1584885511}}</ref> [[Andrew Yao]] proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.<ref name="yao82">[[Andrew Chi-Chih Yao]]. [https://www.di.ens.fr/users/phan/secuproofs/yao82.pdf Theory and applications of trapdoor functions]. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.</ref>

# that theyThey hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.:<ref name=Kelsey/>

#* Every CSPRNG should withstand "state compromise extension attacks".<ref name=Kelsey>{{cite book | last1=Kelsey | first1=John | last2=Schneier | first2=Bruce | last3=Wagner | first3=David | last4=Hall | first4=Chris | title=Fast Software Encryption | chapter=Cryptanalytic Attacks on Pseudorandom Number Generators | publisher=Springer Berlin Heidelberg | publication-place=Berlin, Heidelberg | year=1998 | isbn=978-3-540-64265-7 | issn=0302-9743 | doi=10.1007/3-540-69710-1_12 | url = https://www.schneier.com/wp-content/uploads/2017/10/paper-prngs.pdf }}</ref>{{rp|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.

''Example:''For Ifinstance, 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 appearsis conjectured 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 is currently in use (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]].

Line 47 ⟶ 46:

{{main|Randomness extractor}}

Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality, quasi-random bit stream.<ref name=santha-vazirani>

{{cite conference

| author = Miklos Santha, Umesh V. Vazirani

Line 73 ⟶ 72:

==Designs==

CSPRNG designs are divided into two classes:

# thoseDesigns based on cryptographic primitives such as [[cipher]]s and [[cryptographic hash]]es,

# thoseDesigns based uponon mathematical problems thought to be [[NP-hardness|hard.]]

===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]] using, for example, a special construct that the [[NIST]] in SP 800-90A calls [[CTR DRBG|CTR_DRBG]]. CTR_DBRG typically uses [[Advanced Encryption Standard]] (AES).

** [[Advanced Encryption Standard|AES]]-[[Block cipher mode of operation#CTR|CTR]] DRBG_DRBG is often used as a random number generator in systems that use AES encryption.<ref>{{cite book |first1=David |last1=Kleidermacher |first2=Mike |last2=Kleidermacher |url=https://books.google.com/books?id=E9hBXN-HK1cC |title=Embedded Systems Security: Practical Methods for Safe and Secure Software and Systems Development |publisher=Elsevier |date=2012 |page=256|isbn=9780123868862 }}</ref><ref>

{{cite web |first1=George |last1=Cox |first2=Charles |last2=Dike |first3=DJ |last3=Johnston |url=http://www.hotchips.org/wp-content/uploads/hc_archives/hc23/HC23.18.2-security/HC23.18.210-Random-Numbers-Cox-Intel-e.pdf |title=Intel's Digital Random Number Generator (DRNG) |date=2011}}</ref>

** 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 [[NIST Post-Quantum Cryptography Standardization|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.<ref name="fke">{{cite web |last1=Bernstein |first1=Daniel J. |title=2017.07.23: Fast-key-erasure random-number generators: An effort to clean up several messes simultaneously. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs |url=https://blog.cr.yp.to/20170723-random.html}}</ref>

* A stream cipher can be converted into a CSPRNG. This has been done with RC4, [[ISAAC (cipher)|ISAAC]], and [[ChaCha20]], to name a few.

* A cryptographically secure [[cryptographic hash function|hash]] might also be a base of a good CSPRNG, using, for example, a construct that NIST calls [[Hash DRBG|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|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]] has writtenwrote 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'' (amount of bits provided per iteration) 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.

===Practical schemes===

Line 95 ⟶ 94:

* Implementations of [[/dev/random]] in Unix-like systems.

** [[Yarrow algorithm|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 (PRNG)|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 OS'OSs beginning around Dec. 2019.

** The Linux kernel CSPRNG, which uses ChaCha20 to generate data,<ref>{{cite web |publisher=Github |url=https://github.com/torvalds/linux/blob/e192be9d9a30555aae2ca1dc3aad37cba484cd4a/drivers/char/random.c |title=Github commit of random.c |date=July 2, 2016}}</ref> and [[BLAKE2s]] to ingest entropy.<ref>{{Cite web |title=Linux 5.17 Random Number Generator Seeing Speed-Ups, Switching From SHA1 To BLAKE2s - Phoronix |url=https://www.phoronix.com/news/Linux-5.17-RNG |website=www.phoronix.com}}</ref>

* ''[[arc4random]]'', a CSPRNG in Unix-like systems that seeds from {{tt|/dev/random}}. It originally is based on [[RC4]], but all main implementations now use [[ChaCha20]].<ref>{{cite web |publisher=CVS |url=http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random.c?rev=1.25&content-type=text/x-cvsweb-markup |title=CVS log of arc4random.c |date=October 1, 2013}}</ref><ref>{{cite web |publisher=CVS |url=http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/gen/arc4random.c?rev=1.26&content-type=text/x-cvsweb-markup&only_with_tag=MAIN |title=CVS log of arc4random.c |date=November 16, 2014}}</ref> <ref>{{cite web |url = https://www.freebsd.org/releases/12.0R/relnotes.html#userland-libraries |title = FreeBSD 12.0-RELEASE Release Notes: Runtime Libraries and API |date = 5 March 2019 |website = FreeBSD.org |access-date = 24 August 2019 }}</ref>

* ''[[CryptGenRandom]]'', part of [[Microsoft]]'s [[Cryptographic Application Programming Interface|CryptoAPI]], offered on Windows. Different versions of Windows use different implementations.

* [[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 [[Triple DES|TDEA]] ([[Triple DES#Keying options|keying option 2]]) key bundle ''k'' and (the initial value of) a 64-bit [[random seed]] ''s''.<ref>{{cite book |url=http://www.cacr.math.uwaterloo.ca/hac |title=Handbook of Applied Cryptography |first1=Alfred |last1=Menezes |first2=Paul |last2=van Oorschot |first3=Scott |last3=Vanstone |author-link1=Alfred Menezes |author-link2=Paul van Oorschot |author-link3=Scott Vanstone |publisher=CRC Press |year=1996 |chapter=Chapter 5: Pseudorandom Bits and Sequences |chapter-url=http://www.cacr.math.uwaterloo.ca/hac/about/chap5.pdf}}</ref> Each time a random number is required, it executes the following steps:{{blistolist

|1= ObtainsObtain the current date/time ''D'' to the maximum resolution possible.

|2= ComputesCompute a temporary value {{math|''t'' {{=}} TDEA_''k''(''D'')}}.

|3= ComputesCompute the random value {{math|''x'' {{=}} TDEA_''k''(''s'' ⊕ ''t'')}}, where ⊕ denotes bitwise [[exclusive or]].

|4= UpdatesUpdate the seed {{math|''s'' {{=}} TDEA_''k''(''x'' ⊕ ''t'')}}.}}<!--

-->Obviously, the technique is easily generalized to any block cipher; [[Advanced Encryption Standard|AES]] has been suggested.<ref name=Malicious_Cryptography2>

{{cite book

| first1=Adam |last1=Young |first2=Moti |last2=Yung

Line 113 ⟶ 112:

| url = http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0764549758.html

| isbn = 978-0-7645-4975-5

}}</ref> If the key ''k'' is leaked, the entire X9.17 stream can be predicted; this weakness is cited as a reason for creating Yarrow.<ref name="report1999">{{cite book |last1=Kelsey |first1=John |last2=Schneier |first2=Bruce |last3=Ferguson |first3=Niels |titlechapter=Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator |journaltitle=Sixth Annual Workshop on Selected Areas in Cryptography |series=Lecture Notes in Computer Science |date=August 1999 |volume=1758 |pages=13–33 |doi=10.1007/3-540-46513-8_2 |isbn=978-3-540-67185-5 |chapter-url=https://www.schneier.com/wp-content/uploads/2016/02/paper-yarrow.pdf}}</ref>

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.{{efn|The use of entropy-mixing after CSPRNG initialization has been question by [[Daniel J. Bernstein]].<ref name=":1">{{cite web |author=Daniel J. Bernstein |author-link=Daniel J. Bernstein |date=2014-02-05 |title=cr.yp.to: 2014.02.05: Entropy Attacks! |url=http://blog.cr.yp.to/20140205-entropy.html |quote=Is there any serious argument that adding new entropy all the time is a good thing? The Linux /dev/urandom manual page claims that without new entropy the user is "theoretically vulnerable to a cryptographic attack", but (as I've mentioned in various venues) this is a ludicrous argument}}</ref>}}

==Standards==

Several CSPRNGs have been standardized. For example,:

* FIPS 186-4<ref>{{Cite web|url=http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf|title=FIPS 186-4}}</ref>

* [[NIST SP 800-90A]]:<!--

{{block indent|This withdrawn standard has four PRNGs. Two of them are uncontroversial and proven: CSPRNGs named Hash_DRBG<ref>{{Cite web| url=https://eprint.iacr.org/2007/345.pdf | first=Wilson | last=Kan | title=Analysis of Underlying Assumptions in NIST DRBGs | date=September 4, 2007 | access-date=November 19, 2016 }}</ref> and HMAC_DRBG.<ref>{{Cite web | url = https://www.cs.cmu.edu/~kqy/resources/thesis.pdf | title = The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator | first = Katherine Qinru | last = Ye | date = April 2016 | access-date=November 19, 2016 }}</ref>

--><p>ThisThe withdrawnthird PRNG in this standard, has[[CTR DRBG]], is based on a [[block cipher]] running in four[[counter PRNGsmode]]. TwoIt ofhas them arean uncontroversial anddesign but has been proven: CSPRNGsto namedbe Hash_DRBG<ref>{{Citeweaker web|in url=https://eprint.iacr.org/2007/345.pdfterms |of first=Wilsondistinguishing |attack, last=Kanthan |the title=Analysis[[security level]] of Underlyingthe Assumptionsunderlying inblock NISTcipher DRBGswhen |the date=Septembernumber 4,of 2007bits |output access-date=Novemberfrom 19,this 2016PRNG }}</ref>is andgreater than two to the power of the underlying block cipher's block size in HMAC_DRBGbits.<ref name="CTR_DRBG">{{Cite web | url = httpshttp://wwweprint.csiacr.cmu.eduorg/~kqy2006/resources/thesis379.pdf | title = TheSecurity NotoriousBounds PRG:for Formalthe verificationNIST ofCodebook-based theDeterministic HMAC-DRBGRandom pseudorandom numberBit generatorGenerator | first = KatherineMatthew QinruJ. | last = YeCampagna | date = AprilNovember 20161, 2006 | access-date = November 19, 2016 }}</ref></p><!--

--><p>When the maximum number of bits output from this PRNG is equal to the 2^blocksize, 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.<ref name="CTR_DRBG"/> 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.<ref name="CTR_DRBG"/></p><!--

--><p>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.<ref name="CTR_DRBG">{{Cite web | url = http://eprint.iacr.org/2006/379.pdf | title = Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator | first = Matthew J. | last = Campagna | date = November 1, 2006 | access-date = November 19, 2016 }}</ref></p><!--

--><p>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.</p><!--

--><p>When the maximum number of bits output from this PRNG is equal to the 2^blocksize, 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.<ref name="CTR_DRBG"/> 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.<ref name="CTR_DRBG"/></p><!--

--><p>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 [[Kleptography|kleptographic]] NSA backdoor.<ref>{{Cite news| url=http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/| first=Nicole | last=Perlroth | newspaper=The New York Times | title=Government Announces Steps to Restore Confidence on Encryption Standards | date= September 10, 2013 | access-date = November 19, 2016 | url-access=limited}}</ref></p>

--><p>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.</p><!--

}}

* NIST SP 800-90A Rev.1

--><p>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 [[Kleptography|kleptographic]] NSA backdoor.<ref>{{Cite news| url=http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/| first=Nicole | last=Perlroth | newspaper=The New York Times | title=Government Announces Steps to Restore Confidence on Encryption Standards | date= September 10, 2013 | access-date = November 19, 2016 | url-access=limited}}</ref></p>

* NIST SP 800-90A Rev.1:{{block indent|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

Line 139:

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.<ref>{{Cite journal |urllast1=https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final|title=A Statistical Test Suite for Random and Pseudorandom NumberRukhin Generators for Cryptographic Applications|first1=Andrew |last1last2=RukhinSoto |first2=Juan |last2last3=SotoNechvatal |first3=James |last3last4=NechvatalSmid |first4=Miles |last4last5=SmidBarker |first5=Elaine |last5last6=BarkerLeigh |first6=Stefan |last6last7=LeighLevenson |first7=Mark |last7last8=LevensonVangel |first8=Mark |last8last9=VangelBanks |first9=David |last9last10=BanksHeckert |first10=N. |last10last11=HeckertDray |first11=James |last11last12=DrayVo |first12=San |last12last13=VoBassham |first13=Lawrence|last13=Bassham |date=April 30, 2010 |title=A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications |url=https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final |journal=NIST |doi=10.6028/NIST.SP.800-22r1a |via=csrc.nist.gov |doi-access=free}}</ref>

==Security flaws==

==NSA kleptographic backdoor in the Dual_EC_DRBG PRNG==

===NSA kleptographic backdoor in the Dual_EC_DRBG PRNG===

{{main|Dual_EC_DRBG}}

''[[The Guardian]]'' and ''[[The New York Times]]'' have reported in 2013 that the [[National Security Agency]] (NSA) inserted a [[backdoor (computing)|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 reportreported<ref name=Guardian>{{cite web|title=Revealed: how US and UK spy agencies defeat internet privacy and security|url=https://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security|work=The Guardian|access-date=7 September 2013|author=James Borger|author2=Glenn Greenwald|date=6 September 2013}}</ref><ref>{{cite news|title=N.S.A. Able to Foil Basic Safeguards of Privacy on Web|url=https://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=all&_r=0|newspaper=The New York Times|access-date=7 September 2013|author=Nicole Perlroth|date=5 September 2013}}</ref> that, as independent security experts long suspected,<ref>{{cite magazine|title=Did NSA Put a Secret Backdoor in New Encryption Standard?|url=https://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115|magazine=Wired|access-date=7 September 2013|author=Bruce Schneier|date=15 November 2007}}</ref> the NSA hashad 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 ''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 [[Kleptography|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.<ref name="green">{{cite web|url=http://blog.cryptographyengineering.com/2013/09/rsa-warns-developers-against-its-own.html|title=RSA warns developers not to use RSA products|author=Matthew Green|date=20 September 2013 }}</ref> [[RSA Security]] received a $10 million payment from the NSA to do so.<ref name="reuters">{{cite news|url=https://www.reuters.com/article/us-usa-security-rsa-idUSBRE9BJ1C220131220|title=Exclusive: Secret contract tied NSA and security industry pioneer|author=Joseph Menn | work=Reuters|date=20 December 2013}}</ref>

==Security flaws==

===DUHK attack===

On October 23, 2017, [[Shaanan Cohney]], [[Matthew D. Green|Matthew Green]], and [[Nadia Heninger]], [[cryptographer]]s at Thethe [[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."<ref>{{cite web|url=https://duhkattack.com/paper.pdf|title=Practical state recovery attacks against legacy RNG implementations|website=duhkattack.com|author1=Shaanan Cohney|author-link=Shaanan Cohney|author2=Matthew D. Green|author2-link=Matthew D. Green|author3=Nadia Heninger|author3-link=Nadia Heninger}}</ref><ref>{{cite web|url=https://it.slashdot.org/story/17/10/25/0047224/duhk-crypto-attack-recovers-encryption-keys-exposes-vpn-connections|title=DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections|website=slashdot.org|date=25 October 2017 |access-date=25 October 2017}}</ref>

===Japanese PURPLE cipher machine===

Line 172 ⟶ 173:

{{DEFAULTSORT:Cryptographically Secure Pseudorandom Number Generator}}

[[Category:Cryptographic algorithms]]

[[Category:Cryptographically secure pseudorandom number generators]]