Introduction to the Diffie-Hellman key exchange

The Diffie-Hellman (DH) key exchange (and variants thereof) is widely used in many protocols (such as TLS, SSH, IKE (IPSec), Signal, etc.) to bootstrap some symmetric key material which may then be used to secure communication channel between two parties. This introduction focuses on the different ways the DH key exchange is used in practice in several protocols (especially TLS) and the impact of these different approaches on the security. This is intended as a prelude for the upcoming next episodes about how TLS works.

Prerequisites: public key vs. private key vs. secret key key, encryption, MAC, digital signature, cryptographic hash.

Concepts introduced: Diffie-Hellman key exchange, anonymous vs. authenticated Diffie-Hellman key exchange, ephemeral vs. static Diffie-Hellman key pairs/exchange, triple Diffie-Hellman key exchange (3DH), forward secrecy, key compromise impersonation (KCI), identity misbinding attack, unknown key-share attack.

Update 2024-11-12: add some notes about using RSA-based key exchange.

After a quick overview, we will present the unauthenticated DH key exchange. The downside of the unauthenticated DH key exchange is that the parties have no assurance that they are actually communicating with the intended party: this approach only protects against passive eavesdroppers but not against active attackers. and it is therefore usually desirable to authenticate at least one participant. We will see several approaches to integrating some authentication (for either or both parties) in the key exchange:

• one party may be authenticated using a static DH key pair bound to its identity;
• one party may be authenticated by including a digital signature in the key exchange;
• both parties may be mutually authenticated by including a shared secret in the key exchange.

Table of content

Overview

Motivation

Let us assume that Alice and Bob want to communicate over the network. They would like to protecte themselves from eavesdroppers (Eve^[1]) listening to their communications (confidentiality) and active attackers (Mallory^[2]) tampering with their communications (data integrity). They could use encryption and Message Authentication Codes (MACs) in order to provide confidentiality and data integrity^[3] respectively. In order to do that, they need to agree on some shared keys to use (for the encryption and/or MAC).

Obviously, Alice cannot simply send these shared keys to Bob in clear text over the network: these secrets keys would not be secret at all. An attacker could eavesdrop them and use them to decrypt the communications or tamper with them. Instead, Alice and Bob would need a method to agree on some shared keys without sending these keys (or any other informations which could be used to compute them) in clear text over the network.

Summary

The Diffie-Hellman key agreement is a method for two parties to agree on a shared secret without revealing this shared secret to eavesdroppers.

How? The two parties exchange Diffie-Hellman public keys and each party then uses its own Diffie-Hellman private key with the other party Diffie-Hellman public key to compute the same shared secret (the Diffie-Hellman shared secret). This shared secret is not revealed to eavesdroppers because even though the eavesdropper can observe the DH public keys, he does not know any of the two DH private keys: he therefore cannot compute the DH shared secret.

The following diagram gives an idea about how this works. Some details on these computations are given in appendix.

Why? The two parties can use this shared secret to secure some communication by deriving^[4] some symmetric key material from the shared secret.

key_materiel = KDF(z)

key_materiel = KDF(z, some_context)

Unauthenticated Diffie-Hellman key exchange

The unauthenticated (anonymous) Diffie-Hellman key exchange uses ephemeral DH key pairs for each party: each party generates a new Diffie-Hellman (public/private) key pair for each Diffie-Hellman key exchange. This is called ephemeral-ephemeral Diffie-Hellman.

Explanation:

1. each party generates a fresh (ephemeral) DH key pair;
2. the two parties exchange their ephemeral DH public keys;
3. each party uses its ephemeral DH private key and the other party DH public key to compute the same shared secret (the DH shared secret);
4. this shared secret can be used to derive^[4:1] key material in order to establish a secure communication channel.

Each party can compute the same shared secret using its private DH key and the other party public DH key:

shared_secret_between_alice_and_bob = DH(alice_private_key, bob_public_key)
                                    = DH(bob_private_key, alice_public_key)

A passive attacker, only knows the DH public keys but not the DH private keys: he cannot compute the DH shared secret and the key material.

