Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG)^{[1]} is a claimed ISO, and formerly by the National Institute of Standards and Technology (NIST). Dual_EC_DRBG is based on the elliptic curve discrete logarithm problem (ECDLP) and was for some time one of the four (now three) CSPRNGs standardized in NIST SP 80090A.
Sometime before its first known publication in 2004, a possible backdoor was discovered with the Dual_EC_DRBG's design, with the design of Dual_EC_DRBG having the unusual property that it was theoretically impossible for anyone but Dual_EC_DRBG's designers (NSA) to confirm the backdoor's existence. Doubts about Dual_EC_DRBG's security and performance had also been expressed even before it was standardized. Bruce Schneier concluded shortly after standardization that the "rather obvious" backdoor (along with other deficiencies) would mean that nobody would use Dual_EC_DRBG.^{[2]} In 2013, New York Times reported that documents in their possession but never released to the public "appear to confirm" that the backdoor was real, and had been deliberately inserted by the National Security Agency as part of the NSA's Bullrun decryption program. The alleged backdoor would allow NSA to decrypt for example SSL/TLS encryption which used Dual_EC_DRBG as a CSPRNG.^{[3]} In December 2013, a Reuters news article alleged that in 2004, before NIST standardized Dual_EC_DRBG, NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default in the RSA BSAFE cryptography library, which resulted in RSA Security becoming the most important distributor of the backdoored algorithm.^{[4]} RSA responded to this and subsequent media reports to "categorically deny" any insinuation that RSA had ever knowingly colluded with the NSA to incorporate a flaw in Dual_EC_DRBG, saying "we have never kept [our] relationship [with the NSA] a secret".
Members of the ANSI standard group, to which Dual_EC_DRBG was first submitted, were aware of the exact mechanism of the potential backdoor and how to disable it,^{[5]} but did not take sufficient steps to unconditionally disable the backdoor. The general cryptographic community was initially not aware of the potential backdoor, until of Dan Shumow and Niels Ferguson 2007 rediscovery, or of Certicom's Daniel R. L. Brown and Scott Vanstone's 2005 patent application describing the backdoor mechanism.
In September 2013, The New York Times reported that internal NSA memos leaked by Edward Snowden indicated that the NSA had worked during the standardization process to eventually become the sole editor of the Dual_EC_DRBG standard,^{[6]} and concluded that the Dual_EC_DRBG standard did indeed contain a backdoor for the NSA.^{[7]} As response, NIST stated that "NIST would not deliberately weaken a cryptographic standard."^{[8]} According to the New York Times story, the NSA spends $250 million per year to insert backdoors in software and hardware as part of the Bullrun program.^{[9]} A Presidential advisory committee subsequently set up to examine NSA's conduct recommended among other things that the US government "fully support and not undermine efforts to create encryption standards".^{[10]}
In April 21, 2014, NIST withdrew Dual EC_DRBG from its draft guidance on random number generators recommending "current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible."^{[11]}
Contents

Timeline 1

Security 2

Standardization and implementations 3

Software and hardware which contained the possible backdoor 4

See also 5

References 6

External links 7
Timeline
Time

What happened

August 1997

Adam L. Young and Moti Yung present their cryptovirology paper "The Prevalence of Kleptographic Attacks on DiscreteLog Based Cryptosystems" at Crypto 1997. The paper presents a recipe on how to build asymmetric backdoors into crypto algorithms based on discrete logs. The primitive they introduced is the 'discrete log kleptogram' that would later be designed into the ECDRBG.

11 September 2001

The changed climate after 9/11 leads NSA to discard many previous limitations, and to even ignore laws, in the quest to make intelligence gathering more efficient. NSA leaker William Binney describes it as "After September 11, everything has changed".^{[12]}

ANSI X9.82 standardization process kicksoff in the early 2000s

NSA drives to include Dual_EC_DRBG in the ANSI X9.82 standard in the ANSI X9.82 standardization process that kickedoff in the early 2000s.^{[5]}

After the ANSI X9.82 standardization process kickedoff and before NIST publication

