up:: Foundations MOC
Dual_EC_DRBG
Dual_EC_DRBG, the Dual Elliptic Curve Deterministic Random Bit Generator, was one of the four random number generators NIST standardized in SP 800-90 in 2006, and the only one built on elliptic-curve math. Its security depended on two fixed curve points, P and Q, published in the standard with no account of how they were chosen, and whoever chose them could have kept a secret number that lets them predict every future output from a small sample. NIST recommended against it in September 2013, removed it from its draft guidance in April 2014, and deleted it from SP 800-90A Revision 1 in June 2015.
Source: NIST, “NIST Removes Cryptography Algorithm from Random Number Generator Recommendations,” April 21, 2014, nist.gov, which states the revised document “retains three of the four previously available options” and “omits an algorithm known as Dual_EC_DRBG.”
The short version:
- Dual_EC_DRBG made random bits by multiplying points on an elliptic curve using two fixed constants, P and Q. NIST’s 2014 postmortem states that “NSA provided Dual EC DRBG.”
- In 2007, Dan Shumow and Niels Ferguson of Microsoft showed that anyone who knows the secret number linking P and Q can recover the generator’s internal state from about 32 bytes of output and predict everything it produces next.
- Proven: the design admits an undetectable trapdoor. Reported: September 2013 journalism on Snowden documents described an NSA-engineered weakness in a 2006 NIST standard, which NIST’s postmortem calls “alleged.”
- Juniper’s ScreenOS showed the mechanism works in the field: in December 2015 Juniper disclosed unauthorized code in its firewalls, and researchers traced the VPN-decryption flaw to a changed Q.
- The lesson outlived the algorithm: NIST now commits to publishing “the provenance of any constants,” and the review of this failure urged “open competitions,” the model the post-quantum competition followed.
Picture a building that hands out door codes by running a public formula over two numbers painted on the lobby wall. The formula is sound, but whoever painted the numbers could have picked them as a matched pair, and the person holding the key to that match can hear one door code and work out every code that follows. From the lobby, a matched pair and an innocent pair look exactly alike, and the painter never said how the numbers were picked.
What was Dual_EC_DRBG?
Dual_EC_DRBG was a deterministic random bit generator, the kind of CSPRNG that stretches a small secret seed into a long stream of bits for keys and nonces. NIST published SP 800-90 in June 2006 with four such generators, revised it in March 2007, and reissued it as SP 800-90A in January 2012. The same generators were written into the financial-industry standard ANSI X9.82 Part 3, which also became an ISO standard in 2007.
| Generator (SP 800-90, 2006) | Built on | Designed by, per NIST’s 2014 postmortem | Status today |
|---|---|---|---|
| Hash_DRBG | A hash function | NSA design, modified by NIST | Approved in SP 800-90A Rev. 1 |
| HMAC_DRBG | HMAC | NIST | Approved in SP 800-90A Rev. 1 |
| CTR_DRBG | A block cipher (AES) | NIST | Approved in SP 800-90A Rev. 1 |
| Dual_EC_DRBG | The elliptic-curve discrete logarithm problem | NSA | Removed in Rev. 1, disallowed by SP 800-131A Rev. 2 |
It stood out before anyone raised a backdoor. It was “two orders of magnitude slower than the other PRNGs,” per a 2014 USENIX analysis, and its output carried a small statistical bias, raised by Kristian Gjøsteen in 2006, because it discarded too few bits of each curve point.
Sources: NIST, SP 800-90A, January 2012, csrc.nist.gov, Appendix H (“This original version of this Recommendation was completed in June, 2006. In March 2007, the following changes were made”); NIST ITL, “Supplemental ITL Bulletin for September 2013,” csrc.nist.gov (“In 2006, NIST published NIST Special Publication (SP) 800-90”); J. Kelsey, “Dual EC in X9.82 and SP 800-90,” NIST, May 2014, csrc.nist.gov, for the designers, the ISO adoption, and the bias history; S. Checkoway et al., “On the Practical Exploitability of Dual EC in TLS Implementations,” USENIX Security 2014, usenix.org, for the speed comparison; NIST, SP 800-131A Rev. 2, March 2019, csrc.nist.gov (“The use of Dual_EC_DRBG is disallowed”).
How does the Dual_EC_DRBG backdoor work?
The generator keeps a secret state s. Each step computes r = x(s·P), outputs x(r·Q) with its top 16 bits dropped, and moves to the next state x(r·P), where x( ) takes a point’s x-coordinate. Recovering s from the output means solving an elliptic-curve discrete logarithm, as hard as breaking ECC, for anyone who doesn’t know how P and Q relate.
That relationship is the backdoor. On a NIST prime-order curve some integer e always satisfies e·Q = P, and whoever made Q by picking a secret d and setting Q = d·P knows e, because e is d inverted modulo the curve’s order. With e, the attack from the 2007 talk runs in four moves:
- Take one 30-byte output block. Only its top 16 bits are missing, so try all 65,536 completions.
- Keep each completion that is a valid x-coordinate, which gives a point A.
- Compute x(e·A) for each. One A equals r·Q, and e·r·Q = r·P, so one candidate is the next internal state.
- Discard candidates that fail to reproduce the next 2 bytes. The survivor is the state, and every future output follows.
Shumow and Ferguson ran this on P-256 with a Q they generated themselves: “In every experiment 32 bytes of output was sufficient to uniquely identify the internal state of the PRNG.” They proposed two fixes, discard more bits per output and “Generate a random point Q for each instance of the PRNG,” and they were careful about what they claimed: “WHAT WE ARE NOT SAYING: NIST intentionally put a back door in this PRNG.” A weakness open to the one party holding a secret key and closed to everyone else is what cryptographers call a kleptographic backdoor.
Sources: D. Shumow and N. Ferguson, “On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng,” CRYPTO 2007 rump session, rump2007.cr.yp.to, slides 2 to 9; NIST, SP 800-90A, January 2012, csrc.nist.gov, §10.3.1.
Why did NIST keep Dual_EC_DRBG after the warning?
The concern predated the public talk. NIST’s postmortem records that in October 2005 Ferguson “made a formal comment on the document in X9 pointing this out,” and that NSA answered it had “generated (P, Q) in a secure, classified way.” NIST’s response was to add an optional procedure for generating verifiably random points while it “Required original (P,Q) for validation” and “Never explained why someone might generate their own (P, Q) in standard.” The 2012 text reflects this: the default points “shall be used in applications requiring certification under [FIPS 140].” Of the option, NIST later wrote: “As far as we know nobody used it.”
After the 2007 talk, NIST told Bruce Schneier it had “no evidence that anyone has, or will ever have, the ‘secret numbers’” and was “not withdrawing the algorithm at this time,” and in January 2008 the ANSI committee kept the generator as specified. The postmortem compresses the error into one sentence: NIST asked “Do we think there is a trapdoor into Dual EC DRBG?” when it “should have asked: Should we include an algorithm in our standards that could have a trapdoor?” Among the causes it lists is reliance on NSA “for expertise we lacked on elliptic curve cryptography.”
Sources: J. Kelsey, NIST, May 2014, csrc.nist.gov, slides 24, 25, 27, 32, 34, 41 and 44; NIST, SP 800-90A, January 2012, csrc.nist.gov, Appendix A.1.
What did the 2013 Snowden reporting say about Dual_EC_DRBG?
On September 5, 2013, The New York Times, The Guardian and ProPublica published reporting on NSA documents supplied by Edward Snowden. The articles did not print the algorithm’s name. They described “a standard adopted in 2006” by NIST, reported that “Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency,” and quoted a memo: “Eventually, N.S.A. became the sole editor.” NIST drew the connection itself, writing that “news reports prompted public concern about the trustworthiness of Dual_EC_DRBG.”
On December 20, 2013, Reuters reported, citing “two sources familiar with the contract,” that RSA Security received “$10 million in a deal that set the NSA formula as the preferred, or default, method for number generation” in its BSAFE toolkit. RSA responded that “under no circumstances does RSA design or enable any back doors in our products,” and NSA declined to comment. RSA’s executive chairman later told the 2014 RSA Conference that the default “allowed us to meet government certification requirements.” NIST told its external reviewers that over 50 validated cryptographic modules implemented the generator.
Sources: J. Larson (ProPublica), N. Perlroth and S. Shane (The New York Times), “Revealed: The NSA’s Secret Campaign to Crack, Undermine Internet Security,” ProPublica, September 5, 2013, propublica.org, published jointly with The New York Times; J. Menn, “Exclusive: Secret contract tied NSA and security industry pioneer,” Reuters, December 20, 2013, archived copy; NIST, April 21, 2014, nist.gov; Checkoway et al., USENIX Security 2014, usenix.org, for the publication date and the RSA Conference quote; NIST VCAT, “NIST Cryptographic Standards and Guidelines Development Process,” July 2014, nist.gov, Appendix D minutes, for the module count.
How did NIST withdraw Dual_EC_DRBG?
The withdrawal took 21 months from the first public recommendation to the final standard, and nearly 8 years from the rump-session talk.
| Date | Event |
|---|---|
| October 2005 | Niels Ferguson files a formal X9 comment on the possible trapdoor |
| June 2006 | NIST completes SP 800-90 with four DRBGs, including Dual_EC_DRBG |
| 2007 | Shumow and Ferguson present the backdoor possibility at the CRYPTO rump session |
| January 2012 | SP 800-90A reissues the generators, Dual_EC_DRBG included |
| September 2013 | NIST “strongly recommends” Dual_EC_DRBG “no longer be used” and reopens SP 800-90A for comment |
| April 21, 2014 | NIST removes it from the draft Rev. 1 and urges users to “transition to one of the three remaining approved algorithms as quickly as possible” |
| July 14, 2014 | NIST’s Visiting Committee on Advanced Technology finalizes its process review |
| June 2015 | SP 800-90A Rev. 1 published; “The Dual_EC_DRBG has been removed,” and the 2012 edition is withdrawn |
| March 2016 | NIST IR 7977 sets the new standards-development principles |
| March 2019 | SP 800-131A Rev. 2: “The use of Dual_EC_DRBG is disallowed” |
Sources: NIST ITL, September 2013, csrc.nist.gov; NIST, April 21, 2014, nist.gov; NIST VCAT, July 2014, nist.gov; NIST, SP 800-90A Rev. 1, June 2015, csrc.nist.gov; NIST IR 7977, March 2016, csrc.nist.gov; NIST, SP 800-131A Rev. 2, csrc.nist.gov; J. Kelsey, NIST, May 2014, csrc.nist.gov, for 2005 and 2007.
Was the Dual_EC_DRBG backdoor ever exploited?
The mechanism has been exploited in a shipping product, with constants other than NIST’s. In December 2015, Juniper announced that “During a recent internal code review, Juniper discovered unauthorized code in ScreenOS” that could “decrypt VPN connections.” Its advisory for CVE-2015-7756 covered ScreenOS 6.2.0r15 through 6.2.0r18 and 6.3.0r12 through 6.3.0r20 and warned “There is no way to detect that this vulnerability was exploited.”
Juniper had said in 2013 that ScreenOS used “self-generated basis points” and filtered Dual_EC output through a second generator. A peer-reviewed reverse-engineering study found the unauthorized change was “a change to the Q parameter,” that “Juniper’s countermeasures against a Dual EC attack are never executed,” and, using a Q of the researchers’ own, that “it is possible to passively decrypt a single IKE handshake and its associated VPN traffic.” In January 2016 Juniper said it would replace Dual_EC in ScreenOS 6.3 and that “The investigation of the origin of the unauthorized code continues.”
The 2014 USENIX study measured the same risk for TLS. With constants they generated themselves, the authors recovered TLS plaintext from RSA BSAFE and Windows SChannel, the C version of BSAFE falling in a worst case of 0.04 minutes on a 4-node cluster. OpenSSL-FIPS was saved by a bug that “prevented the library from running when Dual EC is enabled.”
Sources: Juniper Networks, “Important Announcement about ScreenOS,” December 17, 2015, archived copy; Juniper Networks, Security Advisory JSA10713, archived copy; S. Checkoway et al., “A Systematic Analysis of the Juniper Dual EC Incident,” ACM CCS 2016, eprint.iacr.org; Juniper Networks, “Advancing the Security of Juniper Products,” January 2016, archived copy; Checkoway et al., USENIX Security 2014, usenix.org, Table 1.
What is proven about Dual_EC_DRBG, and what is only reported?
The story mixes three kinds of claim, and they carry different weight.
| Claim | Standing | Basis |
|---|---|---|
| Whoever chose P and Q could hold a key that predicts all output from about 32 bytes | Proven, and demonstrated on P-256 with a self-made Q | Shumow and Ferguson 2007 |
| A trapdoored pair is indistinguishable from an innocent one | Proven, since telling them apart means solving the discrete log | SP 800-90A §10.3.1; Shumow and Ferguson 2007 |
| NSA supplied the generator and generated the default points | Stated by NIST | Kelsey 2014 |
| NSA engineered the weakness deliberately | Reported, from Snowden documents | NYT, Guardian, ProPublica, 2013 |
| RSA was paid $10 million to make it the BSAFE default | Reported by Reuters, citing 2 sources; RSA denies enabling back doors | Reuters, 2013 |
| The mechanism was exploited in a shipping product | Proven for Juniper ScreenOS with a substituted Q | Checkoway et al. 2016 |
| Anyone holds the key to NIST’s own default Q | Not established; NIST calls it alleged | Kelsey 2014 |
NIST has never said the default points are trapdoored. It removed the algorithm “Based on its own evaluation, and in response to the lack of public confidence,” and its postmortem records only that “NSA is alleged to have done this.”
Why do the constants in a cryptographic standard matter?
Every standard fixes some numbers, and each one is a place a designer could hide something. The defense is to derive them in a way anyone can repeat, so that the designer visibly had no choice. Cryptographers call these “nothing-up-my-sleeve” numbers, and the three common approaches differ in how much freedom they leave:
- Derived from well-known mathematics. The 64 round constants of SHA-256 “represent the first thirty-two bits of the fractional parts of the cube roots of the first sixty-four prime numbers,” per FIPS 180-4. There is nothing to choose.
- Hashed from a published seed. The “verifiably random” X9.62 method, which SP 800-90A offered for alternative Dual_EC points, proves the constant came from the seed and leaves open where the seed came from, the question behind NIST P-256 and rigid curves such as Curve25519.
- Asserted without derivation. Dual_EC_DRBG’s defaults, described by NIST in 2013 as points “the provenance of which were not described.”
NIST turned the lesson into policy: its 2016 process document commits that “specifications of new algorithms or schemes provide design rationale, including a description of the provenance of any constants used within the specification.”
Sources: NIST, FIPS 180-4, csrc.nist.gov, §4.2.2; NIST, SP 800-90A, January 2012, csrc.nist.gov, Appendix A.2.1; NIST ITL, September 2013, csrc.nist.gov; NIST IR 7977, March 2016, csrc.nist.gov, §2 and §7.
How did Dual_EC_DRBG shape post-quantum cryptography?
The external review NIST commissioned after Dual_EC set terms the post-quantum transition inherited. The VCAT’s July 2014 report said NIST “must be in a position to assess” NSA advice “and reject it when warranted,” and “strongly encourages standard development through open competitions, where appropriate.” The post-quantum competition NIST opened in December 2016 ran on that model, with every candidate and every attack in public.
The thinking shows up inside the algorithms too. ML-KEM avoids a fixed matrix constant: its public matrix is “generated pseudorandomly using XOF with only a seed stored in the encryption key,” so each key pair derives its own and anyone can recompute it. And FIPS 203 requires ML-KEM’s random bytes to “be generated using an approved RBG, as prescribed in SP 800-90A,” so a sound post-quantum algorithm fed by a compromised generator is only as strong as the generator.
Sovereignty over selection is the other inheritance. South Korea ran a national competition, KpqC, and China runs NGCC; China’s organizers cite the quantum threat and “novelty and diversity” as their reasons. Dual_EC is the best-documented public case for wanting to see how a standard’s constants were chosen before trusting it; that reading is this Guide’s assessment, and neither program has published it as a reason.
One last connection: Dual_EC’s trapdoor is itself an elliptic-curve discrete logarithm, the problem Shor’s algorithm solves. A cryptographically relevant quantum computer could compute the secret linking P and Q for any published pair, which would open the backdoor to anyone who owns one.
Sources: NIST VCAT, July 2014, nist.gov, §3; NIST, FIPS 203, August 2024, csrc.nist.gov, §3.3 and Algorithm 13; KpqC Research Group, kpqc.or.kr; M. Roetteler, M. Naehrig, K. M. Svore, K. Lauter, “Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms,” ASIACRYPT 2017, arxiv.org, for the quantum attack on elliptic-curve discrete logarithms. The NGCC quotation comes from the ICCS program introduction cited in NGCC (China).
Has this happened before?
The closest precedent is the one that went the other way. IBM designed DES around 1974 with NSA providing “technical advice,” and the design criteria for its S-box constants were withheld, so “Many people speculated… that the lack of disclosure was due to some ‘trap door’ or hidden weakness.” In 1994 Don Coppersmith, one of the S-box designers, explained that the team knew differential cryptanalysis “as early as 1974,” hardened the constants against it, and kept quiet because “After discussions with NSA, it was decided that disclosure of the design considerations would reveal the technique.” The secret constants in DES made the cipher stronger, and the reason became public only in 1994, after academics had independently rediscovered the attack around 1990.
In both cases an agency shaped a standard’s constants without explaining them, and from outside the two looked identical. One was protection and the other a probable trapdoor, and nobody outside could tell which for years. A published rationale for every constant is the fix for both.
Source: D. Coppersmith, “The Data Encryption Standard (DES) and its strength against attacks,” IBM Journal of Research and Development 38(3), May 1994, doi.org.
Common misconceptions
- “Dual_EC_DRBG was broken by cryptanalysis.” Its math held. The risk sits in who knows the relationship between P and Q; without that secret, predicting the output stays as hard as an elliptic-curve discrete logarithm.
- “It’s proven that NSA put a backdoor in it.” The possibility is proven and NSA’s authorship of the generator is confirmed by NIST. Deliberate insertion rests on reporting from Snowden documents, and nobody has published the secret number.
- “Juniper proves NIST’s constants were trapdoored.” Juniper used its own Q, and an unknown party replaced it. The incident proves the mechanism is exploitable in practice; it says nothing about NIST’s defaults.
- “Passing validation means a component is safe.” Dual_EC_DRBG was implemented in over 50 validated modules, and validation required the unexplained default points.
- “The post-quantum standards removed the randomness risk.” ML-KEM still draws its secrets from an SP 800-90A generator, so the quality and provenance of that generator still decide whether the keys are secret.
Questions people ask
What does DRBG stand for? Deterministic random bit generator, NIST’s term for a cryptographically secure pseudorandom generator. Dual_EC_DRBG was the elliptic-curve member of the family, and CSPRNG and DRBG covers the three that remain approved.
Is Dual_EC_DRBG still used anywhere? NIST disallows it under SP 800-131A Rev. 2, RSA advised developers to stop using it, OpenSSL began removing it from its FIPS module, and Juniper replaced it in ScreenOS. Older firmware and pinned library versions from before 2015 may still contain it, since NIST noted in 2014 that some products listed it as included without using it by default.
Why did RSA make it the default in BSAFE? Reuters reported a $10 million deal with NSA, which RSA disputed in its statement. RSA’s executive chairman said publicly in 2014 that the default helped the company “meet government certification requirements.”
Is P-256 backdoored too? No weakness has ever been found in P-256. Its seed was published without an account of how it was chosen, which is a provenance question, and Curve25519 vs P-256 covers that debate.
Does the NIST PQC competition prevent another Dual_EC? It removes the specific failure, an unexplained constant from one party, because every candidate’s design and parameters were public and attacked for years. Trust in the random generator and in the shipped implementation still has to be earned separately.
Why do some countries run their own post-quantum competitions? South Korea and China chose their own algorithms through national competitions, and China’s organizers cite the quantum threat and design diversity. Dual_EC is part of the context as a documented case of what happens when outsiders can’t check how a standard’s constants were chosen.
Go deeper
The generator family it belonged to: CSPRNG and DRBG · HMAC · Elliptic-Curve Cryptography (ECC) · discrete logarithm problem
The provenance debate it started: NIST P-256 · Curve25519 vs P-256 · FIPS 180-4 · NIST
The competitions that answer it: The NIST PQC Competition · KpqC (South Korea) · NGCC (China)
Where the randomness lesson lands now: FIPS 203 (ML-KEM) · Cryptographic Supply-Chain Risk · Why Does Strong Cryptography Still Fail
Everything here is the map, given freely. When your team needs to know which random generators and constants its own systems are trusting, and how fast they could be replaced, that’s the work I do.
Last verified 2026-09-28 · Maintained by Addie LaMarr, LaMarr Labs.