How Diffie-Hellman Fails in Practice
summary
An Internet-wide scan connects to 14.3 million hosts and finds ~40% using mod-p Diffie–Hellman, with about 70,000 distinct primes and 750 groups whose subgroup orders yield small factors via ECM. Implementations reuse common Oakley primes, letting a heavy precomputation with number field sieve (sieving on thousands of cores, linear algebra on hundreds) break 512-bit handshakes in minutes and makes attacking 768/1024-bit groups realistic at nation-state cost, so precomputation enables fast online breaks against many deployed sessions.
AI-written summary · about
chapters (20)
- 0:00Intro
- 3:13Warm-up: Elementary discrete log algorithms
- 9:45Diffie-Hellman deployment in practice
- 15:02Short exponents with composite group orders. A sad tale
- 18:34Subexponential algorithms for prime fields: Index calculus
- 19:41Index calculus: Linear algebra
- 21:02Actually computing individual logs
- 22:14Index calculus running time
- 23:18Number field sieve
- 26:37Implementing the NFS with CADO NFS
- 27:44Implementing the NFS with CADO-NFS
- 33:29Authentication in TLS Diffie-Hellman Key Exchange
- 34:22Some differences between practice and theory
- 36:10Encryption in TLS Diffie-Hellman Key Exchange
- 39:12Export cipher suites in TLS
- 43:16Man-in-the-middle downgrade attack to export DH
- 52:39Carrying out the downgrade attack
- 54:01Cost estimates for discrete log
- 58:20James Bamford, 2012. Wired
- 59:122013 NSA Black Budget
related talks
21mHow to defend from an attacker armed with a mathematician
05mHow to defend from an attacker armed with a mathematician
29mHow Prime Numbers Keep the Internet Secure
51mA Retrospective on the Use of Export Cryptography
28mThe Million-Key Question—Investigating the Origins of RSA Public Keys
56mAsymmetric Encryption: A Deep Dive
57mShor's Algorithm is Scary NOW
26mBaby Sharks: Small Subgroup Attacks on DKG Implementations