Key Exchange: Hybrid X3DH

Four DH operations, one post-quantum KEM, zero trust in servers.

What is X3DH

The Extended Triple Diffie-Hellman (X3DH) protocol, originally designed by Trevor Perrin and Moxie Marlinspike for the Signal Protocol, enables two parties to establish a shared secret even when one party is offline. This is critical for asynchronous messaging: you need to be able to send someone a message without them being online to participate in a handshake.

Traditional Diffie-Hellman requires both parties to be online simultaneously to exchange ephemeral keys. X3DH solves this by pre-publishing a set of public keys (a "prekey bundle") to a server. The initiator fetches this bundle and performs multiple DH operations against it to derive a shared secret. The responder can later reconstruct the same secret when they come online and receive the initial message.

Why Four DH Operations

X3DH performs four (or three, if no one-time prekey is available) Diffie-Hellman computations. Each provides a distinct security property:

DH1 = DH(IK_A, SPK_B)     Alice's identity key  ↔  Bob's signed prekey
DH2 = DH(EK_A, IK_B)      Alice's ephemeral key ↔  Bob's identity key
DH3 = DH(EK_A, SPK_B)     Alice's ephemeral key ↔  Bob's signed prekey
DH4 = DH(EK_A, OPK_B)     Alice's ephemeral key ↔  Bob's one-time prekey

The combined output of all four DH operations is fed into HKDF to derive the session key. An attacker must compromise all relevant private keys to recover the session key. Compromising any single key is insufficient.

Post-Quantum Integration

Classical X3DH is secure against all known classical attacks but is vulnerable to quantum computers running Shor's algorithm. A sufficiently powerful quantum computer could solve the elliptic curve discrete logarithm problem and recover the shared secret from the public keys alone.

RVNT extends X3DH with a fifth key agreement operation using ML-KEM-768 (FIPS 203), a lattice-based key encapsulation mechanism:

Classical X3DH:
  SK = HKDF(DH1 || DH2 || DH3 || DH4)

RVNT Hybrid X3DH:
  (PQ_CT, PQ_SS) = ML-KEM-768.Encapsulate(Bob's PQ public key)
  SK = HKDF(DH1 || DH2 || DH3 || DH4 || PQ_SS)

Why Hybrid

The hybrid approach provides defense in depth:

• If quantum computers never materialize: X25519 continues to provide the same security it always has. ML-KEM adds no risk (its output is simply concatenated before hashing).
• If ML-KEM is broken (classical attack): X25519 still protects the session. The attacker must also break all four DH operations.
• If quantum computers arrive: ML-KEM-768 protects the session. Even if Shor's algorithm breaks X25519, the lattice-based KEM remains secure.
• If both are broken: You have bigger problems, but this is not a realistic near-term threat.

ML-KEM-768 Parameters

The Initial Message

After computing the session key, Alice constructs an initial message that contains everything Bob needs to reconstruct the same session key:

InitialMessage {
    ik_a:          Alice's Ed25519 identity public key  [32 bytes]
    ek_a:          Alice's ephemeral X25519 public key  [32 bytes]
    opk_id:        ID of Bob's consumed OPK             [4 bytes]
    pq_ciphertext: ML-KEM-768 ciphertext                [1088 bytes]
    payload:       First message, encrypted with SK     [variable]
}

Bob receives this message and:
1. Looks up OPK by opk_id, deletes it from storage
2. Computes DH1 = DH(SPK_B, IK_A_dh)
3. Computes DH2 = DH(IK_B_dh, EK_A)
4. Computes DH3 = DH(SPK_B, EK_A)
5. Computes DH4 = DH(OPK_B, EK_A)
6. Computes PQ_SS = ML-KEM.Decapsulate(PQK_B_private, pq_ciphertext)
7. Derives SK = HKDF(DH1 || DH2 || DH3 || DH4 || PQ_SS)
8. Decrypts payload with SK
9. Initializes Double Ratchet with SK

Security Properties

Mutual Authentication

Both parties' identity keys participate in the key derivation (DH1 uses Alice's identity key, DH2 uses Bob's). An attacker who does not possess either identity private key cannot derive the session key. However, X3DH provides implicit authentication -- the parties do not receive explicit proof of each other's identity until the first response message. Key verification (safety numbers) provides explicit authentication.

Forward Secrecy

Alice's ephemeral key is generated fresh for each session and deleted after the X3DH computation. Compromise of Alice's or Bob's long-term identity keys after the session is established does not reveal the session key, because the ephemeral key required to compute DH2, DH3, and DH4 no longer exists.

Deniability

X3DH provides offline deniability. Either Alice or Bob could have independently computed the session transcript. There is no non-repudiation: a third party cannot cryptographically prove that Alice sent a specific message, because Bob could have generated the same transcript himself.

Replay Protection

One-time prekeys (DH4) prevent replay attacks. Each OPK is consumed on first use. If an attacker replays Alice's initial message, Bob's OPK will already be deleted, and the attacker cannot complete the protocol. If no OPK is available, replay protection relies on the session's Double Ratchet state advancing beyond the replayed message.

Comparison: Plain DH vs X3DH vs RVNT Hybrid

The additional overhead of ML-KEM-768 (~1088 bytes for the ciphertext + 1184 bytes for the public key in the bundle) is a deliberate tradeoff. Bandwidth is cheap. Retroactive decryption of your messages by a future quantum computer is not.

Further Reading

• Double Ratchet -- What happens after X3DH establishes the session
• Post-Quantum (ML-KEM) -- Deep dive into ML-KEM-768 and the quantum threat
• Protocol Specification -- Complete wire formats and test vectors