{"id":1517,"date":"2013-09-08T11:31:03","date_gmt":"2013-09-08T16:31:03","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1517"},"modified":"2017-01-12T12:31:14","modified_gmt":"2017-01-12T17:31:14","slug":"nsa-possibly-breaking-us-laws-but-still-bound-by-laws-of-computational-complexity","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1517","title":{"rendered":"NSA: Possibly breaking US laws, but still bound by laws of computational complexity"},"content":{"rendered":"

Update (Sept. 9):<\/strong><\/span> Reading more about these things, and talking to friends who are experts in applied cryptography, has caused me to do the unthinkable, and change my mind<\/em> somewhat.\u00a0 I now feel that, while the views expressed in this post were OK as far as they went, they failed to do justice to the … complexity<\/em> (har, har) of what’s at stake.\u00a0 Most importantly, I didn’t clearly explain that there’s an enormous continuum between, on the one hand, a full break of RSA or Diffie-Hellman (which still seems extremely unlikely to me), and on the other, “pure side-channel attacks” involving no new cryptanalytic ideas.\u00a0 Along that continuum, there are many plausible places where the NSA might be.\u00a0 For example, imagine that they had a combination of side-channel attacks, novel algorithmic advances, and<\/em> sheer computing power that enabled them to factor, let’s say, ten 2048-bit RSA keys every year.\u00a0 In such a case, it would still make perfect sense that they’d want to insert backdoors into software, sneak vulnerabilities into the standards, and do whatever else it took to minimize their need to resort to such expensive attacks.\u00a0 But the possibility of number-theoretic advances well beyond what the open world knows certainly wouldn’t be ruled out.\u00a0 Also, as Schneier has emphasized, the fact that NSA has been aggressively pushing elliptic-curve cryptography in recent years invites the obvious speculation that they know something<\/em> about ECC that the rest of us don’t.<\/p>\n

And that brings me to a final irony in this story.\u00a0 When a simpleminded complexity theorist like me hears his crypto friends going on and on about the latest clever attack that still requires exponential time, but that puts some of the keys in current use just within reach<\/em> of gigantic computing clusters, his first instinct is to pound the table and shout: “well then, so why not just increase all your key sizes by a factor of ten?\u00a0 Sweet Jesus, the asymptotics are on your side!\u00a0 if you saw a killer attack dog on a leash, would you position yourself just outside<\/em> what you guesstimated to be the leash’s radius?\u00a0 why not walk a mile away, if you can?”\u00a0 The crypto experts invariably reply that it’s a lot more complicated than I realize, because standards, and efficiency, and smartphones … and before long I give up and admit that I’m way out of my depth.<\/p>\n

So it’s amusing that one obvious response to the recent NSA revelations—a response that sufficiently-paranoid people, organizations, and governments might well actually take, in practice—precisely matches the na\u00efve complexity-theorist intuition.\u00a0 Just increase the damn key sizes by a factor of ten (or whatever).<\/p>\n

Another Update (Sept. 20):<\/strong><\/span> In my original posting, I should also have linked to Matthew Green’s excellent post<\/a>.\u00a0 My bad.<\/p>\n

\n

Last week, I got an email from a journalist with the following inquiry.\u00a0 The recent Snowden revelations<\/a>, 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.”\u00a0 So, the journalist wanted to know, what could these “groundbreaking” capabilities be?\u00a0 And in particular, was it possible that the NSA was buying quantum computers from D-Wave, and using them to run Shor’s algorithm to break the RSA cryptosystem?<\/p>\n

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.\u00a0 (For one thing, D-Wave themselves have said repeatedly that they have no interest in Shor’s algorithm or factoring.\u00a0 Admittedly, I guess that’s what D-Wave would<\/em> say, were they making deals with NSA on the sly!\u00a0 But it’s also what the Easter Bunny would say.)\u00a0 More generally, I said that if the open scientific world’s understanding is anywhere close to correct, then quantum computing might someday<\/em> become a practical threat to cryptographic security, but it isn’t one yet.<\/p>\n

That, of course, raised the extremely interesting question of what “groundbreaking capabilities” the Director of National Intelligence was<\/em> referring to.\u00a0 I said my personal guess was that,\u00a0with ~99% probability, he meant various implementation vulnerabilities and side-channel attacks—the sort of thing that we know<\/em> 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.\u00a0 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.\u00a0 (I would’ve guessed even less than 1% probability for the latter, before the recent breakthrough by Joux<\/a> solving discrete log in fields of small characteristic in quasipolynomial time.)<\/p>\n

Then, on Thursday, a big New York Times<\/em> article<\/a> appeared, based on 50,000 or so documents that Snowden leaked to the Guardian<\/em> and that still aren’t public.\u00a0 (See also an important Guardian<\/em> piece<\/a> by security expert Bruce Schneier, and accompanying Q&A<\/a>.)\u00a0 While a lot remains vague, there might be more public information right now about current NSA cryptanalytic capabilities than there’s ever been.<\/p>\n

So, how did my uninformed, armchair guesses fare?\u00a0 It’s only halfway into the NYT article that we start getting some hints:<\/p>\n

The files show that the agency is still stymied by some encryption, as Mr. Snowden suggested in a question-and-answer session<\/a> on The Guardian\u2019s Web site in June.<\/p>\n

\u201cProperly implemented strong crypto systems are one of the few things that you can rely on,\u201d 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…<\/p>\n

Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency\u2019s success depends on working with Internet companies \u2014 by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware…<\/p>\n

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency\u2019s 2013 budget request was to \u201cinfluence policies, standards and specifications for commercial public key technologies,\u201d the most common encryption method.<\/p>\n

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.<\/p>\n

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 \u201ca challenge in finesse.\u201d<\/p>\n

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.\u00a0 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.\u00a0 To put it bluntly: sure, if it wants to, the NSA can probably read your email.\u00a0 But that isn’t mathematical cryptography’s fault<\/em>—any more than it would be mathematical crypto’s fault if goons broke into your house and carted away your laptop.\u00a0 On the contrary, properly-implemented, backdoor-less strong crypto is something that apparently scares<\/em> the NSA enough that they go to some lengths to keep it from being widely used.<\/p>\n

I should add that, regardless of how<\/em> 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<\/em> that it collects so much is of course unsettling enough from a civil-liberties perspective.\u00a0 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.\u00a0 Such a public debate is essential if we’re serious about calling ourselves a democracy.<\/p>\n

At the same time, to me, perhaps the most shocking feature of the Snowden revelations is just how un<\/em>shocking they’ve been.\u00a0 So far, I haven’t seen anything that shows the extent of NSA’s surveillance to be greater<\/em> than what I would’ve considered plausible a priori<\/em>.\u00a0 Indeed, the following could serve as a one-sentence summary of what we’ve learned from Snowden:<\/p>\n

Yes, the NSA is<\/em>, 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.<\/p>\n

(Come to think of it, people living in caves might have been even more<\/em> certain that the NSA was doing those things.\u00a0 Maybe that’s why they moved to caves.)<\/p>\n

So, rather than dwelling on civil liberties, national security, yadda yadda yadda, let me move on to discuss the implications of the Snowden revelations for something that really<\/em> matters: a 6-year-old storm in theoretical computer science’s academic teacup.\u00a0 As many readers of this blog might know, Neal Koblitz—a respected mathematician and pioneer of elliptic curve cryptography, who (from numerous allusions in his writings) appears to have some connections at the NSA<\/del> (on reflection, this is unfair to Koblitz; he does report\u00a0conversations with NSA people in his writings, but has never had any financial connection with NSA)—published a series of scathing<\/a> articles<\/a>, in the Notices of the American Mathematical Society<\/em> and elsewhere, attacking the theoretical computer science approach to cryptography.\u00a0 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.\u00a0 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 …\u00a0taste<\/em> and experience<\/em>, who can just see<\/em> what’s likely to be vulnerable and what isn’t.<\/p>\n

Back in 2007, my mathematician friend Greg Kuperberg pointed out the 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<\/em> since Euclid!\u00a0 That is, when you see an unruly mess of insights, related to each other in some tangled way, systematize and organize it.\u00a0 Turn the tangle into a hierarchical tree (or dag).\u00a0 Isolate the minimal<\/em> assumptions (one-way functions?\u00a0 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.\u00a0 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.\u00a0 And yet, in case after case, the clarity and rigor of the systematizing approach has eventually won out.\u00a0 So it seems weird for a mathematician, of all people, to bet against the systematizing approach when applied to cryptography.<\/p>\n

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.\u00a0 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:<\/p>\n

Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.<\/p>\n

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.\u00a0 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<\/em> of the people or organizations proposing it.\u00a0 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<\/em> them there—now looks close to an established fact.\u00a0 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.<\/p>\n

Schneier’s final piece of advice is this: “Trust the math.\u00a0 Encryption is your friend.”<\/p>\n

“Trust the math.”<\/em>\u00a0 On that note, here’s a slightly-embarrassing confession.\u00a0 When I’m watching a suspense movie (or a TV show like Homeland<\/em>), 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.\u00a0 It always calms me down.\u00a0 Even if the entire universe turned out to be a cruel illusion, it would still be the case that NP \u2282 P\/poly would collapse the polynomial hierarchy, and I can tell you exactly why.\u00a0 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.\u00a0 Math could be defined<\/em> as that which can still be trusted, even when you can’t trust anything else.<\/p>\n","protected":false},"excerpt":{"rendered":"

Update (Sept. 9): Reading more about these things, and talking to friends who are experts in applied cryptography, has caused me to do the unthinkable, and change my mind somewhat.\u00a0 I now feel that, while the views expressed in this post were OK as far as they went, they failed to do justice to the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5,11],"tags":[],"class_list":["post-1517","post","type-post","status-publish","format-standard","hentry","category-complexity","category-nerd-interest"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1517","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1517"}],"version-history":[{"count":17,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1517\/revisions"}],"predecessor-version":[{"id":2305,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1517\/revisions\/2305"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}