David Adrian
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. First, we present Logjam, a novel flaw in TLS that lets a man-in-the-middle downgrade connections to "export-grade" Diffie-Hellman. To carry out this attack, we implement the number field sieve discrete log algorithm. 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 find 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 are being changed to reject short groups. We go on to consider Diffie-Hellman with 768- and 1024-bit groups. We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources. A small number of fixed or standardized groups are used by millions of servers; performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers. A close reading of published NSA leaks shows that the agency's attacks on VPNs are consistent with having achieved such a break. We conclude that moving to stronger key exchange methods should be a priority for the Internet community.
- S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert, A. Kruppa, F. Morain, E. Thomé, and P. Zimmermann.upshape cado-nfs, an implementation of the number field sieve algorithm, 2014. Release 2.1.1.Google Scholar
- R. Barbulescu. Algorithmes de logarithmes discrets dans les corps finis. PhD thesis, Université de Lorraine, France, 2013.Google Scholar
- R. Barbulescu, P. Gaudry, A. Joux, and E. Thomé. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In Eurocrypt, 2014.Google ScholarCross Ref
- E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid. NIST Special Publication 800--57: Recommendation for Key Management, 2007.Google Scholar
- D. J. Bernstein. How to find smooth parts of integers, 2004. http://cr.yp.to/factorization/smoothparts-20040510.pdf.Google Scholar
- D. J. Bernstein and T. Lange. Batch NFS. In Selected Areas in Cryptography, 2014.Google Scholar
- B. Beurdouche, K. Bhargavan, A. Delignat-Lavaud, C. Fournet, M. Kohlweiss, A. Pironti, P.-Y. Strub, and J. K. Zinzindohoue. A messy state of the union: Taming the composite state machines of TLS. In IEEE Symposium on Security and Privacy, 2015.Google ScholarDigital Library
- C. Bouvier, P. Gaudry, L. Imbert, H. Jeljeli, and E. Thomé. New record for discrete logarithm in a prime finite field of 180 decimal digits, 2014. http://caramel.loria.fr/p180.txt.Google Scholar
- R. Canetti and H. Krawczyk. Security analysis of IKE's signature-based key-exchange protocol. In Crypto, 2002. Google ScholarDigital Library
- A. Commeine and I. Semaev. An algorithm to solve the discrete logarithm problem with the number field sieve. In PKC, 2006. Google ScholarDigital Library
- D. Coppersmith. Solving linear equations over GF(2) via block Wiedemann algorithm. Math. Comp., 62(205), 1994. Google ScholarDigital Library
- R. Crandall and C. B. Pomerance. Prime Numbers: A Computational Perspective. Springer, 2001.Google ScholarCross Ref
- B. den Boer. Diffie-Hellman is as strong as discrete log for certain primes. In Crypto, 1988. Google ScholarDigital Library
- W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Inform. Theory, 22(6):644--654, 1976. Google ScholarDigital Library
- Z. Durumeric, E. Wustrow, and J. A. Halderman. ZMap: Fast Internet-wide scanning and its security applications. In Usenix Security, 2013. Google ScholarDigital Library
- M. Friedl, N. Provos, and W. Simpson. Diffie-Hellman group exchange for the secure shell (SSH) transport layer protocol. RFC 4419, Mar. 2006.Google Scholar
- W. Geiselmann, H. Kopfer, R. Steinwandt, and E. Tromer. Improved routing-based linear algebra for the number field sieve. In Information Technology: Coding and Computing, 2005. Google ScholarDigital Library
- W. Geiselmann and R. Steinwandt. Non-wafer-scale sieving hardware for the NFS: Another attempt to cope with 1024-bit. In Eurocrypt, 2007. Google ScholarDigital Library
- D. Gillmor. Negotiated finite field Diffie-Hellman ephemeral parameters for TLS. IETF Internet Draft, May 2015.Google Scholar
- D. M. Gordon. Designing and detecting trapdoors for discrete log cryptosystems. In Crypto, 1992. Google ScholarDigital Library
- D. M. Gordon. Discrete logarithms in GF(p) using the number field sieve. SIAM J. Discrete Math., 6(1), 1993. Google ScholarDigital Library
- D. Harkins and D. Carrel. The Internet key exchange (IKE). RFC 2409, Nov. 1998. Google ScholarDigital Library
- T. Jager, K. G. Paterson, and J. Somorovsky. One bad apple: Backwards compatibility attacks on state-of-the-art cryptography. In NDSS, 2013.Google Scholar
- A. Joux and R. Lercier. Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method. Math. Comp., 72(242):953--967, 2003. Google ScholarDigital Library
- C. Kaufman, P. Hoffman, Y. Nir, P. Eronen, and T. Kivinen. Internet key exchange protocol version 2 (IKEv2). RFC 7296, Oct. 2014.Google Scholar
- S. Kent. IP authentication header. RFC 4302, Dec. 2005.Google Scholar
- S. Kent. IP encapsulating security payload (ESP). RFC 4303, Dec. 2005.Google Scholar
- T. Kleinjung. Cofactorisation strategies for the number field sieve and an estimate for the sieving step for factoring 1024 bit integers, 2006. http://www.hyperelliptic.org/tanja/SHARCS/talks06/thorsten.pdf.Google Scholar
- T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, H. te Riele, A. Timofeev, and P. Zimmermann. Factorization of a 768-bit RSA modulus. In Crypto, 2010. Google ScholarDigital Library
- A. Langley, N. Modadugu, and B. Moeller. Transport layer security (TLS) false start. IETF Internet Draft, 2010.Google Scholar
- A. K. Lenstra and H. W. Lenstra, Jr., editors. The Development of the Number Field Sieve. Springer, 1993.Google ScholarCross Ref
- M. Lipacis. Semiconductors: Moore stress = structural industry shift. Technical report, Jefferies, 2012.Google Scholar
- U. M. Maurer. Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. In Crypto, 1994. Google ScholarDigital Library
- U. M. Maurer and S. Wolf. Diffie-Hellman oracles. In Crypto, 1996. Google ScholarDigital Library
- N. Mavrogiannopoulos, F. Vercauteren, V. Velichkov, and B. Preneel. A cross-protocol attack on the TLS protocol. In ACM CCS, pages 62--72, 2012. Google ScholarDigital Library
- C. Meadows. Analysis of the Internet key exchange protocol using the NRL protocol analyzer. In IEEE Symposium on Security and Privacy, 1999.Google ScholarCross Ref
- Microsoft Security Bulletin MS15-055. Vulnerability in Schannel could allow information disclosure, May 2015. https://technet.microsoft.com/en-us/library/security/ms15-055.aspx.Google Scholar
- NIST. FIPS PUB 186--4: Digital signature standard, 2013.Google Scholar
- Oak Ridge National Laboratory. Introducing Titan, 2012. https://www.olcf.ornl.gov/titan.Google Scholar
- H. Orman. The Oakley key determination protocol. RFC 2412, Nov. 1998. Google ScholarDigital Library
- S. C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over $\mathrmGF(p)$ and its cryptographic significance (corresp.). Trans. Inform. Theory, 24(1), 1978. Google ScholarDigital Library
- J. M. Pollard. A Monte Carlo method for factorization. BIT Numerical Mathematics, 15(3):331--334, 1975.Google ScholarDigital Library
- O. Schirokauer. Virtual logarithms. J. Algorithms, 57(2):140--147, 2005. Google ScholarDigital Library
- I. A. Semaev. Special prime numbers and discrete logs in finite prime fields. Math. Comp., 71(237):363--377, 2002. Google ScholarDigital Library
- D. Shanks. Class number, a theory of factorization, and genera. In Proc. Sympos. Pure Math., volume 20. 1971.Google Scholar
- Spiegel Staff. Prying eyes: Inside the NSA's war on Internet security. Der Spiegel, Dec 2014. http://www.spiegel.de/international/germany/inside-the-nsa-s-war-on-internet-security-a-1010361.html.Google Scholar
- W. Stein et al. Sage Mathematics Software (Version 6.5). The Sage Development Team, 2015. http://www.sagemath.org.Google Scholar
- stud: The scalable TLS unwrapping daemon, 2012. https://github.com/bumptech/stud/blob/19a7f19686bcdbd689c6fbea31f68a276e62d886/stud.c#L593.Google Scholar
- E. Thomé. Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm. J. Symbolic Comput., 33(5):757--775, 2002. Google ScholarDigital Library
- P. C. Van Oorschot and M. J. Wiener. Parallel collision search with application to hash functions and discrete logarithms. In ACM CCS, 1994. Google ScholarDigital Library
- P. C. Van Oorschot and M. J. Wiener. On Diffie-Hellman key agreement with short exponents. In Eurocrypt, 1996. Google ScholarDigital Library
- D. Wagner and B. Schneier. Analysis of the SSL 3.0 protocol. In 2nd Usenix Workshop on Electronic Commerce, 1996. Google ScholarDigital Library
- J. Wagnon. SSL profiles part 5: SSL options, 2013. https://devcentral.f5.com/articles/ssl-profiles-part-5-ssl-options.Google Scholar
- P. Zimmermann et al. GMP-ECM, 2012. https://gforge.inria.fr/projects/ecm.Google Scholar
- APEX active/passive exfiltration. Media leak, Aug. 2009. http://www.spiegel.de/media/media-35671.pdf.Google Scholar
- Fielded capability: End-to-end VPN SPIN 9 design review. Media leak. http://www.spiegel.de/media/media-35529.pdf.Google Scholar
- FY 2013 congressional budget justification. Media leak. http://cryptome.org/2013/08/spy-budget-fy13.pdf.Google Scholar
- GALLANTWAVE@scale. Media leak. http://www.spiegel.de/media/media-35514.pdf.Google Scholar
- Innov8 experiment profile. Media leak. http://www.spiegel.de/media/media-35509.pdf.Google Scholar
- Intro to the VPN exploitation process. Media leak, Sept. 2010. http://www.spiegel.de/media/media-35515.pdf.Google Scholar
- LONGHAUL -- WikiInfo. Media leak. http://www.spiegel.de/media/media-35533.pdf.Google Scholar
- POISONNUT -- WikiInfo. Media leak. http://www.spiegel.de/media/media-35519.pdf.Google Scholar
- SIGINT strategy. Media leak. http://www.nytimes.com/interactive/2013/11/23/us/politics/23nsa-sigint-strategy-document.html.Google Scholar
- SPIN 15 VPN story. Media leak. http://www.spiegel.de/media/media-35522.pdf.Google Scholar
- TURMOIL/APEX/APEX high level description document. Media leak. http://www.spiegel.de/media/media-35513.pdf.Google Scholar
- TURMOIL IPsec VPN sessionization. Media leak, Aug. 2009. http://www.spiegel.de/media/media-35528.pdf.Google Scholar
- TURMOIL VPN processing. Media leak, Oct. 2009. http://www.spiegel.de/media/media-35526.pdf.Google Scholar
- VALIANTSURF (VS): Capability levels. Media leak. http://www.spiegel.de/media/media-35517.pdf.Google Scholar
- VALIANTSURF -- WikiInfo. Media leak. http://www.spiegel.de/media/media-35527.pdf.Google Scholar
- VPN SigDev basics. Media leak. http://www.spiegel.de/media/media-35520.pdf.Google Scholar
- What your mother never told you about SIGDEV analysis. Media leak. http://www.spiegel.de/media/media-35551.pdf.Google Scholar
Index Terms
- Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
Recommendations
Imperfect forward secrecy: how Diffie-Hellman fails in practice
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. First, we present Logjam, a novel flaw in TLS that lets a man-in-the-middle downgrade connections to "...
Certificateless Broadcast Signcryption with Forward Secrecy
CIS '11: Proceedings of the 2011 Seventh International Conference on Computational Intelligence and SecurityCertificate less cryptography achieves the best of the two worlds: it inherits from identity-based techniques a solution to the certificate management problem in public-key encryption, whilst removing the secret key escrow functionality inherent to the ...
Kleptography: using cryptography against cryptography
EUROCRYPT'97: Proceedings of the 16th annual international conference on Theory and application of cryptographic techniquesThe notion of a Secretly Embedded Trapdoor with Universal Protection (SETUP) has been recently introduced. In this paper we extend the study of stealing information securely and subliminally from black-box cryptosystems. The SETUP mechanisms presented ...
Comments