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.
Pingback: Peter Woit: The NSA, NIST and the AMS | mathbabe
You admit that the AMS articles do not deny that the NSA could have a backdoor to DUAL_EC_DRBG. So maybe the NSA does have a backdoor, but the info is classified. The backdoor would not be a proven weakness unless the NSA leaked the data, or someone got it by solving a discrete log problem.
Why are you blaming the AMS? It is just reporting the different views on this subject. If you do not believe that we should have a military intelligence agency doing work like this, then complain to President Obama, not the AMS.
Roger,
I think all the evidence is that there is an NSA backdoor to this standard, and that Matthew Green is right: they’re not admitting this because they intend to keep compromising standards. If so, the two Notices pieces are intentionally misleading and the AMS is being used by the NSA to mislead the math community. This is not about “views on the subject”, it’s about what the facts of the matter are, and these are not letters to the editor, but refereed articles.
Even those who have no trouble with the NSA backdooring NIST standards should not be happy with the AMS being used this way.
“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”.
Well, I think that if and whenever such assurances will be given, you should not trust them very much.
I don’t understand what you consider misleading about Wertheimer’s statement. Is it that you feel the use of “discovered” in the clause “after security researchers discovered the potential for a trapdoor” suggests that this was the first discovery of that potential? To me it doesn’t suggest that. (For comparison, in his Notices article on this subject Hales refers to “the back door algorithm discovered by Ferguson and Shumow,” and he certainly doesn’t intend to suggest that NSA had previously been unaware of it. It would be overly fastidious to reply “No, NSA discovered it, while Ferguson and Shumow merely re-discovered it.”)
As I read it, Wertheimer’s statement seems clear and unambiguous. He says it was a mistake for NSA to continue supporting the algorithm once the public knew it had the potential for a back door. That may be a cynical or distasteful statement, but I’m not convinced it was intended to mislead anyone.
guest,
Maybe I’m not cynical enough, but I suspect that (assuming the backdoor) the reason Wertheimer does not address the P,Q issue is that an out and out bald-faced lie to the math community is beyond what he is willing to stomach (and that he has plenty of mathematician colleagues who also would not stomach this if it was done by someone speaking for them). Besides that, the Snowden (or other) documents may very well contain the details of what happened and this may someday come out, providing some incentive not to put your name to a public lie.
Anonymous,
Taken as a whole, the article basically claims to address in detail the controversial issue of the accusation that they backdoored a standard, while cynically evading ever actually addressing the issue. I don’t see any way to characterize this as other than misleading, and think it was a huge mistake by the AMS to allow this to appear in the Notices without requiring that the issue be addressed (even if by explicitly saying that the NSA refuses to answer the question).
Beyond the evasion of the central issue, there’s also a string of other misleading statements about the history of this issue, for the details of those, see Matthew Green’s account (his conclusion “could easily lead people to the wrong understanding” is a synonym for “misleading”).
Did you read the le Monde article? If the Wertheimer statement was not misleading, why are they reporting that the Wertheimer article admits the NSA backdoored the algorithm (when it carefully does no such thing?)
I still think that the way Wertheimer’s statement is written, he encourages the “we should have stopped this once we found out there was a problem” reading rather than the cynical “we should have stopped this once we were caught” reading (the French are cynics..) . The ambiguity is intentional, misleading and the AMS should not have allowed this to happen.
Why should anyone be surprised? If they are willing to backdoor to begin with, why would they not continue to try to mislead the public? The whole point of backdooring is to be able to monitor communications without people knowing it. Surely their opinions on this haven’t changed retroactively just because they got caught. So big surprise, he’s being shifty and evasive. But unintentionally he is just making things clearer than before. If he had nothing to hide, he’d lay the truth out.
The CIA has a long and well known history of infiltrating, directing, and manipulating media sources for their own ends. One might expect the editors of AMS Notices would be aware of this history and be cautious about allowing themselves to be used as a conduit for such disinformation.
http://en.wikipedia.org/wiki/Operation_Mockingbird
After 1953, the network was overseen by CIA Director Allen Dulles, by which time Operation Mockingbird had major influence over 25 newspapers and wire agencies. The usual methodology was placing reports developed from intelligence provided by the CIA to witting or unwitting reporters. Those reports would then be repeated or cited by the preceding reporters which in turn would then be cited throughout the media wire services. These networks were run by people with well-known liberal but pro-American big business and anti-Soviet views such as William S. Paley (CBS), Henry Luce (Time and Life Magazine), Arthur Hays Sulzberger (New York Times), Alfred Friendly (managing editor of the Washington Post), Jerry O’Leary (Washington Star), Hal Hendrix (Miami News), Barry Bingham, Sr. (Louisville Courier-Journal), James Copley (Copley News Services) and Joseph Harrison (Christian Science Monitor).[6]
http://en.wikipedia.org/wiki/CIA_influence_on_public_opinion
In 2012, Tricia Jenkins released a book, The CIA in Hollywood: How the Agency Shapes Film and Television, which further documents the CIA’s efforts at manipulating its public image through entertainment media from the 1990s to the present. The book explains that the CIA has used motion pictures to boost recruitment, mitigate public affairs disasters (like Aldrich Ames), bolster its own image, and even intimidate terrorists through disinformation campaigns. That same year CIA was portrayed by Aidan Gillen in the third installment of the Christopher Nolan’s Batman film series.
USA 2014
The CIA worked with prominent national security reporter Ken Dilanian while he published articles for the L.A. Times to secure positively written stories informed by CIA narrative. [36] Specifically, Dilanian sent full stories to the CIA before they were published on at least one occasion and on at least one other radically rewrote a story on the CIA’s urging. The CIA also encouraged a publication indicating few collateral deaths were associated with a strike from its controversial drone strike program in contradiction to eye witness testimony recorded by an Amnesty International investigation [37] and which also contradicts a documents obtained by a FOIA request indicating that acceptable numbers of collateral damage are pre-calculated for drone strike targets and while typically valued at around 10 innocent deaths can sometimes be significantly more. [38]
http://monthlyreview.org/1999/11/01/the-cia-and-the-cultural-cold-war-revisited/
U.S. and European anticommunist publications receiving direct or indirect funding included Partisan Review, Kenyon Review, New Leader, Encounter and many others. Among the intellectuals who were funded and promoted by the CIA were Irving Kristol, Melvin Lasky, Isaiah Berlin, Stephen Spender, Sidney Hook, Daniel Bell, Dwight MacDonald, Robert Lowell, Hannah Arendt, Mary McCarthy, and numerous others in the United States and Europe. In Europe, the CIA was particularly interested in and promoted the Democratic Left and ex-leftists, including Ignacio Silone, Stephen Spender, Arthur Koestler, Raymond Aron, Anthony Crosland, Michael Josselson, and George Orwell.
Just to be clear, you say you “think the AMS needs to immediately cut off its cooperative programs with the agency,” by this you mean that the funding program of the NSA/AMS
(for personal grants and optionally supporting a recipient’s graduate student) should be discontinued, right? It is probably unusual for the AMS to say that they want to stop a funding opportunity offered by a government office, turning down money on moral grounds.
Anonymous,
I don’t think any of this is relevant here (and I really don’t want to get involved in general discussion of the history of the activities of the CIA and NSA). In this case what is coming from the NSA is being published with their name on it, and to the extent it’s misleading, it is so not surreptitiously, but out in the open.
The relevant historical analogy though may be that in the DUAL_EC_DRBG case the NSA took advantage of the NIST and its cryptographers to put out bad crypto, here they’re taking advantage of the AMS and its editors to put out misleading information about the earlier NIST story. In the NIST case the problem was that NIST cryptographers didn’t push back when being used by the NSA, here it seems the editors didn’t push back.
Shannon,
If the NSA really is using the AMS to mislead the math community, all I’m saying is that an appropriate response would be for the AMS to withdraw from cooperation with them. This doesn’t mean shutting off the NSA grant system, it means the AMS should tell the NSA it doesn’t want to lend its name to this or to any longer play a role in their administration. As far as I can tell, currently the main AMS involvement in the grants is in choosing review panels, so de facto the main change would be that the AMS would tell the NSA they had to do this themselves (like the NSF and every other agency that provides research grants to mathematicians).
Presentation on the issue from 2007: “WHAT WE ARE SAYING: The prediction resistance of this PRNG (as presented in NIST SP800-90) is dependent on solving one instance of the elliptic curve discrete log problem. (And we do not know if the algorithm designer knew this before hand.)”
Blog post from a security blogger at the time: Even if no one knows the secret numbers, the fact that the backdoor is present makes Dual_EC_DRBG very fragile. If someone were to solve just one instance of the algorithm’s elliptic-curve problem, he would effectively have the keys to the kingdom. He could then use it for whatever nefarious purpose he wanted. Or he could publish his result, and render every implementation of the random-number generator completely insecure.
The Notices article now says at the top of the first page:
It’s psyops from the start. Deny, evade, use the spiral of silence and make sure all affiliated publications stay on message. The goal is to outlast first outrage, then interest, and finally memory. When you see articles proclaiming things like “This NSA backdoor conspiracy again”, you’ll know they’ve moved onto the final stage: Mockery, painting anyone still concerned as a tinfoil hatter to discourage inquiry.
Psyops is not about argument. It’s about “feels over reals”. In the absence of clear evidence, and open debate, its easy to turn people away or off with distraction, confusion, and ridicule. Over time, and in the absence of any kind of investigative media, it will eventually work.
Elliptic Curve cyptography is done. No-one can trust the NIST standards, possibly their research, and more importantly no-one can trust everyone to not be using those standards. This isn’t about trusting the mathematics, it’s about trusting the implementations. Thos have been compromised and short of a total worldwide agreement to adopt new, compromise-exclusionary ones, ECC is not going to be able to be trusted by anyone.
And we can’t have the agreement while the psy-ops campaign to shut down debate is in effect. RiP ECC.
Pingback: scientists/ mathematicians scrounge some spine against the @#%& NSA | Turing Machine
I don’t understand; or, rather, I think I do. This is a clash of cultures where there is an expectation that a mathematician is a mathematician is a mathematician, upholding certain ideals, wherever they happen to be sitting. This is an unreasonable expectation. The NSAs sole mandate is to intercept communications and decrypt them into plain text if needed. By definition it is their responsibility to facilitate, create, and guard backdoors an trapdoors in crypto when the opportunity arises. They are under no obligation to discuss it. People involved will be given National Security Letters (NSLs) and they will not be permitted to speak out it. However, it was total naivete to involve them from the get-go. Haranguing them for a mea culpa is a wast of time and is about as naive as the farmer wondering why that nice boy didn’t just east as much corn as he wanted.
Actually that is not their “sole mandate”. They are supposed to also be protecting
US government communications. By introducing a backdoor (and assuming noone else would figure it out) they have weakened their own communications.
Carey,
Like Wertheimer, you’re ignoring the main point here. It’s one thing for the NSA to act secretly and refuse to discuss it, that’s what they do. It’s quite another to instead go public, and do this by putting out misleading information via the the AMS.
I do think the AMS was naive here, with their conception that they are just hosting an exchange of people’s viewpoints, and thus trying to get the view of someone on the NSA side was important. The problem is that the Wertheimer article is instead essentially an official response from the US government about a matter of fact, the only time it has been willing to address this matter of fact. Presented with such a document, the AMS should have realized it was in danger of being used, and insisted that the Wertheimer article address clearly the question of the backdoor instead of misleading about it.
@tt: good point, they do have precisely that dual mandate. I misspoke.
@ Peter: I don’t think I am ignoring it. This was my point about the clash of cultures. Retired or not from NSA at the time of writing the piece, Wertheimer is a mathematician and, if you read some of his bio, pretty far from the stereotypical apparatchik. Maybe he just feels like discussing the issue with his peers. But, even if it was an intentional attempt to mislead the public, per your suggestion, so what? It seems to me that the issue was involving the NSA to begin with. I suppose I am not debating a fact but a matter of opinion. It doesn’t bother me that they aren’t coming clean or that they may be deliberately misleading the public. I expect that given their jobs, right or wrong. I do agree with you that the AMS has put itself in a funny spot by being a medium for the discussion.
Carey,
I think it wasn’t a mistake, but perfectly reasonable for the AMS to try and get a response from the NSA to the accusations about the backdoor. It’s surprising they did get a response (and no, given NSA security, I don’t think this came about because some guy just felt like talking about it, this was a policy decision, probably made at a very high level).
I seem to be less cynical than most people in that I’m surprised that someone at the NSA, given the chance to just say “no comment”, would instead decide to write an intentionally misleading public statement. My suspicion is that that’s not the way Wertheimer sees it, but that he’s so used to the point of view that outsiders have no right to know anything that he doesn’t realize what he is doing. It really was the job of the AMS to point it out to him and ask for either a real answer to the question or a clear statement that he wasn’t allowed to provide one.
Peter, even if Green is right that the NSA plans to continue nefarious spy schemes, I don’t see anyone being misled. As Fred points out, it has been known since 2007 that anyone with a solution to the EC discrete log problem can create a backdoor to the pseudorandom number generator, and that you can eliminate the problem by generating your own P and Q. The NSA is not saying whether it has that discrete log value or used it to spy on anyone.
I am not sure why it matters that the NSA spell this out for you. If you are concerned that the NSA is spying on your random numbers, then I suggest using your own P and Q or another generator, regardless of what the NSA says. You seem to think that the AMS needs to get some assurances from the NSA for you, but I do not see how any such assurances would do you any good.
Roger,
The record shows that the people at NIST were misled about this (see the report of their investigation). The assurances I think the AMS now needs from the NSA are about whether they’ve been used to mislead the math community. To all appearances, this is what has happened, so the NSA owes both the AMS and the math community an explanation.
Pingback: A Letter to the AMS | Not Even Wrong