According to John Kelsey (who was listed as author of NIST SP 80090A together with Elaine Barker), the possibility of the backdoor by carefully chosen P and Q values was brought up at an ANSI X9.82 meeting. As a result, a way was specified for implementers to choose their own P and Q values.^{[13]} It turned out later that the specific subtle formulation that NIST put into the standard meant that you could only get the crucial FIPS 1402 validation of your implementation if you used the original compromised P and Q values.^{[14]}

June 2004

A draft of ANSI X9.82, Part 3 is published, which includes Dual_EC_DRBG.^{[5]} It is unknown if earlier drafts were published.

Sometime in 2004

RSA makes Dual_EC_DRBG the default CSPRNG in BSAFE. In 2013 Reuters reports this is a result of a secret $10 million deal with NSA.^{[4]}

21 January 2005

Priority date of a patent application^{[15]} by the two Certicom members of the ANSI X9.82 standardization committee. The patent describes the working of an elliptic curve CSPRNG backdoor identical to the potential backdoor in Dual_EC_DRBG, and ways to neutralize such a hidden backdoor by choosing alternative curve points and more bit truncation in the output function.^{[5]}

Sometime 2005^{[16]}

ISO/IEC 18031:2005 is published, and includes Dual_EC_DRBG.^{[5]}

December 2005^{[17]}

The first draft of NIST SP 80090A is released to the public, includes Dual_EC_DRBG.^{[3]}

16 March 2006

Kristian Gjøsteen publishes Comments on DualECDRBG/NIST SP 80090, Draft December 2005 showing that part of Dual_EC_DRBG is "not cryptographically sound", and constructing a bitpredictor with an advantage of 0.0011, which is considered unacceptable for a CSPRNG.^{[3]}^{[17]}

29 March 2006

Daniel R. L. Brown publishes "Conjectured Security of the ANSINIST Elliptic Curve RNG", concluding that "[Dual_EC_DRBG] should be a serious consideration", assuming less truncation of the curve points than is present in Dual_EC_DRBG, as shown necessary by Gjøsteen's 2006 paper. The paper also anticipates Shumow and Ferguson's 2007 announcement of a possible backdoor: "This proof makes essential use of Q being random. The reason for this is more than just to make the proof work. If Q is not random, then it may be the case the adversary knows a d such that dQ = P. Then dR_{i} = dS_{i+1}, so that such a distinguisher could immediately recover the secret prestates from the output. Once the distinguisher gets the prestates, it can easily distinguish the output from random. Therefore, it is generally preferable for Q to be chosen randomly, relative to P."^{[18]}

29 May 2006

Berry Schoenmakers and Andrey Sidorenko publish a Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, showing that empirically the output from Dual_EC_DRBG can be distinguished from random bits, concluding that Dual_EC_DRBG is insecure as a CSPRNG. Note that this is a separate problem from the backdoor. The authors also point out that the security claim of the Dual_EC_DRBG is only supported by informal discussion. No proof of security (e.g., via a reduction argument) is given.^{[19]} It follows that NIST ignored the provably secure pseudorandom number generators that had long existed in the peerreviewed academic literature.

June 2006

NIST SP 80090A is published, includes Dual_EC_DRBG with the defects pointed out by Kristian Gjøsteen and Berry Schoenmakers and Andrey Sidorenko not having been fixed.

August 2007

Dan Shumow and Niels Ferguson gives an informal presentation pointing out that the choices giving rise to the predictability documented in the 2006 papers enabled a backdoor, with attacker chosen P and Q.^{[20]}

15 November 2007

Bruce Schneier publishes an article with the title "Did NSA Put a Secret Backdoor in New Encryption Standard?" in Wired, based on Dan Shumow and Niels Ferguson's presentation.^{[2]}

6 June 2013

The first news stories (unrelated to Dual_EC_DRBG) based on Edward Snowden's leak of NSA documents are published.

5 September 2013

Existence of NSA's Bullrun program is revealed, based on the Snowden leaks. One of the purposes of Bullrun is described as being "to covertly introduce weaknesses into the encryption standards followed by hardware and software developers around the world." The New York Times states that "the N.S.A. had inserted a back door into a 2006 standard adopted by N.I.S.T... called the Dual EC DRBG standard."^{[21]}

10 September 2013

