NSA Backdoors in Encryption Standards (Dual EC DRBG)

Overview

For decades, the idea that the NSA might be deliberately weakening the encryption standards that protect global communications was dismissed by most people outside the cryptography community as paranoia. The agency, after all, had a dual mandate: to conduct signals intelligence (spying on foreign communications) and to protect American communications from foreign adversaries. Surely the agency tasked with securing American encryption would not deliberately weaken it — because doing so would make everyone, including the Americans the NSA was supposed to protect, more vulnerable.

Then Edward Snowden started talking.

In September 2013, documents leaked by the former NSA contractor revealed that the agency had, in fact, been doing exactly what the paranoid had feared. Through a classified program called BULLRUN, the NSA had been systematically working to undermine encryption standards, inserting backdoors into cryptographic algorithms, collaborating with technology companies to weaken their products, and spending hundreds of millions of dollars annually on efforts to make the world’s digital communications accessible to American intelligence.

The most concrete and damning example was Dual EC DRBG, a random number generator that the NSA had pushed through the National Institute of Standards and Technology (NIST) as a federal standard in 2006, and that the agency had paid RSA Security $10 million to adopt as a default in its widely used cryptographic products. Cryptographers had warned since 2007 that the algorithm appeared to contain a backdoor. They were right.

This theory is classified as confirmed: the Snowden documents established beyond reasonable dispute that the NSA deliberately weakened Dual EC DRBG, that the agency operated BULLRUN as a systematic program to undermine encryption, and that RSA Security was paid to adopt the compromised standard.

Origins & History

The Crypto Wars: A Brief Prehistory (1990s)

The Dual EC DRBG scandal did not emerge from a vacuum. It was the latest chapter in a decades-long conflict between the intelligence community and the technology sector over encryption — a conflict known as the Crypto Wars.

In the early 1990s, the Clinton administration proposed the Clipper Chip, a hardware encryption device that would have been installed in consumer electronics with a built-in backdoor accessible to law enforcement. The proposal generated fierce opposition from the technology industry, privacy advocates, and cryptographers, who argued that any backdoor could be exploited by adversaries as well as the government. The Clipper Chip was abandoned by 1996 after a researcher named Matt Blaze discovered a vulnerability that rendered its escrow system bypassable.

The Clipper Chip’s failure taught the NSA an important lesson: if you cannot mandate a backdoor through public policy, you might be able to achieve the same result through technical subterfuge.

The Birth of Dual EC DRBG (2004-2006)

Random number generators (RNGs) are the bedrock of cryptographic security. Every encryption key, every secure communication, every digital signature depends on the generation of numbers that are, for practical purposes, unpredictable. If an adversary can predict the output of a random number generator, they can reconstruct the encryption keys it produces and break the encryption.

Dual EC DRBG was a random number generator based on elliptic curve cryptography. It was developed with significant input from the NSA and submitted to NIST for inclusion in Special Publication 800-90, a set of recommended random number generators published in 2006. NIST, whose cryptographic standards are widely adopted by both government and the private sector, approved Dual EC DRBG alongside three other random number generators.

From the beginning, Dual EC DRBG had unusual characteristics. It was dramatically slower than the alternative algorithms — roughly 1,000 times slower than CTR_DRBG, one of the competing standards. It produced its random bits through a mathematically complex process involving two points on an elliptic curve, designated P and Q, whose relationship to each other was unexplained. The NSA specified the values of P and Q but did not explain how they had been chosen.

Shumow and Ferguson Sound the Alarm (August 2007)

In August 2007, at the annual CRYPTO conference in Santa Barbara, Microsoft researchers Dan Shumow and Niels Ferguson delivered a presentation titled “On the Possibility of a Back Door in the NIST SP 800-90 Dual Ec Prng.” Their analysis was technical but the conclusion was straightforward: if someone knew the mathematical relationship between the constants P and Q — specifically, if Q was a known multiple of P — they could predict the output of the generator after observing just 32 bytes of its output.

In other words, whoever chose P and Q could hold a master key to every encryption system that relied on Dual EC DRBG.

Shumow and Ferguson did not claim the NSA had actually inserted a backdoor. They merely demonstrated that the algorithm’s design was perfectly suited for one. The presentation was the cryptographic equivalent of pointing out that a bank vault’s blueprints showed a hidden door that only the architect knew about.

Bruce Schneier’s Warning (November 2007)

