Leaked NSA docs suggest Dual_EC_DRBG backdoor

An algorithm used to generate random numbers adopted by the National Institute of Standards and Technology was written by the US National Security Agency to contain a backdoor, leaked Snowden documents reveal.

The New York Times report provided further details into separate documents leaked by former NSA contractor Edward Snowden that alleged the agency had weakened then unnamed encryption standards.

The internal memos state the Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) used in a 2006 National Institute of Standards and Technology standard and adopted by the International Organisation for Standardisation was written by the NSA.

“The road to developing this standard was smooth once the journey began,” an NSA memo stated according to the NY Times. “However, beginning the journey was a challenge in finesse.”

The possibility for such a backdoor was first flagged in 2006 and again a informal paper presented at the Crypto 2007 conference by researchers Dan Shumow and Niels Ferguson. (PDF)

Cryptographer Bruce Schneier wrote in a 2007 Wired article titled "Did NSA Put a Secret Backdoor in New Encryption Standard?" of the Shumow-Ferguson research that the generator in question stood out from the other three then competing proposals because it was "three orders of magnitude slower than its peers" and was the only standard "championed by the NSA".

In describing the algorithm and its potential flaws, Schneier said:

"There are a bunch of constants -- fixed numbers -- in the standard used to define the algorithm's elliptic curve ... What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output."

"To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG."

Breaking the random-number generator meant breaking the entire security system, he said.

The leaked documents suggest the NSA wrangled Canada’s Communications Security Establishment which at the time ran the standards process for the International Organization for Standardisation.

“After some behind-the-scenes finessing with the head of the Canadian national delegation and with the (Communications Security Establishment), the stage was set for NSA to submit a rewrite of the draft,” the memo read according to the NY Times.

“Eventually, NSA became the sole editor.”

@chriseng basically dual_ec_dbrg confirmed backdoored, a big passive break of SSL in 2010, lotsa VPNs owned (somehow)

— Dan Kaminsky (@dakami) September 5, 2013

The leaks spurred the NIST to reopen public review of the Special Publication 800-90 in which the algorithm was contained and to deny that it deliberately weakened the security mechanism.

"NIST would not deliberately weaken a cryptographic standard. We will continue in our mission to work with the cryptographic community to create the strongest possible encryption standards for the US Government and industry at large," it said in a statement.

It said the body was "required by statute" to consult with the NSA adding its mandate was to "develop standards and guidelines to protect federal information and information systems" and that private industry had "voluntarily" adopted the standards due to its perceived security robustness.

Copyright © SC Magazine, Australia