The NIST Public Affairs Office director released a statement, saying that "NIST would not deliberately weaken a cryptographic standard."^{[22]} The statement does not address the fact that NIST ultimately ignored the warning about a possible backdoor in the standard from NIST's own cryptographer, John Kelsey.

19 September 2013

RSA Security advises its customers to stop using Dual_EC_DRBG in RSA Security's BSAFE toolkit and Data Protection Manager, citing NIST guidance made Sept. 12, 2013 that indicated: "NIST strongly recommends that, pending the resolution of the security concerns and the reissuance of SP 80090A, the Dual_EC_DRBG, as specified in the January 2012 version of SP 80090A, no longer be used." ^{[23]} Initial media reports cast suspicion over RSA's continued use of Dual_EC_DRBG as the default in its BSAFE and Data Protection Manager products, particularly after 2007 in light of previous published concerns over the potential for a backdoor in the algorithm. RSA Chief of Technology Sam Curry writes a short justification for RSA Security's choice to use Dual_EC_DRBG as default, which is widely criticized by cryptographers, and forgets to mention the later revealed $10 million deal with NSA to use Dual_EC_DRBG.^{[24]}

18 December 2013

A presidential advisory committee set up to examine the NSA recommended that the US government "fully support and not undermine efforts to create encryption standards"^{[10]}

20 December 2013

Reuters reports on the existence of a $10 million deal between RSA and NSA to set Dual_EC_DRBG as the default CSPRNG in BSAFE.^{[4]}

22 December 2013

RSA Security posts statements categorically denying that it "entered into a 'secret contract' with the NSA to incorporate a known flawed random number generator into its BSAFE encryption libraries" though its statements do not deny the existence of a $10 million deal between RSA and the NSA to set Dual_EC_DRBG as the standard in BSAFE.^{[25]} Some news sites such as BBC summarize the press release as a direct denial of existence of the $10 million deal,^{[26]} while other commentary point out that it is not clear what claims exactly the carefully worded RSA Security press release is denying, if any.^{[27]}^{[28]}

25 February 2014

In his 2014 RSA Conference keynote speech, RSA Security Executive Chairman (and EMC Executive Vice President) Art Coviello implied that RSA Security had not seen merit in the 2006 and 2007 research papers that pointed out flaws in Dual_EC_DRBG until NIST issued guidance to stop using the CSPRNG. Coviello said RSA Security had seen decreasing revenue from encryption, and no longer wanted to expend resources driving encryption research, but as "contributor to and beneficiary of open standards" would trust NIST and NSA guidance, and blamed NSA for tricking the company.^{[29]}

21 April 2014

Following a public comment period and review, NIST removed Dual_EC_DRBG as a cryptographic algorithm from its draft guidance on random number generators, recommending "that current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible."^{[11]}

