(How) did they break Diffie-Hellman?

Earlier this year, a research paper presented a new attack against the Diffie-Hellman key exchange protocol. Among other things, the paper came with a reasonable explanation of how the NSA might be able to read a lot of the Internet’s VPN traffic. I wrote a blog about this in May.
Last month, the paper was presented at a conference and thus made the news again. Because I believed some of the news articles misunderstood the paper I just like writing about cryptography, I thought I’d explain what Diffie-Hellman is, what the paper showed and what its consequences are.

Chicken or the egg

Diffie-Hellman (named after its inventors Whitfield Diffie and Martin Hellman) attempts to solve the chicken-or-egg problem in cryptography: for Alice and Bob to communicate securely over a public channel such as the Internet they need to share a common encryption key. But for them to agree on such a key they need to be able to communicate securely over a public channel.
(N.B. in a typical situation where the protocol is used, Alice is a web browser or a VPN client; Bob is a web server using HTTPS, or a VPN server.)
Diffie-Hellman is called a key-exchange protocol, which is a bit of misnomer, as rather than exchange a previously generated key, the protocol actually generates the key.
In the first step, Alice and Bob both choose a (large) random number, which they both keep secret. Let’s call Alice’s number a and Bob’s number b.
Now using a ‘mechanism’ (more on which later) that is part of the protocol, Alice uses a to compute a second number, which is denoted g^a. Bob uses the same mechanism to compute a number g^b. Alice and Bob then share g^a and g^b with each other, over a public channel.
So we are now in the following situation:

• Alice knows a, g^a and g^b;
• Bob knows b, g^a and g^b;
• Anyone being able to read their communication only knows g^a and g^b.

Now using the same mechanism as before, Alice uses her secret number a and the number g^b, which Bob sent her, to create a new number (g^b)^a. Bob, likewise, uses b and g^a to create a number (g^a)^b. Because maths can be kind like that, (g^b)^a and (g^a)^b are in fact the same number. This is the shared key they will use.
The reason this works is that, while it is easy for Alice to use a to compute g^a, it is impossible for someone who only knows g^a to compute a — and the same of course also holds for b and g^b. It is also impossible to compute the shared secret key using only g^a and g^b.

Nothing is impossible

It is important to note that as so often in cryptography, ‘impossible’ doesn’t literally means that. It just means that it is extremely expensive and time-consuming. If the numbers involved are large enough, it can take the fastest clusters of computers millions of years to crack the algorithm; hence it is considered secure.
But computers keep getting faster, thus sometimes making the impossible possible. Many Diffie-Hellman implementations use numbers of a little over 300 digits long (1024 bits). These keys, the paper showed, can be cracked within a year for around 100 million US dollars. (Some people believe it can be done even more cheaply, but only the ballpark figure matters here.)
While 100 million dollars is not beyond the reach of the most powerful nation states (read: the NSA) it is unlikely that they ever pay this much to crack a single key. There’s almost always a cheaper way to get the same information; buying a very expensive wrench, for example.
Except for one essential detail. The mechanism used by Diffie-Hellman to generate the keys involves a choice: that of something mathematicians call an Abelian group, or, as they are more or less equivalent in this case, that of a prime number.
The attack the paper describes has two parts. The first part is the most expensive bit and involves doing a lot of computations that only depend on the chosen prime number. Only the second part involves the specific numbers g^a and g^b shared by Alice and Bob. An attacker who has done enough computations in the first part can perform the second part in more or less real time.

Sharing prime numbers

Imagine what would happen if many Diffie-Hellman implementations used the same fixed prime number: an adversary could spend a lot of time and money doing the required computations for this prime number and subsequently use that to crack key exchanges as they happen in real time. Knowledge of the secret key allows an adversary to read all the supposedly encrypted traffic between millions of Alices and Bobs around the world.
And this is exactly what was (and to some extent still is) the case: the paper showed for example that one in six of the most used HTTPS servers shared the same prime number. It’s even worse when it comes to VPN servers, of which 66% shared the same prime number. Although the latter figure has been disputed, if this was indeed what the NSA used to read VPN traffic, it would explain some Snowden slides rather well.
It is worth noting that sharing the same prime number is not as stupid as it may seem. Using your own unique prime number may be safer against this kind of attack, there are many traps to avoid when doing so. Most importantly, a lot of prime numbers are unsuitable and make the protocol a lot weaker. The paper also showed that several implementations used such unsuitable primes (and, somewhat intriguingly, some implementations used numbers that weren’t prime at all). There is thus a lot to say for choosing known safe (though widely used) prime numbers, despite the downsides we now understand well.
It would actually be a good rule of thumb to choose the strength of your encryption algorithms such that it would be too expensive for the most powerful adversary to attack, even if they would automatically crack all other implementations of the same protocol. For Diffie-Hellman, using longer numbers of 2048 bits (more than 600 digits) will do just fine.
It is thus not true that the researchers have broken Diffie-Hellman. Nor is it true that choosing “non-random prime numbers” (as I’ve seen someone claim somewhere) is inherently wrong.
However, longer numbers makes the algorithm more expensive to run. There would thus be a good argument to use Elliptic Curve Diffie-Hellman (ECDH) instead, a similar protocol that uses a different kind of maths. Its most important benefit is that it provides the same level of security with much smaller numbers.

Downgrading

On an aside, the paper also showed a related attack, which involves a “protocol downgrade”, where an adversary could convince Alice and Bob that the other could only use a mechanism with 160-digit (512-bit) numbers. The cost of cracking the secret key in this case, even if the mechanism used a unique prime number, is not beyond the means of a small criminal organisation.
Although this is a serious problem, from a cryptographic point of view it is less interesting. I also don’t know how likely it is for this attack to be used in the wild frequently: for a nation-state attacker a downgrade attack leaves too many traces, while for a criminal group, obtaining a man-in-the-middle position isn’t entirely trivial and often not needed to achieve their goals.