Warning: vulnerable to active attack (unauthenticated)

One major downside of using an unauthenticated DH key exchange is that it is vulnerable to active attacks. As the exchange is not authenticated, one participant cannot be sure that the party he has been conducting a DH key agreement with is the one he is really intending to communicate with. By intercepting the key exchange, an active attacker may impersonate one party, intercept the communications, etc.

In the following sections, we will cover how to authenticate a Diffie-Hellman key exchange using some long-term secret. This may be a static DH private key, a signing private key, a pre-shared key (PSK) or a passphrase.

Authenticating the Diffie-Hellman key exchange using a static Diffie-Hellman key

Vulnerable one-way authentication using ephemeral-static Diffie-Hellman key exchange

A party (here Bob) can authenticate itself by using a static DH key pair bound to its identity.

If only one party is authenticated this way, the other party uses an ephemeral DH key pair: this is ephemeral-static Diffie-Hellman (DHES). If each party uses a (different) static DH key pair, this is static-static Diffie-Hellman (discussed below).

Replay Attack on static Diffie-Hellman key exchange

In the previous diagram, an attacker could make a replay attack on the party using the static DH key pair.

This can be fixed by having this party send a random nonce and including this nonce to derive the key material.

Mutual authentication using static-static Diffie-Hellman key exchange

If each party uses a static a DH key pair, we get static-static Diffie-Hellman. In this case, the DH shared secret is always the same between the two parties. However, we don't want to reuse the same key material as the result of different key exchanges between the same pair of parties. In order prevent this, the parties can exchange nonces; then, they derive the key material from the DH shared secret and the nonces.

Warning: key compromise impersonation (KCI)

In all these key exchange authentication methods, Alice authenticates herself using some authentication secret (either a static DH private key, a signing private key, a PSK or a passphrase). If an attacker manages to obtain Alice's authentication secret, this attacker can impersonate Alice.

In static-static DH^[5], if the attacker manages to get Alice's private DH key, he can in addition impersonate anyone else when they are talking to Alice. This vulnerability is called Key Compromise Impersonation (KCI).

See KCI Attacks against TLS for a practical application in TLS.

Mutual authentication using a triple Diffie-Hellman

Another solution to provide mutual authentication is to use a triple Diffie-Hellman (3DH)^[6] key agreement. Each participant uses both a static DH key pair and an ephemeral DH key pair. They combine the DH shared secrets resulting from three DH key agreements:

• one ephemeral-static DH key agreement which authenticates Alice (using Alice's static key pair and Bob's ephemeral key pair);
• one ephemeral-static DH key agreement which authenticates Bob (using Bob's static key pair and Alice's ephemeral key pair);
• one ephemeral-ephemeral DH key agreement which provides forward secrecy^[7] (using both participants' ephemeral key pairs).

Authenticating Diffie-Hellman key exchange using digital signature

Instead of using static DH key pairs, we can use digital signatures to authenticate the DH key exchange.

Badly authenticated Diffie-Hellman key exchange using digital signatures

One simple (but broken) solution would be for each party to sign either its own ephemeral DH public key or the two DH public keys.

However, this approach is vulnerable to unknown key-share attack (alsa known as identity misbinding attacks). If Alice tries to established a mutually authenticated communications with Charlie and if Charlie is malicious (for example because it has been compromised), Charlie can trick Alice into establishing a communication with Bob instead:

• from the point of view of Alice, a mutually authenticated communication happens between Alice and Charlie;
• from the point of view of Bob, a mutually authenticated communication happens between Alice and Bob.

This attack is possible because the attacker (Charlie) is able to manipulate the handshake messages without being detected.

Better authenticated Diffie-Hellman key exchange using digital signatures

Several approaches can be used to prevent this type of manipulations from getting unnoticed:

• in the ISO/IEC IS 9798-3 key exchange protocol, the digital signature covers both ephemeral DH public keys and the recipient identity,
  • B → A: sign(Ka,Kb,A)sb
  • A → B: sign(Kb,Ka,B)sa
• in SIGMA (Sign-and-MAC), each party sends a signature of the DH public keys and the MAC of its own identity (using a secret key derived from the DH shared secret),
  • B → A: sign(Ka,Kb,A)sb, MAC(B,K)
  • A → B: sign(Kb,Ka,B)sa, MAC(A,K)
• in TLS v1.2 and v1.3, leach party sends (in the Finished messages) a MAC of the hash of all the previous handshake messages (which include the identity of the authenticated parties in the Certificate messages).

Key pair reuse

In the protocol as described in the previous diagram, the peers must not reuse the ephemeral Diffie-Hellman key pairs (each Diffie-Hellman ephemeral key pair must be used only once). If Alice reuses a Diffie-Hellman key pair, an man-in-the-middle might replay the previous messages originating from Bob as described in the following diagram (same attack previously described in the context ot a static Diffie Hellman key echange).

Because Alice reused the same Diffie-Hellman key pair and did not contribute another one-time contribution to the key exchange:

• Mallory can replay Bob's previous signature to Alice;
• Mallory can force the derivation of the previous same key material (reusing encryption key is bad);
• Mallory might be able to replay protected messages from the previous session.

If the peers exchange nonces in addition to the ephemeral Diffie-Hellman public keys (and if these nonces are integrated in the key derivation and signatures), reusing the Diffie-Hellman key pair would not completely compromise the security of the key exchange.

Authenticating the Diffie-Hellman key exchange using a shared secret

Authenticating the Diffie-Hellman key exchange using a pre-shared key

We can combine ephemeral-ephemeral Diffie-Hellman with some other secret shared, the pre-shared key (PSK), between the client and the server:

• the PSK is used to provide mutual authentication;
• ephemeral-ephemeral DH is used to provide forward secrecy with respect to the PSK.

Authenticating the Diffie-Hellman key echange using a password

Other key exchanges based on Diffie-Hellman are designed to be used with low-entropy shared secrets (such as secrets derived from a password).

Conclusion

We have seen how the DH key agreement can be used to generate key material between two parties.

It is usually desirable to authenticate either or both parties in order to protect against active attacks. Each party may be authenticated for example by:

• including a DH static key pair associated with the party's identity in the key exchange;
• including a digital signature of the key exchange.

Alternatively, mutual authentication may be achieved by including some shared secret in the key exchange.

Forward secrecy can be achieved by including an ephemeral-ephemeral DH key agreement in the key exchange.

Each party can be protected against replay attacks by contributing some ephemeral value to the key exchange:

• either an ephemeral DH key pair;
• or a random nonce which is included in the key derivation.

Appendix, encryption using Diffie-Hellman

The Diffie-Hellman key exchange protocol can be used for hybrid public-key encryption: both the Elgamal encryption (not discussed here) and the Diffie-Hellman Integrated Encryption Scheme (DHIES) are based on DH. In this context, the receiver cannot contribute any ephemeral value (which could be used to provide forward secrecy and anti-replay protection).

Diffie-Hellman Integrated Encryption Scheme

In DHES-based encryption, the sender generates an ephemeral DH key pair and derives a DH shared-secret with the recipient static DH public pair. It then derives some key material from this shared secret which might either be:

• a (secret) content encryption key (CEK) used to directly encrypt (and authenticate) the data (direct key agreement);
• a (secret) key encryption key (KEK) used to encrypt a CEK (key agreement with key wrapping).

{
    "alg":"ECDH-ES",
    "enc":"A128GCM",
    "apu":"QWxpY2U",
    "apv":"Qm9i",
    "epk": {
        "kty":"EC",
        "crv":"P-256",
        "x":"gI0GAILBdu7T53akrFmMyGcsF3n5dO7MmwNBHKW5SV0",
        "y":"SLW_xSffzlPWrHEVI30DHM_4egVwt3NQqeUD7nMFpps"
    }
}

Encryption based on static-static Diffie-Hellman

If both the sender and the receiver use static DH keys, the sender is authenticated as well (assuming that authenticated encryption is used). A nonce must be included in this case: otherwise the key material would always be the same between the same two parties.

Another advantage of this approach is that the sender can decrypt the message as well (without having to keep the CEK around).

Combining static-static and ephemeral-static Diffie-Hellman

The HPKE scheme in authenticated mode with DHKEM uses a similar approach to provide public-key authenticated encryption. Instead of using a nonce, the sender combines a static-static DH key agreement and a DHES key agreement:

• the static-static DH key agreement uses the sender's static DH key and the recipient's static DH key;
• the DHES key agreement uses a sender's ephemeral DH key and the recipient's static DH key.

The sender and the receiver both derive the key material from both DH shared secrets and the three DH public keys.

Appendix, mathematical considerations

Diffie-Hellman parameters

The two parties first agree on a finite cyclic group (𝒢, .) to use for the Diffie-Hellman exchange and a generator g ∈ 𝒢 of this group. The choice of these two parameters may be hardcoded in the protocol/implementation/configuration or could be negotiated in some way.

Let n the order of the group, we have |𝒢| = n and 𝒢 = { gⁱ : i ∈ {0, …, n - 1} }. In other words, the function f(i) = gⁱ is a bijection from {0, …, n - 1} (or equivalently ℤ/nℤ) to 𝒢.

Key generation

Summary:

• a private DH key is an element of {0, …, n - 1};
• a public DH key is an element of 𝒢;
• the generator g defines the mapping from the private key set {0, …, n - 1} to the public key set 𝒢.

For generating a DH private key, a party chooses a random integer 1 < ka < n: this value is the private key. The associated DH public key is the corresponding element of 𝒢: Ka = g^ka ∈ 𝒢.

This is only interesting if we are working in a group 𝒢 where computing the private key ka from the public key Ka (discrete logarithm problem) is not tractable. One necessary condition is for n to be large enough for a brute-force approach to be intractable.

Key agreement

Once two parties Alice and Bob have exchanged their DH public keys Ka and Kb, they can compute the same DH shared secret z:

• for Alice, it is computed as z = Kb^ka ∈ 𝒢;
• for Bob, it is computed as z = Ka^kb ∈ 𝒢.

The two parties compute the same value because Kb^ka = (g^kb)^ka = g ^kb.ka = g ^ka.kb = (g^ka)^kb = Ka^kb.

An attacker knows Ka and Kb but not ka and kb and cannot reproduce any of these two computations. In order to compute the DH shared secret z, the attacker has to solve the Computational Diffie-Hellman problem. One way to solve this problem would be to solve the discrete logarithm problem. Moreover, solving the Computational Diffie-Hellman problem is equivalent to the discrete logarithm problem for many classes of groups.

Notations Summary

Where:

• n is the order of the group;
• ∀x ∈ 𝒢;
• ∀y ∈ 𝒢;
• ∀i ∈ ℤ.

Appendix, RSA key exchange

The following diagram represents the classic RSA transport key exchange as featured in old TLS ciphersuites (RSA-Encrypted Premaster Secret).

In this scheme, the TLS client would send a premaster secret (z) to the server encrypted with the (usually static) server RSA public key^[11]:

struct {
    public-key-encrypted PreMasterSecret pre_master_secret;
} EncryptedPreMasterSecret;

struct {
    select (KeyExchangeAlgorithm) {
        case rsa:
            EncryptedPreMasterSecret;
        case dhe_dss:
        case dhe_rsa:
        case dh_dss:
        case dh_rsa:
        case dh_anon:
            ClientDiffieHellmanPublic;
    } exchange_keys;
} ClientKeyExchange;

This does not provide forward secrecy with respect to the server static RSA private key and its usage is therefore deprecated in TLS.

It is possible to get forward secrecy by using an ephemeral RSA keypair. As far as I known, this approach is not used in practice because generating RSA keys is computationally expensive.

The key exchange in the previous figure is not authenticated (and is therefore vulnerable to active attacks). As for the ephemeral Diffie-Hellman key exchange, you need to add signatures, nonces and key confirmation in order to secure against active attackers.

/* TLS 1.1 */
struct {
      select (KeyExchangeAlgorithm) {
          case diffie_hellman:
              ServerDHParams params;
              Signature signed_params;
          case rsa:                    /* Message only send when using RSA_EXPORT */
              ServerRSAParams params;  /* might be an ephemeral RSA public key */
              Signature signed_params; /* using static RSA key bound to server certificate */
      };
} ServerKeyExchange;

References

• RFC 2631, Diffie-Hellman Key Agreement Method
• RFC 5683, Password-Authenticated Key (PAK) Diffie-Hellman Exchange
• RFC 7664, Dragonfly
• RFC 6637, ECC in OpenPGP
• RFC 5246, TLS v1.2
• RFC 8446, TLS v1.3
• RFC 6347, DTLS v1.2
• RFC 4253, SSHv2 transport layer
• RFC 5656, ECC in SSHv2 (ECDH, ECMQV and ECDSA)
• RFC 8731, Curve25519 and Curve448 for SSHv2
• RFC 8110, Wifi OWE (Opportunistic Wireless Encryption)
• RFC 5931, EAP-PWD
• RFC 8492, TLS-PWD
• RFC 4306, IKEv2
• RFC 4492, ECC in TLS (ECDH, ECDHE and ECDSA)
• RFC 7435, Opportunistic Security
• RFC 5054, TLS-SRP (Secure Remote Password)
• RFC 5116, An Interface and Algorithms for Authenticated Encryption
• RFC 7516, JWE (JSON Web Encryption)
• RFC 7518, JWA (JSON Web Algorithms)
• RFC 3370, CMS algorithms
• RFC 6278, Static-Static ECDH in CMS
• Draft for Hybdrid Public Key Encryption (HPKE)
• Draft for Encrypted Client Hello (ECH)
• XML encryption
• NIST Special Publication 800-56A R2 - Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography
• NIST Special Publication 800-56A R3 - Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography
• Off-the-Record (OTR), Nikita Borisov et al
• The Noise Protocol Framework, Trevor Perrin
• WireGuard: Next Generation Kernel Network Tunnel, Jason A. Donenfeld
• Signal - The Double Ratchet Algorithm, Trevor Perrin, Moxie Marlinspike
• Signal - The X3DH Key Agreement Protocol (triple Diffie-Hellman), Moxie Marlinspike, Trevor Perrin
• Supersingular isogeny Diffie–Hellman (SIDH), Luca De Feo et al
• Cryptanalysis of the Dragonfly Key ExchangeProtoco, Dylan Clarke and Feng Hao
• On the Security of the SPEKE Password-Authenticated Key Exchange Protocol, Philip MacKenzie
• On the Provable Security of the Dragonfly Protocol, Jean Lancrenon, Marjan Škrobot
• On reusing ephemeral keys in Diffie-Hellman key agreement protocols, Alfred Menezes and Berkant Ustaoglu
• Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses, Jee Hea An
• SoK: Secure Messaging, Nik Unger and Sergej Dechand
• Key Confirmation in Key Exchange: A Formal Treatment and Implications for TLS 1.3, Marc Fischlin et al
• Authentication in Key-Exchange: Definitions, Relations and Composition, Cyprien Delpech de Saint Guilhem et al
• SIGMA: the ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and its Use in the IKE Protocols, Hugo Krawczyk
• Authentication and Authenticated Key Exchanges, Whitfield Diffie
• Modular Security Proofs for Key Agreement Protocols, Caroline Kudla, Kenneth G. Paterson
• Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, David Adrian et al
• Understanding HKDF²
• Raccoon Attack: Finding and Exploiting Most-Significant-Bit-Oracles in TLS-DH(E)

Digital signatures, non-repudiation and deniability:

• A Brief Introduction to Deniability
• Ok Google: please publish your DKIM secret keys
• Digital signatures and how to avoid them

Backlinks:

• Exploring security vulnerabilities in NFC digital wallets