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.

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.

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

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 a secret key.

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 using Alice's static key pair and Bob's ephemeral key pair which authenticates Alice;
• one ephemeral-static DH key agreement using Bob's static key pair and Alice's ephemeral key pair which authenticates Bob;
• one ephemeral-ephemeral DH key agreement using both participants' ephemeral key pairs which provides forward secrecy^[7].

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

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.

alt="Generator g; Alice's private key ka; Alice's public key Ka = ka.g; Bob's private key kb; Bob's public key Kb = kb.g; DH shared secret: z = ka.kb.g = kb.ka.kg"> <figcaption> Badly authenticated Diffie-Hellman (BADH) </figcaption>

However, this approach is vulnerable to 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.

Correctly authenticated Diffie-Hellman

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;
• in SIGMA (Sign-and-MAC), each party sends a MAC of its own identity as well (using a secret key derived from the DH shared secret);
• in TLS v1.2 and v1.3, each party sends (in the Finished messages) a MAC of the previous handshake messages (which includes the identity of the authenticated parties in the Certificate messages).

src="/img/dh-sigma.puml"> <figcaption> Authenticated key exchange using SIGMA </figcaption>

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).

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.

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 𝒢 = { i.g : i ∈ {0, …, n - 1} }. In other words, the function f(i) = 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 = ka.g ∈ 𝒢.

This is only interesting if we are working in a 𝒢 where computing the private key ka from the public key Ka (discrete logarithm problem) is not tractable. One necessary conditions 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 = ka . Kb ∈ 𝒢;
• for Bob, it is computed as z = kb . Ka ∈ 𝒢.

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

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.

Summary

Where n is the order of the group. ∀x ∈ 𝒢, ∀y ∈ 𝒢, ∀i ∈ ℤ.

References

• RFC2631, Diffie-Hellman Key Agreement Method
• RFC5683, Password-Authenticated Key (PAK) Diffie-Hellman Exchange
• RFC7664, Dragonfly
• RFC6637, ECC in OpenPGP
• RFC5246, TLS v1.2
• RFC8446, TLS v1.3
• RFC6347, DTLS v1.2
• RFC4253, SSHv2 transport layer
• RFC5656, ECC in SSHv2 (ECDH, ECMQV and ECDSA)
• RFC8731, Curve25519 and Curve448 for SSHv2
• RFC8110, Wifi OWE (Opportunistic Wireless Encryption)
• RFC5931, EAP-PWD
• RFC8492, TLS-PWD
• RFC4306, IKEv2
• RFC4492, ECC in TLS (ECDH, ECDHE and ECDSA)
• RFC7435, Opportunistic Security
• RFC5054, TLS-SRP (Secure Remote Password)
• RFC5116, An Interface and Algorithms for Authenticated Encryption
• RFC7516, JWE (JSON Web Encryption)
• RFC7518, JWA (JSON Web Algorithms)
• RFC3370, CMS algorithms
• RFC6278, 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

Backlinks:

• Exploring security vulnerabilities in NFC digital wallets