Information Trust Institute

Back to Listing

TSS/SoS Speaker Series: J. Alex Halderman (University of Michigan), "Logjam: Diffie-Hellman, Discrete Logs, the NSA, and You"

Event Type
Information Trust Institute
CSL Auditorium (B02)
Feb 9, 2016   4:00 pm  
J. Alex Halderman, University of Michigan


Diffie-Hellman key exchange is a cornerstone of modern cryptography at the core of protocols like HTTPS and SSH.  Last year, collaborators and I discovered that Diffie-Hellman, as used in practice, is significantly less secure than widely believed. With the number field sieve algorithms, computing a single discrete log in prime fields is more difficult than factoring an RSA modulus of the same size. However, an adversary who performs a large precomputation for a prime $p$ can then quickly calculate arbitrary discrete logs in groups modulo that prime, amortizing the cost over all targets that share this parameter. Although this fact is well known among mathematical cryptographers, it seems to have been lost among practitioners.

Using these observations, we developed Logjam, an attack on TLS in which a man-in-the-middle can downgrade a connection to 512-bit “export-grade'' Diffie-Hellman. After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logs in that group in about a minute. We found that 82% of vulnerable servers use a single 512-bit group, allowing us to compromise connections to 7% of Alexa Top Million HTTPS sites. In response, major browsers have been changed to reject short groups.


In the more widespread case of 1024-bit Diffie-Hellman, we estimate that discrete log computations are plausible given nation-state resources, and a close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break. A small number of fixed or standardized groups are used by millions of servers, and we estimate that performing precomputation for a single 1024-bit group would allow passive eavesdropping on about 18% of popular HTTPS sites, and a second group would allow decryption of traffic to about 66% of IPsec VPNs and 26% of SSH servers. We conclude that the security community should prioritize moving to stronger key exchange methods.

link for robots only