Extended Triple Diffie-Hellman (X3DH) Protocol
LATEST POSTINFOSEC BASICS
Extended Triple Diffie-Hellman (X3DH) Protocol
Purpose:
X3DH is designed to allow two parties (commonly called Alice and Bob) to establish a shared secret even when they are not online at the same time. It achieves this by leveraging both long-term and short-term keys that are published to a server.
How It Works:
Prepublished Keys:
Identity Key: Each user publishes a long-term public key that serves as their identity.
Prekey: In addition to the identity key, each user publishes one or more ephemeral (or semi-ephemeral) prekeys to the server.
Signature: The prekeys are signed (typically with an elliptic-curve DSA) so that their authenticity can be verified against the identity key.
Key Agreement Process:
When Alice wants to send a message to Bob:Fetching Keys:
Alice retrieves Bob’s identity key and one or more of his prekeys from the server.Generating Ephemeral Key:
Alice generates her own ephemeral Diffie-Hellman key pair (a short-term key used just for this session).Multiple Diffie-Hellman Exchanges:
Instead of relying on a single Diffie-Hellman exchange (which would require both parties to be online), Alice computes several Diffie-Hellman shared secrets using different combinations of keys. For example, she might calculate:The shared secret between her ephemeral key and Bob’s identity key.
The shared secret between her ephemeral key and Bob’s prekey.
(Optionally) The shared secret between her identity key and Bob’s prekey.
(Optionally) The shared secret between her ephemeral key and Bob’s one-time prekey if one is provided.
Each of these Diffie-Hellman computations uses elliptic-curve Diffie-Hellman (ECDH) algorithms.
Combining Secrets:
These individual shared secrets are then hashed together—using a key derivation function—to produce a single fresh key. This key is then used to encrypt the initial message.
Initial Message:
Alice sends Bob an initial message that includes:Her identity key and ephemeral key.
A note indicating which of Bob’s prekeys was used.
A ciphertext encrypted under the newly derived shared key, so that Bob can verify he has computed the same value when he processes his stored keys.
This process allows secure key establishment even when Alice and Bob are not simultaneously online.
The Ratchet Protocol
Purpose:
Once the shared key is established via X3DH, the ratchet mechanism takes over to continuously update (or “ratchet”) the keys used for encrypting messages. This provides forward secrecy (past communications remain secure even if current keys are compromised) and future secrecy (compromising a key doesn’t compromise future messages).
How It Works:
Continuous Key Derivation:
After the initial key agreement, every time a message is sent or received, a new message key is derived from the previous key. This “ratcheting” ensures that each message is encrypted with a unique key.Double Ratchet Mechanism:
Typically, Signal employs a double ratchet:Symmetric-key ratchet: Quickly updates the message keys using a hash chain.
Asymmetric-key ratchet: When a party sends a message, they may also include a new ephemeral key, triggering another round of Diffie-Hellman exchanges. This refreshes the long-term shared secret and contributes additional forward secrecy.
The ratchet ensures that even if an attacker learns a current key, previous and future message keys remain secure.
Mechanisms for Discovering Signal Keys in Your Address Book
Purpose:
This component deals with how the protocol manages and finds the public keys of people in your contacts (your address book). It simplifies the process of initiating secure communications with known contacts.
How It Works:
Key Distribution:
A server stores the published identity keys and prekeys of users. When you want to contact someone, your client automatically fetches their public keys from this server.Trust and Verification:
Since each prekey is signed by the corresponding identity key, your client can verify that the keys it obtains are authentic and haven’t been tampered with.Address Book Integration:
Signal-enabled applications often integrate with your address book. They match phone numbers or other identifiers to the published keys, making it seamless to start a secure conversation with someone you know.
This mechanism underpins the user experience, ensuring that key discovery happens behind the scenes while maintaining strong security properties.
X3DH enables asynchronous key establishment by using a combination of long-term identity keys, prekeys, and ephemeral keys, allowing two parties to derive a shared secret even if they are not online simultaneously.
The ratchet protocol then takes over to update encryption keys continuously, ensuring that each message is protected with a fresh key and providing robust forward and future secrecy.
Finally, integrated key discovery mechanisms ensure that users can easily and securely find the public keys of their contacts, streamlining the process of initiating secure conversations.
Imagine Alice wants to send an encrypted message to Bob. Bob has already uploaded his public keys to a server, and Alice will use these along with her own keys to derive a shared secret.
Setup
Bob’s Published Keys
Bob has two important keys published on the server:Identity Key: This is Bob’s long-term key.
Prekey: An ephemeral key (or a set of them) intended to be used for establishing sessions.
Alice’s Keys
Identity Key: Alice’s long-term key.
Ephemeral Key: Alice generates a fresh ephemeral key for this session.
For our example, we’ll use a simple Diffie-Hellman–like system with:
A small prime modulus p=37p = 37p=37
A generator g=2g = 2g=2
These numbers are only for demonstration—they are far too small for any real security.
Assumed Key Values
Bob’s Keys:
Private Identity Key: b=3b = 3b=3
Public Identity Key: B=gbmod p=23mod 37=8B = g^b \mod p = 2^3 \mod 37 = 8B=gbmodp=23mod37=8Private Prekey: pb=11p_b = 11pb=11
Public Prekey: PB=gpbmod p=211mod 37P_B = g^{p_b} \mod p = 2^{11} \mod 37PB=gpbmodp=211mod37
Let’s compute 2112^{11}211: 211=20482^{11} = 2048211=2048. To find 2048mod 372048 \mod 372048mod37:
37×55=203537 \times 55 = 203537×55=2035, so the remainder is 2048−2035=132048 - 2035 = 132048−2035=13.
Thus, PB=13P_B = 13PB=13.
Alice’s Keys:
Private Identity Key: a=5a = 5a=5
Public Identity Key: A=gamod p=25mod 37=32A = g^a \mod p = 2^5 \mod 37 = 32A=gamodp=25mod37=32Private Ephemeral Key: e=7e = 7e=7
Public Ephemeral Key: E=gemod p=27mod 37E = g^e \mod p = 2^7 \mod 37E=gemodp=27mod37
27=1282^7 = 12827=128; 128mod 37=128−(3×37=111)=17128 \mod 37 = 128 - (3 \times 37 = 111) = 17128mod37=128−(3×37=111)=17.
So, E=17E = 17E=17.
The X3DH Diffie-Hellman Computations
Alice will combine three Diffie-Hellman computations using different pairs of keys:
DH1: Using her ephemeral key and Bob’s identity key
DH1=(B)emod p=87mod 37(or equivalently gb⋅e)DH1 = (B)^e \mod p = 8^7 \mod 37 \quad \text{(or equivalently } g^{b \cdot e} \text{)}DH1=(B)emodp=87mod37(or equivalently gb⋅e)
Since 8=238 = 2^38=23, then 87=(23)7=2218^7 = (2^3)^7 = 2^{21}87=(23)7=221.
We need to compute 221mod 372^{21} \mod 37221mod37. (For brevity, suppose we compute it and find:)DH1=29.DH1 = 29.DH1=29.
DH2: Using her ephemeral key and Bob’s prekey
DH2=(PB)emod p=137mod 37(or equivalently gpb⋅e=g11×7=g77)DH2 = (P_B)^e \mod p = 13^7 \mod 37 \quad \text{(or equivalently } g^{p_b \cdot e} = g^{11 \times 7} = g^{77} \text{)}DH2=(PB)emodp=137mod37(or equivalently gpb⋅e=g11×7=g77)
Since the multiplicative group modulo 37 has order 36, we can reduce the exponent modulo 36:
77mod 36=77−2×36=577 \mod 36 = 77 - 2 \times 36 = 577mod36=77−2×36=5.
Thus,DH2=25mod 37=32.DH2 = 2^5 \mod 37 = 32.DH2=25mod37=32.
DH3: Using her identity key and Bob’s prekey
DH3=(PB)amod p=135mod 37(or equivalently gpb⋅a=g11×5=g55)DH3 = (P_B)^a \mod p = 13^5 \mod 37 \quad \text{(or equivalently } g^{p_b \cdot a} = g^{11 \times 5} = g^{55} \text{)}DH3=(PB)amodp=135mod37(or equivalently gpb⋅a=g11×5=g55)
Reduce the exponent: 55mod 36=55−36=1955 \mod 36 = 55 - 36 = 1955mod36=55−36=19.
Now,DH3=219mod 37.DH3 = 2^{19} \mod 37.DH3=219mod37.
(Suppose from our computations we find:)
DH3=35.DH3 = 35.DH3=35.
Deriving the Shared Secret
Alice now combines these three Diffie-Hellman outputs—often by concatenating them and passing them through a cryptographic hash function or a key derivation function (KDF)—to create a fresh shared secret key:
Shared Secret=H(DH1∥DH2∥DH3)=H(29∥32∥35)\text{Shared Secret} = H(DH1 \parallel DH2 \parallel DH3) = H(29 \parallel 32 \parallel 35)Shared Secret=H(DH1∥DH2∥DH3)=H(29∥32∥35)
Both Alice and Bob will perform similar calculations. When Bob receives Alice’s initial message (which includes her ephemeral key E=17E = 17E=17 and her identity key A=32A = 32A=32, along with an indication of which prekey was used), he will compute:
DH1′=Ebmod p=173mod 37DH1' = E^{b} \mod p = 17^3 \mod 37DH1′=Ebmodp=173mod37 (which equals the same DH1DH1DH1 if calculated correctly),
DH2′=Epbmod pDH2' = E^{p_b} \mod pDH2′=Epbmodp,
DH3′=Apbmod pDH3' = A^{p_b} \mod pDH3′=Apbmodp.
In our simplified example, these will match the values Alice computed (29, 32, and 35), so after applying the same hash/KDF, Bob will derive the identical shared secret key.
Using the Shared Secret
Once both parties have this shared secret, it is used to encrypt and authenticate messages. From here, the ratchet protocol takes over—each time a message is sent, the key is “ratcheted” (i.e., updated) using a combination of new Diffie-Hellman exchanges and a hash chain. This ensures that every message is encrypted with a new key, providing forward and future secrecy.
Summary of Our Example
Bob’s keys:
B=8B = 8B=8 (identity), PB=13P_B = 13PB=13 (prekey)Alice’s keys:
A=32A = 32A=32 (identity), E=17E = 17E=17 (ephemeral)Computed Diffie-Hellman values:
DH1=29DH1 = 29DH1=29
DH2=32DH2 = 32DH2=32
DH3=35DH3 = 35DH3=35
Shared Secret:
H(29∥32∥35)H(29 \parallel 32 \parallel 35)H(29∥32∥35)
(Both parties compute the same value.)
This process allows Alice and Bob to establish a secure session even if they’re not online at the same time and sets the stage for the ongoing ratchet-based key updates during their conversation.
1.The Symmetric-Key (Hash-Chain) Ratchet
Concept:
For every message sent, a new message key is generated from the current chain key, and then the chain key is updated (or “ratcheted forward”) by hashing it.
Step-by-Step Example:
Starting Point:
Initial chain key: CK0CK_0CK0
Both parties know CK0CK_0CK0 (derived from K0K_0K0).
Alice Sends Her First Message:
Message Key Derivation:
Alice computes a message key MK1MK_1MK1 using a hash function HHH. For example, MK1=H(CK0∥“Alice-Message-1”)MK_1 = H(CK_0 \parallel \text{“Alice-Message-1”})MK1=H(CK0∥“Alice-Message-1”) (In real implementations, the label might be implicit in the protocol’s state.)Encryption:
Alice encrypts her message using MK1MK_1MK1.Chain Key Update:
She then updates the chain key for future messages: CK1=H(CK0)CK_1 = H(CK_0)CK1=H(CK0)Sending:
Alice sends her encrypted message (and any necessary metadata, such as a message counter) to Bob.
Bob Receives the Message:
Re-Derivation:
Bob, having CK0CK_0CK0, computes the same MK1=H(CK0∥“Alice-Message-1”)MK_1 = H(CK_0 \parallel \text{“Alice-Message-1”})MK1=H(CK0∥“Alice-Message-1”) and uses it to decrypt the message.Chain Key Update:
Bob also updates his chain key to CK1=H(CK0)CK_1 = H(CK_0)CK1=H(CK0).
Bob’s Reply Using the Symmetric Ratchet:
Now, Bob uses the updated chain key CK1CK_1CK1 for his message.
Message Key Derivation:
He computes his message key as: MK2=H(CK1∥“Bob-Message-1”)MK_2 = H(CK_1 \parallel \text{“Bob-Message-1”})MK2=H(CK1∥“Bob-Message-1”)Encryption & Update:
He encrypts his reply with MK2MK_2MK2 and updates the chain key: CK2=H(CK1)CK_2 = H(CK_1)CK2=H(CK1)Sending:
Bob sends his encrypted reply to Alice.
This symmetric ratchet ensures that each message is encrypted with a fresh key. Even if an attacker somehow learns MK1MK_1MK1 or MK2MK_2MK2, they cannot work backward to derive CK0CK_0CK0 (backward secrecy) or predict future keys (forward secrecy).
2. The Asymmetric (DH) Ratchet
While the symmetric ratchet updates keys with every message, the DH ratchet is used to introduce new entropy into the system periodically—ensuring that if a chain key is ever compromised, future keys remain secure.
When Does the DH Ratchet Kick In?
At certain points in the conversation (for example, when one party sends a message after a pause or when a new ephemeral key is generated), a new Diffie–Hellman (DH) exchange is performed.
Step-by-Step Example:
Triggering the DH Ratchet:
Suppose after several messages, Alice wants to “rekey” the conversation. She generates a new ephemeral DH key pair and includes her new public key EA2E_{A2}EA2 in her outgoing message.
Bob’s Response:
When Bob receives the message with EA2E_{A2}EA2, he uses his own current ephemeral DH key (or generates one if needed) to compute a new DH shared secret DH1DH_1DH1.
For example: DH1=ECDH(EA2,Bob’s current DH private key)DH_1 = \text{ECDH}(E_{A2}, \text{Bob’s current DH private key})DH1=ECDH(EA2,Bob’s current DH private key)
Mixing in the New DH Secret:
Both parties then combine this new DH shared secret with their current chain key (say, CK2CK_2CK2) to create a new chain key: CK′=H(CK2∥DH1)CK' = H(CK_2 \parallel DH_1)CK′=H(CK2∥DH1)
This mixing step “resets” the symmetric ratchet with fresh entropy.
Resuming the Symmetric Ratchet:
From this point, they use CK′CK'CK′ as the base. The next message will use: MK3=H(CK′∥“Next Message”)MK_3 = H(CK' \parallel \text{“Next Message”})MK3=H(CK′∥“Next Message”)
And then they update the chain key: CK′′=H(CK′)CK'' = H(CK')CK′′=H(CK′)
The process then continues as before, with each message updating the chain key.
Putting It All Together: The Double Ratchet
Symmetric Ratchet:
Handles fast, per-message key updates. Every time a message is sent, the chain key is updated using a one-way hash. This provides forward secrecy within a session.DH (Asymmetric) Ratchet:
Occasionally, one party sends a new ephemeral DH key. When the other party receives it, they perform a new DH exchange. The resulting shared secret is mixed into the current chain key to produce a completely new chain. This step injects fresh randomness and ensures that even if previous keys are compromised, the future of the conversation remains secure.
Together, these two ratchets ensure that:
Forward Secrecy: Even if a current key is exposed, past messages (which used different keys) remain safe.
Future Secrecy: New keys are generated with fresh entropy from the DH ratchet, preventing an attacker from predicting or reconstructing future keys.
In Summary
Initial Setup:
Alice and Bob start with a shared secret K0K_0K0 from X3DH, from which they derive a chain key CK0CK_0CK0.Symmetric Ratchet Steps:
For each message, derive a message key MK=H(CK∥message info)MK = H(CK \parallel \text{message info})MK=H(CK∥message info).
Update the chain key CKCKCK by computing CKnew=H(CK)CK_{\text{new}} = H(CK)CKnew=H(CK).
Asymmetric (DH) Ratchet Step:
At periodic intervals, a party generates a new ephemeral DH key.
A DH exchange yields a fresh shared secret DH1DH_1DH1.
The current chain key is mixed with DH1DH_1DH1 to produce a new chain key CK′CK'CK′.
This double ratchet design is at the heart of protocols like Signal, ensuring that even if part of the key material is compromised, an attacker cannot decrypt past or future messages.