Notes on X3DH
Published:
Updated:
Some notes on X3DH (Extended Triple Diffie-Hellman).
Table of content
Motivation
X3DH is a asynchronous variant of the triple Diffie-Hellman key exchange.
The goal is to have an asynchronous (aka non-interactive, aka zero round trip) authenticated Diffie-Hellman key exchange with interactive forward secrecy between Alice and Bob:
- Alice initiates the exchange;
- but Bob is offline.
This is used to bootstrap some asynchronous communication channel (eg. Signal) between Alice and Bob.
Context
In the synchronous case (when Alice and Bob are both online), we can achieve this using some form of authenticated Diffie-Hellmman key exchange such as:
- an ephemeral Diffie-Hellman key exchange authenticated using digital signatures;
- or a triple Diffie-Hellman key exchange (see previous post for an overview).
The latter combines three Diffie-Hellman 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 (using both participants' ephemeral key pairs).
X3DH
Overview
X3DH is an extensions of 3DH for asynchronous communications. As Bob is offline, we have to be more lenient about his ephemeral contributions: Bob cannot generate a new ephemeral (short-lived, used only once, whose private key is never persisted and erased immediately after use) contribution on the spot. Instead, Bob's ephemeral contribution is replaced with a more long-lived contribution, called a prekey (because it is contributed beforehand) keypair (pSPKB, SPKB):
- which is generated beforehand;
- whose public key SPKB is published beforehand on a server;
- whose private pSPKB is persisted by Bob.
| Key agreement | Role | 3DH (Alice/Bob) | X3DH (Alice/Bob) |
|---|---|---|---|
| DH1 | authenticates Alice | static/ephemeral | static/prekey |
| DH1 | authenticated Bob | ephemeral/static | ephemeral/static |
| DH3 | forward secrecy | ephemeral/ephemeral | ephemeral/pre-key |
| DH4 | better forward secrecy | N/A | ephemeral/one-time prekey (optional) |
This relaxes the forward secrecy guarantees provided by the key exchange. As Bob's private prekey pSPKB is persisted, it increases the risk that it may be compromised at a later time. If compromised, it may be used by an attacker to derive the agreed-upon key material for all communications established by other people to Bob with that keypair[1].
This is mitigated in three ways:
- Bob's prekey is changed periodically in order to reduce the window of exposure and the impact of a compromised pSPKB.
- Bob may additionally generate one-time prekeys (pOPKB, OPKB) and publish their public keys to the server. Each one-time prekey public key is sent only once by the server and used only once. If one is available, it is included in an additionnal (ephemeral/one-time prekey) key agreement.
- X3DH is usually followed by the Double Ratchet algorithm. As soon as Bob sends a message, he contributes a new Diffie-Hellman (ratchet) key pair and the resulting shared secret will be used for following messages.
Sequence Diagram
Keys
| Public key | Private key | Name | Lifetime |
|---|---|---|---|
| IKA | pIKA | Alice's identity key | static |
| EKA | pEKA | Alice's ephemeral key | ephemeral |
| IKB | pIKB | Bob's identity key | static |
| SKB | pSKB | Bob's signed prekey | reused but changed periodically |
| OKB | pOKB | Bob's one-time prekey | one-time use (but private key still persisted) |
Alice and Bob identity key pairs:
- static;
- used for authentication;
- used for both DH key-agreement and signing[2].
Bob's signed (DH) prekey pairs:
- kind-of ephemeral, refreshed periocially (eg. once per week, once per month);
- provides forward secrecy;
- stored on the server for offline use;
- public key signed with the Bob's identity key (pIKA).
Bob's one-time (DH) prekey pairs:
- optional (used when available);
- kind-of ephemeral (one-time, refreshed as needed);
- provides stronger forward secrecy;
- public key stored on the server for offline use.
Alice's ephemeral (DH) key pair:
- provides forward secrecy.
References
- The X3DH Key Agreement Protocol (HTML), Moxie Marlinspike, Trevor Perrin
- The X3DH Key Agreement Protocol (PDF), Moxie Marlinspike, Trevor Perrin
- The Double Ratchet Algorithm (HTML), Trevor Perrin, Moxie Marlinspike
- The Double Ratchet Algorithm (PDF), Trevor Perrin, Moxie Marlinspike
- Forward Secure Asynchronous Messaging from Puncturable Encryption, Matthew D. Green and Ian Miers (2015)
- Advanced cryptographic ratcheting, Moxie Marlinspike (2013)
- Forward Secrecy for Asynchronous Messages, Moxie Marlinspike (2013)
- Off-the-Record Messaging, Ian Goldberg and the OTR Development Team
Appendix, notations
- DH(pK1, K2), Diffie-Hellman shared-secret computation using DH private key and DH public key pK1, K2
- sign(pK, X), signature of message X with private key pK
- X || Y, concatenation
- KDF(X), key derivation
- PRF(X)
See the relevant section of the specification for more details of the impact of a compromised key. ↩︎
Elliptic-Curve key pairs may be used for either signature or Diffe-Hellman key agreement. In general, it is not safe to use the same key pair both for signature and for DH key agreement. However, X3DH uses XEdDSA and the XEdDSA spec hints that this might be safe to do this in this case:
↩︎XEdDSA enables use of a single key pair format for both elliptic curve Diffie-Hellman and signatures. In some situations it enables using the same key pair for both algorithms.
[...]
In theory, under some circumstances it is safe to use a key pair to produce signatures and also use the same key pair within certain Diffie-Hellman based protocols. In practice this is a complicated topic requiring careful analysis, and is outside the scope of the current document.