Last week, I got an email from a journalist with the following inquiry. The recent Snowden revelations, which made public for the first time the US government’s “black budget,” contained the following enigmatic line from the Director of National Intelligence: “We are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” So, the journalist wanted to know, what could these “groundbreaking” capabilities be? And in particular, could he mean that the NSA was buying quantum computers from D-Wave, and using them to run Shor’s algorithm to break the RSA cryptosystem?
I replied that, yes, that’s “possible,” but only in the same sense that it’s “possible” that the NSA is using the Easter Bunny for the same purpose. (For one thing, D-Wave themselves have said repeatedly that they have no interest in Shor’s algorithm or factoring. Admittedly, I guess that’s what D-Wave would say, were they making deals with NSA on the sly! But it’s also what the Easter Bunny would say.) More generally, I said that if the open scientific world’s understanding is anywhere close to correct, then quantum computing might someday become a practical threat to cryptographic security, but it isn’t one yet.
That, of course, raised the extremely interesting question of what “groundbreaking capabilities” the Director of National Intelligence was referring to. I said my personal guess was that, with ~99% probability, he meant various implementation vulnerabilities and side-channel attacks—the sort of thing that we know has compromised deployed cryptosystems many times in the past, but where it’s very easy to believe that the NSA is ahead of the open world. With ~1% probability, I guessed, the NSA made some sort of big improvement in classical algorithms for factoring, discrete log, or other number-theoretic problems. (I would’ve guessed even less than 1% probability for the latter, before the recent breakthrough by Joux solving discrete log in fields of small characteristic in quasipolynomial time.)
Then, on Thursday, a big New York Times article appeared, based on 50,000 or so documents that Snowden leaked to the Guardian and that still aren’t public. (See also an important Guardian piece by security expert Bruce Schneier, and accompanying Q&A.) While a lot remains vague, there might be more public information right now about current NSA cryptanalytic capabilities than there’s ever been.
So, how did my uninformed, armchair guesses fare? It’s only halfway into the NYT article that we start getting some hints:
The files show that the agency is still stymied by some encryption, as Mr. Snowden suggested in a question-and-answer session on The Guardian’s Web site in June.
“Properly implemented strong crypto systems are one of the few things that you can rely on,” he said, though cautioning that the N.S.A. often bypasses the encryption altogether by targeting the computers at one end or the other and grabbing text before it is encrypted or after it is decrypted…
Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware…
Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.
Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members.
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.”
So, in pointing to implementation vulnerabilities as the most likely possibility for an NSA “breakthrough,” I might have actually erred a bit too far on the side of technological interestingness. It seems that a large part of what the NSA has been doing has simply been strong-arming Internet companies and standards bodies into giving it backdoors. To put it bluntly: sure, if it wants to, the NSA can probably read your email. But that isn’t mathematical cryptography’s fault—any more than it would be mathematical crypto’s fault if goons broke into your house and carted away your laptop. On the contrary, properly-implemented, backdoor-less strong crypto is something that apparently scares the NSA enough that they go to some lengths to keep it from being widely used.
I should add that, regardless of how NSA collects all the private information it does—by “beating crypto in a fair fight” (!) or, more likely, by exploiting backdoors that it itself installed—the mere fact that it collects so much is of course unsettling enough from a civil-liberties perspective. So I’m glad that the Snowden revelations have sparked a public debate in the US about how much surveillance we as a society want (i.e., “the balance between preventing 9/11 and preventing Orwell”), what safeguards are in place to prevent abuses, and whether those safeguards actually work. Such a public debate is essential if we’re serious about calling ourselves a democracy.
At the same time, to me, perhaps the most shocking feature of the Snowden revelations is just how unshocking they’ve been. So far, I haven’t seen anything that shows the extent of NSA’s surveillance to be greater than what I would’ve considered plausible a priori. Indeed, the following could serve as a one-sentence summary of what we’ve learned from Snowden:
Yes, the NSA is, in fact, doing the questionable things that anyone not living in a cave had long assumed they were doing—that assumption being so ingrained in nerd culture that countless jokes are based around it.
(Come to think of it, people living in caves might have been even more certain that the NSA was doing those things. Maybe that’s why they moved to caves.)
As many readers of this blog might know, Neal Koblitz—a respected mathematician and pioneer of elliptic curve cryptography, who has some ties to NSA—published a series of scathing articles, in the Notices of the American Mathematical Society and elsewhere, attacking the theoretical computer science approach to cryptography. Koblitz’s criticisms were varied and entertainingly-expressed: the computer scientists are too sloppy, deadline-driven, self-promoting, and corporate-influenced; overly trusting of so-called “security proofs” (a term they shouldn’t even use, given how many errors and exaggerated claims they make); absurdly overreliant on asymptotic analysis; “bodacious” in introducing dubious new hardness assumptions that they then declare to be “standard”; and woefully out of touch with cryptographic realities. Koblitz seemed to suggest that, rather than demanding the security reductions so beloved by theoretical computer scientists, people would do better to rest the security of their cryptosystems on two alternative pillars: first, standards set by organizations like the NSA with actual real-world experience; and second, the judgments of mathematicians with …taste and experience, who can just see what’s likely to be vulnerable and what isn’t.
Back in 2007, my mathematician friend Greg Kuperberg pointed out an irony to me: here we had a mathematician, lambasting computer scientists for trying to do for cryptography what mathematics itself has sought to do for everything since Euclid! That is, when you see an unruly mess of insights, related to each other in some tangled way, systematize and organize it. Turn the tangle into a hierarchical tree (or dag). Isolate the minimal assumptions (one-way functions? decisional Diffie-Hellman?) on which each conclusion can be based, and spell out all the logical steps needed to get from here to there—even if the steps seem obvious or boring. Any time anyone has tried to do that, it’s been easy for the natives of the unruly wilderness to laugh at the systematizing newcomers: the latter often know the terrain less well, and take ten times as long to reach conclusions that are ten times less interesting. And yet, in case after case, the clarity and rigor of the systematizing approach has eventually won out. So it seems weird for a mathematician, of all people, to bet against the systematizing approach when applied to cryptography.
The reason I’m dredging up this old dispute now, is that I think the recent NSA revelations might put it in a slightly new light. In his article—whose main purpose is to offer practical advice on how to safeguard one’s communications against eavesdropping by NSA or others—Bruce Schneier offers the following tip:
Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.
Here Schneier is pointing out a specific issue with ECC, which would be solved if we could “merely” ensure that NSA or other interested parties weren’t providing input into which elliptic curves to use. But I think there’s also a broader issue: that, in cryptography, it’s unwise to trust any standard because of the prestige, real-world experience, mathematical good taste, or whatever else of the people or organizations proposing it. What was long a plausible conjecture—that the NSA covertly influences cryptographic standards to give itself backdoors, and that otherwise-inexplicable vulnerabilities in deployed cryptosystems are sometimes there because the NSA wanted them there—now looks close to an established fact. In cryptography, then, it’s not just for idle academic reasons that you’d like a publicly-available trail of research papers and source code, open to criticism and improvement by anyone, that takes you all the way from the presumed hardness of an underlying mathematical problem to the security of your system under whichever class of attacks is relevant to you.
Schneier’s final piece of advice is this: “Trust the math. Encryption is your friend.”
“Trust the math.”On that note, here’s a slightly-embarrassing confession. When I’m watching a suspense movie (or a TV show like Homeland), and I reach one of those nail-biting scenes where the protagonist discovers that everything she ever believed is a lie, I sometimes mentally recite the proof of the Karp-Lipton Theorem. It always calms me down. Even if the entire universe turned out to be a cruel illusion, it would still be the case that NP ⊂ P/poly would collapse the polynomial hierarchy, and I can tell you exactly why. It would likewise be the case that you couldn’t break the GGM pseudorandom function without also breaking the underlying pseudorandom generator on which it’s based. Math could be defined as that which can still be trusted, even when you can’t Trust math—even (or especially) when you don’t trust anything else.
Log in
reply
