Editing Diffie–Hellman key exchange (section)

=== Practical attacks on Internet traffic ===
The [[General number field sieve|number field sieve]] algorithm, which is generally the most effective in solving the [[discrete logarithm problem]], consists of four computational steps. The first three steps only depend on the order of the group G, not on the specific number whose finite log is desired.<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}}</ref> It turns out that much Internet traffic uses one of a handful of groups that are of order 1024&nbsp;bits or less.<ref name=imperfectfs/> By [[precomputing]] the first three steps of the number field sieve for the most common groups, an attacker need only carry out the last step, which is much less computationally expensive than the first three steps, to obtain a specific logarithm. The [[Logjam (computer security)|Logjam]] attack used this vulnerability to compromise a variety of Internet services that allowed the use of groups whose order was a 512-bit prime number, so called [[export of cryptography|export grade]]. The authors needed several thousand CPU cores for a week to precompute data for a single 512-bit prime. Once that was done, individual logarithms could be solved in about a minute using two 18-core Intel Xeon CPUs.<ref name=imperfectfs/>

As estimated by the authors behind the Logjam attack, the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would cost on the order of $100 million, well within the budget of a large national [[intelligence agency]] such as the U.S. [[National Security Agency]] (NSA). The Logjam authors speculate that precomputation against widely reused 1024-bit DH primes is behind claims in [[2010s global surveillance disclosures|leaked NSA documents]] that NSA is able to break much of current cryptography.<ref name=imperfectfs/>

To avoid these vulnerabilities, the Logjam authors recommend use of [[elliptic curve cryptography]], for which no similar attack is known. Failing that, they recommend that the order, ''p'', of the Diffie–Hellman group should be at least 2048&nbsp;bits. They estimate that the pre-computation required for a 2048-bit prime is 10<sup>9</sup> times more difficult than for 1024-bit primes.<ref name="imperfectfs">{{cite web|url=https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf |archive-url=https://web.archive.org/web/20150906213656/https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf |archive-date=2015-09-06 |url-status=live|title=Imperfect Forward Secrecy: How Diffie–Hellman Fails in Practice|last1=Adrian|first1=David|last2=Bhargavan|first2=Karthikeyan|date=October 2015|last3=Durumeric|first3=Zakir|last4=Gaudry|first4=Pierrick|last5=Green|first5=Matthew|last6=Halderman|first6=J. Alex|last7=Heninger|first7=Nadia|last8=Springall|first8=Drew|last9=Thomé|first9=Emmanuel|display-authors=1|last10=Valenta|first10=Luke|last11=VanderSloot|first11=Benjamin|last12=Wustrow|first12=Eric|last13=Zanella-Béguelin|first13=Santiago|last14=Zimmermann|first14=Paul}}</ref>