Security
The stated purpose of including the Dual_EC_DRBG in NIST SP 80090A is that its security is based on computational hardness assumptions from number theory. A mathematical security reduction proof can then prove that as long as the number theoretical problems are hard, the random number generator itself is secure. However, the makers of Dual_EC_DRBG did not publish a security reduction for Dual_EC_DRBG, and it was shown soon after the NIST draft was published that Dual_EC_DRBG was indeed not secure, because it output too many bits per round.^{[30]}^{[31]}^{[32]} The output of too many bits (along with carefully chosen elliptic curve points P and Q) is what makes the NSA backdoor possible, because it enables the attacker to revert the truncation by brute force guessing. The output of too many bits was not corrected in the final published standard, leaving Dual_EC_DRBG both insecure and backdoored.^{[3]}
In many other standards, constants which are meant to be arbitrary are chosen by the nothing up my sleeve number principle, where the constants are derived from, for example, pi, in a way that leaves little room for adjustment. However, Dual_EC_DRBG did not specify how the default P and Q constants were chosen, possibly because they were constructed by NSA to be backdoored. Because the standard committee were aware of the potential for a backdoor, a way for an implementer to choose their own secure P and Q were included.^{[5]}^{[13]} But the exact formulation in the standard was written such that use of the alleged backdoored P and Q was required for FIPS 1402 validation, so the OpenSSL project chose to implement the backdoored P and Q, even though they were aware of the potential backdoor and would have preferred generating their own secure P and Q.^{[33]} New York Times would later write that NSA had worked during the standardization process to eventually become the sole editor of the standard.^{[6]}
A security proof was later published for Dual_EC_DRBG by Daniel R.L. Brown and Kristian Gjøsteen, showing that the generated elliptic curve points would be indistinguishable from uniformly random elliptic curve points, and that if less bits were output in the final output truncation, and if the two elliptic curve points P and Q were independent, and if three problems were shown to be hard (only one of which is generally accepted as being hard), then Dual_EC_DRBG is secure. The proof relied on the assumption that three problems were hard: the decisional Diffie–Hellman assumption (which is generally accepted to be hard), and two newer problems which are not generally accepted to be hard: The truncated point problem, and the xlogarithm problem.^{[30]}^{[31]} Dual_EC_DRBG was quite slow compared to many alternative CSPRNGs (which don't have security reductions^{[34]}), but Daniel R.L. Brown argue that the security reduction makes the slow Dual_EC_DRBG a valid alternative (assuming implementors disable the obvious backdoor).^{[34]} Note that Daniel R.L. Brown works for Certicom, the main owner of elliptic curve cryptography patents, so there may be a conflict of interest in promoting an EC CSPRNG.
The alleged NSA backdoor would allow the attacker to determine the internal state of the random number generator from looking at the output from a single round (32 bytes); all future output of the random number generator can then easily be calculated, until the CSPRNG is reseeded with an external source of randomness. This makes for example SSL/TLS vulnerable, since the setup of a TLS connection includes the sending of a randomly generated cryptographic nonce in the clear.^{[3]} NSA's alleged backdoor would depend on NSA knowing the single e such that e*Q=P  this is a hard problem, given Q and P, but easy to generate if you can choose P and Q.^{[20]} So e is a secret key presumably known only by NSA, and the alleged backdoor is a kleptographic asymmetric hidden back door.^{[35]} Matthew Green's blog post The Many Flaws of Dual_EC_DRBG has a simplified explanation of how the alleged NSA backdoor might work employing the discretelog kleptogram introduced in Crypto 1997.^{[36]}
Standardization and implementations
NSA first introduced Dual_EC_DRBG in the ANSI X9.82 DRBG in the early 2000s, including the same parameters which created the alleged backdoor, and Dual_EC_DRBG was published in a draft ANSI standard. Dual_EC_DRBG also exists in the ISO 18031 standard.^{[5]}
According to John Kelsey (who together with Elaine Barker was listed as author of NIST SP 80090A), the possibility of the backdoor by carefully chosen P and Q was brought up at an ANSI X9F1 Tool Standards and Guidelines Group meeting.^{[5]}
At least two members of the Members of the ANSI X9F1 Tool Standards and Guidelines Group which wrote ANSI X9.82, Daniel R. L. Brown and Scott Vanstone from Certicom,^{[5]} were aware of the exact circumstances and mechanism in which a backdoor could occur, since they filed a patent application^{[15]} in January 2005 on exactly how to insert or prevent the backdoor in DUAL_EC_DRBG. The working of the "trap door" mentioned in the patent is identical to the one later confirmed in Dual_EC_DRBG. Brown and Vanstone's patent list two necessary conditions for the backdoor to exist
1) Chosen Q
An elliptic curve random number generator avoids escrow keys by choosing a point Q on the elliptic curve as verifiably random. Intentional use of escrow keys can provide for back up functionality. The relationship between P and Q is used as an escrow key and stored by for a security domain. The administrator logs the output of the generator to reconstruct the random number with the escrow key.
2) Small output truncation
[0041] Another alternative method for preventing a key escrow attack on the output of an ECRNG, shown in Figures 3 and 4 is to add a truncation function to ECRNG to truncate the ECRNG output to approximately half the length of a compressed elliptic curve point. Preferably, this operation is done in addition to the preferred method of Figure 1 and 2, however, it will be appreciated that it may be performed as a primary measure for preventing a key escrow attack. The benefit of truncation is that the list of R values associated with a single ECRNG output r is typically infeasible to search. For example, for a 160bit elliptic curve group, the number of potential points R in the list is about 2^{80}, and searching the list would be about as hard as solving the discrete logarithm problem. The cost of this method is that the ECRNG is made half as efficient, because the output length is effectively halved.
According to John Kelsey, the option in the standard to choose a verifiably random Q was added as an option in response to the suspected backdoor.,^{[13]} though in such a way that FIPS 1402 validation could only be attained by using the possibly backdoored Q.^{[33]} Steve Marquess (who helped implement NIST SP 80090A for OpenSSL) speculated that this requirement to use the potentially backdoored points could be evidence of NIST complicity.^{[37]} It is not clear why the standard did not specify the default Q in the standard as a verifyably generated nothing up my sleeve number, or why the standard did not use greater truncation, which Brown's patent said could be used as the "primary measure for preventing a key escrow attack". The small truncation was unusual compared to previous EC PRGs, which according to Matthew Green had only output 1/2 to 2/3 of the bits in the output function.^{[3]} The low truncation was in 2006 shown by Gjøsteen to make the RNG predictable and therefore unusable as a CSPRNG, even if Q had not been chosen to contain a back door.^{[17]} The standard says that implementations "should" use the small max_outlen provided, but gives the option of outputting a multiple of 8 less bits. Appendix C of the standard gives a loose argument that outputting less bits will make the output less uniformly distributed. Brown's 2006 security proof relies on outlen being much smaller the default max_outlen value in the standard.
The ANSI X9F1 Tool Standards and Guidelines Group which discussed the back door also included three employees from the prominent security company RSA Security.^{[5]} In 2004, RSA Security made an implementation of Dual_EC_DRBG which contained the NSA backdoor the default CSPRNG in their

NIST SP 80090A  Recommendation for Random Number Generation Using Deterministic Random Bit Generators

Dual EC DRBG  Collection of Dual_EC_DRBG information, by Daniel J. Bernstein, Tanja Lange, and Ruben Niederhagen.

On the Practical Exploitability of Dual EC in TLS Implementations  Key research paper by Stephen Checkoway et al.

The prevalence of kleptographic attacks on discretelog based cryptosystems  Adam L. Young, Moti Yung (1997)

Patent US 2007189527, Brown, Daniel R. L. & Vanstone, Scott A., "Elliptic curve random number generation" on the Dual_EC_DRBG backdoor, and ways to negate the backdoor.

Comments on DualECDRBG/NIST SP 80090, Draft December 2005 Kristian Gjøsteen's March 2006 paper concluding that Dual_EC_DRBG is predictable, and therefore insecure.

A Security Analysis of the NIST SP 80090 Elliptic Curve Random Number Generator Daniel R. L. Brown and Kristian Gjøsteen's 2007 security analysis of Dual_EC_DRBG. Though at least Brown was aware of the backdoor (from his 2005 patent), the backdoor is not explicitly mentioned. Use of nonbackdoored constants and a greater output bit truncation than Dual_EC_DRBG specifies are assumed.

On the Possibility of a Back Door in the NIST SP80090 Dual Ec Prng Dan Shumow and Niels Ferguson's presentation, which made the potential backdoor widely known.

The Many Flaws of Dual_EC_DRBG  Matthew Green's simplified explanation of how the and why the backdoor works.

A few more notes on NSA random number generators  Matthew Green

Sorry, RSA, I'm just not buying it  Summary and timeline of Dual_EC_DRBG and public knowledge.

[Cfrg] Dual_EC_DRBG ... [was RE: Requesting removal of CFRG cochair] A December 2013 email by Daniel R. L. Brown defending Dual_EC_DRBG and the standard process.
External links

^ "Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised)" (PDF).

^ ^{a} ^{b} ^{c} ^{d}

^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} Matthew Green. "The Many Flaws of Dual_EC_DRBG".

^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} Menn, Joseph (December 20, 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". San Francisco. Reuters. Retrieved December 20, 2013.

^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} ^{i} ^{j} http://blog.cryptographyengineering.com/2013/12/afewmorenotesonnsarandomnumber.html

^ ^{a} ^{b} ^{c} "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian.

^ Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Retrieved September 11, 2013.

^ Cryptographic Standards Statement NIST 10 September 2013

