{"id":2293,"date":"2015-05-22T21:41:23","date_gmt":"2015-05-23T01:41:23","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2293"},"modified":"2017-01-12T16:30:00","modified_gmt":"2017-01-12T21:30:00","slug":"nsa-in-ppoly-the-power-of-precomputation","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2293","title":{"rendered":"NSA in P\/poly: The Power of Precomputation"},"content":{"rendered":"

Even after the Snowden revelations, there remained at least one big mystery about what the NSA was doing and how. \u00a0The NSA’s classified 2013 budget request mentioned, as a priority item,\u00a0“groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” \u00a0There was a requested increase, of several hundred million dollars, for “cryptanalytic IT services” and “cryptanalysis and exploitation services program C” (whatever that was). \u00a0And a classified presentation slide showed encrypted data being passed to a high-performance computing system called “TURMOIL,” and decrypts coming out. \u00a0But whatever was going on inside TURMOIL\u00a0seemed to be secret even within<\/em> NSA; someone at\u00a0Snowden’s level wouldn’t have had access\u00a0to the\u00a0details.<\/p>\n

So, what was (or is) inside the NSA’s cryptanalytic black box? \u00a0A quantum computer? \u00a0Maybe even one that they bought from D-Wave? \u00a0(Rimshot.) \u00a0A fast classical factoring algorithm? \u00a0A proof of P=NP? \u00a0Commentators on the Internet rushed to suggest each of these far-reaching possibilities. \u00a0Some of us tried to\u00a0pour cold water<\/a> on these speculations—pointing out that one could envision\u00a0many\u00a0scenarios\u00a0that were a little\u00a0more prosaic, a little more tied to the details of how public-key crypto is actually used in the real world. \u00a0Were we just na\u00efve?<\/p>\n

This week, a\u00a0new bombshell 14-author paper<\/a>\u00a0(see also the website<\/a>) advances an exceedingly plausible hypothesis about what may<\/em> have been\u00a0the NSA’s greatest\u00a0cryptanalytic secret of recent years. \u00a0One of the authors is J. Alex Halderman<\/a> of the University of Michigan, my\u00a0best friend since junior high school, who I’ve blogged about<\/a> before<\/a>. \u00a0Because of that,\u00a0I had some advance knowledge\u00a0of this scoop, and found myself having to do what regular Shtetl-Optimized<\/em> readers will know is the single hardest thing in the world for me: bite my tongue and not say\u00a0anything.<\/em> \u00a0Until now, that is.<\/p>\n

Besides Alex, the other authors are\u00a0David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green,\u00a0Nadia Heninger, Drew Springall, Emmanuel Thom\u00e9, Luke Valenta,\u00a0Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-B\u00e9guelink, and Paul Zimmermann (two of these, Green and Heninger, have previously turned up on Shtetl-Optimized<\/em>).<\/p>\n

These authors study vulnerabilities in Diffie-Hellman key exchange<\/a>, the\u00a0“original” (but still widely-used) public-key cryptosystem, the one that predates even RSA. \u00a0Diffie-Hellman is the thing where Alice and Bob first agree on a huge prime number p<\/em> and a number g<\/em>, then Alice picks a secret a<\/em> and sends Bob ga<\/sup><\/em> (mod p<\/em>), and Bob picks a secret b<\/em> and sends Alice gb<\/sup><\/em> (mod p<\/em>), and then Alice and Bob\u00a0can both compute (ga<\/sup><\/em>)b<\/sup><\/em>=(gb<\/sup><\/em>)a<\/sup><\/em>=gab<\/sup><\/em> (mod p<\/em>), but an eavesdropper who’s listening in only knows p<\/em>, g<\/em>, ga<\/sup><\/em> (mod p<\/em>), and gb<\/sup><\/em> (mod p<\/em>), and one can plausibly conjecture that it’s hard from those things alone to get gab<\/sup><\/em> (mod p<\/em>). \u00a0So then Alice and Bob share a secret unknown to the eavesdropper, which they didn’t before, and they can use that secret to start doing cryptography.<\/p>\n

As far as anyone knows today, the best\u00a0way to break Diffie-Hellman is simply by calculating discrete logarithms: that is, solving the problem of recovering a<\/em> given only g<\/em> and h<\/em>=ga<\/sup><\/em> (mod p<\/em>). \u00a0At least on a classical computer, the fastest known algorithm for discrete logarithms (over fields of prime order) is the number field sieve (NFS). \u00a0Under plausible conjectures about the distribution of “smooth” numbers, NFS uses time that grows like exp((1.923+o(1))(log p<\/em>)1\/3<\/sup>(log log p<\/em>)2\/3<\/sup>), where the exp and logs are base e<\/em> (and yes, even the lower-order stuff like (log log p<\/em>)2\/3<\/sup>\u00a0makes a big difference in practice). \u00a0Of course, once you know the running time of the best-known algorithm, you can then try to choose a key size (that is, a value of log(p<\/em>)) that’s out of reach for that algorithm on the computing hardware of today.<\/p>\n

(Note that the recent breakthrough<\/a> of Antoine Joux, solving discrete log in quasipolynomial time in fields of small characteristic, also relied heavily on sieving\u00a0ideas. \u00a0But there are no improvements from this\u00a0yet for the “original” discrete log problem, over prime fields.)<\/p>\n

But there’s one\u00a0crucial further fact, which has been understood\u00a0for at least a decade by theoretical cryptographers, but somehow was slow to\u00a0filter out to the people who deploy\u00a0practical cryptosystems. \u00a0The further fact is that in NFS, you can arrange things so that almost all the discrete-logging effort\u00a0depends only on the prime number p, and not at all on the specific numbers g and h for which you’re trying to take\u00a0the discrete log<\/em>. \u00a0After this initial “precomputation” step, you then have a massive database\u00a0that you can use to speed up the “descent” step: the step of solving ga<\/sup><\/em>=h<\/em> (mod p<\/em>), for any\u00a0(g<\/em>,h<\/em>) pair that you want.<\/p>\n

It’s a little like the complexity class P\/poly<\/a>, where a single, hard-to-compute “advice string” unlocks exponentially many inputs once you have it. \u00a0(Or\u00a0a bit more precisely, one could say that NFS reveals\u00a0that exponentiation modulo a prime number is sort of<\/em>\u00a0a trapdoor one-way function<\/a>, except that the trapdoor information is subexponential-size, and given the trapdoor, inverting the function is still\u00a0subexponential-time, but a milder subexponential than before.)<\/p>\n

The kicker is that,\u00a0in practice, a large percentage of all clients and servers that\u00a0use Diffie-Hellman key exchange use the same few prime numbers p<\/em>. \u00a0This means that, if you wanted to decrypt a large fraction of all the traffic encrypted with Diffie-Hellman, you wouldn’t need\u00a0to do NFS over and over: you could just do it for a few p<\/em>‘s and cache the results. \u00a0This fact can singlehandedly change the outlook for\u00a0breaking Diffie-Hellman.<\/p>\n

The story is different depending on the key size, log(p<\/em>). \u00a0In the 1990s, the US government insisted on “export-grade” cryptography for products sold overseas (what a quaint concept!), which meant that the key size was restricted to 512 bits. \u00a0For 512-bit keys, Adrian et al. were able to implement NFS and use it to do the precomputation\u00a0step in about 7 days on a cluster with a few thousand cores. \u00a0After this initial precomputation step (which produced 2.5GB of data), doing the descent, to find the discrete log for a specific (g<\/em>,h<\/em>) pair, took only about 90 seconds on a 24-core machine.<\/p>\n

OK, but no one still<\/em> uses 512-bit keys, do they? \u00a0The first part of Adrian et al.’s paper demonstrates\u00a0that, because of implementation issues, even today you can force many servers to “downgrade” to the 512-bit, export-grade keys—and then, having done so, you can stall for time for 90 seconds as you figure out the session key, and then do a man-in-the-middle attack and take over and impersonate the server. \u00a0It’s an impressive example of the sort of game computer security researchers have been playing for a long time—but it’s really just a warmup to the main act.<\/p>\n

As you’d expect, many servers today are configured more intelligently, and will only agree to 1024-bit keys. \u00a0But even there, Adrian et al. found that a large fraction of servers\u00a0rely on just a single 1024-bit prime (!), and many of the ones that don’t rely on just a few other primes. \u00a0Adrian et al. estimate that, for a single 1024-bit prime, doing the NFS precomputation would take about 45 million years using a single core—or to put it more ominously, 1 year using 45 million cores. \u00a0If you built special-purpose hardware, that could go down by almost two orders of magnitude, putting the monetary cost at a few hundred million dollars, completely within the reach of a sufficiently determined nation-state. \u00a0Once the precomputation was done, and the terabytes\u00a0of output stored in a data center somewhere, computing a particular discrete log would then take about 30 days using 1 core, or mere minutes using a supercomputer. \u00a0Once again, none of this is assuming any algorithmic advances beyond what’s publicly known. \u00a0(Of course, it’s possible that the NSA also<\/em> has some algorithmic advances; even modest ones could obviate the need for special-purpose hardware.)<\/p>\n

While writing this post, I did my own back-of-the-envelope, and got that using NFS, calculating\u00a0a 1024-bit discrete log should be about\u00a07.5 million times harder than calculating\u00a0a 512-bit discrete log. \u00a0So, extrapolating from the 7 days it took Adrian et al.\u00a0to do it for 512 bits, this suggests that it might’ve\u00a0taken them about\u00a0143,840 years to calculate\u00a01024-bit discrete logs with the few thousand\u00a0cores\u00a0they had, or 1 year if they had 143,840 times as many cores\u00a0(since almost all this stuff is extremely parallelizable). \u00a0Adrian et al. mention optimizations that they expect would improve this by a factor of 3,\u00a0giving us about 100 million core-years, very\u00a0similar to\u00a0Adrian et al.’s\u00a0estimate of 45 million core-years (the lower-order terms in the running time of NFS might account for some of the remaining discrepancy).<\/p>\n

Adrian et al. mount a detailed argument in their paper that all\u00a0of the details about NSA’s “groundbreaking cryptanalytic capabilities” that we learned from the Snowden documents match what would<\/em>\u00a0be true if the NSA were doing something like the above. \u00a0The way Alex put it to me is that, sure, the NSA might not have been doing this, but if not, then he would like\u00a0to\u00a0understand why<\/em> not—for it would’ve been completely\u00a0feasible within the cryptanalytic budget they had, and the NSA would’ve known that, and it would’ve been a\u00a0very good\u00a0codebreaking value for the money.<\/p>\n

Now that we know about this weakness of Diffie-Hellman key exchange, what can be done?<\/p>\n

The most obvious solution—but a good one!—is just to use longer keys. \u00a0For decades, when applied cryptographers would announce some attack like this, theorists like me would say with exasperation: “dude, why don’t you fix\u00a0all<\/em> these problems in one stroke by\u00a0just, like, increasing the key sizes by a\u00a0factor of 10? \u00a0when it’s an exponential against a polynomial, we all know the exponential\u00a0will win eventually, so why not just go out to where it does?” \u00a0The applied cryptographers explain to us, with equal exasperation in their voices, that there are all sorts of reasons why not, from efficiency to\u00a0(maybe the biggest thing) backwards-compatibility.<\/em>\u00a0 You can’t unilaterally demand 2048-bit keys, if millions of your customers are using browsers that only understand\u00a01024-bit keys. \u00a0On the other hand, given the new revelations, it looks like there really will be\u00a0a big\u00a0push\u00a0to migrate to larger key sizes, as the theorists would’ve suggested from their ivory towers.<\/p>\n

A second, equally-obvious solution is to stop relying so much on the same few prime numbers<\/em> in Diffie-Hellman key exchange. \u00a0(Note that the reason RSA isn’t vulnerable to this particular attack is that it inherently requires a different composite number N<\/em> for each public key.) \u00a0In practice, generating a new huge\u00a0random prime number tends to be expensive—taking, say, a few minutes—which is why people so often rely on “standard” primes. \u00a0At the least, we could use\u00a0libraries of millions of “safe” primes, from which a prime for a given session is\u00a0chosen randomly.<\/p>\n

A third\u00a0solution is to migrate to elliptic-curve cryptography<\/a> (ECC), which as far as anyone knows today, is much less vulnerable to descent attacks than the original Diffie-Hellman scheme. \u00a0Alas, there’s been a lot of understandable distrust of ECC after the DUAL_EC_DBRG<\/a> scandal, in which it came out\u00a0that the NSA backdoored some of NIST’s elliptic-curve-based\u00a0pseudorandom generators by choosing particular parameters\u00a0that it knew how handle. \u00a0But maybe the right lesson to draw is mod-p\u00a0groups and elliptic-curve groups\u00a0both<\/em>\u00a0seem to be pretty good for cryptography, but the mod-p groups are less good if everyone is using the same few prime numbers p (and<\/em>\u00a0those primes are “within nation-state range”), and the elliptic-curve groups are less good if everyone is using the same few parameters. \u00a0(A lot of these things do seem pretty\u00a0predictable\u00a0with hindsight, but how many did you<\/em> predict?)<\/p>\n

Many people will use this paper to ask political questions, like: hasn’t the NSA’s codebreaking mission once again usurped\u00a0its mission to ensure the nation’s information security? \u00a0Doesn’t the 512-bit vulnerability that many Diffie-Hellman implementations still face, as a holdover from the 1990s export rules, illustrate why\u00a0encryption should never\u00a0be deliberately weakened for purposes of “national security”? \u00a0How can we get over the issue of backwards-compatibility, and get everyone using strong crypto? \u00a0People absolutely should be asking such\u00a0questions.<\/p>\n

But for\u00a0readers of this blog, there’s one question that probably looms even larger than those of freedom versus security, openness versus secrecy, etc.: namely, the question of theory versus practice. \u00a0Which “side” should be said to have “won” this round? \u00a0Some will say: those useless theoretical cryptographers, they didn’t even know how their coveted Diffie-Hellman system could be broken in the real world! \u00a0The theoretical cryptographers might reply: of course<\/em>\u00a0we\u00a0knew about the ability to do precomputation with NFS! \u00a0This wasn’t some NSA secret; it’s something we discussed openly for years. \u00a0And if someone told us\u00a0how Diffie-Hellman\u00a0was actually being used (with much of the\u00a0world relying on the same few primes), we could’ve immediately spotted\u00a0the potential for such an attack. \u00a0To which others might reply: then why didn’t you spot it?<\/p>\n

Perhaps the right lesson to draw is how silly such debates really are. \u00a0In the end, piecing this story together\u00a0took a team that was willing to do everything from learning some fairly difficult number theory to\u00a0coding up\u00a0simulations\u00a0to\u00a0poring over the Snowden documents for clues about the NSA’s budget. \u00a0Clear thought doesn’t respect the boundaries between disciplines, or between theory and practice.<\/p>\n

(Thanks very much to Nadia Heninger and Neal Koblitz for reading this post and correcting a few errors in it. \u00a0For more about this, see Bruce Schneier’s post<\/a>\u00a0or Matt Green’s post<\/a>.)<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Even after the Snowden revelations, there remained at least one big mystery about what the NSA was doing and how. \u00a0The NSA’s classified 2013 budget request mentioned, as a priority item,\u00a0“groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” \u00a0There was a requested increase, of several hundred million dollars, for “cryptanalytic IT services” […]<\/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-2293","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\/2293","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=2293"}],"version-history":[{"count":10,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2293\/revisions"}],"predecessor-version":[{"id":2306,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2293\/revisions\/2306"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}