You are here
Logjam: The Flaw that Threatens the Internet
In collaboration with researchers from Inria Paris-Rocquencourt and Microsoft Research, as well as Johns Hopkins University, Michigan University, and the University of Pennsylvania in the US, last spring we demonstrated a serious weakness in the TLS protocol used for secure connections to the Internet. This weakness affected a large number of Internet services (web, email, vpn, etc.), with consequences ranging from lack of confidentiality to server identity theft. In this column, we would like to revisit this attack and its practical implications.
TLS, a protocol found everywhere on the Internet
The TLS protocol (standing for Transport Layer Security) is the mechanism automatically used, often imperceptibly for the user, to secure an Internet connection between two machines. For example, the difference between two addresses in the form of http://wikipedia.org and https://wikipedia.org, is that in the second case, the data exchanged between a machine and the Wikipedia server is encrypted in TLS. More precisely, the role of TLS in this type of connection is firstly to guarantee confidentiality: neither an access provider nor anyone wiretapping the line should be able to determine the content of the communication. The most they could find out is that the user is connected to Wikipedia, and the amount of data that has travelled along the network.
Another function of TLS that is just as critical is authenticity. A system of certificates, genuine digital identity cards, enables users to know that the pages they are browsing are indeed provided by Wikipedia, and not by a pirate server stealing their identity.
TLS is a very complex protocol in which numerous cryptographic algorithms are combined to ensure security and speed of execution. At the very beginning of the connection, in a first phase called "handshake," the two machines (the web server and the personal computer, in the foregoing example), agree on the algorithms that should be used. In fact, considering that many computers are not very up-to-date, and that they only know algorithms from a decade ago, a server must speak a very large number of cryptographic languages for interoperability reasons. The two machines then produce and exchange what is called a session key. This temporary key will serve to encrypt communications during the connection.
The theory of numbers at the service of cryptography
Within TLS, the calculations allowing two machines to agree to a key are often performed using the Diffie-Hellman algorithm, whose security is based on the complex mathematical problem of the discrete logarithm.
Without getting into the details, one could say that the problem of the discrete logarithm is based on the use of large prime numbers, and that the larger these numbers, the more secure the system, but also the heavier the calculations. Our expertise lies in quantifying this compromise precisely.
We know the algorithms involved very well, and hold the record for the largest prime number for which the discrete logarithm problem was solved.1 To give an idea, this record involves a 180-digit prime number, whereas the recommended minimal size is on the order of 600 digits. There's some leeway! Unfortunately, there are still too many systems on the Internet that are protected by prime numbers of only 300 digits, or even less. In IT as in other fields, the existence of a compromise between cost and security is frequent, and subsequent abuse is well known...
The Logjam attack: a problem of size
Looking at US legislation from the late 1990s is essential to understand the Logjam attack. At the time, the export of cryptographic products was highly regulated. Consequently, encrypting protocols explicitly provided for an "Export mode" during connections, limiting the size of the prime numbers used to 155 digits. This "genetic defect" of the TLS is still present in specifications as well as many software programs, both for servers and personal computers. This mode is of course not activated by default, but is still considered acceptable if one of the machines requests it during the handshake. A minor subtlety in the protocol (which can be qualified as a design flaw) allows an ill-intentioned attacker to slip into the connection and make the two parties believe that the other one wants to switch to Export mode. However, this requires solving the discrete logarithm problem for a 155-digit number, a calculation which, as we saw, is possible with sufficient time and means of calculation, but not during the few seconds of the handshake. More worrying is a second subtlety, familiar to specialists of discrete logarithms: when the prime number does not change, precalculations make it possible to solve each instance much more quickly.
Thus, for a 155-digit number, a few days using a cluster of a thousand modern processor cores is enough to complete this precalculation, and the discrete logarithm can then be broken in a few seconds. In practice, only a handful of different prime numbers are actually used. The reason is not theoretical (there are many prime numbers of the desired size), but simply to facilitate application. This, in fact, would not pose a problem provided the size of the prime number was sufficient, but with a limited number of 155-digit numbers, the attack ultimately proves to be quite realistic.
The importance of proof-of-concept
Demonstrating that a security weakness is actually exploitable is no mean feat. In the case of the Logjam attack, it is not enough to mathematically show that the calculation can be performed during the handshake. In this respect, presenting a software program that is able to do so using moderate means is a crucial argument. Yet this is what our CADO-NFS software program for integer factorization and the calculation of discrete logarithms has made possible. Developped over the last eight years, primarily by members of our Nancy team, and freely disseminated, it helps force security solution vendors to follow the new recommendations for the prime number size to be used.
Therefore, when this vulnerability was made public, it was taken especially seriously: thousands of servers were reconfigured to no longer accept switching to Export mode, and personal computer browsers were updated as well.
In addition to the Export mode attack, the second advantage of our work was to give, for the first time, an order of magnitude for the time required to break the discrete logarithm once precalculations are complete. Since this amount of time is finally very short, even for rather large prime numbers, questions surrounding the feasibility and cost of precalculations become critical, mostly because this cost will be recouped by the fact that the same precalculation can be used to break millions of connections.
All eyes are naturally on intelligence agencies. The ambient paranoia with regard to the NSA in the wake of Edward Snowden's revelations is all the more reason to not play with fire: let the size of prime numbers be increased! It is high time to follow the recommendations and start using prime numbers of at least 600 digits. Better still, modern cryptography must continue the transition toward more secure encryption algorithms based on more complex functions such as elliptical curves.
The analysis, views and opinions expressed in this section are those of the authors and do not necessarily reflect the position or policies of the CNRS.
Other opinions
Director of research at CNRS, Pierrick Gaudry is a member of the Loria...