Among the many disturbing aspects of the behavior of the NSA revealed by the Snowden documents, the most controversial one directly relevant to mathematicians was the story of the NSA’s involvement in a flawed NIST cryptography standard (for more see here and here). The New York Times reported:
Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”
The standard was based on the mathematics of elliptic curves, so this is a clearly identifiable case where mathematicians seem to have been involved in using their expertise to subvert the group tasked with producing high quality cryptography. A big question this raises has been what the NIST will do about this. In April they removed the dubious algorithm from their standards, and published the public comments (many of which were highly critical) on a draft statement about their development process.
At the same time a panel of experts was convened to examine what had gone wrong in this case, and this panel has (on a very short time-scale) just produced its report (associated news stories here, here and here). The rules of how such panels are set up evidently require that each panelist provide an individual report, rather than attempt to have a consensus version. The new NIST document gives these reports together with minutes of the meetings where the panelists were provided with information. It seems that the NSA provided no information at all as part of this process, and they remain unwilling to answer any questions about their actions.
Appendix E contains the individual reports. These include, from Edward Felten:
The bottom line is that NIST failed to exercise independent judgment but instead deferred extensively to NSA with regard to DUAL_EC. After DUAL_EC was proposed, two major red-flags emerged. Either one should have caused NIST to remove DUAL_EC from the standard, but in both cases NIST deferred to NSA requests to keep DUAL_EC…
at the time NIST had nobody on staff with expertise in elliptic curves.
NSA’s vastly superior expertise on elliptic curves led NIST to defer
to NSA regarding DUAL_EC, while NIST people spent more of their limited time on other parts of the standard that were closer to their expertise.
From Bart Preneel:
There is no doubt that the inclusion of Dual EC DRBG in SP 800-90A was a serious mistake…
The explanations provided by NIST are plausible, but it seems that not all decisions in the standardization process of SP 800-90A are properly documented; moreover, we did not have access to the source documents. This means that it is impossible to decide whether this mistake involved in addition to clever manipulation of the standards processes by NSA also some form of pressure on the technical and/or management staff of NIST. It is also not clear whether there would be any traces of such pressure in documents. Without access to the documents, it is also diffcult to decide whether or not NIST has deliberately weakened Dual EC DRBG…
However, it seems that NSA (with its dual role) seems to be prepared to weaken US government standards in order to facilitate its SIGINT role. This undermines the credibility of NIST and prevents NIST reaching its full potential in the area of cryptographic standards. In view of this, the interface between NSA and NIST and the role of the NSA should be made much more precise, requiring an update to the Memorandum of Understanding. At the very least, the terms “consult”, “coordination” and “work closely” should be clarified. Ideally, NIST should no longer be required to coordinate with NSA. There should be a public record of each input or comment by NSA on standards or guidelines under development by NIST.
From Ronald Rivest (the “R” in “RSA”):
Recent revelations and technical review support the hypothesis that, nonetheless, the NSA has been caught with “its hands in the cookie jar” with respect to the development of the Dual-EC-DRBG standard. It seems highly likely that this standard was designed by the NSA to explicitly leak users’ key information to the NSA (and to no one else). The Dual-EC-DRBG standard apparently (and I would suggest, almost certainly) contains a “back-door” enabling the NSA to have surreptitious access. The back-door is somewhat clever in that the standard is not designed to be “weak” (enabling other foreign adversaries to perhaps exploit the weakness as well) but “custom” (only the creator (NSA) of the magical P,Q parameters in the standard will have such access).
[Recommendation]
NIST (and the public) should know whether there are any other current NIST cryptographic standards that would not be acceptable as standards if everyone knew what the NSA knows about them. These standards should be identified and scheduled for early replacement. If NSA refuses to answer such an inquiry, then any standard developed with significant NSA input should be assumed to be “tainted,” unless it possesses a verifiable proof of security acceptable to the larger cryptographic community. Such tainted standards should be scheduled for early replacement.
One way this goes beyond the now-withdrawn NIST standard is that the committee also looked at other NIST current standards now in wide use, which in at least one other case depend upon a specific choice of elliptic curves made by the NSA, with no explanation provided of how the choice was made. In particular, Rivest recommends changing the ECDSA standard in FIPS186 because of this problem.
For a detailed outline of the history of the Dual-EC-DRBG standard, see here. Note in particular that this states that in 2004 when the author asked where the Dual-EC-DRBG elliptic curves came from, the response he got was “NSA had told not to talk about it.”
Also this week, the AMS Notices contains a piece by Richard George, a mathematician who worked at the NSA for 41 years before recently retiring. Presumably this was vetted by the NSA, and is a reasonably accurate version of the case they want to make to the public. Personally I’d describe the whole thing as outrageous, for a long list of reasons, but here I’ll just focus on what it says about Dual-EC-DRBG, since it now seems likely that it is all we will ever get from the NSA about this. It says:
I have never heard of any proven weakness in a cryptographic
algorithm that’s linked to NSA; just innuendo.
The reaction from a commenter here (publicly anonymous, but self-identified to me) was:
As a member of a standards committee involved the removal of the mentioned algorithm from a standard, none of the members believe the “innuendo” theory, and all believe it was deliberately weakened.
Read carefully (and I think it was written very carefully…), note that George never directly denies that the NSA back-doored Dual-EC-DRBG, just claims there is no “proven weakness”. In other words, since how they chose the elliptic curves is a classified secret, no one can prove anything about how this was done. All the public has is the Snowden documents which aren’t “proof”. This is highly reminiscent of the US government’s continuing success at keeping legal challenges to NSA actions out of the courts, even when what is at issue are actions that everyone agrees happened, on the grounds that plaintiff can’t “prove” that they happened, since they are classified. Snowden’s release of documents may yet allow some of these cases to come to a court, just as they were the one thing capable of getting the NIST to acknowledge the Dual-EC-DRBG problem.
I hope that there will be more response to the NSA issue from the Math community than there has been so far. In particular, Rivest’s call for the removal from NIST standards of material from the NSA which the NSA refuses to explain should be endorsed. The innuendo from George is that the NSA may be refusing to explain because they used superior technology to choose better, more secure elliptic curves. If this is the case I don’t see why an official statement to that effect, from the NSA director, under oath, cannot be provided.
On the many other issues the George article raises, I hope that the AMS Notices will see some appropriate responses in the future. Comments here should be restricted to the NIST/NSA story, with those from anyone knowledgeable about this story most encouraged.
Update: The NIST has made available on its website the materials provided to the panel looking into this.
One remarkable thing about the panel’s investigation is that the NSA evidently refused to participate, in particular refusing to make anyone available to answer questions at the panel’s main meeting on May 29 (see page 12 of the report). This appears to be in violation of the Memorandum of Understanding that governs the NIST/NSA relationship, which explicitly states that “The NSA shall … Be responsive to NIST requests for assistance including, but not limited to, all matters related to cryptographic algorithms and cryptographic techniques, information security, and cybersecurity.” All evidence I’ve seen is that the NSA sees itself as above any need to ever justify any of its actions. I can’t see any possible argument as to why they did not have an obligation to participate in the work of this committee.
Update: A new development in this story is a letter from Congressman Grayson to NSA Director Clapper asking exactly the right questions about what happened at the NIST. Will be interesting to see if a member of Congress can get anything out of the NSA beyond the usual stone-walling.
