Content deleted Content added
Susanjenie (talk | contribs) mNo edit summary Tag: Reverted |
→See also: added Twirl, a proposed device in 2003 that could factor 1024-bit moduli |
||
| (8 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Security vulnerability in Diffie–Hellman key exchange}}
'''Logjam''' is a [[Vulnerability (computing)|security vulnerability]] in systems that use [[Diffie–Hellman key exchange]] with the same prime number. It was discovered by a team of computer scientists and publicly reported on May 20, 2015.<ref name="paper">{{cite web |url=https://weakdh.org |title=The Logjam Attack |website=weakdh.org |date=2015-05-20 |access-date=2015-05-20 |archive-date=2021-03-29 |archive-url=https://web.archive.org/web/20210329172612/https://weakdh.org/ |url-status=live }}</ref> The discoverers were able to demonstrate their attack on 512-bit ([[export of cryptography from the United States|US export-grade]]) DH systems. They estimated that a state
==Details==
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 [[General number field sieve|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.<ref>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 {{US patent|5724425|Method and apparatus for enhancing software security and distributing software}}: "If ''q'' has been chosen correctly, extracting logarithms modulo ''q'' requires a precomputation proportional to <math>L(q) = e^{\sqrt{\ln q \times \ln\ln q}}</math> though after that individual logarithms can be calculated fairly quickly."</ref> 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 attack|man-in-the-middle network attacker]] to downgrade a [[Transport Layer Security]] (TLS) connection to use 512-bit DH [[export of cryptography from the United States|export-grade]] cryptography, allowing them 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.<ref>{{cite web |last1=Adrian |first1=David |last2=Bhargavan |first2=Karthikeyan |last3=Durumeric |first3=Zakir |last4=Gaudry |first4=Pierrick |last5=Green |first5=Matthew |last6=Halderman |first6=J. Alex |last7=Heninger |first7=Nadia |author7-link=Nadia Heninger |last8=Springall |first8=Drew |last9=Thomé |first9=Emmanuel |last10=Valenta |first10=Luke |last11=VanderSloot |first11=Benjamin |last12=Wustrow |first12=Eric |last13=Zanella-Béguelin |first13=Santiago |last14=Zimmermann |first14=Paul |title=Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice |url=https://weakdh.org/imperfect-forward-secrecy.pdf |date=October 2015 |access-date=2015-05-23 |archive-date=2020-02-27 |archive-url=https://web.archive.org/web/20200227111819/https://weakdh.org/imperfect-forward-secrecy.pdf |url-status=live }} Originally published in Proc. 22nd Conf. on Computers and Communications Security (CCS). Republished, CACM, Jan. 2019, pp. 106-114, with Technical Perspective, "Attaching Cryptographic Key Exchange with Precomputation", by Dan Boneh, p. 105.</ref> Its CVE ID is {{CVE|2015-4000}}.<ref name = "CVE-2015-4000">{{cite web
Line 18:
"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."</ref>
The authors also estimated the feasibility of the attack against 1024-bit Diffie–Hellman primes. By design, many Diffie–Hellman implementations use the same pre-generated [[prime number|prime]] for their field. This was considered secure, since the [[discrete
Claims on the practical implications of the attack were however disputed by security researchers Eyal Ronen and [[Adi Shamir]] in their paper "Critical Review of Imperfect Forward Secrecy".<ref>{{Cite
== Responses ==
Line 43 ⟶ 38:
| url=https://support.apple.com/HT204942
| title=About the security content of OS X Yosemite v10.10.4 and Security Update 2015-005
| date=23 January 2017
| publisher=[[Apple Inc.]]
| quote=This issue, also known as Logjam, [...] was addressed by increasing the default minimum size allowed for DH ephemeral keys to 768 bits.
Line 51 ⟶ 46:
| url=https://support.apple.com/HT204941
| title=About the security content of iOS 8.4
| date=18 August 2020
| publisher=[[Apple Inc.]]
| quote=This issue, also known as Logjam, [...] was addressed by increasing the default minimum size allowed for DH ephemeral keys to 768 bits.
Line 75 ⟶ 70:
* [[POODLE]]
* [[Server-Gated Cryptography]]
* [[TWIRL]]
== References ==
| |||