Despite wide public criticism, including the public identification of the possibility that the National Security Agency put a backdoor into a recommended implementation, it was, for seven years, one of four CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.
One of the weaknesses publicly identified was the potential of the algorithm to harbour a cryptographic backdoor advantageous to those who know about it—the United States government's National Security Agency (NSA)—and no one else.
In 2013, The 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 NSA as part of its Bullrun decryption program.
[10] 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".
[11] On 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.
"Raising to a power" in this context, means using the special operation defined for points on elliptic curves.
[22][35][36] 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.
Brown argues that the security reduction makes the slow Dual_EC_DRBG a valid alternative (assuming implementors disable the obvious backdoor).
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.
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.
[39] Matthew Green's blog post The Many Flaws of Dual_EC_DRBG[40] has a simplified explanation of how the alleged NSA backdoor works by employing the discrete-log kleptogram introduced in Crypto 1997.
[6] According to John Kelsey (who together with Elaine Barker was listed as author of NIST SP 800-90A), the possibility of the backdoor by carefully chosen P and Q was brought up at an ANSI X9F1 Tool Standards and Guidelines Group meeting.
[41] 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,[6] were aware of the exact circumstances and mechanism in which a backdoor could occur, since they filed a patent application[18] in January 2005 on exactly how to insert or prevent the backdoor in DUAL_EC_DRBG.
[41] 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.
The benefit of truncation is that the list of R values associated with a single ECRNG output r is typically infeasible to search.
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,[15] though in such a way that FIPS 140-2 validation could only be attained by using the possibly backdoored Q.
[5] 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 backdoor.
Brown's 2006 security proof relies on outlen being much smaller the default max_outlen value in the standard.
Brown writes in the conclusion: "Therefore, the ECRNG should be a serious consideration, and its high efficiency makes it suitable even for constrained environments."
Shumow and Ferguson had been tasked with implementing Dual_EC_DRBG for Microsoft, and at least Furguson had discussed the possible backdoor in a 2005 X9 meeting.
[45] 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 800-90A as draft standard, and re-opening SP800-90B/C for public comment.
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.
[49] The technical accuracy of the statement was widely criticized by cryptographers, including Matthew Green and Matt Blaze.
[28] 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.
[2][50] 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 [3] Following the New York Times story asserting that Dual_EC_DRBG contained a backdoor, 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:[38] 1.
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.
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 software-controlled command-line switch to select the encryption algorithm, or a "registry" system, like most Microsoft products, such as Windows Vista: A Trojan is really, really big.
So there’s a benefit to getting it into the library and into the product.In December 2013, a proof of concept backdoor[39] was published that uses the leaked internal state to predict subsequent random numbers, an attack viable until the next reseed.
In December 2015, Juniper Networks announced[55] that some revisions of their ScreenOS firmware used Dual_EC_DRBG with the suspect P and Q points, creating a backdoor in their firewall.
[56][57][58] Allegations that the NSA had persistent backdoor access through Juniper firewalls had already been published in 2013 by Der Spiegel.