Trust the math? An Update

Back in September, I wrote here about the news that Snowden’s revelations that confirmed suspicions that back in 2005-6 NSA mathematicians had compromised an NIST standard for elliptic-curve cryptography. The new standard was promoted as an improvement using sophisticated mathematical techniques, when these had really just been used to introduce a backdoor allowing the NSA to break encryption using this standard. There still does not seem to have been much discussion in the math community of the responsibility of mathematicians for this (although the AMS this month is running this opinion piece).

After my blog post, some nice detailed descriptions of how this was done and the mathematics involved appeared. See for instance The Many Flaws of Dual_EC_DRBG by Matthew Green, and The NSA back door to NIST by Thomas Hales. The Hales piece will appear soon in the AMS Notices. Hales also has a more recent piece, Formalizing NIST Standards, which argues for the use of formal verification methods to check such standards. Also appearing after my blog post was the news that RSA Security was now advising people not to use one of its products in default mode, the BSAFE toolkit.

One mystery that remained was why the NIST had promulgated a defective standard, knowing full well that experts were suspicious of it. Also unclear was why RSA Security would include a suspicious standard in their products. Back in September they told people that (see here) they had done this because:

The hope was that elliptic curve techniques—based as they are on number theory—would not suffer many of the same weaknesses as other techniques

and issued a statement saying:

RSA always acts in the best interest of its customers and under no circumstances does RSA design or enable any backdoors in our products. Decisions about the features and functionality of RSA products are our own.

Today there are new revelations about this (it’s unclear from what source), which explain what helped make RSA swallow the bogus mathematics: a payment from the NSA of $10 million. I guess there’s a lesson in this: when you can’t figure out why someone went along with a bad mathematical argument, maybe it’s because someone else gave them $10 million…

Update
: For another explanation of the math behind this, see videos here and here featuring Edward Frenkel.

Update: There’s a response to the Reuters story from RSA here. As I read it, it says

  • They do have a secret contract with the NSA that they cannot discuss
  • They used the NSA back-doored algorithm in their product because they trust the NSA
  • They didn’t remove it when it became known because they really are incompetent, not because the NSA was paying them to act incompetent

It’s hard to see why anyone would now trust their products.

This entry was posted in Uncategorized. Bookmark the permalink.

27 Responses to Trust the math? An Update

  1. Tinos says:

    Both bitcoin and PGP use elliptic curve cryptograpy. Lately, the exchange rate for bitcoin has been soaring. Do you have an opinion on whether or not it is really secure?

  2. S. Molnar says:

    $10 million is the corporate rate; it looks like $3 million may be the individual rate.

  3. Yatima says:

    Note that in this case we are talking about

    Dual Elliptic Curve Deterministic Random Bit Generator

    which are less random than thought. It is recommended to get random bits, including pseudorandom bits, from elsewhere.

    Elliptic Curve Cryptography is something else.

    And Bitcoin uses Hashcash, based on SHA-256, not Elliptic Curve Cryptography.

    See also: How the Bitcoin protocol actually works

  4. Peter Woit says:

    Tinos,
    Anyone looking for info on what cryptography to trust should be looking elsewhere than this blog, since I’m no expert. While trying to figure out what and who to trust, I’m just pointing out that now you have to realize that part of the math community and the main US standards organization have been actively trying to deceive you. And the main commercial cryptography company has been bought off to also try and deceive you. People in general, and mathematicians in particular, might want to think about whether something should be done…

  5. anon says:

    The RSA response is certainly ridiculous but now that I think about it actually, I don’t see anything necessarily wrong about mathematicians working on military projects of this sort. (And the behaviour of the NSA should not be unexpected; this is, after all, what they usually do.) Mathematicians have a long history of working in the defence industry. If I remember correctly, even Euler translated a treatise on ballistics. And of course, in more recent times, Ulam was involved in the design of the hydrogen bomb and nuclear pulse propulsion.

  6. Peter Woit says:

    anon,
    One can reasonably argue that mathematicians at the NSA who came up with this were just following orders, and that any at RSA who were encouraged to play dumb were also just following the policy of their employers. One can also argue that all of this is perfectly legal (although the fact that courts have been thwarted from ruling on whether these things violate the Bill of Rights may mean the legality issue is still up in the air).

    There remains the question though of what people in general should do in response to the NSA revelations, and of what the mathematics community in particular should do in response to the fact that mathematics and mathematicians have played a role in this. “Nothing” is one defensible position, as is Beilinson’s “treat the NSA the way mathematicians treated the KGB in the former Soviet Union”. In any case, I think there’s a strong argument for publicizing what is known about exactly what happened here so that people can make up their own minds about what they think about it.

  7. OMF says:

    Mathematicians have a long history of working in the defence industry. If I remember correctly, even Euler translated a treatise on ballistics.

    No. The situation that Mathematics finds itself in is completely unprecedented.

    The NSA is probably the world’s single largest employer of pure mathematicians. At ~1000 or so. Since there are about ~100,000 mathematicians in the world, this is a sizable enough fraction ~1% of the world’s quotient, to say nothing of the research funding and recruitment operations of the NSA outside of those in its direct employment. Within the US itself, the influence of the organisation is obviously even stronger.

    This bears many similarities towards the move in physics towards “Big Science” in the post war period, but also several key differences.

    Firstly, unlike big science, the developments at the NSA have been almost exclusively negative, socially, politically and scientifically. The mathematics employed there is being turned into a tool of oppression in a way that few scientific developments have even been so directly employed. Secondly, a large body of mathematicians are now engaged in research — and now we know in publishing research — that is deliberately incomplete and even deceitful. This second development is on a scale previously unheard of in this discipline.

    Finally, we may likely see a large political split developing in the mathematics community, centered around the cooperation of mathematicians with the NSA. Elements of this can be seen in the December issue of the AMS notices — Alexander Beilinson’s letter calling for the AMS to sever its NSA ties along with the conspicuous absence of the monthly NSA recruitment advertisement. Politics — real politics — has entered the mathematical community for the first time, the US community in particular, in a very direct and unavoidable way.

    Even in the Soviet Union, mathematics was in general an apolitical activity, and mathematicians were given considerable autonomy. However the recent NSA scandal has brought mathematics and its activities directly into the political spotlight, and these activities into question. The world may be facing a situation where certain types of mathematical research becomes restricted, or taboo, or boycotted. This would be an unprecedented development. From ancient times, mathematics has always been an international, collegial activity; outside the temporal and certainly the political sphere; No longer?

    The greatest irony in all of this is that the branch of mathematics involved — number theory — was only 50 years ago regarded as the most “pure”, abstract, and austere expression of the subject. The “Queen of Mathematics” in Gauss’ words. Now the Queen seems to have fallen in with a bad sort, and the scandal threatens to rock the entire Kingdom to its foundations.

  8. anon says:

    OMF,
    I completely disagree. We are entering a brave new world and we (including mathematicians) must embrace it or be left behind. It’s not only the NSA by the way, but also the IDA in Princeton and many other agencies. In any case, no one is forcing anyone to do research they are uncomfortable with, or that is “so harmful for the fabric of human society,” as Beilinson would put it. I seem to recall that one or two decades ago there was a controversy when it was discovered that some mathematicians were receiving military funding and an attempt was made to expose them. Even W. Browder, whose father I think was chairman of the Community Party of America, called it a witchhunt.

  9. anon says:

    I mean *Communist* Party of America.

  10. Peter Woit says:

    anon,
    I agree with you that we are entering a brave new world (Snowden did a lot to show how far we have gotten into this world already), but personally I don’t believe we should embrace it, quite the opposite.

  11. In my view, mathematicians should accept the vocation of developing protocols that are transparent, open to independent scrutiny, verifiable, and capable of replacing the protocols used by institutions that have shown they cannot be trusted.

    These should be developed for currency, telecommunications, networking, data storage, and voting.

    If such developments succeeded, they might replace existing protocols or, perhaps, keep them honest.

    If such developments do not succeed, there is an obvious danger that we will end up living in 1984 with no way out.

    Preliminary signposts for such protocols: PGP, Bitcoin, Tor.

  12. Wayne says:

    I’m afraid I’m unable to discern the correspondence between your latest update’s summary bullets about RSA, or any inference that can be drawn from their summary of 22 December, which supports the conclusions you draw. RSA states that their reliance was on the NIST, which aside from sharing two letters in its acronym has nothing in particular do with the NSA.

    Many — perhaps along with RSA itself — now wish something more than RSA’s trust in the NIST had been their guiding force in 2007. But if I am reading your latest addition correctly, I simply don’t follow the logic suggesting such a wish provides evidence of incompetence and a (company-denied) secret contract with the NSA?

    Wayne

  13. Jim Akerlund says:

    I am having a problem with separating the mathematicians involvement with the NSA and the NSA’s use of spycraft. It looks like this RSA story is the NSA’s use of spycraft. Reading Google’s and Yahoo’s interserver transmissions is more spycraft. True, mathematicians did create the eliptic curve pseudo random number generator, but where the problem seems to be occurring is the adoption of this number generator industry wide, which is out of the hands of mathematicians. I guess I am looking for the smoking gun that is in the mathematicians hands in this NSA mess.

  14. Peter Woit says:

    Wayne,
    The problems with this elliptic curves algorithm were publicized back in 2007, the question is why RSA kept this as the default in this particular product after that time. Their argument that they didn’t do this because they were paid off really only leaves true incompetence as an explanation (they were unaware of the claimed problem despite it being publicized, so incompetent at knowing their own field, or were aware of the claimed problem, but made the incompetent judgment that the claims were wrong).
    Their statement acknowledges their relationship to NSA, says they never “divulge details of customer engagements”. To me their denial seems carefully worded not to deny a contract with the NSA whose details they cannot divulge, just to deny a specific accusation about exactly what is in the contract.

    It’s quite true that the details of how the NSA corrupted the NIST approval process have still not been revealed. I don’t understand why this is the case if the NIST wants to regain any credibility for its cryptography standards.

  15. Peter Woit says:

    Jim Akerlund,
    I’m not well-informed about this, but I would assume there are mathematicians involved in the NIST standards approval process for a cryptographic standard based on this kind of mathematics. Similarly I would assume RSA Security employs mathematicians to evaluate such cryptographic algorithms. If neither organization uses mathematicians to make such evaluations, but just decides “oh, an NSA mathematician says everything is fine”, that would explain how this happened, but I’m finding it hard to believe these organizations operate in such an unprofessional manner.

  16. NotSuper says:

    Off topic, sorry, but this may be of interest for this blog:
    http://phys.org/news/2013-12-electron-shapeliness-supersymmetry.html

  17. milkshaken says:

    based on the Reuters article, by the time the 10million deal went down RSA was not doing any crypto research in house anymore (because their reorganized their research group out of existence) so they were eager to grab the NSA-supplied goodness, just to stay at the technology edge – They might have done it even without the cash… So this was not failure of math, just corporate culture as usual. More interesting would be to read about the NIST part of the story

  18. maqroll says:

    Trust the mathematicians (who work for the NSA)?
    ” requested removal of an NSA employee from an IETF group co-chairmanship”
    http://www.ietf.org/mail-archive/web/cfrg/current/msg03554.html
    (by way of Bruce Schneier’s blog https://www.schneier.com/blog/archives/2013/12/nsa_spying_who.html)
    I’m not a mathematician or cryptographer. I do not know whether or how/how much the particular algorithm/standard is important. Maybe not at all, maybe a lot. But the question is whether we can trust even mathematicians. Distrust of science & scientists is widespread – in many contexts (e.g., pharmaceuticals) scientists are seen as shills for the corporations that employ them. Naively, one might have thought mathematicians were immune to this sort of suspicion – after all they have to provide “proofs” don’t they?
    How should mathematicians who work (worked) for the NSA be treated? Ban them from at least positions of power on cryptographic standards bodies? Trust them, which becomes impossible in light of Snowden’s disclosures?

  19. Abraham Sternlieb says:

    Peter
    After reading all the above,it is not unreasonable to speculate that Milner Prizes represent a sofisticated endeavor by some unfriendly party to sabotage the USA physics community,by means of encouraging the brightest minds to go into unreasonably wasteful directions such as String Theory,thus diverting them from generating meaningful and useful science for the nation

  20. Falcon says:

    IMHO the amount of panic Snowden’s revelations have generated is becoming pathological. I find especially amusing comparisons with the USSR/KGB, not to mention Orwell’s Oceania. It is remarkable how before Snowden the unbearable involvement of the government in our personal lives went completely unnoticed. As someone originating from the USSR I assure you that we did not have the privilege of this blissful ignorance.

    What I find even more ridiculous is making the mathematicians employed by the NSA into some sort of villains, as if they are in any way responsible for the abuse or at least knowingly followed obviously foul orders. I don’t think that if the NSA and other defense related organizations consisted exclusively of Snowdens the nation would be better off.

  21. milkshaken says:

    the sad part is that what must have been a top management betrayal is going to affect all current and former RSA employees; it’s something bound to come up every time they apply for a job.

  22. paddy says:

    A somewhat on-topic news item: Crown Finally Pardons Alan Turing.

  23. Pingback: Trust the math? An Update | Not Even Wrong | CL...

  24. milkshaken says:

    Matthew Green fills in new background info on the NIST involvement (on his blog – a post written yesterday). Turns out, at least some cryptographers on the committee that helped to set the new standard knew about the backdoor right from the beginning – since January of 2005 – and they went along with it and kept quiet…

  25. werner says:

    It seems like it took less than two years for a couple of guys at MS to identify the weaknesses of this algorithm and warn against its use. The warnings were public and I suppose that anyone whose life or livelihood really depends on crypto would have learned of them quickly. If their trick couldn’t go unnoticed for two years, maybe all those NSA mathematicians aren’t THAT good after all…

  26. Peter Woit says:

    werner,
    Perhaps the point of this story is that the NSA mathematicians don’t need to be very good when others are being paid to look the other way.