Abstract
We investigate the security of Diffie-Hellman key exchange as used in popular Internet protocols and find it to be 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. The algorithm can be tuned to reduce individual log cost even further. Although this fact is well known among mathematical cryptographers, it seems to have been lost among practitioners deploying cryptosystems. Using these observations, we implement a new attack on TLS in which a man-in-the-middle can downgrade a connection to 512-bit export-grade cryptography. In the 1024-bit case, 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.
(Joint work with David Adrian, Karthikeyan Bhargavan, J. Alex Halderman, Benjamin VanderSloot, Eric Wustrow, Zakir Durumeric, Pierrick Gaudry, Matthew Green, Drew Springall, Emmanuel Thomé, Luke Valenta, Santiago Zanella-Béguelin, and Paul Zimmermann.)