nav search
Data Center Software Security Transformation DevOps Business Personal Tech Science Emergent Tech Bootnotes BOFH

NSA: SO SORRY we backed that borked crypto even after you spotted the backdoor

Non-apology to mathematicians for Dual EC DRBG shenanigans

By Iain Thomson, 14 Jan 2015

The NSA's former director of research Michael Wertheimer says it's "regrettable" that his agency continued to support Dual EC DRBG even after it was widely known to be hopelessly flawed.

Writing in Notices, a publication run by the American Mathematical Society, Wertheimer outlined the history of the Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG), and said that an examination of the facts made it clear no malice was involved.

Dual EC DRBG is a random number generator championed by the NSA in the 2000s. Number generators are an essential component of encryption systems; a weak generator will leave encrypted data vulnerable to decoding by an attacker.

This random number generator was eventually approved as a trustworthy algo by the US National Institute of Standards and Technology (NIST), despite concerns that it could be faulty, and RSA made it the default encryption systems in its BSAFE toolkits. A subsequent report suggested the NSA paid RSA $10m to include the flawed algorithm – a claim RSA denies.

In 2007 two Microsoft security researchers, Dan Shumow and Niels Ferguson, pointed out that there were serious flaws with Dual EC DRBG, and that using it with elliptic curve points generated by the NSA could create a "trap door" that would allow encryption to be easily broken.

"With hindsight, NSA should have ceased supporting the Dual EC DRBG algorithm immediately after security researchers discovered the potential for a trapdoor. In truth, I can think of no better way to describe our failure to drop support for the Dual EC DRBG algorithm as anything other than regrettable," Wertheimer wrote [PDF].

"The costs to the Defense Department to deploy a new algorithm were not an adequate reason to sustain our support for a questionable algorithm. Indeed, we support NIST's April 2014 decision to remove the algorithm. Furthermore, we realize that our advocacy for the Dual EC DRBG casts suspicion on the broader body of work NSA has done to promote secure standards."

The case doesn't prove the NSA is actively trying to subvert crypto standards, Wertheimer argued, merely that a mistake had been made and then rectified. He pointed out that the NSA was keen to fund more mathematical research and – post September 11 – this work was vitally needed.

On the other hand…

But Wertheimer's version of events isn't sitting well with some experts in the field. Assistant research professor Matthew Green of Johns Hopkins University Information Security Institute in Maryland has written a rebuttal to Wertheimer, pointing out several holes in his story.

For a start, Prof Green said problems with Dual EC DRBG systems that used the NSA's elliptic curve points were first noticed way back in 2004 by members of an ANSI standards committee, when NIST was still considering backing the algorithm. Someone on the panel even went as far as to file a patent on breaking encryption using the system.

In response, ANSI, a key US standards body, did very little, Green notes. It too continued to promote Dual EC DRBG, using the NSA's data points as standard, but as a sop to concerns added an alternative point generation algorithm. Unfortunately, to see this, you had to buy the non-public-domain ANSI standard and work out how to implement it.

"This is, to paraphrase Douglas Adams, the standards committee equivalent of putting the details in the bottom of a locked filing cabinet stuck in a disused lavatory with a sign on the door saying 'Beware of the leopard,'" Green said.

"To the best of our knowledge, nobody has ever used ANSI's alternative generation procedure in a single one of the many implementations of Dual EC DRBG in commercial software. It's not even clear how you could have used that procedure in a FIPS-certified product, since the FIPS evaluation process still requires you to test against the NSA-generated points."

He also points out that the ANSI investigation of problems was hardly an open process. Instead it was carried out in closed committee by ANSI, NIST, the NSA, and a few select companies and the results were not made public.

"As a record of history, Dr Wertheimer's letter leaves much to be desired, and could easily lead people to the wrong understanding," Green concluded. "Given the stakes, we deserve a more exact accounting of what happened with Dual EC DRBG. I hope someday we'll see that." ®

The Register - Independent news and views for the tech community. Part of Situation Publishing