The last few days have seen some new revelations about the NSA’s role in compromising NIST standard elliptic curve cryptography algorithms. Evidently this is an old story, going back to 2007, for details see Did NSA Put a Secret Backdoor in New Encryption Standard? from that period. One of the pieces of news from Snowden is that the answer to that question is yes (see here):
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 NIST has now, six years later, put out a Bulletin telling people not to use the compromised standard (known as Dual_EC_DRBG), and reopening for public comment draft publications that had already been reviewed last year. Speculation is that there are other ways in which NIST standard elliptic curve cryptography has been compromised by the NSA (see here for some details of the potential problems).
The NSA for years has been pushing this kind of cryptography (see here), and it seems unlikely that either they or the NIST will make public the details of which elliptic curve algorithms have been compromised and how (presumably the NIST people don’t know the details but do know who at the NSA does). How the security community and US technology companies deal with this mess will be interesting to follow, good sources of information are blogs by Bruce Schneier and Matthew Green (the latter recently experienced a short-lived fit of idiocy by Johns Hopkins administrators).
The mathematics being used here involves some very non-trivial number theory, and it’s an interesting question to ask how much more the NSA knows about this than the rest of the math community. Scott Aaronson has an excellent posting here about the theoretical computation complexity aspects, which he initially ended with advice from Bruce Schneier: “Trust the math.” He later updated the posting saying that after hearing from experts he had changed his mind a bit, and now realized there were more subtle ways in which the NSA could have made number-theoretic advances that could give them unexpected capabilities (beyond the back-doors inserted via the NIST).
Evidently the NSA spends about $440 million/year on cryptography research, about twice the total amount spent by the NSF on all forms of mathematics research. How much they’re getting for their money, and how deeply involved the mathematics research community is are interesting questions. Charles Seife, who worked for the NSA when he was a math major at Princeton, has a recent piece in Slate that asks: Mathematicians, why are you not speaking out?. It asks questions that deserve a lot more attention from the math community than they have gotten so far.
Knowledgeable comments about this are welcome, others and political rants are encouraged to find somewhere else. There’s a good piece on this at Slashdot…