Editing Diffie–Hellman key exchange (section)

== Security and practical considerations ==
The protocol is considered secure against eavesdroppers if ''G'' and ''g'' are chosen properly. In particular, the order of the group G must be large, particularly if the same group is used for large amounts of traffic. The eavesdropper has to solve the [[Diffie–Hellman problem]] to obtain ''g''<sup>''ab''</sup>. This is currently considered difficult for groups whose order is large enough. An efficient algorithm to solve the [[discrete logarithm problem]] would make it easy to compute ''a'' or ''b'' and solve the Diffie–Hellman problem, making this and many other public key cryptosystems insecure. Fields of small characteristic may be less secure.<ref>{{cite conference | first1=Razvan | last1=Barbulescu | first2=Pierrick | last2=Gaudry | first3=Antoine | last3=Joux | first4=Emmanuel | last4=Thomé | title=A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic | series=Lecture Notes in Computer Science | book-title=Advances in Cryptology – EUROCRYPT 2014 | conference=Proceedings 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques | location=Copenhagen, Denmark | volume=8441 |year=2014 | pages=1–16 | doi=10.1007/978-3-642-55220-5_1 | isbn=978-3-642-55220-5 | url=http://hal.inria.fr/docs/00/90/90/87/PDF/article.pdf |archive-url=https://web.archive.org/web/20200322030320/https://hal.inria.fr/docs/00/90/90/87/PDF/article.pdf |archive-date=2020-03-22 |url-status=live }}</ref>

The [[Order (group theory)|order]] of ''G'' should have a large prime factor to prevent use of the [[Pohlig–Hellman algorithm]] to obtain ''a'' or ''b''. For this reason, a [[Sophie Germain prime]] ''q'' is sometimes used to calculate {{nowrap|1=''p'' = 2''q'' + 1}}, called a [[safe prime]], since the order of ''G'' is then only divisible by 2 and ''q''. Sometimes ''g'' is chosen to generate the order ''q'' subgroup of ''G'', rather than ''G'', so that the [[Legendre symbol]] of ''g<sup>a</sup>'' never reveals the low order bit of ''a''. A protocol using such a choice is for example [[Internet Key Exchange|IKEv2]].<ref>{{cite news |title=RFC 4306 Internet Key Exchange (IKEv2) Protocol |publisher=Internet Engineeringrg/web/20150107073645/http://www.ietf.org/rfc/rfc4306.txt }}</ref>

The generator ''g'' is often a small integer such as 2. Because of the [[random self-reducibility]] of the discrete logarithm problem a small ''g'' is equally secure as any other generator of the same group.

If Alice and Bob use [[random number generator]]s whose outputs are not completely random and can be predicted to some extent, then it is much easier to eavesdrop.

In the original description, the Diffie–Hellman exchange by itself does not provide [[authentication]] of the communicating parties and can be vulnerable to a [[man-in-the-middle attack]].
Mallory (an active attacker executing the man-in-the-middle attack) may establish two distinct key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing her to decrypt, then re-encrypt, the messages passed between them. Note that Mallory must be in the middle from the beginning and continuing to be so, actively decrypting and re-encrypting messages every time Alice and Bob communicate. If she arrives after the keys have been generated and the encrypted conversation between Alice and Bob has already begun, the attack cannot succeed. If she is ever absent, her previous presence is then revealed to Alice and Bob. They will know that all of their private conversations had been intercepted and decoded by someone in the channel. In most cases it will not help them get Mallory's private key, even if she used the same key for both exchanges.

A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. Variants of Diffie–Hellman, such as [[Station-to-Station protocol|STS protocol]], may be used instead to avoid these types of attacks.

=== Denial-of-service attack ===

A [[Common Vulnerabilities and Exposures|CVE]] released in 2021 (''[https://nvd.nist.gov/vuln/detail/CVE-2002-20001 CVE-2002-20001]'') disclosed a [[denial-of-service attack]] (DoS) against the protocol variants use ephemeral keys, called D(HE)at attack.<ref name=dheatattack>{{cite journal|last1=Pfeiffer|first1=Szilárd|last2=Tihanyi|first2=Norbert|date=25 December 2023|title=D(HE)at: A Practical Denial-of-Service Attack on the Finite Field Diffie-Hellman Key Exchange|journal=[[IEEE Access]]|volume=12|pages=957–980|doi=10.1109/ACCESS.2023.3347422|doi-access=free}}</ref> The attack exploits that the Diffie–Hellman key exchange allows attackers to send arbitrary numbers that are actually not public keys, triggering expensive modular exponentiation calculations on the victim's side. Another CVEs released  disclosed that the Diffie–Hellman key exchange implementations may use long private exponents  (''[https://nvd.nist.gov/vuln/detail/CVE-2022-40735 CVE-2022-40735]'') that arguably make modular exponentiation calculations unnecessarily expensive<ref name="Oorschot Wiener 1996">{{cite book|last1=van Oorschot|first1=P.C.|last2=Wiener|first2=M.J.|date=1996|title=Advances in Cryptology — EUROCRYPT '96|chapter=On Diffie-Hellman Key Agreement with Short Exponents|series=Lecture Notes in Computer Science |volume=1070 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-68339-9_29|url-status=live|publication-date=2001|publisher=Springer, Berlin, Heidelberg|pages=332–343|doi=10.1007/3-540-68339-9_29|isbn=978-3-540-61186-8 |archive-url=https://web.archive.org/web/20230219191210/https://link.springer.com/chapter/10.1007/3-540-68339-9_29|archive-date=2023-02-19}}</ref> or may unnecessary check peer's public key (''[https://nvd.nist.gov/vuln/detail/CVE-2024-41996 CVE-2024-41996]'') has similar resource requirement as key calculation using a long exponent.<ref>{{cite web |last1=Elaine |first1=Barker |last2=Lily |first2=Chen |last3=Allen |first3=Roginsky |last4=Apostol |first4=Vassilev |last5=Richard |first5=Davis |title=Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography |url=https://csrc.nist.gov/pubs/sp/800/56/a/r3/final |publisher=National Institute of Standards and Technology|doi=10.6028/NIST.SP.800-56Ar3|doi-access=free|publication-date=2018}}</ref> An attacker can exploit both vulnerabilities together.

=== 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>

=== Security against quantum computers ===
[[Quantum computing|Quantum computers]] can break public-key cryptographic schemes, such as RSA, finite-field DH and elliptic-curve DH key-exchange protocols, using [[Shor's algorithm]] for solving the [[Integer factorization|factoring problem]], the [[Discrete logarithm|discrete logarithm problem]], and the period-finding problem. A [[Post-Quantum Extended Diffie–Hellman|post-quantum variant of Diffie-Hellman algorithm]] was proposed in 2023, and relies on a combination of the quantum-resistant CRYSTALS-Kyber protocol, as well as the old elliptic curve [[X25519]] protocol. A quantum Diffie-Hellman key-exchange protocol that relies on a [[Quantum cryptography|quantum one-way function]], and its security relies  on  fundamental principles of quantum mechanics has also been proposed in the literature.<ref>{{Cite journal |last=Nikolopoulos |first=Georgios M. |date=2025-01-16 |title=Quantum Diffie–Hellman key exchange |url=https://pubs.aip.org/aip/apq/article/2/1/016107/3331640/Quantum-Diffie-Hellman-key-exchange |journal=APL Quantum |volume=2 |issue=1 |pages=016107 |doi=10.1063/5.0242473 |issn=2835-0103|arxiv=2501.09568 }}</ref>