At the Black Hat security conference in Las Vegas, a quartet of researchers, Alex Stamos, Tom Ritter, Thomas Ptacek, and Javed Samuel, implored everyone involved in cryptography, from software developers to certificate authorities to companies buying SSL certificates, to switch to newer algorithms and protocols, lest they wake up one day to find that all of their crypto infrastructure is rendered useless and insecure by mathematical advances.
We've written before about asymmetric encryption and its importance to secure communication. Asymmetric encryption algorithms have pairs of keys: one key can decrypt data encrypted with the other key, but cannot decrypt data encrypted with itself.
The asymmetric algorithms are built on an underlying assumption that certain mathematical operations are "hard," which is to say, that the time it takes to do the operation increases proportional to some number raised to the power of the length of the key ("exponential time"). This assumption, however, is not actually proven, and nobody knows for certain if it is true. The risk exists that the problems are actually "easy," where "easy" means that there are algorithms that will run in a time proportional only to the key length raised to some constant power ("polynomial time").
The most widely used asymmetric algorithms (Diffie Hellman, RSA, and DSA) depend on the difficulty of two problems: integer factorization, and the discrete logarithm. The current state of the mathematical art is that there aren't—yet—any easy, polynomial time solutions to these problems; however, after decades of relatively little progress in improving algorithms related to these problems, a flurry of activity in the past six months has produced faster algorithms for limited versions of the discrete logarithm problem.
At the moment, there's no known way to generalize these improvements to make them useful to attack real cryptography, but the work is enough to make cryptographers nervous. They draw an analogy with the BEAST, CRIME, and BREACH attacks used to attack SSL. The theoretical underpinnings for these attacks are many years old, but for a long time were dismissed as merely theoretical and impossible to use in practice. It took new researchers and new thinking to turn them into practical attacks.
When that happened, it uncovered a software industry ill-prepared to cope. A lot of software, rather than allowing new algorithms and protocols to be easily plugged in, has proven difficult or impossible to change. This means that switching to schemes that are immune to the BEAST, CRIME, and BREACH attacks is much more difficult than it should be. Though there are newer protocols and different algorithms that avoid the problems that these attacks exploit, compatibility concerns mean that they can't be rapidly rolled out and used.
The attacks against SSL are at least fairly narrow in scope and utility. A general purpose polynomial time algorithm for integer factorization or the discrete logarithm, however, would not be narrow in scope or utility: it would be readily adapted to blow wide open almost all SSL/TLS, ssh, PGP, and other encrypted communication. (The two mathematical problems, while distinct, share many similarities, so it's likely that an algorithm that solved integer factorization could be adapted in some way to solve the discrete logarithm, and vice versa).
Worse, it would make updating these systems in a trustworthy manner nearly impossible: operating systems such as Windows and OS X depend on digital signatures that in turn depend on these same mathematical underpinnings to protect against the installation of fraudulent or malicious updates. If the algorithms were undermined, there would be no way of verifying the authenticity of the updates.
While there's no guarantee that this catastrophe will occur—it's even possible that one day it might be proven that the two problems really are hard—the risk is enough to have researchers concerned. The difficulties of change that BEAST et al. demonstrated mean that if the industry is to have a hope of surviving such a revolution in cryptography, it must start making changes now. If it waits for a genius mathematician somewhere to solve these problems, it will be too late to do anything about it.
Fortunately, a solution of sorts does exist. A family of encryption algorithms called elliptic curve cryptography (ECC) exists. ECC is similar to the other asymmetric algorithms, in that it's based on a problem that's assumed to be hard (in this case, the elliptic curve discrete logarithm). ECC, however, has the additional property that its hard problem is sufficiently different from integer factorization and the regular discrete logarithm that breakthroughs in either of those shouldn't imply breakthroughs in cracking ECC.
However, support for ECC is still very problematic. Much of the technology is patented by BlackBerry, and those patents are enforced. There are certain narrow licenses available for implementations of ECC that meet various US government criteria, but the broader patent issues have led some vendors to refuse to support the technology.
Further, support of protocols that can use ECC, such as TLS 1.2 (the latest iteration of SSL technology) is still not widely available. Certificate authorities have also been slow to offer ECC certificates.
As such, the researchers are calling for the computer industry as a whole to do two things. First, embrace ECC today. Second, ensure that systems that use cryptography are agile. They must not be lumbered with limited sets of algorithms and obsolete protocols. They must instead make updating algorithms and protocols quick and easy, to ensure that software systems can keep pace with the mathematical research and adapt quickly to new developments and techniques. The cryptopocalypse might never happen—but we should be prepared in case it does.
reader comments
73