Another crypto downgrade attack: Logjam

If more evidence was needed that deliberately weakening cryptographic algorithms based on politics is likely to go astray, the new Logjam attack against TLS seems to provide it. All of that evidence probably won't stop politicians (and others) from further attempts to cripple crypto, sadly, but it may at least provide some guidance to those who must implement those decisions down the road. In the meantime, though, there is yet another attack against the encryption used by the web and other internet protocols.

Downgrade attack

There are two related pieces to Logjam. The first is a crypto downgrade attack (somewhat akin to the FREAK attack) that, once again, abuses the export-strength ciphers that were mandated by the US government and are often still supported for backward compatibility. In this case, though, the attack is against Diffie-Hellman (DH) key exchange, rather than the RSA keys targeted by FREAK. Also unlike FREAK, the Logjam crypto downgrade attack uses a flaw in the TLS protocol instead of exploiting a bug in some TLS implementations.

The basic problem that Logjam exploits is that the message a server sends for key exchange can be undetectably replaced with a weaker variant. The message that uses a DH key that has been restricted to using prime numbers of at most 512 bits for political reasons (i.e. DHE_EXPORT ciphers) and one that uses the non-export variety can't be distinguished by clients. So a properly functioning server that supports, but does not prefer, DHE_EXPORT ciphers will send a key exchange message using a 1024-bit (or larger) DH group (i.e. one that has been derived from a 1024-bit prime). A man in the middle can intercept that message and rewrite it using the server's 512-bit group without alerting the client that anything has changed.

It turns out that the vast majority of servers that support DHE_EXPORT also use the same 512-bit prime number. The Logjam paper [PDF] shows that 82% of DHE_EXPORT-supporting web servers used a prime that had been distributed with the Apache web server for a number of years. It also reports that nearly 5% of the 14.3 million HTTPS web sites supported DHE_EXPORT, so roughly 4% of the net is using that one prime number. This practice was not seen as a problem, as the paper notes:

In order to exploit the downgrade to DHE_EXPORT, an attacker needs to be able to calculate discrete logarithms in near real-time. It is a nearly impossible math problem, but one that is made vastly easier with access to the prime number of interest. Using that, the man in the middle can precompute values that allow it to extract the session key from the key exchange. Once that is obtained, the man in the middle can pretend to be the server with impunity; the client will be none the wiser.

On a system with four six-core Xeon processors, the researchers' proof of concept was able to crack the session key in an average of 90 seconds. That may seem like a long time for users to wait for the browser to connect to the server—and it is, at least for interactive sessions. There are a number of techniques described in the paper to work around that delay.

To start with, non-interactive uses, such as curl or Git, are often unattended so they have long timeouts and "we could hijack their connections without much difficulty". There is a TLS warning alert mechanism that can be used to reset the browsers' handshake timers. The delay still might be noticed by the user, however, so the attacker might choose to compromise a request for some background resource that won't delay the page display. There is also the fact that many TLS implementations cache their ephemeral key and reuse it multiple times; that allows the calculation to be done once and to be used again and again. Beyond that, more optimization or more powerful systems could potentially reduce the average time to crack the key substantially.

Diffie-Hellman and state-level attackers

The second piece of the Logjam report looks at how vulnerable the DH key exchange is to attack when there is no downgrade ability. Once again, various protocols often use (or even specify) the same prime numbers everywhere. The paper specifically mentions SSH, TLS, and Internet Key Exchange (IKE) which is used by IPsec. Currently, 768-bit DH groups are fairly widespread and the paper estimates that precomputing the values needed would require around 36,000 core-years, which is "within reach by computing power available to academics". Once that precomputation is done, doing a single 768-bit discrete log computation is on the order of two core-days.

Perhaps even more eye-opening, though, is that 1024-bit DH groups are estimated to be crackable by state-level attackers (i.e. governments and their ilk). Precomputation is on the order of 45 million core-years, which is an enormous effort, but could be reduced with specialized hardware. Once that was done, the discrete log calculations could be done in roughly 30 core-days. That estimate leads to a possible answer to a question that has been asked frequently in the crypto community:

Documents leaked by Snowden indicate that the NSA has been passively decrypting virtual private network (VPN) traffic. The paper concludes that the documented information is consistent with an attack against the 1024-bit DH group used by IKE. That doesn't mean it is the mechanism used by the NSA, but it could be.

That leads the authors of the paper (David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin, and Paul Zimmermann) to a number of recommendations. Disabling DHE_EXPORT ciphers, and configuring the other DHE ciphers to use groups of 2048 bits or larger, head that list. Browsers and other clients should require groups of at least 1024 bits to avoid the downgrade attack but still interoperate with servers that have not been upgraded.

Avoiding fixed-prime groups is another recommendation, as is transitioning to elliptic curve DH (ECDH), which does not provide as much of an advantage for precomputation. The parameters for ECDH still need to be worked out—those recommended by the US government are viewed with suspicion due to NSA influence on their choice.

The last two recommendations are admonishments to politicians and the crypto community respectively. First: "In combination with FREAK, our attacks warn of the long-term debilitating effects of deliberately weakening cryptography." But there is also lots of room for better communication by the crypto community:

For those wanting to check their status, the Logjam web site will warn if their browser is susceptible to the attack (i.e. if it will accept DH groups with less than 1024 bits). Another page provides tools to test servers and information on how to upgrade those that are found to have an inadequate DH group size (i.e. less than 2048). For example, the LWN.net server needs an upgrade to its DH group, which we will be taking care of soon.

This research is quite timely, interesting, and important, though it may not require a "drop everything" response—at least for sites that don't support DHE_EXPORT. For those that believe their traffic may be targeted by state-level attackers, however, prudence would seem to indicate a faster response. At this point, after the information leaked by Snowden and others, these kinds of attacks seem a little less surprising—we have known that secret services were decrypting lots of this data for some time. Now, at least, we may know some of the "how" as well.