Log jam © 2007 born1945 (CC BY 2.0)

A group of fourteen researchers from France and the US presented a paper at CCS 2015 in which they showed several problems with the way Diffie-Hellman (DH) key-exchange is used in practice. The DH protocol sets up session keys for encrypted communications in VPNs, HTTPS, and other protocols. Being able to decode the DH key exchange thus allows a Man-in-the-Middle (MitM) to intercept and sometimes even alter the subsequent communication.

The paper is available in PDF. A smaller article concentrates on the implications for pervasive monitoring. And the authors made a Web site, weakdh.org, with advise for system administrators.

Logjam, an attack on 512-bit, “export-grade” DH keys

One problem is that encryption with 512-bit keys can now be broken in about a week with resources (storage and computing power) available to a typical university. That's not enough to read, let alone modify, a communication in real time… except when the same key is used over and over again. And that turns out to be the case: There are two 512-bit keys that account for 92% of servers. When the server's 512-bit prime number is known, recovering the session key takes about a minute, which is fast enough that many clients will not notice the slow start of the conversation.

As most clients and servers can handle 1024 bits and more, 512-bit keys should rarely be seen in practice, except that a MitM that can alter messages between the client and the server can make the server believe the client only handles 512-bit keys. Downgrading to 512 bits is a legacy from the times when the US didn't allow 1024-bit-capable software to be exported. The authors of the paper call this MitM attack the “LogJam” attack.

The authors approached several implementers of client and server software earlier this year and 512-bit support has since been disabled in the latest versions of many programs.

1024-bit keys not safe against Pervasive Monitoring

Of the 1024-bit keys, there is also a handful that are used by very many servers. However, even knowing the keys, 1024 bits is strong enough that recovering a session key is out of reach of most organisations. But not necessarily for an organisation with the resources of the NSA. Pre-computing factors for the most popular 1024-bit primes far enough to allow recovering session keys in a reasonable time would probably take a year and cost a billion dollars. But then the communications of some 18% of the most popular secure Web sites can be decoded; still not in real time, but the communications can be stored and promising ones can be decoded within weeks. An even larger percentage of VPNs and SSH servers is vulnerable to this attack.

It is not known if the NSA or any other organisation has actually done that work. The authors argue that some material made public by Edward Snowden can be explained by assuming the NSA has done so and is indeed capable of decoding a certain percentage of encrypted communications.

The authors therefore recommend to use 2048-bit keys, to generate new keys for every server installation instead of using the default keys that come with the software, and to use elliptic-curve DH instead of the traditional discrete-log DH, when possible.

Update 2015-10-15: Paul Wouters and Jari Arkko of the IAB posted an article on the IETF site with some pointers to work going on in the IETF and with a pointer to another article by Paul Wouters that argues that the authors of the LogJam paper overestimated the number of vulnerable VPN servers: