Last summer I wrote here about an article in the AMS Notices which appeared to make misleading claims about the NSA’s involvement in putting a backdoor in an NIST cryptography standard known as DUAL_EC_DRBG. The article by Richard George, a mathematician who worked at the NSA, addressed the issue of the NSA doing this kind of thing by discussing an example of past history when they were accused of doing this, but were really actually strengthening the standard. He then went on to claim that:
I have never heard of any proven weakness in a cryptographic algorithm that’s linked to NSA; just innuendo.
This appears to be a denial of an NSA backdoor in the standard, while not saying so explicitly. If there is a backdoor, as most experts believe and the Snowden documents indicate, this was a fairly outrageous use of the AMS to mislead the math community and the public. At the time I argued with some at the AMS that they should insist that George address explicitly the question of the existence of the backdoor, but didn’t get anywhere with that. One of their arguments was that George was speaking for himself, not the NSA.
The question of fact here is a very simple and straightforward mathematical one: how was the choice used in the standard of points P and Q on an elliptic curve made? There is a known way to do this that provides a backdoor. Did the NSA use this method, or some other one for which no backdoor is known? The NSA refused to cooperate with the NIST investigation into this question. The only record of what happened when the NIST asked about how P and Q were chosen early on in the development of the standard is this, which indicates that people were told by the NSA that they were not allowed to publicly discuss the question.
Remarkably, the latest AMS Notices has a new article with an extensive discussion of the DUAL_EC_DRBG issue, written by mathematician Michael Wertheimer, the NSA Director of Research. At first glance, Wertheimer appears to claim that the NSA was unaware of the possibility of a backdoor:
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.
On close reading though, one realizes that Wertheimer does not address at all the basic question: how were P and Q chosen? His language does not contain any actual denial that P and Q have a backdoor.
For a careful examination of the Wertheimer piece by an expert, see this from Matthew Green. Green concludes that
… 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.
In a recent podcast on the subject Green states
I think it’s still going on… I think that the NSA has really adopted a policy of tampering with cryptographic products and they’re not going to give that up. I don’t think that this is a time that they want to go out admitting what they did in this particular case as a result of that.
Given that this is now the only official NSA statement about the DUAL_EC_DRBG issue, the Notices article has drawn a lot of attention, see for instance here. The Register summarizes the story with the headline NSA: So sorry we backed that borked crypto even after you spotted the backdoor.
The publication of the George and Wertheimer pieces by the AMS has created a situation where there are just two possibilities:
- Despite what experts believe and Snowden documents indicate, the NSA chose P and Q by a method that did not introduce a backdoor. For some reason though they are unwilling to state publicly that this is the case.
- P and Q were chosen with a backdoor, and the AMS has now repeatedly been used to try and mislead the mathematics community about this issue.
I’ve contacted someone at the AMS to try and find out whether the question of a backdoor in P and Q was addressed in the refereeing process of the article, but been told that they won’t discuss this. I think this is an issue that now needs to be addressed by the AMS leadership, specifically by demanding assurances from Wertheimer that the NSA did not choose a backdoored P and Q. If this is the case I can see no reason why such assurances cannot be provided. If the NSA and Wertheimer won’t provide this, I think the AMS needs to immediately cut off its cooperative programs with the agency. There may be different opinions about the advisability of such programs, but I don’t think there can be any argument about the significance of the AMS being used by the NSA to mislead the mathematics community.
Update: There’s an Ars Technica story here, with a peculiar update of its own:
An NSA spokesperson emailed Ars on Friday to say Wertheimer retired in the fall of 2014 and submitted the article after he left his position. The Notices article made no mention of his retirement.
Another odd thing about the Wertheimer piece is that in a different part of it he seems to reveal what I would have thought the NSA considered a closely held piece of information about Taliban communication methods (see here). If he can discuss that publicly, why can’t he say whether P and Q were backdoored?
Update: This is getting international attention, with le Monde reporting the AMS Notices piece as an admission by the NSA that they backdoored DUAL_EC_DRBG.
Update: The NIST has put out a revised draft on its cryptographics standards process and asked for comments. On the NSA problem, it says that no changes have been made to the NSA-NIST Memorandum of Understanding, and that
cooperation with NIST is governed by an MOU between the two agencies and technical staff meet monthly to discuss ongoing collaborative work and future priorities.
It seems (see the NIST VCAT report) that, despite its obligations under the MOU, the NSA has refused to explain what it did with regards to compromising the DUAL_EC_DRBG standard, and experts believe (see above) that the NSA is committed to continuing to tamper with cryptographic products. Under these circumstances I don’t see how the NIST can expect anyone to not be suspicious of their standards.
A promise is made to identify NSA contributions to standards, but a footnote says that names of some NSA staff cannot be revealed and that documents involving NIST-NSA collaboration provided in response to FOIA requests may be redacted. I don’t see anything here that would keep the NSA from misleading or corrupting NIST staff to produce a backdoored standard, while keeping their input out of any record available to the public.