Content deleted Content added
No edit summary |
m →Details: Expanded reference |
||
Line 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.<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|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}} 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
| |||