Logjam (computer security)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Logjam is a security vulnerability against a Diffie–Hellman key exchange ranging from 512-bit (US export-grade) to 1024-bit keys.[1] It was discovered by a group of computer scientists and publicly reported on May 20, 2015.[2][3][4]


Diffie–Hellman key exchange depends for its security on the presumed difficulty of solving the discrete logarithm problem. The authors took advantage of the fact that the number field sieve algorithm, which is generally the most effective method for finding discrete logarithms, consists of four large computational steps, of which the first three depend only on the order of the group G, not on the specific number whose finite log is desired. If the results of the first three steps are precomputed and saved, they can be used to solve any discrete log problem for that prime group in relatively short time. This vulnerability was known as early as 1992.[5] It turns out that much Internet traffic only uses one of a handful of groups that are of order 1024-bits or less.

One approach enabled by this vulnerability that the authors demonstrated was using a man-in-the-middle network attacker to downgrade a Transport Layer Security (TLS) connection to use 512 bit DH export-grade cryptography, allowing him to read the exchanged data and inject data into the connection. It affects the HTTPS, SMTPS, and IMAPS protocols, among others. The authors needed several thousand CPU cores for a week to precompute data for a single 512-bit prime. Once that was done, however, individual logarithms could be solved in about a minute using two 18-core Intel Xeon CPUs.[6] Its CVE ID is CVE-2015-4000.[7]

The authors also estimated the feasibility of the attack against 1024 bit Diffie–Hellman primes. By design, many Diffie–Hellman implementations use the same pregenerated prime for their field. This was considered secure, since the discrete log problem is still considered hard for big-enough primes even if the group is known and reused. The researchers calculated the cost of creating logjam precomputation for one 1024-bit prime at hundreds of millions of USD, and noted that this was well within range of the FY2012 $10.5 billion U.S. Consolidated Cryptologic Program (which includes NSA). Because of the reuse of primes, generating precomputation for just one prime would break two-thirds of VPNs and a quarter of all SSH servers globally. The researchers noted that this attack fits claims in leaked NSA papers that NSA is able to break much current crypto. They recommend using primes of 2048 bits or more as a defense or switching to Elliptic curve Diffie–Hellman (ECDH).[1]


See also[edit]


  1. ^ a b "The Logjam Attack". weakdh.org. 2015-05-20. 
  2. ^ Dan Goodin (2015-05-20). "HTTPS-crippling attack threatens tens of thousands of Web and mail servers". Ars Technica. 
  3. ^ Charlie Osborne (2015-05-20). "Logjam security flaw leaves top HTTPS websites, mail servers vulnerable". ZDNet. 
  4. ^ https://www.wsj.com/articles/new-computer-bug-exposes-broad-security-flaws-1432076565
  5. ^ Whitfield Diffie, Paul C. Van Oorschot, and Michael J. Wiener "Authentication and Authenticated Key Exchanges", in Designs, Codes and Cryptography, 2, 107-125 (1992), Section 5.2, available as Appendix B to U.S. Patent 5,724,425
  6. ^ Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice" (PDF). 
  7. ^ "CVE-2015-4000". Common Vulnerabilities and Exposures List. The MITRE Corporation. 2015-05-15. 
    "The TLS protocol 1.2 and earlier, when a DHE_EXPORT ciphersuite is enabled on a server but not on a client, does not properly convey a DHE_EXPORT choice, which allows man-in-the-middle attackers to conduct cipher-downgrade attacks by rewriting a ClientHello with DHE replaced by DHE_EXPORT and then rewriting a ServerHello with DHE_EXPORT replaced by DHE, aka the 'Logjam' issue."
  8. ^ "Microsoft Security Bulletin MS15-055. Vulnerability in Schannel Could Allow Information Disclosure (3061518)". Microsoft Corporation. 2015-05-12. This security update resolves a vulnerability in Microsoft Windows that facilitates exploitation of the publicly disclosed Logjam technique, [...] The security update addresses the vulnerability by increasing the minimum allowable DHE key length to 1024 bits. 
  9. ^ https://blog.torproject.org/blog/tor-browser-452-released
  10. ^ "About the security content of OS X Yosemite v10.10.4 and Security Update 2015-005". Apple Inc. This issue, also known as Logjam, [...] was addressed by increasing the default minimum size allowed for DH ephemeral keys to 768 bits. 
  11. ^ "About the security content of iOS 8.4". Apple Inc. This issue, also known as Logjam, [...] was addressed by increasing the default minimum size allowed for DH ephemeral keys to 768 bits. 
  12. ^ "Mozilla Foundation Security Advisory 2015-70 - NSS accepts export-length DHE keys with regular DHE cipher suites". Mozilla. FIXED IN Firefox 39.0 [...] This attack [...] is known as the "Logjam Attack." This issue was fixed in NSS version 3.19.1 by limiting the lower strength of supported DHE keys to use 1023 bit primes. 
  13. ^ "Stable Channel Updates". Retrieved 6 Nov 2015. 

External links[edit]