Diffie–Hellman (DH) key exchangeSynonyms of Diffie–Hellman key exchange include: Diffie–Hellman–Merkle key exchange Diffie–Hellman key agreement Diffie–Hellman key establishment Diffie–Hellman key negotiation Exponential key exchange Diffie–Hellman protocol Diffie–Hellman handshake is a mathematical method of securely generating a symmetric cryptographic key over a public channel. It is named after Whitfield Diffie and Martin Hellman who published it in 1976. DH is one of the earliest practical examples of key exchange implemented within the field of cryptography.
Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier. By contrast, the Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric-key cipher.
The scheme was published by Whitfield Diffie and Martin Hellman in 1976 and named as one of Ralph Merkle's original public key protocols in 1978. The method was followed shortly after by the RSA cryptosystem, an implementation of public-key cryptography using asymmetric algorithms. In 1997 it was revealed that James H. Ellis, Clifford Cocks, and Malcolm J. Williamson of GCHQ, the British signals intelligence agency, had previously shown in 1969 how public-key cryptography could be achieved.
Diffie–Hellman is used to secure a variety of Internet services. However, research published in October 2015 suggests that the parameters in use for many DH Internet applications at that time were not strong enough to prevent compromise by very well-funded attackers, such as the security services of some countries.
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). Forward secrecy results from the use of ephemeral keys: the private keys are discarded once key agreement is complete, making them safe from later compromise. Ephemeral keys are practical because it is computationally cheap to create public-private key pairs suitable for use with Diffie-Hellman exchange.
Expired US patent 4200770 from 1977 describes the now public-domain algorithm. It credits Hellman, Diffie, and Merkle as inventors.
Name In 2006, Hellman suggested the algorithm be called Diffie–Hellman–Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography (Hellman, 2006), writing:
Description
General overview
Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for secret communication for exchanging data over a public network. An analogy illustrates the concept of public key exchange by using colors instead of very large numbers:
The process begins by having the two parties, Alice and Bob, publicly agree on an arbitrary starting color that does not need to be kept secret. In this example, the color is yellow. Each person also selects a secret color that they keep to themselves – in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from the partner with their own private color. The result is a final color mixture (yellow-brown in this case) that is identical to their partner's final color mixture.
If a third party listened to the exchange, they would only know the common color (yellow) and the first mixed colors (orange-tan and light-blue), but it would be very hard for them to find out the final secret color (yellow-brown). Bringing the analogy back to a real-life exchange using large numbers rather than colors, this determination is computationally expensive; it is impossible to compute in a practical amount of time even for modern supercomputers.
Cryptographic explanation The simplest and the original implementation, later formalized as Finite Field Diffie–Hellman in RFC 7919, 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. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to . Here is an example of the protocol, with non-secret values in , and secret values in . Alice and Bob publicly agree to use a modulus = and base = (which is a primitive root modulo 23). Alice chooses a secret integer = 4, then sends Bob = mod = mod = (in this example both and have the same value 4, but this is usually not the case) Bob chooses a secret integer = 3, then sends Alice = mod = mod = Alice computes = mod = mod = Bob computes = mod = mod = Alice and Bob now share a secret (the number 18).
Both Alice and Bob have arrived at the same values because under mod p,
More specifically,
Only a and b are kept secret. All the other values – p, g, ga mod p, and gb mod p – are sent in the clear. The strength of the scheme comes from the fact that gab mod p = gba mod p take extremely long times to compute by any known classical algorithm just from the knowledge of p, g, ga mod p, and gb mod p. Such a function that is easy to compute but hard to invert is called a one-way function. 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.
Of course, much larger values of a, b, and p would be needed to make this example secure, since there are only 23 possible results of n mod 23. However, if p is a prime of at least 600 digits, then even the fastest modern computers using the fastest known algorithm cannot find a given only g, p and ga mod p. Such a problem is called the discrete logarithm problem. The computation of ga mod p is known as modular exponentiation and can be done efficiently even for large numbers. Note that g need not be large at all, and in practice is usually a small integer (like 2, 3, ...).
Secrecy chart The chart below depicts who knows what, again with non-secret values in , and secret values in . Here Eve is an eavesdropper – she watches what is sent between Alice and Bob, but she does not alter the contents of their communications. , public (primitive root) base, known to Alice, Bob, and Eve. = , public (prime) modulus, known to Alice, Bob, and Eve. = , Alice's private key, known only to Alice. = , Bob's private key known only to Bob. = , Alice's public key, known to Alice, Bob, and Eve. = mod = , Bob's public key, known to Alice, Bob, and Eve. = mod =
+ Alice Known Unknown = = = = mod = mod = = = mod = mod = + Bob Known Unknown = = = = mod = mod = = = mod = mod = + Eve Known Unknown = = , = , =
Now is the shared secret key and it is known to both Alice and Bob, but not to Eve. Note that it is not helpful for Eve to compute , which equals + mod .
Note: It should be difficult for Alice to solve for Bob's private key or for Bob to solve for Alice's private key. If it is not difficult for Alice to solve for Bob's private key (or vice versa), then an eavesdropper, Eve, may simply substitute her own private / public key pair, plug Bob's public key into her private key, produce a fake shared secret key, and solve for Bob's private key (and use that to solve for the shared secret key). Eve may attempt to choose a public / private key pair that will make it easy for her to solve for Bob's private key.
Generalization to finite cyclic groups Here is a more general description of the protocol: Alice and Bob agree on a natural number n and a generating element g in the finite cyclic group G of order n. (This is usually done long before the rest of the protocol; g and n are assumed to be known by all attackers.) The group G is written multiplicatively. Alice picks a random natural number a with 1 < a < n, and sends the element ga of G to Bob. Bob picks a random natural number b with 1 < b < n, and sends the element gb of G to Alice. Alice computes the element of G. Bob computes the element of G.
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.
For example, the elliptic curve Diffie–Hellman protocol is a variant that represents an element of G as a point on an elliptic curve instead of as an integer modulo n. Variants using hyperelliptic curves have also been proposed. 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.
Ephemeral and/or static keys The used keys can either be ephemeral or static (long term) key, but could even be mixed, so called semi-static DH. These variants have different properties and hence different use cases. An overview over many variants and some also discussions can for example be found in NIST SP 800-56A. A basic list: ephemeral, ephemeral: Usually used for key agreement. Provides forward secrecy, but no authenticity. static, static: Would generate a long term shared secret. Does not provide forward secrecy, but implicit authenticity. Since the keys are static it would for example not protect against replay-attacks. ephemeral, static: For example, used in ElGamal encryption or Integrated Encryption Scheme (IES). If used in key agreement it could provide implicit one-sided authenticity (the ephemeral side could verify the authenticity of the static side). No forward secrecy is provided.
It is possible to use ephemeral and static keys in one key agreement to provide more security as for example shown in NIST SP 800-56A, but it is also possible to combine those in a single DH key exchange, which is then called triple DH (3-DH).
Triple Diffie–Hellman (3-DH) In 1997 a kind of triple DH was proposed by Simon Blake-Wilson, Don Johnson and Alfred Menezes, which was improved by C. Kudla and K. G. Paterson in 2005 and shown to be secure.
The long term secret keys of Alice and Bob are denoted by a and b respectively, with public keys A and B, as well as the ephemeral key pairs (x, X) and (y, Y). Then protocol is: + Triple Diffie–Hellman (3-DH) protocol Alice () Bob () The long term public keys need to be transferred somehow. That can be done beforehand in a separate, trusted channel, or the public keys can be encrypted using some partial key agreement to preserve anonymity. 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. US patent "Advanced modular handshake for key agreement and optional authentication".
Extended Triple Diffie–Hellman (X3DH) X3DH was initially proposed as part of the Double Ratchet Algorithm used in the Signal Protocol. The protocol offers forward secrecy and cryptographic deniability. It operates on an elliptic curve.