^ "Secret Documents Reveal N.S.A. Campaign Against Encryption". The New York Times. 5 September 2013.

^ ^{a} ^{b} "NSA should stop undermining encryption standards, Obama panel says". Ars Technica.

^ ^{a} ^{b} "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations". National Institute of Standards and Technology. 21 April 2014.

^ "Untersuchungsausschuss im Bundestag: USInformant vergleicht NSA mit einer Diktatur". Spiegel (Spiegelonline GmbH). 3 July 2014. Retrieved 4 July 2014.

^ ^{a} ^{b} ^{c} http://cryptome.org/2013/12/80090dualecdrbg.pdf

^ http://marc.info/?l=opensslannounce&m=138747119822324&w=2

^ ^{a} ^{b} US 2007189527, Brown, Daniel R. L. & Vanstone, Scott A., "Elliptic curve random number generation"

^ http://www.iso.org/iso/iso_catalogue/catalogue_ics/catalogue_detail_ics.htm?csnumber=30816

^ ^{a} ^{b} ^{c} http://www.math.ntnu.no/~kristiag/drafts/dualecdrbgcomments.pdf

^ Daniel R. L. Brown (2006). "Conjectured Security of the ANSINIST Elliptic Curve RNG".

^ http://eprint.iacr.org/2006/190.pdf

^ ^{a} ^{b} http://rump2007.cr.yp.to/15shumow.pdf

