The discovery last week of another major flaw in TLS was announced, nicknamed "Logjam" by the group of prominent cryptographers who discovered it. It's getting so hard to keep track of these flaws that researchers at INRIA in France created a "zoo" classifying the attacks (which is not yet updated to include Logjam or the FREAK attack discovered in March). Despite the fact that these attacks seem to be announced every few months now, Logjam is a surprising and important finding with broad implications for the Internet. In this post I'll offer a technical primer of the Logjam vulnerability.

Logjam is actually two related but separate vulnerabilities in the way that certain common types of secure connections are established. The first is a novel active attack whereby a man-in-the-middle can force a connection to downgrade to a decades-old key exchange algorithm with well known vulnerabilities. This is a clever combination of cryptanalysis and a break in the protocol logic of TLS. The second attack, while generally known for years, was demonstrated by the researchers to be much more feasible in practice than commonly realized. It appears that the NSA may have been able for years to decrypt a significant portion of secure traffic on the Internet. Most disconcertingly, this would mean that instead of working to fix this widespread problem, the NSA intentionally left us all vulnerable.

Logjam affects TLS and other protocols which use traditional (i.e., non-Elliptic Curve) Diffie-Hellman key exchange. Normally this approach is preferred to "static" RSA because it enables forward secrecy, but it can be broken by an adversary who can compute the relevant discrete logarithms-that is, an attacker who can solve for x in the equation g^x = y (mod p) given g, y, and p (which is a prime number). This is a famous and thoroughly studied problem in cryptography, and its difficulty depends mostly on how large p is. For large enough p, this is believed to be infeasible, and the Diffie-Hellman key exchange algorithm is considered secure.

A key insight detailed by earlier researchers that the Logjam attack authors exploit is that, for primes p which are small enough to compute a discrete logarithm, most of the work can be done once and stored if one wants to compute multiple discrete logarithms modulo the same p. As noted above, this enables two distinct attacks:

1. If p is a 512-bit prime (considered too small to be secure), after a large but feasible amount of precomputation one can compute discrete logs in a matter of minutes. This is so fast that it enables a devious downgrade attack on TLS. Much like with the FREAK attack, many TLS servers still support an archaic "export mode" ciphersuite which uses a 512-bit prime. An active network attacker can modify the message from the client so that it looks like the client is only willing to use the export Diffie-Hellman algorithm. Unlike with FREAK, which took advantage of servers failing to check if such a downgrade happened, for Diffie-Hellman ciphersuites servers do check when the client later re-sends its list of supported ciphersuites. Unfortunately, 512-bit Diffie-Hellman can be broken so fast that the attacker can delay this response and then replace it with a forged one re-affirming that only the weak ciphersuite was supported. This attack affects a non-trivial fraction of servers: 8.4% of the top 1 million web servers as well as mail servers and many others. 
2. If p is a larger prime, in particular a 1024-bit prime which is the most common choice in software implementations of Diffie-Hellman today, then it may be feasible for a nation-state-level attacker (e.g. the NSA) to precompute the information needed to compute discrete logs modulo a few common values of p. Once this work is finished, an active downgrade attack is no longer needed. The attacker can simply record 1024-bit Diffie-Hellman exchanges happening naturally and compute the shared secret at their leisure, no longer needing to finish in minutes to be successful. The precomputation is quite expensive, requiring several million computers running for a year to break a single prime. With some algorithmic speedups and with custom hardware, however, this attack might be feasible with a budget of tens to hundreds of millions of dollars. Given the NSA's budget, it's plausible that this precomputation may have been performed several times, once for each the most common values of p used on the Internet. This would enable the NSA to break a single connection in something like 30 CPU-days. This is too costly to speculatively break all traffic on the internet, but cheap enough to break a large number of specific connections of interest. The Logjam authors and others have further speculated that this might be the large-scale cryptanalysis breakthrough by the NSA described by James Bamford in 2012 and alluded to in some of the Snowden documents. There's no definitive proof here, but it's a plausible (and disturbing) interpretation.

On the technical side, the fix is simple to the first problem. Export-grade Diffie-Hellman ciphersuites need to be banished to the dustbin of history. The major browsers have all announced plans to disable 512-bit Diffie-Hellman permanently. Fortunately, there's no evidence that this attack has been performed in the wild, and this fix should cause relatively few compatibility problems.

The second problem is a bit trickier because there are still many legitimate servers preferring 1024-bit Diffie-Hellman. The Logjam authors estimated that about 25% of popular HTTPS (web) servers, 25% of SSH servers and the majority of VPN servers employ Diffie-Hellman with a vulnerable prime as their most preferred key exchange algorithm. This makes it hard for browsers to disable support for these algorithms. Instead, sysadmins need to upgrade all of these servers to use stronger methods to prevent passive eavesdropping.

If you're a sysadmin you can follow this guide to upgrade to eliminate old ciphersuites. Moving from 1024-bit Diffie-Hellman to 2048-bit Diffie-Hellman works, but the best bet is to forget the traditional prime-based Diffie-Hellman and move to elliptic-curve Diffie-Hellman (ECDH), which is not vulnerable to these attacks and is more efficient.