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…
Interesting to note how little things have changed from the time of the Church Committee. From page 2:
“At the same time, we must insist that these agencies operate strictly within the law. They were established to spy on foreign governments and to fend off foreign spies. We must know to what degree they have turned their techniques inward to spy on the American people instead. If such unlawful and improper conduct is not exposed and stopped, it could, in time, undermine the very foundations of freedom in our own land.
So the committee intends to hold public hearings, not only on the domestic abuses of the CIA, and the FBI, but on the improper activities of such other Government agencies as the Internal Revenue Service, the Post Office, and the National Security Agency.”
http://www2.gwu.edu/~nsarchiv/NSAEBB/NSAEBB58/RNCBW25.pdf
I think Benjamin Franklin said it most clearly:
“They who can give up essential liberty to obtain a little temporary safety, deserve neither liberty nor safety. ”
I believe we are well into the ‘deserve neither liberty nor safety’ side of things now. I don’t feel very safe, or liberated in light of the revelation of our government’s new homeland pastime. The Yahoo CEO is now saying they were basically threatened into submission. The silence on this issue is deafening because ‘speaking out’ as you put it is now a crime.
http://www.theguardian.com/technology/2013/sep/11/yahoo-ceo-mayer-jail-nsa-surveillance
Just a run of the mill ignoramus here, but I would be very surprised if any significant advances in number theory pertaining to crypto have been made secretly by the NSA. It is just hard to imagine, regardless of how much money they spent, that anyone could really develop in a vacuum like that. How many genuinely promising young mathematicians have “disappeared” to work exclusively for the NSA? And I don’t just mean “this kid might make a good grad student for that idea I had last year” promising, I mean Hardy promising if not Ramajunan promising. How many Terry Tao’s are whisked away each year by the NSA to push the field forward in secret? It seems far more likely that good old fashioned spycraft, politics and manipulation of standards bodies will be the way to compromise standards and institutions now and in the future, rather than fundamental mathematical research somehow pursued in secret rooms by nebulous “geniuses” who where somehow missed by the universities of the world for long enough to be hoovered up by the NSA.
Mathematicians who work for the NSA have blood on their hands just like those who used to work to build bombs. Let’s stop giving these funding hungry leeches respect and promotions. They are working to destroy what remains of democratic society.
crypting is peanuts compared to mapping out the social networks. And if the devices attached to providers are just splitting off the fiber, then they get all the raw stuff anyway. And now it is reported that Israel is getting raw feed – we don’t even know who gets to play with all this stuff.
I think it’s important to remember that what is being talked about here is not the NSA making some sort of mathematical leap which allows them to break encryption, but rather the NSA inserting weaknesses into the encryption scheme from the start. Certainly that would involve doing some tough math, but it’s a different sort of thing then breaking an existing encryption scheme. I doubt very seriously that the NSA has figured out how to factor large numbers in polynomial time. Anyone remember the movie “Sneakers?”
Joel,
The raw feed does you no good if it’s properly encrypted, that’s the whole point of https: You can protect yourself, use PGP for email, Tor to browse, etc. Any traffic you have with the web using https is safe (unless the NSA HAS figured out how to factor very large numbers in polynomial time :-), though of course anything password protected (like say your FB page) is hackable unless you’re very careful about passwords.
@Jeff M
nothing on your list is safe from the NSA.
PGP: It seems the NSA can break key up to length 2048 and most passwords are not very safe to begin with.
Tor: The NSA can do end-point correlation analysis and recently an FBI attack compromised a large number of exit nodes.
https/SSL was explicitly mentioned as one of the protocols undermined by NSA.
As for your FB password: The NSA does not even need it because the large US web companies cooperate with them anyways.
Joseph/Jeff M,
I think if you look into this carefully (and this is what Scott Aaronson started learning after his initial posting), you’ll find that the situation is much more complicated than you think. The problem is not as simple as “have NSA mathematicians made revolutionary advances such as polynomial time factoring?”. The implementation of standard encryption algorithms is quite a complicated story, and the possibility of NSA mathematical advances that exploit weaknesses in the implementations (either unintentionally there or introduced by the NSA through their abuse of the NIST processes) is very real.
For any particular encryption algorithm, the story of possible attacks on it can be quite complicated. One should also keep in mind that when you see “https”, telling you that some sort of encryption is going on, that doesn’t tell you which algorithm is being used. From experience, I can assure you that the question of configuring which SSL encryption algorithms are supported and used on a webserver is not a trivial one.
Peter et al
I’m sorry, I really doubt the NSA can break RSA if it’s properly done. There are hacks which attempt to get around the polynomial time problem, and as Peter points out https can mean different things, some of which are better than others. Passwords are very hackable, unless you’re very good about it, and as Wolfgang says Tor is only so good, it just means they have to spend a lot more time to get in, and odds are they can’t get nearly as much. That said, anything you do like that means the NSA has to devote much more time to you. Wolfgang, what’s your reference for the NSA being able to hack 2048 bits? That would seem to me to be too much…
@Jeff McGowan
Bruce Schneier, who has seen the Snowden documents, wrote on his blog:
“We’re already trying to phase out 1024-bit RSA keys in favor of 2048-bit keys. Perhaps we need to jump even further ahead and consider 3072-bit keys.”
He later published a new public key of length 4096.
Btw Symantec now owns PGP and is a company known to cooperate with the NSA.
If you use PGP you should use a program compiled from the original source with a compiler you fully trust.
Wolfgang, thanks, I’m going to have to look into this. And you’re right about PGP and sources,on the Mac at least you can just compile the GNU version yourself…
Spending money and employing mathmaticians is a good thing. Like all military and secret technology if they have come across some radical new math it will eventually become known to all and then all of us can benefit.
Pingback: A question of trust: Why the NSA revelations have the security industry in turmoil — Tech News and Analysis
Phil Zimmerman, who originated PGP cryptography, left the company when Symantec took over in 2010. Last year he founded a start-up to provide secure communication.
It is worth recalling that last month, he terminated the email component of his service because even he could not assure privacy in the existing legal and technological system.
It will take years at best before a legal and technological framework can be created in which realistic privacy will be possible, which is most likely to emerge from the open source world.
Zimmerman’s analog of Moore’s law: the ability of computers to track us doubles every eighteen months.
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.
When I got pulled into the military during the Vietnam War, I didn’t end up carrying a rifle through a rice paddy. Neither did a fellow soldier who had gotten drafted out of a highly ranked graduate program in mathematics.
According to the Mathematics Genealogy Project, he has written his thesis. I see nothing else definitive about him online.
No conclusion can be drawn from this single instance, but I wonder how many other mathematicians have, in a sense, gone missing.
Maybe some mathematicians were not visible long enough to go missing. If you’ve seen the film Zero Dark Thirty the fictional character Maya (a composite) is described as having been recruited out of high school. Whether this is believable or not I do not know; if so, the question arises: How could the talent spotters have found her? There are all manner of Math Camps and competitions (at least one of which if I recall correctly is openly sponsored by NSA) that might in principle identify very talented young people, and perhaps even provide tuition and mentoring in math, in exchange for national service for a period of 3 or 5 years. NSA made a half-hearted pass at me in college; I was doing physics, Russian, Greek and math. The chair of the Slavic Languages department told me (1973) about an exam I might want to take one Saturday, offered by NSA. I declined.
GCHQ like to use code cracking competitions to attract “curious, tenacious and creative candidates who have the intellectual ability, though not necessarily the practical experience or qualifications” They launched a new one yesterday see http://www.gchq.gov.uk/Press/Pages/solve-cyber-secret.aspx
This tactic may net some talented young mathematicians before they publish or start a doctorate.
SSL gets cracked by NSA through man-in-the middle type of attacks, by employing fake certificates – no nimble math magic there.
The NSA employs more mathematicians (between 10 and 20 000) than the rest of the world combined. It is also well known that the NSA knows more about number theory than the rest of the world combined.
The back doors in its algorithms are known in expert circles since more than a decade. They are used by European cryptography producers as sales argument to convince customers not to buy American cryptography products. And indeed, no European country does so, for any sensitive equipment (communications to embassies, military encryption). What the NSA does in return is also known since decades (hiring spies as technicians in these companies, etc).
The naiveté of the doubters here is appalling.
Peter,
In the interests of full disclosure, what has your brush been with the NSA, if one exists? I know sometimes you bring up math related subjects for the social relevance. Is that the reasaon your writing about this?
Apparently, getting recruited out of high school isn’t entirely unheard of.
http://www.forbes.com/sites/stevenbertoni/2011/09/21/sean-parker-agent-of-disruption/4/
Jim,
I’ve never had any contact with the NSA that I know of (although, from what one reads, presumably like everybody else I’ve had a large amount of contact with them that I don’t know about…). This posting was just meant to inform others about something that seems to me an issue that should be of general interest in the math and physics community.
I saw some place quote me as an “expert” on this, and I’d like to make clear that that is not at all the case. I know a little bit about the mathematics involved and about computer networks, but have no expertise on either topic.
Pingback: Bruce Schneier’s Bat Signal Alarms Internet Engineers | The Alphaville Herald
Pingback: Elliptical Training Secrets « Pink Iguana
Pingback: The Mess Arrives | davidenicholson
Pingback: Eschew Obfuscation » Reshared post from Able Lawrence:
Pingback: NSA-Skandale: So funktionieren Kryptografie-Hintertüren | TokNok Deutschland
“Meanwhile, over in Building 5300, the NSA succeeded in building an even faster supercomputer. “They made a big breakthrough,” says another former senior intelligence official, who helped oversee the program. The NSA’s machine was likely similar to the unclassified Jaguar, but it was much faster out of the gate, modified specifically for cryptanalysis and targeted against one or more specific algorithms, like the AES. In other words, they were moving from the research and development phase to actually attacking extremely difficult encryption systems. The code-breaking effort was up and running.
The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. “Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it,” he says. The reason? “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”
http://www.wired.com/threatlevel/2012/03/ff_nsadatacenter/all/
See this September 23 interview with Bruce Schneier in Technology Review: