Crypto experts speaking at the Black Hat USA 2013 conference yesterday said there's a real -- though perhaps not overwhelming -- possibility that much of the Internet's encryption will soon become completely unraveled. This grand unveiling of secrets, they contended, could arrive within a handful of years. To avoid what they jokingly called a "Cyber Pompei," they strongly encouraged a switch from algorithms based on the
All of a sudden RSA and Diffie-Hellman fall immediately all over the world.
chief technology officer, Artemis Internet Inc.
The Diffie-Hellman scheme, first published in 1976, allows for secure exchange of secret keys -- a step critical for broad use of symmetric-key cryptography -- and is based on the computational difficulty of solving the discrete logarithm problem (DLP). The RSA algorithm in turn derives its secrecy from the difficulty of factoring the products of very large prime numbers.
Noting that many "surprises" to the general security community where crypto is concerned are presaged by papers appearing in academic journals several years prior, Alex Stamos, chief technology officer of San Francisco-based Artemis Internet Inc., pointed out that there have been important breakthroughs in solving the DLP problem over the course of this year. These breakthroughs come following roughly thirty years of relative stagnation, and the sudden increase in the speed at which DLP solutions can be processed has galvanized the academic cryptography community.
Tom Ritter, a researcher with San Francisco-based iSEC partners, explained there are four basic steps to solving a discrete log equation, and improvements have been made in all four. While solving this sort of problem is not the same as factoring the product of two large primes, there are enough similarities that it's reasonable to suppose a significant further breakthrough in DLP would lead to corresponding breakthroughs in the factoring problem. "When we improve one," Ritter said, "we tend to improve the other in short order."
"We are not saying this is definite," Stamos said. "What we're saying is that if you look at things right now, this is kind of like we're at the movie and the general has just run up the stairs into the Oval Office and has given Morgan Freeman the picture of an asteroid that has a 10% chance of hitting the Earth. This is the crypto equivalent of the asteroid hitting the earth."
"Our conclusion is that there's a small, but definite chance that RSA [and similar cryptosystems] will not be useful for security purposes within the next two to five years."
And it could happen fast. "One of these guys could be sitting at a whiteboard, have a breakthrough, throw it out over the crypto mailing list … and all of a sudden RSA and Diffie-Hellman fall immediately all over the world. The moment that breakthrough happens, there's very little implementation work that needs to be done."
The solution, the team said, is to jump ship and move to elliptical curve cryptography (ECC) before the actual fall of RSA and Diffie-Hellman. This is doable: ECC is implemented on most desktop and mobile platforms, the speakers noted. But many of the implementations are quirky and not well exercised, because in almost every case where ECC might be used in normal scenarios, the software defaults to use RSA. Furthermore, there are some patent issues that might create licensing issues for some ECC adopters: Stamos made a direct call to BlackBerry to "do the right thing for the world" and issued a statement that they would not make patent infringement claims against ECC implementers and adopters.
The NSA has blessed a collection of encryption algorithms called "Suite B" that includes several standards based on ECC. Notably missing are RSA and Diffie-Hellman, suggesting that perhaps the NSA sees the writing on the wall where those two are concerned. "A very interesting data point," Stamos said, "is that when it was time to sign .RU, the Russian government refused to allow RSA to be used."
After the session, both Ritter and Stamos acknowledged that it was at least possible that either the NSA or Russia had already made the breakthroughs this talk predicted. And there's a precedent for that, too. Though this wasn't mentioned in the session presentation, the Diffie-Hellman key exchange protocol, while published by Diffie and Hellman in 1976, had previously and independently been discovered by researchers at Government Communications Headquarters (GCHQ), the British equivalent of the NSA. One of the British researchers, Clifford Cocks, also discovered the RSA algorithm prior to the RSA crypto team. GCHQ kept it all under wraps.