I’ve been working on some other blog posts, including a conclusion of (or at least an installment in) this exciting series on zero knowledge proofs. That’s coming soon, but first I wanted to take a minute to, well, rant.

The subject of my rant is this fascinating letter authored by NSA cryptologist Michael Wertheimer in February’s Notices of the American Mathematical Society. Dr. Wertheimer is currently the Director of Research at NSA, and formerly held the position of Assistant Deputy Director and CTO of the Office of the Director of National Intelligence for Analysis.

In other words, this is a guy who should know what he’s talking about.

The subject of Dr. Wertheimer’s letter is near and dear to my heart: the alleged subversion of NIST’s standards for random number generation — a subversion that was long suspected and apparently confirmed by classified documents leaked by Edward Snowden. The specific algorithm in question is called Dual EC DRBG, and it very likely contains an NSA backdoor. Those who’ve read this blog should know that I think it’s as suspicious as a three dollar bill.

Reading Dr. Wertheimer’s letter, you might wonder what I’m so upset about. On the face of it, the letter appears to express regret. To quote (with my emphasis):

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. 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. 

I agree with all that. The trouble is that on closer examination, the letter doesn’t express regret for the inclusion of Dual EC DRBG in national standards. The transgression Dr. Wertheimer identifies is merely that NSA continued to support the algorithm after major questions were raised. That’s bizarre.

Even worse, Dr. Wertheimer reserves a substantial section of his letter for a defense of the decision to deploy Dual EC. It’s those points that I’d like to address in this post.

Let’s take them one at a time.

1: The Dual_EC_DRBG was one of four random number generators in the NIST standard; it is neither required nor the default.

It’s absolutely true that Dual EC was only one of four generators in the NIST standard. It was not required for implementers to use it, and in fact they’d be nuts to use it — given that overall it’s at least two orders of magnitude slower than the other proposed generators.

The bizarre thing is that people did indeed adopt Dual EC in major commercial software packages. Specifically, RSA Security included it as the default generator in their popular BSAFE software library. Much worse, there’s evidence that RSA was asked to do this by NSA, and were compensated for their compliance.

This is the danger with standards. Once NIST puts its seal on an algorithm, it’s considered “safe”. If the NSA came to a company and asked it to use some strange, non-standard algorithm, the request would be considered deeply suspicious by company and customers alike. But how can you refuse to use a standard if your biggest client asks you to? Apparently RSA couldn’t.

2: The NSA-generated elliptic curve points were necessary for accreditation of the Dual_EC_DRBG but only had to be implemented for actual use in certain DoD applications.

This is a somewhat misleading statement, one that really needs to be unpacked.

First, the original NSA proposal of Dual EC DRBG contained no option for alternate curve points. This is an important point, since its the selection of curve points that give Dual EC its potential for a “back door”. By generating two default points (P, Q) in a specific way, the NSA may have been able to create a master key that would allow them to very efficiently decrypt SSL/TLS connections.

If you like conspiracy theories, here’s what NIST’s John Kelsey was told when he asked how the NSA’s points were generated:

In 2004-2005, several participants on the ANSI X9 tools committee pointed out the potential danger of this backdoor. One of them even went so far as to file a patent on using the idea to implement key escrow for SSL/TLS connections. (It doesn’t get more passive aggressive than that.)

In response to the discovery of such an obvious flaw, the ANSI X9 committee immediately stopped recommending the NSA’s points — and relegated them to be simply an option, one to be used by the niche set of government users who required them.

I’m only kidding! Actually the committee did no such thing.

Instead, at the NSA’s urging, the ANSI committee retained the original NSA points as the recommended parameters for the standard. It then added an optional procedure for generating alternative points. When NIST later adopted the generator in its SP800-90A standard, it mirrored the ANSI decision. But even worse, NIST didn’t even bother to publish the alternative point generation algorithm. To actually implement it, you’d need to go buy the (expensive) non-public-domain ANSI standard and figure it out to implement it yourself:

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’.

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 (conducted by CMVP) still requires you to test against the NSA-generated points.

3. The trapdoor concerns were openly studied by ANSI X9F1, NIST, and by the public in 2007. 

This statement has the benefit of being literally true, while also being pretty damned misleading.

It is true that in 2007 — after Dual EC had been standardized — two Microsoft researchers, Dan Shumow and Neils Ferguson openly raised the alarm about Dual EC. The problem here is that the flaws in Dual EC were not first discovered in 2007. They were discovered much earlier in the standardization process and nobody ever heard about them.

As I noted above, the ANSI X9 committee detected the flaws in Dual EC as early as 2004, and in close consultation with NSA agreed to address them — in a manner that was highly beneficial to the NSA. But perhaps that’s understandable, given that the committee was anything but ‘open’.

In fact, this is an important aspect of the controversy that even NIST has criticized. The standardization of these algorithms was conducted through ANSI. And the closed ANSI committee consisted of representatives from a few select companies, NIST and the NSA. No public notice was given of the potential vulnerabilities discovered in the RNG. Moreover, a patent application that might have shone light on the backdoor was mired in NSA pre-publication review for over two years.

This timeline issue might seem academic, but bear this in mind: we now know that RSA Security began using the Dual EC DRBG random number generator in BSAFE — as the default, I remind you — way back in 2004. That means for three years this generator was widely deployed, yet serious concerns were not communicated to the public.

To state that the trapdoor concerns were ‘openly’ studied in 2007 is absolutely true. It’s just completely irrelevant.

In conclusion

I’m not a mathematician, but like anyone who works in a mathematical area, I find there are aspects of the discipline that I love. For me it’s the precision of mathematical statements, and the fact that the truth or falsity of a statement can — ideally — be evaluated from the statement itself, without resorting to differing opinions or understandings of the context.

While Dr. Wertheimer’s letter is hardly a mathematical work, it troubles me to see such confusing statements in a publication of the AMS. As a record of history, Dr. Wertheimer’s letter leaves much to be desired, and could easily lead people to the wrong understanding.

Given the stakes, we deserve a more exact accounting of what happened with Dual EC DRBG. I hope someday we’ll see that.