Science of Security Speaker Series: Logjam: Diffie-Hellman, Discrete Logs, the NSA, and You

  • Posted on January 27, 2016 at 9:30 am by
  • Categorized Events.
  • Comments are off for this post.

halderman_um14-md_REDUCEDJ. Alex Halderman, University of Michigan
February 9
, 2016, 4:00 p.m., B02 Coordinated Science Lab
Slides | Video

Abstract: 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.

Bio: J. Alex Halderman is an Associate Professor of Computer Science and Engineering at the University of Michigan and Director of Michigan’s Center for Computer Security and Society. His interests include computer and network security, Internet security measurement, censorship resistance, and electronic voting, as well as the interaction of technology with law and international affairs. Named one of Popular Science’s “Brilliant 10” for 2015, his recent projects include ZMap, Let’s Encrypt, and the Telex censorship resistance system.