Extended Triple Diffie-Hellman Key Agreement (X3DH)

When I built my Signal Protocol messenger, X3DH was the first cryptographic primitive I had to understand. It’s the handshake that happens when Alice sends her first message to Bob a complex dance of public keys that establishes a shared secret without either party being online simultaneously.

What Problem Does X3DH Solve?

Traditional Diffie-Hellman requires both parties to be online at the same time to exchange ephemeral public keys. But messaging apps don’t work that way you want to send a message even if the recipient is offline.

X3DH allows Alice to establish a shared secret with Bob using only his pre-published public keys. Bob uploads these keys to the server once, and Alice can use them anytime to initiate a secure conversation.

The Four Keys Involved

Bob uploads a “key bundle” containing:

flowchart LR
    subgraph "Bob's Key Bundle"
        IK[🔑 Identity Key<br/>Curve25519<br/>Long-term]
        SPK[🔑 Signed Prekey<br/>Medium-term<br/>Rotated ~weekly]
        OPK[📦 400+ One-Time Prekeys<br/>Ephemeral<br/>Used once, deleted]
        KYBER[🔐 Kyber Prekey<br/>Post-quantum<br/>Optional]
    end
    
    subgraph Server
        BUNDLE[(Key Bundle Store)]
    end
    
    IK --> BUNDLE
    SPK --> BUNDLE
    OPK --> BUNDLE
    KYBER -.-> BUNDLE
  1. Identity Key (IK) A long-term Curve25519 key pair. Think of it as Bob’s cryptographic identity.
  2. Signed Prekey (SPK) A medium-term key (rotated every few weeks) signed by the identity key.
  3. One-Time Prekeys (OPKs) 400+ ephemeral keys, each used only once then deleted.
  4. Kyber Prekey (Optional) Post-quantum key for future-proofing against quantum computers.

The Mathematical Dance

When Alice wants to message Bob, she generates an ephemeral key pair just for this session. Then she performs three or four Diffie-Hellman exchanges:

sequenceDiagram
    participant Alice
    participant Server
    participant Bob
    
    Note over Bob: Bob uploads keys once
    Bob->>Server: Identity Key (IK_B)
    Bob->>Server: Signed Prekey (SPK_B)
    Bob->>Server: One-Time Prekeys (OPK_B)
    
    Note over Alice: Alice wants to message Bob
    Alice->>Alice: Generate ephemeral key (E_A)
    
    Alice->>Server: Fetch Bob's key bundle
    Server-->>Alice: IK_B, SPK_B, OPK_B
    Server->>Server: Delete OPK_B (consumed)
    
    Note over Alice: Perform 4 DH exchanges
    Alice->>Alice: DH1 = DH(E_A, IK_B)
    Alice->>Alice: DH2 = DH(E_A, SPK_B)
    Alice->>Alice: DH3 = DH(IK_A, SPK_B)
    Alice->>Alice: DH4 = DH(E_A, OPK_B)
    
    Alice->>Alice: SK = KDF(DH1 || DH2 || DH3 || DH4)
    
    Alice->>Server: Send initial message + E_A (public)
    Server-->>Bob: Deliver when online
    
    Note over Bob: Bob receives message
    Bob->>Bob: Derive same SK using<br/>his private keys + E_A
DH1 = DH(Alice's ephemeral private key, Bob's identity public key)
DH2 = DH(Alice's ephemeral private key, Bob's signed prekey public key)
DH3 = DH(Alice's identity private key, Bob's signed prekey public key)
DH4 = DH(Alice's ephemeral private key, Bob's one-time prekey public key) [optional]

The shared secret is derived by concatenating these DH outputs and running them through a KDF (Key Derivation Function):

SK = KDF(DH1 || DH2 || DH3 [|| DH4])

Why Four Diffie-Hellmans?

Each DH exchange provides different security properties:

flowchart TB
    subgraph "What Each DH Exchange Provides"
        DH1["DH1: Alice's ephemeral × Bob's Identity"] -->|"Proves Bob's identity"| AUTH[✅ Authentication]
        
        DH2["DH2: Alice's ephemeral × Bob's Signed Prekey"] -->|"Fresh ephemeral contribution"| FS[✅ Forward Secrecy]
        
        DH3["DH3: Alice's Identity × Bob's Signed Prekey"] -->|"Both long-term + medium-term keys"| FUTURE[✅ Future Secrecy]
        
        DH4["DH4: Alice's ephemeral × Bob's One-Time Prekey"] -->|"Truly ephemeral, never reused"| EFS[✅ Extra Forward Secrecy]
    end
    
    style DH1 fill:#e1f5fe
    style DH2 fill:#e8f5e9
    style DH3 fill:#fff3e0
    style DH4 fill:#fce4ec
  • DH1 Authentication: Proves Alice is talking to the real Bob (only Bob has the identity private key)
  • DH2 Forward Secrecy: Even if Bob’s identity key is compromised later, past messages remain secure
  • DH3 Future Secrecy: If the ephemeral key leaks, future messages are still protected
  • DH4 Extra Forward Secrecy: One-time prekeys provide the strongest forward secrecy

Implementation Challenges

Prekey Depletion

Bob uploads 400 one-time prekeys. Each time someone initiates a conversation with him, one is consumed. When the count drops below 10, the server notifies Bob’s client to upload more.

# Server-side: consuming a one-time prekey
prekey = await PreKey.find_one(
    PreKey.user_keys_id == user_keys.id,
    PreKey.used == False,
)
if prekey:
    prekey_id = prekey.prekey_id
    prekey_public = prekey.prekey_public
    await prekey.delete()  # Used once, never again

remaining = await PreKey.find(
    PreKey.user_keys_id == user_keys.id,
    PreKey.used == False,
).count()

if remaining < PREKEY_LOW_THRESHOLD:
    asyncio.ensure_future(_notify_prekey_low(user_id, remaining))

Session Establishment

Once X3DH completes, the shared secret initializes the Double Ratchet. But critically, the X3DH result is never used directly for encryption. It’s the root key for the ratchet’s first chain.

The Kyber-1024 Addition

Signal added Kyber (a post-quantum key encapsulation mechanism) to X3DH. The concern: quantum computers could one day break elliptic curve cryptography.

flowchart TB
    subgraph "Classic X3DH"
        C1[DH1] --> KDF
        C2[DH2] --> KDF
        C3[DH3] --> KDF
        C4[DH4] --> KDF
    end
    
    subgraph "PQXDH (Post-Quantum X3DH)"
        P1[DH1] --> KDF2[KDF]
        P2[DH2] --> KDF2
        P3[DH3] --> KDF2
        P4[DH4] --> KDF2
        KEM[KEM Encapsulate<br/>Kyber-1024] --> KDF2
    end
    
    KDF --> SK[Shared Secret]
    KDF2 --> SK2[Shared Secret<br/>Quantum-Resistant]
    
    style KEM fill:#e1f5fe
    style KDF2 fill:#e8f5e9

Kyber works differently it’s a KEM, not a Diffie-Hellman exchange. Alice generates a Kyber ciphertext that only Bob can decrypt with his private key:

# PQXDH (Post-Quantum X3DH) adds a fifth component
kyber_ciphertext = kyber_encapsulate(bob_kyber_public_key)
shared_secret = KDF(DH1 || DH2 || DH3 [|| DH4] || kyber_shared_secret)

Even if quantum computers break Curve25519, the Kyber component remains secure.

X3DH in Practice

When I implemented this, the biggest pain points were:

  1. Key serialization Converting libsignal’s internal key formats to base64 for transmission
  2. Prekey rotation Handling the case where Bob regenerates keys while Alice has old ones cached
  3. Identity verification How do users know they’re talking to the right person? (Answer: safety numbers)

Code: X3DH Session Establishment

Here’s how the client establishes a session using a prekey bundle:

Future<void> ensureSession(
  String recipientUserId,
  PreKeyBundleResponse bundle,
) async {
  // Guard: skip X3DH entirely if we already have a session
  if (await hasSession(recipientUserId)) {
    return;
  }

  const int deviceId = 1;

  // Build the libsignal PreKeyBundle from server response
  final preKeyBundle = PreKeyBundle(
    registrationId: bundle.registrationId,
    deviceId: bundle.deviceId,
    preKeyId: bundle.prekeyId,
    preKeyPublic: bundle.prekeyPublic != null
        ? base64Decode(bundle.prekeyPublic!)
        : null,
    signedPreKeyId: bundle.signedPrekeyId,
    signedPreKeyPublic: base64Decode(bundle.signedPrekeyPublic).toList(),
    signedPreKeySignature: base64Decode(
      bundle.signedPrekeySignature,
    ).toList(),
    identityKey: base64Decode(bundle.identityKey).toList(),
    // Kyber prekey for PQXDH
    kyberPreKeyId: bundle.kyberPrekeyId ?? 0,
    kyberPreKeyPublic: bundle.kyberPrekeyPublic != null
        ? base64Decode(bundle.kyberPrekeyPublic!).toList()
        : null,
    kyberPreKeySignature: bundle.kyberPrekeySignature != null
        ? base64Decode(bundle.kyberPrekeySignature!).toList()
        : null,
  );

  await processPrekeyBundleWithCallbacks(
    remoteName: recipientUserId,
    remoteDeviceId: deviceId,
    bundle: preKeyBundle,
    loadSession: (name, devId) => _loadSession(name, devId),
    storeSession: (name, devId, record) => _storeSession(name, devId, record),
    getIdentityKeyPair: () => _getIdentityKeyPairBytes(),
    getLocalRegistrationId: () async => _signal.registrationId ?? 0,
    saveIdentity: (name, devId, identityKey) =>
        _saveRemoteIdentity(name, devId, identityKey),
  );
}

The processPrekeyBundleWithCallbacks function performs the X3DH calculation and initializes the session state. The resulting shared secret seeds the Double Ratchet’s root key.

Summary

X3DH is elegant in its asymmetry: Bob can be completely offline while Alice establishes a secure channel with him. The combination of long-term, medium-term, and ephemeral keys provides defense in depth compromising one key type doesn’t break everything.

Next, read about the Double Ratchet algorithm that uses this shared secret to encrypt actual messages with perfect forward secrecy.

Tags:
#cryptography #signal-protocol #x3dh #key-exchange #security

Random Fact

The first computer mouse was made of wood and had only one button.