Three months later, Bruce Schneier, one of the world’s most respected cryptographers and security researchers, published an article in Wired magazine titled “Did NSA Put a Secret Backdoor in New Encryption Standard?” Schneier’s assessment was characteristically direct: “I don’t understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: it’s public, and it’s obvious. It makes no sense from an engineering perspective: it’s too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: it’s brand new. My recommendation, if you’re in a position to do so, is not to use Dual_EC_DRBG under any circumstances.”

Schneier noted that NIST had allowed the algorithm through despite the concerns, and that the NSA’s involvement in the standard-setting process was well-established. But without documentary proof, the claim that the algorithm was deliberately backdoored remained — as Schneier acknowledged — a suspicion rather than a fact.

RSA Security’s $10 Million Deal (2006-2013)

Meanwhile, RSA Security — a company whose very name evoked the mathematical foundations of modern encryption, named after the inventors of the RSA algorithm — had made Dual EC DRBG the default random number generator in two of its most widely used products: BSafe, a cryptographic toolkit used by software developers, and Data Protection Manager, an enterprise security product.

This decision was baffling to many in the security community. Dual EC DRBG was slow, suspect, and unnecessary — the other NIST-approved generators were faster, simpler, and not clouded by backdoor suspicions. Why would RSA, of all companies, choose the worst option as its default?

The answer came in December 2013, when Reuters reported that RSA had received a $10 million contract from the NSA to make Dual EC DRBG the default in its products. RSA’s revenue that year was approximately $900 million, making the NSA payment a relatively small sum — but one that apparently sufficed to influence a critical technical decision that affected the security of RSA’s customers worldwide.

RSA denied that it had knowingly compromised its products, stating: “We made the decision to use Dual EC DRBG as the default in BSAFE toolkits in 2004, in the context of an industry-wide effort to develop newer, stronger methods of encryption.” The company said it had relied on NIST’s endorsement. This defense convinced almost no one in the cryptography community.

The Snowden Bombshell (September 2013)

The Snowden documents, published simultaneously by the New York Times, the Guardian, and ProPublica in September 2013, provided the documentary proof that Schneier and the cryptographic community had lacked. The documents described BULLRUN, a multi-hundred-million-dollar NSA program dedicated to defeating encryption. Among BULLRUN’s methods:

• Inserting vulnerabilities into commercial encryption systems
• Influencing the design of encryption standards
• Working with technology companies to build in backdoors
• Using supercomputers for brute-force cryptanalysis
• Exploiting weak implementations of encryption protocols

The documents specifically referenced the NSA’s success in inserting a backdoor into a NIST encryption standard — an obvious reference to Dual EC DRBG, confirmed by subsequent reporting and analysis.

The Fallout (2013-2014)

The revelations triggered a cascading institutional crisis:

NIST issued a rare public statement recommending that users stop employing Dual EC DRBG and reopened the standard for public review. The institute also launched an internal review of its standard-setting process, an implicit acknowledgment that the NSA had compromised its independence.

RSA Security faced a devastating backlash. Prominent security researchers publicly announced they would boycott RSA’s annual security conference, one of the industry’s most important events. Mikko Hypponen, the chief research officer of F-Secure, published an open letter explaining his boycott: “I don’t really expect your multibillion dollar company to suffer just because of my talk. But I want the record to show that I spoke up.”

The broader technology industry was forced to confront the extent to which the NSA had subverted the standards and products they relied on. The incident accelerated a movement toward stronger, independently verified encryption and contributed to decisions by major tech companies to implement end-to-end encryption in their products.

Key Claims

• The NSA deliberately backdoored Dual EC DRBG: The agency designed the algorithm’s mathematical constants (P and Q) so that it could predict the generator’s output and thus break any encryption that relied on it. Confirmed.

• NIST was co-opted: The NSA used its influence over the NIST standard-setting process to get a compromised algorithm approved as a federal standard, despite the algorithm’s known weaknesses. Confirmed.

• RSA was paid to implement the backdoor: RSA Security received $10 million from the NSA to make the compromised algorithm its default. Confirmed by Reuters reporting; RSA denies knowingly weakening its products.

• BULLRUN represents a systematic effort to undermine encryption: The NSA operates a large-scale program to defeat encryption through multiple methods, not just Dual EC DRBG. Confirmed by Snowden documents.

• Other encryption standards may also be compromised: If the NSA successfully backdoored one standard, it may have done the same to others. Unproven but widely suspected; no other specific backdoors have been documented to the same degree.

Evidence

The evidentiary basis is unusually strong for a conspiracy of this nature:

