Logjam (computer security): Difference between revisions
a few words on discovery of the exploit |
GreenC bot (talk | contribs) Move 1 url. Wayback Medic 2.5 per WP:URLREQ#zdnet.com |
||
(99 intermediate revisions by 68 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Security vulnerability in Diffie–Hellman key exchange}} |
|||
'''Logjam''' is a [[security exploit]] against [[export of cryptography from the United States|US export-grade]] 512-bit [[Diffie–Hellman key exchange|Diffie–Hellman key exchange]] cryptographic algorithm discovered by a group of computer scientists and publicly reported on May 20, 2015.<ref>{{cite web |url=https://weakdh.org |title=The Logjam Attack |website=weakdh.org |date=2015-05-20}}</ref><ref>{{cite web |url=http://arstechnica.com/security/2015/05/https-crippling-attack-threatens-tens-of-thousands-of-web-and-mail-servers/ |title=HTTPS-crippling attack threatens tens of thousands of Web and mail servers |author=Dan Goodin |publisher=[[Ars Technica]] |date=2015-05-20}}</ref><ref>{{cite web |url=http://phoronix.com/scan.php?page=news_item&px=HTTPS-Logjam-Vulnerability |title=Another HTTPS Vulnerability Rattles The Internet |author=Eric Griffith |publisher=[[Phoronix]] |date=2015-05-20}}</ref> |
|||
'''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-level attacker could do so for 1024-bit systems, then widely used, thereby allowing decryption of a significant fraction of Internet traffic. They recommended upgrading to at least 2048 bits for shared prime systems.<ref>{{cite web |url=https://arstechnica.com/security/2015/05/https-crippling-attack-threatens-tens-of-thousands-of-web-and-mail-servers/ |title=HTTPS-crippling attack threatens tens of thousands of Web and mail servers |author=Dan Goodin |website=[[Ars Technica]] |date=2015-05-20 |access-date=2022-04-30 |archive-date=2017-05-19 |archive-url=https://web.archive.org/web/20170519130937/https://arstechnica.com/security/2015/05/https-crippling-attack-threatens-tens-of-thousands-of-web-and-mail-servers/ |url-status=live }}</ref><ref>{{cite news |url=https://www.zdnet.com/article/logjam-security-flaw-leaves-tens-of-thousands-of-https-websites-vulnerable/ |title=Logjam security flaw leaves top HTTPS websites, mail servers vulnerable |author=Charlie Osborne |work=[[ZDNet]] |date=2015-05-20 |access-date=2015-05-23 |archive-date=2015-05-23 |archive-url=https://web.archive.org/web/20150523004129/http://www.zdnet.com/article/logjam-security-flaw-leaves-tens-of-thousands-of-https-websites-vulnerable/ |url-status=live }}</ref><ref>{{cite news|url=https://www.wsj.com/articles/new-computer-bug-exposes-broad-security-flaws-1432076565|title=New Computer Bug Exposes Broad Security Flaws|work=The Wall Street Journal|first=Jennifer|last=Valentino-DeVries|date=2015-05-19|url-access=subscription|access-date=2022-04-30|archive-date=2022-02-24|archive-url=https://web.archive.org/web/20220224011050/https://www.wsj.com/articles/new-computer-bug-exposes-broad-security-flaws-1432076565|url-status=live}}</ref> |
|||
==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 |
|||
| title = CVE-2015-4000 |
|||
| publisher = The MITRE Corporation |
|||
| work = Common Vulnerabilities and Exposures List |
|||
| date = 2015-05-15 |
|||
| url = https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2015-4000 |
|||
| access-date = 2015-06-16 |
|||
| archive-date = 2015-08-11 |
|||
| archive-url = https://web.archive.org/web/20150811065219/http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2015-4000 |
|||
| url-status = live |
|||
}} <br/> |
|||
"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 logarithm 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 [[VPN]]s and a quarter of all [[Secure Shell|SSH]] servers globally. The researchers noted that this attack fits claims in leaked NSA papers that NSA is able to break much current cryptography. They recommend using primes of 2048 bits or more as a defense or switching to [[elliptic-curve Diffie–Hellman]] (ECDH).<ref name="paper" /> |
|||
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 web | url=http://www.wisdom.weizmann.ac.il/~eyalro/RonenShamirDhReview.pdf | first1=Eyal | last1=Ronen | first2=Adi | last2=Shamir | title=Critical Review of Imperfect Forward Secrecy | date=October 2015 | journal= | access-date=2022-04-30 | archive-date=2021-12-11 | archive-url=https://web.archive.org/web/20211211100114/https://www.wisdom.weizmann.ac.il/~eyalro/RonenShamirDhReview.pdf | url-status=live }}</ref> |
|||
== Responses == |
|||
* On May 12, 2015, Microsoft released a patch for [[Internet Explorer]].<ref>{{cite web |
|||
| url=https://technet.microsoft.com/en-us/library/security/ms15-055.aspx |
|||
| title=Microsoft Security Bulletin MS15-055. Vulnerability in Schannel Could Allow Information Disclosure (3061518) |
|||
| date=2015-05-12 |
|||
| publisher=[[Microsoft Corporation]] |
|||
| quote=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. |
|||
| access-date=2015-07-02 |
|||
| archive-date=2015-07-03 |
|||
| archive-url=https://web.archive.org/web/20150703021850/https://technet.microsoft.com/en-us/library/security/ms15-055.aspx |
|||
| url-status=live |
|||
}}</ref> |
|||
* On June 16, 2015, the [[Tor Project]] provided a patch for Logjam to the [[Tor Browser]].<ref>{{cite web|url=https://blog.torproject.org/blog/tor-browser-452-released|title=Tor Browser 4.5.2 is released|first=Mike|last=Perry|date=2015-06-16|publisher=The Tor Project|access-date=2015-06-20|archive-date=2015-06-20|archive-url=https://web.archive.org/web/20150620224433/https://blog.torproject.org/blog/tor-browser-452-released|url-status=live}}</ref> |
|||
* On June 30, 2015, [[Apple Inc.|Apple]] released a patch for both [[OS X Yosemite]] and [[iOS 8]] operating system.<ref> |
|||
{{cite web |
|||
| 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. |
|||
}} |
|||
</ref><ref> |
|||
{{cite web |
|||
| 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. |
|||
}} |
|||
</ref> |
|||
* On June 30, 2015, the [[Mozilla]] project released a fix for the [[Firefox]] browser.<ref>{{cite web |
|||
| title=Mozilla Foundation Security Advisory 2015-70 - NSS accepts export-length DHE keys with regular DHE cipher suites |
|||
| publisher=[[Mozilla]] |
|||
| url=https://www.mozilla.org/en-US/security/advisories/mfsa2015-70/ |
|||
| quote=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. |
|||
| access-date=2015-07-04 |
|||
| archive-date=2015-07-07 |
|||
| archive-url=https://web.archive.org/web/20150707033751/https://www.mozilla.org/en-US/security/advisories/mfsa2015-70/ |
|||
| url-status=live |
|||
}}</ref> |
|||
* On September 1, 2015, Google released a fix for the [[Google Chrome|Chrome]] browser.<ref>{{cite web|url=http://googlechromereleases.blogspot.com/2015/09/stable-channel-update.html|title=Stable Channel Updates|website=Chrome Releases|first=Vivian|last=Zhi|date=2015-09-01|accessdate=2015-11-06|archive-date=2015-10-16|archive-url=https://web.archive.org/web/20151016103016/http://googlechromereleases.blogspot.com/2015/09/stable-channel-update.html|url-status=live}}</ref> |
|||
* On December 6, 2017, [[Internet Engineering Task Force|IETF]] published {{IETF RFC|8270}} called "Increase the Secure Shell Minimum Recommended Diffie-Hellman Modulus Size to 2048 Bits". |
|||
== See also == |
== See also == |
||
Line 9: | Line 72: | ||
== References == |
== References == |
||
{{reflist}} |
{{reflist|40em}} |
||
==External links== |
==External links== |
||
* [https://weakdh.org/ The Logjam Attack] |
* [https://weakdh.org/ The Logjam Attack] |
||
* [https://www.scottaaronson.com/blog/?p=2293 NSA in P/poly: The Power of Precomputation-Shtetl Optimizedl] |
|||
{{SSL/TLS}} |
{{SSL/TLS}} |
||
[[Category:Web security exploits]] |
[[Category:Web security exploits]] |
||
[[Category: |
[[Category:Attacks on public-key cryptosystems]] |
||
[[Category: |
[[Category:2015 in computing]] |
||
[[Category:2015 in computer science]] |
|||
[[Category:Transport Layer Security]] |
[[Category:Transport Layer Security]] |
||
[[Category:Computational hardness assumptions]] |
|||
{{crypto-stub}} |
|||
{{internet-stub}} |
Latest revision as of 16:17, 5 July 2024
Logjam is a 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.[1] The discoverers were able to demonstrate their attack on 512-bit (US export-grade) DH systems. They estimated that a state-level attacker could do so for 1024-bit systems, then widely used, thereby allowing decryption of a significant fraction of Internet traffic. They recommended upgrading to at least 2048 bits for shared prime systems.[2][3][4]
Details
[edit]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 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.[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 pre-generated prime for their field. This was considered secure, since the discrete logarithm 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 cryptography. They recommend using primes of 2048 bits or more as a defense or switching to elliptic-curve Diffie–Hellman (ECDH).[1] 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".[8]
Responses
[edit]- On May 12, 2015, Microsoft released a patch for Internet Explorer.[9]
- On June 16, 2015, the Tor Project provided a patch for Logjam to the Tor Browser.[10]
- On June 30, 2015, Apple released a patch for both OS X Yosemite and iOS 8 operating system.[11][12]
- On June 30, 2015, the Mozilla project released a fix for the Firefox browser.[13]
- On September 1, 2015, Google released a fix for the Chrome browser.[14]
- On December 6, 2017, IETF published RFC 8270 called "Increase the Secure Shell Minimum Recommended Diffie-Hellman Modulus Size to 2048 Bits".
See also
[edit]References
[edit]- ^ a b "The Logjam Attack". weakdh.org. 2015-05-20. Archived from the original on 2021-03-29. Retrieved 2015-05-20.
- ^ Dan Goodin (2015-05-20). "HTTPS-crippling attack threatens tens of thousands of Web and mail servers". Ars Technica. Archived from the original on 2017-05-19. Retrieved 2022-04-30.
- ^ Charlie Osborne (2015-05-20). "Logjam security flaw leaves top HTTPS websites, mail servers vulnerable". ZDNet. Archived from the original on 2015-05-23. Retrieved 2015-05-23.
- ^ Valentino-DeVries, Jennifer (2015-05-19). "New Computer Bug Exposes Broad Security Flaws". The Wall Street Journal. Archived from the original on 2022-02-24. Retrieved 2022-04-30.
- ^ 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 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 though after that individual logarithms can be calculated fairly quickly."
- ^ 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). Archived (PDF) from the original on 2020-02-27. Retrieved 2015-05-23. 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.
- ^ "CVE-2015-4000". Common Vulnerabilities and Exposures List. The MITRE Corporation. 2015-05-15. Archived from the original on 2015-08-11. Retrieved 2015-06-16.
"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." - ^ Ronen, Eyal; Shamir, Adi (October 2015). "Critical Review of Imperfect Forward Secrecy" (PDF). Archived (PDF) from the original on 2021-12-11. Retrieved 2022-04-30.
- ^ "Microsoft Security Bulletin MS15-055. Vulnerability in Schannel Could Allow Information Disclosure (3061518)". Microsoft Corporation. 2015-05-12. Archived from the original on 2015-07-03. Retrieved 2015-07-02.
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.
- ^ Perry, Mike (2015-06-16). "Tor Browser 4.5.2 is released". The Tor Project. Archived from the original on 2015-06-20. Retrieved 2015-06-20.
- ^
"About the security content of OS X Yosemite v10.10.4 and Security Update 2015-005". Apple Inc. 23 January 2017.
This issue, also known as Logjam, [...] was addressed by increasing the default minimum size allowed for DH ephemeral keys to 768 bits.
- ^
"About the security content of iOS 8.4". Apple Inc. 18 August 2020.
This issue, also known as Logjam, [...] was addressed by increasing the default minimum size allowed for DH ephemeral keys to 768 bits.
- ^ "Mozilla Foundation Security Advisory 2015-70 - NSS accepts export-length DHE keys with regular DHE cipher suites". Mozilla. Archived from the original on 2015-07-07. Retrieved 2015-07-04.
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.
- ^ Zhi, Vivian (2015-09-01). "Stable Channel Updates". Chrome Releases. Archived from the original on 2015-10-16. Retrieved 2015-11-06.