Diffie–Hellman key exchange
Diffie–Hellman (DH) key exchange[nb 1] is a mathematical method of securely generating a symmetric cryptographic key over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman.
[1][2] DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography.
However, research published in October 2015 suggests that the parameters in use for many DH Internet applications at that time are not strong enough to prevent compromise by very well-funded attackers, such as the security services of some countries.
[3] The scheme was published by Whitfield Diffie and Martin Hellman in 1976,[2] but in 1997 it was revealed that James H. Ellis,[4] Clifford Cocks, and Malcolm J. Williamson of GCHQ, the British signals intelligence agency, had previously shown in 1969[5] how public-key cryptography could be achieved.
[6] Although Diffie–Hellman key exchange itself is a non-authenticated key-agreement protocol, it provides the basis for a variety of authenticated protocols, and is used to provide forward secrecy in Transport Layer Security's ephemeral modes (referred to as EDH or DHE depending on the cipher suite).
I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography.
Bringing the analogy back to a real-life exchange using large numbers rather than colors, this determination is computationally expensive.
The simplest and the original implementation,[2] later formalized as Finite Field Diffie–Hellman in RFC 7919,[9] of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. To guard against potential vulnerabilities, it is recommended to use prime numbers of at least 2048 bits in length.
This increases the difficulty for an adversary attempting to compute the discrete logarithm and compromise the shared secret.
Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel.
Here is a more general description of the protocol:[10] Both Alice and Bob are now in possession of the group element gab = gba, which can serve as the shared secret key.
The group G satisfies the requisite condition for secure communication as long as there is no efficient algorithm for determining gab given g, ga, and gb.
The supersingular isogeny key exchange is a Diffie–Hellman variant that was designed to be secure against quantum computers, but it was broken in July 2022.
In 1997 a kind of triple DH was proposed by Simon Blake-Wilson, Don Johnson, Alfred Menezes in 1997,[13] which was improved by C. Kudla and K. G. Paterson in 2005[14] and shown to be secure.
For more of such details as well as other improvements like side channel protection or explicit key confirmation, as well as early messages and additional password authentication, see e.g.
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.
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.
A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack.
The 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.
The 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 grade.
The authors needed several thousand CPU cores for a week to precompute data for a single 512-bit prime.
[3] 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).
[3] To avoid these vulnerabilities, the Logjam authors recommend use of elliptic curve cryptography, for which no similar attack is known.
When Alice and Bob share a password, they may use a password-authenticated key agreement (PK) form of Diffie–Hellman to prevent man-in-the-middle attacks.
One simple scheme is to compare the hash of s concatenated with the password calculated independently on both ends of channel.
This is largely for historical and commercial reasons,[citation needed] namely that RSA Security created a certificate authority for key signing that became Verisign.
