# Dual EC DRBG: How a Standard Got a Backdoor **Source**: https://quantumsequrity.com/blog/dual-ec-drbg-backdoor **Category**: Threats & Attacks --- [← Back to Blog](../../blog.html) Threats & Attacks # Dual EC DRBG: How a Standard Got a Backdoor 12 min read In 2006, NIST published Special Publication 800-90A, "Recommendation for Random Number Generation Using Deterministic Random Bit Generators." Among the four DRBGs the document standardized was one called Dual_EC_DRBG, a deterministic random bit generator based on elliptic curve mathematics. Within a year, two Microsoft researchers, Dan Shumow and Niels Ferguson, presented a rump session talk at CRYPTO 2007 raising serious concerns about Dual_EC_DRBG. By 2013, internal NSA documents leaked by Edward Snowden confirmed what cryptographers had suspected: Dual_EC_DRBG contained an intentional backdoor that the NSA had inserted to give itself the ability to predict the random output of any system that used it. NIST withdrew the algorithm in 2014. The Dual_EC_DRBG affair became one of the most consequential lessons about the dangers of trusting cryptographic standards without scrutinizing the math behind them. This post explains the Dual_EC_DRBG backdoor in plain language, walks through the elliptic curve mechanism that allowed it, and shows how the affair changed the way the cryptographic community evaluates standards proposals. ## What Dual_EC_DRBG Actually Did A deterministic random bit generator takes a seed of true randomness and stretches it into a long stream of pseudorandom output. Cryptographic applications use DRBGs constantly: every TLS connection, every key generation, every nonce, every IV depends on a DRBG to produce unpredictable bytes. If the DRBG is predictable, the entire cryptographic system collapses. Dual_EC_DRBG produced its output by performing point multiplication on a fixed elliptic curve, the NIST P-256 curve. Two specific points on the curve, P and Q, were specified in the standard. The algorithm maintained a state s, computed s' = s * P (point multiplication), extracted the x-coordinate of s' to update the state, computed t = s' * Q, and extracted the x-coordinate of t to produce 30 bytes of output per iteration. The strange thing about Dual_EC_DRBG was the choice of P and Q. P was the standard generator of the NIST P-256 curve. Q was a different point, specified by NIST as "a point on the curve" but with no explanation of how it was chosen. The standard simply listed the coordinates of Q without justification. This is where the trouble starts. If Q had been generated through a transparent process (like applying a hash function to a public seed and projecting onto the curve), there would be no concern. But Q was given as a magic number with no provenance, which raised questions about whether it had been chosen to enable a backdoor. ## The Shumow-Ferguson Insight Shumow and Ferguson's 2007 talk made the question concrete. They observed that if there exists a number e such that Q = e * P (in elliptic curve terms, e is the "discrete log" of Q with respect to P), then anyone who knows e can predict the next state of the DRBG given just 30 bytes of output. The math is straightforward. Suppose the DRBG has produced an output value y, which is the x-coordinate of the point t = s' * Q. The attacker recovers all candidate points on the curve with x-coordinate equal to y (there are typically two such points, since elliptic curves are symmetric over the x-axis). Each candidate point t satisfies t = s' * Q. The attacker uses the relation Q = e * P to write t = s' * e * P, which means s' = t * e^-1 mod n, where n is the order of the curve. Now the attacker knows s' (up to two candidates). They run the algorithm forward one step to predict the next output. If their prediction matches the actual next output, they have synced state with the DRBG. From that point on, they can predict every subsequent output. The whole attack requires only knowledge of e, which is the discrete log of Q with respect to P. For someone who chose Q at random by computing Q = e * P, recovering e is trivial: they remember the e they used. For everyone else, recovering e from public data is computationally infeasible (it would require solving the elliptic curve discrete log problem on P-256, which is the security foundation of all NIST P-256-based cryptography). Shumow and Ferguson did not accuse anyone of inserting a backdoor. They simply pointed out that the structure of Dual_EC_DRBG was such that whoever specified Q might possess the key e to a backdoor. This was a polite way of saying: "If you trust NIST to have generated Q honestly, this is fine. If you do not, you have a problem." ## The Snowden Confirmation In September 2013, Edward Snowden's leaks led to a New York Times article confirming what cryptographers had suspected for six years. Internal NSA documents described a $250 million annual program (BULLRUN) aimed at undermining encryption used worldwide. One specific element of BULLRUN involved manipulating cryptographic standards. Although the NSA was never named in court documents, the technical evidence and the public disclosures made it clear that Dual_EC_DRBG's Q parameter was generated with NSA involvement, and that the NSA possessed e, giving it the ability to predict any DRBG state from a small amount of output. The reaction was swift. NIST issued a public statement urging users to stop using Dual_EC_DRBG. RSA Security (which had used Dual_EC_DRBG as the default in its widely deployed BSAFE cryptographic toolkit) removed it as the default in late 2013. By April 2014, NIST published Special Publication 800-90A Revision 1, which removed Dual_EC_DRBG entirely. A Reuters investigation later that year reported that the NSA had paid RSA Security $10 million to make Dual_EC_DRBG the default in BSAFE. RSA disputed the framing of the report but did not dispute the payment itself. The episode caused significant reputational damage to both NIST and RSA Security and sparked broader concerns about the integrity of cryptographic standardization. ## Why This Took So Long to Be Pulled A reasonable question is: if Shumow and Ferguson raised the concern in 2007, why did Dual_EC_DRBG remain a NIST-approved DRBG until 2014? The answer is partly bureaucratic and partly cryptographic. Cryptographically, Dual_EC_DRBG was not provably broken in 2007. The Shumow-Ferguson argument showed that Q's provenance was suspicious, but absent evidence of an actual backdoor, the algorithm was structurally sound. Many cryptographers viewed the situation as "smells bad but not provably bad." Bureaucratically, withdrawing a NIST standard is a slow process. Industry vendors had certified products against SP 800-90A. Federal agencies had compliance requirements that referenced the document. Backing out an algorithm requires negotiation with vendors, agencies, and the broader community. Without smoking-gun evidence, NIST was unable (or unwilling) to move quickly. The Snowden documents provided the smoking gun. With direct evidence of NSA manipulation, NIST had no choice but to withdraw the algorithm and conduct a public review of its standardization processes. ## The Aftermath: A More Public Process The Dual_EC_DRBG affair changed how cryptographic standards get made. NIST commissioned external reviews of its standardization processes and committed to greater transparency. The current post-quantum cryptography standardization (which produced ML-KEM and ML-DSA, see [ML-KEM Explained](ml-kem-explained.md) and [ML-DSA vs SLH-DSA](mldsa-vs-slhdsa.md)) is a model of public, transparent standards development. Algorithms are submitted publicly. Cryptanalysis is done in the open. Multiple rounds of review weed out flawed proposals. The community examines every parameter choice. The IETF also tightened its standards process. RFC 7748 (X25519, January 2016) explicitly chose its curve constants through a transparent procedure: the curve coefficient is the smallest A satisfying the desired security properties. There is no magic number. The same applies to RFC 8032 (Ed25519). These deterministic choices make backdoors structurally impossible. For DRBG selection specifically, the modern recommendation is to use HMAC-DRBG, Hash-DRBG, or CTR-DRBG. All three are based on standard cryptographic primitives (HMAC, SHA-2, AES) and have no magic constants whose provenance you have to trust. NIST SP 800-90A Rev 1 (June 2015) keeps these three and removes Dual_EC_DRBG. ## Lessons for the Post-Quantum Era The Dual_EC_DRBG affair teaches several lessons that apply to the post-quantum migration. The first is that magic constants are dangerous. Any cryptographic algorithm that relies on parameters whose provenance you cannot verify is suspect. ML-KEM and ML-DSA both use parameters that can be derived from public, transparent procedures. The NTT modulus, the polynomial ring structure, the Galois group, all are mathematically motivated and not magic numbers. The second lesson is that standards processes need public scrutiny. The NIST PQC competition was deliberately designed to be open. All submissions, all attacks, and all design rationales are public. Multiple rounds of public review winnowed down hundreds of submissions to a handful of finalists. The transparency makes backdoor insertion much harder, because any proposed parameter has to be defended in public. The third lesson is that hybrid encryption is a hedge against future surprises. Even if some future post-quantum algorithm turned out to have a flaw or a backdoor, combining it with a classical algorithm like X25519 (see [Hybrid Encryption](hybrid-encryption.md)) means the underlying secret stays protected. This defense-in-depth approach is exactly what NIST has recommended for the transition period. ## How QNSQY Handles Randomness QNSQY uses operating-system-provided randomness (getrandom on Linux, BCryptGenRandom on Windows, SecRandomCopyBytes on macOS) for key generation, nonces, and other random material. These OS-level CSPRNGs are themselves backed by hardware random number generators and well-understood DRBGs. There is no use of Dual_EC_DRBG anywhere in the QNSQY codebase, and no reliance on any magic-number-based PRNG. For ephemeral key derivation during encryption, QNSQY uses HKDF (RFC 5869) with BLAKE3 (see [BLAKE3 Hashing](blake3-hashing.md)) for the underlying hash. HKDF is a deterministic function: given the same input randomness, it produces the same output. The randomness comes from the OS, and HKDF stretches it into the various keys needed for encryption. No magic constants, no questionable provenance. The post-quantum primitives (ML-KEM, ML-DSA) use parameters defined in the NIST FIPS standards (FIPS 203 for ML-KEM, FIPS 204 for ML-DSA), which were generated through transparent, public procedures during the NIST PQC competition. Every parameter has a documented derivation. ## FAQ **Was Dual_EC_DRBG actually used in real deployments?** Yes. RSA Security made it the default in BSAFE, which was widely deployed in commercial software. Various government and enterprise applications used it. The full list is hard to enumerate because many deployments used Dual_EC_DRBG transitively through libraries that incorporated BSAFE. The actual harm caused by the backdoor (in terms of intercepted traffic) is unknown. **Is the NSA the only entity that knew the backdoor key?** The leaked documents do not specify who else had access. In principle, any sophisticated nation-state intelligence agency could have independently derived the same backdoor structure (Shumow-Ferguson made this public in 2007). Whether they acted on it is unknown. **Could a similar backdoor be hidden in modern post-quantum algorithms?** The post-quantum standardization process was designed to make this very hard. Parameters were generated through public, transparent procedures. Multiple independent research groups attacked the candidates over years of public review. Any structural backdoor would require collusion among many independent entities to remain hidden, which is much harder to imagine than a single-vendor backdoor. **What should I look for to evaluate a cryptographic standard?** Three things: (1) Are the parameters generated transparently from a published procedure? (2) Has the algorithm been publicly reviewed by independent cryptographers? (3) Is there a clear cryptographic reason for every design choice? If any of these is missing, treat the standard with suspicion. See [NIST FIPS Guide](nist-fips-guide.md) for how modern NIST standards approach these questions. **Does QNSQY use any DRBG that has Dual_EC_DRBG-style risks?** No. QNSQY uses OS-level CSPRNGs and standard HKDF for key derivation. No magic constants, no questionable provenance. ## Sources 1. Shumow, D., and Ferguson, N. "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng." CRYPTO 2007 rump session. https://rump2007.cr.yp.to/15-shumow.pdf 2. National Institute of Standards and Technology. "Recommendation for Random Number Generation Using Deterministic Random Bit Generators." NIST SP 800-90A Rev. 1, June 2015. https://csrc.nist.gov/pubs/sp/800/90/a/r1/final 3. Perlroth, N., Larson, J., and Shane, S. "N.S.A. Able to Foil Basic Safeguards of Privacy on Web." New York Times, September 5, 2013. 4. Menn, J. "Exclusive: Secret contract tied NSA and security industry pioneer." Reuters, December 20, 2013. 5. National Institute of Standards and Technology. "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations." NIST press release, April 21, 2014. https://www.nist.gov/news-events/news/2014/04/nist-removes-cryptography-algorithm-random-number-generator-recommendations 6. Bernstein, D. J., Lange, T., and Niederhagen, R. "Dual EC: A Standardized Back Door." IACR ePrint 2015/767. https://eprint.iacr.org/2015/767 ## Related Articles - [What Is Post-Quantum Cryptography](what-is-post-quantum-cryptography.md) - [ML-KEM Explained](ml-kem-explained.md) - [ML-DSA vs SLH-DSA](mldsa-vs-slhdsa.md) - [Hybrid Encryption](hybrid-encryption.md) - [NIST FIPS Guide](nist-fips-guide.md) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)