^ Perlroth, Nicole (10 September 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times.

^ http://www.nist.gov/director/cybersecuritystatement091013.cfm

^ NIST, National Institute of Standards & Technology. "SUPPLEMENTAL ITL BULLETIN FOR SEPTEMBER 2013". NIST.gov. Retrieved 12 September 2013.

^ ^{a} ^{b} Matthew Green (20130920). "RSA warns developers not to use RSA products". A Few Thoughts on Cryptographic Engineering. Retrieved 20130928.

^ ^{a} ^{b} The Security Division of EMC, RSA,. "RSA Response to Media Claims Regarding NSA Relationship". RSA. Retrieved 22 December 2013.

^ "RSA denies link with US spying agency". BBC News. 23 December 2013.

^ http://www.techdirt.com/articles/20131222/23532125671/rsasdenialconcerning10millionnsatopromotebrokencryptonotreallydenialall.shtml

^ http://arstechnica.com/security/2013/12/rsaissuesnondenyingdenialofnsadealtofavorflawedcryptocode/

^ ^{a} ^{b} Jeffrey Carr (20140226). "Six Cryptographers Whose Work on Dual EC DRBG Were Deemed Without Merit by RSA Chief Art Coviello". Digital Dao.

^ ^{a} ^{b} Kristian Gjøsteen. Comments on DualECDRBG/NIST SP 80090

^ ^{a} ^{b} Daniel R. L. Brown and Kristian Gjøsteen. A Security Analysis of the NIST SP 80090 Elliptic Curve Random Number Generator, CRYPTO 2007, LNCS 4622, Springer, pp. 466–481. IACR ePrint version

^ Berry Schoenmakers and Andrey Sidorenko. Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, IACR ePrint 2006/190.

^ ^{a} ^{b} ^{c} ^{d} Steve Marquess. "Flaw in Dual EC DRBG (no, not that one)". OpenSSL project.

^ ^{a} ^{b} ^{c} http://www.ietf.org/mailarchive/web/cfrg/current/msg03651.html

^ ^{a} ^{b} Aris ADAMANTIADIS: "Dual_Ec_Drbg backdoor: a proof of concept" 31 Dec 2013

^

^ Steve Marquess. "Secure or Compliant, Pick One".

^ "We don’t enable backdoors in our crypto products, RSA tells customers". Ars Technica.

^ https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_ad.html

^ http://msdn.microsoft.com/enus/library/aa375534.aspx

^ http://csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf

^ Perlroth, Nicole (10 September 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". New York Times.

^ http://spectrum.ieee.org/telecom/security/canyoutrustnist

^ "Stop using NSAinfluenced code in our products, RSA tells customers". Ars Technica.

^ "'"$10m NSA contract with security firm RSA led to encryption 'back door. Guardian. 20 December 2013.

^ ^{a} ^{b} wired.com: "How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA" (Zetter) 24 Sep 2013

^ NIST: "DRBG Validation List"

^ http://veridicalsystems.com/blog/secureorcompliantpickone/

^ ^{a} ^{b} Digital Dao: "Evolving Hostilities in the Global Cyber Commons" 24 Jan 2014

^ http://cryptome.org/jya/nsasun.htm
References
See also
In December 2013 a proof of concept backdoor^{[35]} was published that uses the leaked internal state to predict subsequent random numbers, an attack viable until the next reseed.
A Trojan is really, really big. You can’t say that was a mistake. It’s a massive piece of code collecting keystrokes. But changing a bitone to a bittwo [in the registry to change the default random number generator on the machine] is probably going to be undetected. It is a low conspiracy, highly deniable way of getting a backdoor. So there’s a benefit to getting it into the library and into the product.
—Bruce Schneier, ^{[46]}
Bruce Schneier has pointed out that even if not enabled by default, having a backdoored CSPRNG implemented as an option can make it easier for NSA to spy on targets which have a softwarecontrolled commandline switch to select the encryption algorithm, or a "registry" system, like most Microsoft products, such as Windows Vista:
The Dual EC DRBG algorithm is only available to third party developers via the Cryptographic APIs on the [Blackberry] platform. In the case of the Cryptographic API, it is available if a 3rd party developer wished to use the functionality and explicitly designed and developed a system that requested the use of the API.
The BlackBerry software is an example of nondefault use. It includes support for Dual_EC_DRBG, but not as default. BlackBerry Ltd has however not issued an advisory to any of its customers who may have used it, because they do not consider the probable backdoor a vulnerability.^{[49]} Jeffrey Carr quotes a letter from Blackberry:^{[49]}
A list of products which have had their CSPRNGimplementation FIPS 1402 validated is available at the NIST.^{[47]} The validated CSPRNGs are listed in the Description/Notes field. Note that even if Dual_EC_DRBG is listed as validated, it may not have been enabled by default. Many implementations come from a renamed copy of a library implementation.^{[48]}
Implementations which used Dual_EC_DRBG would usually have gotten it via a library. At least RSA Security (BSAFE library), OpenSSL, Microsoft, and Cisco^{[46]} has libraries which included Dual_EC_DRBG, but only BSAFE used it by default. According to the Reuters article which revealed the secret $10 million deal between RSA Security and NSA, RSA Security's BSAFE was most important distributor of the algorithm.^{[4]} There was a flaw in OpenSSL's implementation of Dual_EC_DRBG that made it nonworking outside test mode, from which OpenSSL's Steve Marquess concludes that nobody used OpenSSL's Dual_EC_DRBG implementation.^{[33]}
Software and hardware which contained the possible backdoor
1. Dual_EC_DRBG, as specified in NIST SP 80090A and ANSI X9.823, allows an alternative choice of constants P and Q. As far as I know, the alternatives do not admit a known feasible backdoor. In my view, it is incorrect to imply that Dual_EC_DRBG always has a backdoor, though I admit a wording to qualify the affected cases may be awkward. 2. Many things are obvious in hindsight. I'm not sure if this was obvious. [...] 8. All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se. But maybe that's just because I'm biased or naive.
—Daniel Brown, [1]
Following the New York Times story asserting that Dual_EC_DRBG contained a back door, Brown (who had applied for the backdoor patent and published the security reduction) wrote an email to an ietf mailing list defending the Dual_EC_DRBG standard process:^{[34]}
RSA Security had kept Dual_EC_DRBG as the default CSPRNG in BSAFE even after the wider cryptographic community became aware of the potential backdoor in 2007, but there does not seem to have been a general awareness of BSAFE's usage of Dual_EC_DRBG as a user option in the community. Only after widespread concern about the back door was there an effort to find software which used Dual_EC_DRBG, of which BSAFE was by far the most prominent found. After the 2013 revelations, RSA security Chief of Technology Sam Curry provided Ars Technica with a rationale for originally choosing the flawed Dual EC DRBG standard as default over the alternative random number generators.^{[44]} The technical accuracy of the statement was widely criticized by cryptographers, including Matthew Green and Matt Blaze.^{[24]} On December 20, 2013, it was reported by Reuters that RSA had accepted a secret payment of $10 million from the NSA to set the Dual_EC_DRBG random number generator as the default in two of its encryption products.^{[4]}^{[45]} On December 22, 2013, RSA posted a statement to its corporate blog "categorically" denying a secret deal with the NSA to insert a "known flawed random number generator" into its BSAFE toolkit ^{[25]}
On September 9, 2013, following the Snowden leak, and the New York Times report on the backdoor in Dual_EC_DRBG, the National Institute of Standards and Technology (NIST) ITL announced that in light of community security concerns, it was reissuing SP 80090A as draft standard, and reopening SP80090B/C for public comment. NIST now "strongly recommends" against the use of Dual_EC_DRBG, as specified in the January 2012 version of SP 80090A.^{[41]}^{[42]} The discovery of a backdoor in a NIST standard has been a major embarrassment for the NIST.^{[43]}
Bruce Schneier reported in December 2007 that Microsoft added Dual_EC_DRBG support to Windows Vista, though not enabled by default, and Schneier warned against the known potential back door.^{[39]} Dual_EC_DRBG is still listed as available for Windows 8, according to msdn.microsoft.com,^{[40]} so it was presumably also available in Windows 7.
OpenSSL implemented all of NIST SP 80090A including Dual_EC_DRBG at the request of a client. The OpenSSL developers were aware of the potential backdoor because of Shumow and Ferguson's presentation, and wanted to use the method included in the standard to choose a guarantied nonbackdoored P and Q, but was told that to get FIPS 1402 validation they would have to use the default P and Q. OpenSSL choose to implement Dual_EC_DRBG despite its dubious reputation for completeness, noting that OpenSSL tried to be complete and implements many other insecure algorithms. OpenSSL did not use Dual_EC_DRBG as the default CSPRNG, and it was discovered in 2013 that a bug made the OpenSSL implementation of Dual_EC_DRBG nonfunctioning, meaning that no one could have been using it.^{[33]}
Daniel R. L. Brown's March 2006 paper on the security reduction of Dual_EC_DRBG mentions the need to more output truncation and randomly chosen Q, but mostly in passing, and does not mention his conclusions from his patent that these two defects in Dual_EC_DRBG together can be used as a back door. Brown writes in the conclusion: "Therefore, the ECRNG should be a serious consideration, and its high efficiency makes it suitable even for constrained environments." Note that others have criticised Dual_EC_DRBG as being extremely slow, with Bruce Schneier concluding "It's too slow for anyone to willingly use it",^{[2]} and Matthew Green saying Dual_EC_DRBG is "Up to a thousand times slower" than the alternatives.^{[3]} The potential for a backdoor in Dual_EC_DRBG was not widely publicised outside of internal standard group meetings. It was only after Dan Shumow and Niels Ferguson's 2007 presentation that the potential for a backdoor became widely known. Shumow and Ferguson had found the backdoor because they had been tasked with implementing Dual_EC_DRBG for Microsoft, in the course of which the possible backdoor became apparent. Bruce Schneier wrote in a 2007 Wired article that the Dual_EC_DRBG's flaws were so obvious that nobody would be use Dual_EC_DRBG: "It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it."^{[2]} Schneier was apparently unaware that RSA Security's had used Dual_EC_DRBG as the default in BSAFE since 2004.
A draft of NIST SP 80090A including the Dual_EC_DRBG was published in December 2005. The final NIST SP 80090A including Dual_EC_DRBG was published in June 2006. Documents leaked by Snowden have been interpreted as suggesting that the NSA backdoored Dual_EC_DRBG, with those making the allegation citing the NSA's work during the standardization process to eventually become the sole editor of the standard.^{[6]} The early usage of Dual_EC_DRBG by RSA Security (for which NSA was later reported to have secretly paid $10 million) was cited by the NSA as an argument for Dual_EC_DRBG's acceptance into the NIST SP 80090A standard.^{[4]} RSA Security subsequently cited Dual_EC_DRBG's acceptance into the NIST standard as a reason they used Dual_EC_DRBG.^{[38]}
[29]
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.