Usually, when you hear about broken cryptography, it’s because of some sort of nonmathematical workaround to compromise supposedly encrypted traffic—like intercepting traffic during brief periods when it’s not encrypted, or stealing keys to decrypt it, or identifying code vulnerabilities such as Heartbleed. But a recent paper presented at the ACM Conference on Computer and Communications Security by researchers from the University of Michigan and several other institutions reveals that even the mathematics underlying a common protocol for exchanging cryptographic keys may be vulnerable—especially if the attackers have lots of resources.
The researchers focus on Diffie-Hellman key exchange, a method for two parties to securely share a cryptographic key that was first published in 1976 and is widely used. “Diffie-Hellman is a cornerstone of modern cryptography used for [virtual private networks], HTTPS websites, email, and many other protocols,” two of the paper’s co-authors, Alex Halderman of the University of Michigan and Nadia Heninger of the University of Pennsylvania, wrote on the Freedom to Tinker blog. “We and many others have advocated [for it] as a defense against mass surveillance.” But thanks to advances in computing power and some weaknesses in implementation, it’s “less secure than widely believed,” according to their findings.
The first problem the researchers identify is that some implementations of Diffie-Hellman simply don’t require large enough prime numbers. If the protocol uses 512-bit primes, instead of the more common 1024-bit primes, then breaking it is “well within reach” of the capabilities of modern computation, the researchers write, adding that “two decades of algorithmic and computational improvements have significantly lowered the bar to attacks on such key sizes.”
The length of the prime number matters because it dictates how many different prime numbers an adversary has to test out to find the right one; larger primes mean more possible numbers to test, while shorter primes are less work to break.
But even the 1024-bit prime numbers that we have generally considered to be pretty safe—that is, pretty far beyond the capabilities of what computers can feasibly reverse-engineer—are not necessarily secure from nation-state actors, according to the researchers’ findings. According to the authors’ calculations, the hardware required to crack one of these numbers in one year would conceivably cost hundreds of millions of dollars.
As they point out, that’s not an unthinkable sum of money for an organization like the NSA to spend on decryption efforts. (Some outlets are interpreting the research as suggesting that the NSA may have already done this, but the researchers don’t go that far, saying only that their results suggest it is “plausibly within NSA’s resources” to have broken some 1024-bit Diffie-Hellman.) And given how often the same fixed or standardized 1024-bit groups are reused, the payoff could be huge. Just one of these yearlong calculations costing hundreds of million of dollars could be enough to allow for decryption of 18 percent of popular (that is, within Alexa’s top million) HTTPS sites. A second calculation would further enable decryption of traffic on other Internet protocols—including two-thirds of IPSec virtual private networks and more than one-quarter of SSH servers. (For more detail on the different Internet protocols, see this glossary from Cisco.) That’s a pretty considerable payoff for two years of computation.
Assuming you don’t run a server or develop software, there’s not a whole lot you can or should do about these findings beyond making sure that you’re using an up-to-date Web browser and VPN. Specifying key exchange protocols and the size of the prime numbers used by them is not typically something individual end-users are responsible for, though there are plenty of tools out there that can help you at least figure out how the software you use and the sites you visit measure up when it comes to cryptographic security.
These results are sobering, as the researchers point out, because they suggest that “one of the key recommendations from security experts in response to the threat of mass surveillance … may have actually reduced security for many hosts.” Now, of course, there are new recommendations in light of these findings—summarized by the Electronic Frontier Foundation, as well as the paper’s authors on their site. Furthermore, the paper notes that several technology companies that previously permitted the use of 512-bit primes in their browsers have already updated their products including Internet Explorer, Firefox, and Chrome to ensure that they no longer accept primes smaller than 1024 bits.
All the same, the research is a rather grim, if enlightening, reminder of how rapidly computational advancements can shift the landscape of what’s feasible, how completely practical implementation decisions can undermine mathematical theory, and how even security advice offered with the best of intentions can backfire.