• Snowden documents describing BULLRUN and the NSA’s efforts to weaken encryption standards, published by multiple reputable news organizations
• The 2007 Shumow-Ferguson paper demonstrating the mathematical basis for a backdoor
• Reuters reporting on the $10 million NSA-RSA contract
• NIST’s own withdrawal of the Dual EC DRBG recommendation, effectively confirming the backdoor
• Subsequent academic papers confirming that the Shumow-Ferguson backdoor was exploitable in practice
• NIST’s internal review acknowledging that its standard-setting process had been compromised

Debunking / Verification

This case requires no debunking — it is confirmed. The only remaining questions involve scope: how many other encryption standards has the NSA compromised? How many technology companies have similar arrangements? How extensively has the BULLRUN program been applied?

These questions are, by their nature, difficult to answer. The NSA’s activities in this area are classified, and the Snowden documents represent only a fraction of the agency’s operations. The cryptographic community has responded by developing more transparent standard-setting processes and by favoring algorithms whose mathematical properties can be fully verified.

Cultural Impact

The Dual EC DRBG scandal had a transformative impact on the relationship between the intelligence community and the technology industry. Before the Snowden revelations, many technology companies maintained cooperative relationships with the NSA, sometimes voluntarily, sometimes under legal compulsion. After the revelations, a significant faction of the tech industry adopted an adversarial posture, implementing stronger encryption specifically designed to resist government surveillance.

Apple’s 2014 decision to encrypt iPhone data by default, making it inaccessible even to Apple and therefore to any government with a court order, was widely interpreted as a direct response to the Snowden revelations. Google, Microsoft, and other major companies followed with their own encryption enhancements.

The scandal also reignited the Crypto Wars, with law enforcement and intelligence officials arguing that widespread strong encryption was creating “going dark” problems that impeded legitimate investigations. FBI Director James Comey and Attorney General William Barr both publicly called for technology companies to provide “exceptional access” to encrypted communications — a request that cryptographers universally rejected as technically equivalent to the backdoor the NSA had already been caught installing.

The irony was devastating: the NSA’s own actions in backdooring Dual EC DRBG had made the argument for government-accessible encryption essentially impossible to make with a straight face. Why would anyone trust a government backdoor after the government had been caught secretly installing one?

In Popular Culture

The Dual EC DRBG scandal features prominently in the 2014 documentary Citizenfour, directed by Laura Poitras, which documents Snowden’s disclosure of NSA surveillance programs. Bruce Schneier wrote extensively about the scandal in his 2015 book Data and Goliath: The Hidden Battles to Collect Your Data and Control Your World. The case is discussed in virtually every modern textbook on cryptography and computer security. It has been referenced in television series including Mr. Robot and Silicon Valley, both of which explored themes of government surveillance and encryption.

Timeline

Sources & Further Reading

• Shumow, Dan, and Niels Ferguson. “On the Possibility of a Back Door in the NIST SP 800-90 Dual Ec Prng.” Presentation at CRYPTO 2007.
• Schneier, Bruce. “Did NSA Put a Secret Backdoor in New Encryption Standard?” Wired, November 15, 2007.
• Schneier, Bruce. Data and Goliath: The Hidden Battles to Collect Your Data and Control Your World. W.W. Norton, 2015.
• Greenwald, Glenn. No Place to Hide: Edward Snowden, the NSA, and the U.S. Surveillance State. Metropolitan Books, 2014.
• Perlroth, Nicole, Jeff Larson, and Scott Shane. “N.S.A. Able to Foil Basic Safeguards of Privacy on Web.” New York Times, September 5, 2013.
• Ball, James, Julian Borger, and Glenn Greenwald. “Revealed: How US and UK Spy Agencies Defeat Internet Privacy and Security.” The Guardian, September 5, 2013.
• Menn, Joseph. “Exclusive: Secret Contract Tied NSA and Security Industry Pioneer.” Reuters, December 20, 2013.
• Checkoway, Stephen, et al. “On the Practical Exploitability of Dual EC in TLS Implementations.” USENIX Security Symposium, 2014.
• Poitras, Laura, director. Citizenfour. Praxis Films, 2014.

Related Theories

• NSA Warrantless Wiretapping — The NSA’s domestic surveillance program revealed before the Snowden leaks
• NSA XKeyscore — The NSA’s system for searching global internet communications
• Five Eyes Surveillance — The intelligence-sharing alliance that participated in BULLRUN through GCHQ’s EDGEHILL program