signal-x3dh.ipynb

Kernel: SageMath 10.0

Connect: X3DH in the Signal Protocol

Module 05 | Real-World Connections

Signal uses Extended Triple Diffie-Hellman (X3DH) to establish shared keys between users who may be offline.

Introduction

The Signal Protocol (used by Signal, WhatsApp, and others) faces a challenge that TLS does not: how do you establish a shared secret with someone who is offline?

In TLS, both parties are online and exchange DH key shares in real time. In messaging, Alice might want to send Bob a message while Bob's phone is off.

X3DH (Extended Triple Diffie-Hellman) solves this by having Bob publish prekeys to a server. Alice can use these prekeys to establish a shared secret without Bob being online. When Bob comes online, he can derive the same shared secret and read Alice's messages.

X3DH computes three (or four) DH shared secrets and combines them. Each DH computation provides a different security property.

The X3DH Protocol

Each user has three types of keys:

Key	Lifetime	Purpose
Identity key $(IK)$	Long-term	Authenticates the user
Signed prekey $(SPK)$	Medium-term (rotated weekly/monthly)	Provides forward secrecy
One-time prekey $(OPK)$	Single use	Provides replay protection

Bob publishes his public keys $(IK_B, SPK_B, OPK_B)$ to the server.

Alice fetches Bob's keys and computes:

$$DH_1 = \text{DH}(IK_A, SPK_B) \quad \text{(mutual authentication)}$$$$DH_2 = \text{DH}(EK_A, IK_B) \quad \text{(sender authentication)}$$$$DH_3 = \text{DH}(EK_A, SPK_B) \quad \text{(forward secrecy)}$$$$DH_4 = \text{DH}(EK_A, OPK_B) \quad \text{(replay protection, optional)}$$

where $EK_A$ is Alice's fresh ephemeral key.

The combined session key: $SK = \text{KDF}(DH_1 \| DH_2 \| DH_3 \| DH_4)$

# === Set up the group (toy-sized for demonstration) ===

import hashlib

p = 7919  # safe prime
g = primitive_root(p)

print(f'Group parameters: p = {p}, g = {g}')
print(f'p - 1 = {factor(p - 1)}')
print()

def keygen():
    """Generate a DH key pair (secret, public)."""
    secret = ZZ.random_element(2, p - 2)
    public = power_mod(g, secret, p)
    return secret, public

def dh(my_secret, their_public):
    """Compute a DH shared secret."""
    return power_mod(their_public, my_secret, p)

# === Bob's key bundle (published to server while Bob may be offline) ===

# Bob's identity key (long-term)
ik_b_secret, IK_B = keygen()

# Bob's signed prekey (medium-term, rotated periodically)
spk_b_secret, SPK_B = keygen()

# Bob's one-time prekey (single use, deleted after pickup)
opk_b_secret, OPK_B = keygen()

print('=== Bob\'s key bundle (published to server) ===')
print(f'Identity key  IK_B  = {IK_B}')
print(f'Signed prekey SPK_B = {SPK_B}')
print(f'One-time prekey OPK_B = {OPK_B}')
print()
print('Bob\'s secrets (stored on Bob\'s device, never shared):')
print(f'  ik_b = {ik_b_secret}')
print(f'  spk_b = {spk_b_secret}')
print(f'  opk_b = {opk_b_secret}')

# === Alice initiates (Bob may be offline) ===

# Alice's identity key (long-term)
ik_a_secret, IK_A = keygen()

# Alice's ephemeral key (fresh for this session)
ek_a_secret, EK_A = keygen()

print('=== Alice\'s keys ===')
print(f'Identity key  IK_A = {IK_A}')
print(f'Ephemeral key EK_A = {EK_A}')
print()

# Alice fetches Bob's bundle from the server
print('Alice fetches Bob\'s key bundle from the server...')
print(f'  IK_B  = {IK_B}')
print(f'  SPK_B = {SPK_B}')
print(f'  OPK_B = {OPK_B}')

# === Alice computes the four DH shared secrets ===

# DH1: IK_A <-> SPK_B (mutual authentication)
dh1_alice = dh(ik_a_secret, SPK_B)

# DH2: EK_A <-> IK_B (sender authentication)
dh2_alice = dh(ek_a_secret, IK_B)

# DH3: EK_A <-> SPK_B (forward secrecy)
dh3_alice = dh(ek_a_secret, SPK_B)

# DH4: EK_A <-> OPK_B (replay protection)
dh4_alice = dh(ek_a_secret, OPK_B)

print('=== Alice computes 4 DH shared secrets ===')
print(f'DH1 = DH(ik_a, SPK_B) = {dh1_alice}  [mutual authentication]')
print(f'DH2 = DH(ek_a, IK_B)  = {dh2_alice}  [sender authentication]')
print(f'DH3 = DH(ek_a, SPK_B) = {dh3_alice}  [forward secrecy]')
print(f'DH4 = DH(ek_a, OPK_B) = {dh4_alice}  [replay protection]')
print()

# Derive session key
combined = f'{dh1_alice}||{dh2_alice}||{dh3_alice}||{dh4_alice}'
SK_alice = hashlib.sha256(combined.encode()).hexdigest()
print(f'Alice\'s session key SK = SHA256(DH1||DH2||DH3||DH4)')
print(f'  SK = {SK_alice}')

# === Bob comes online and computes the SAME session key ===

# Bob receives Alice's message with (IK_A, EK_A)
# Bob uses his stored secrets to compute the same 4 DH values

# DH1: SPK_B <-> IK_A (same as Alice's DH1 by commutativity)
dh1_bob = dh(spk_b_secret, IK_A)

# DH2: IK_B <-> EK_A
dh2_bob = dh(ik_b_secret, EK_A)

# DH3: SPK_B <-> EK_A
dh3_bob = dh(spk_b_secret, EK_A)

# DH4: OPK_B <-> EK_A
dh4_bob = dh(opk_b_secret, EK_A)

print('=== Bob computes 4 DH shared secrets ===')
print(f'DH1 = DH(spk_b, IK_A) = {dh1_bob}  [matches Alice? {dh1_bob == dh1_alice}]')
print(f'DH2 = DH(ik_b, EK_A)  = {dh2_bob}  [matches Alice? {dh2_bob == dh2_alice}]')
print(f'DH3 = DH(spk_b, EK_A) = {dh3_bob}  [matches Alice? {dh3_bob == dh3_alice}]')
print(f'DH4 = DH(opk_b, EK_A) = {dh4_bob}  [matches Alice? {dh4_bob == dh4_alice}]')
print()

combined_bob = f'{dh1_bob}||{dh2_bob}||{dh3_bob}||{dh4_bob}'
SK_bob = hashlib.sha256(combined_bob.encode()).hexdigest()
print(f'Bob\'s session key SK = {SK_bob}')
print(f'Keys match: {SK_alice == SK_bob}')

Why Three (or Four) DH Computations?

Each DH computation provides a different security property:

DH	Keys used	Property provided
$DH_1 = DH(IK_A, SPK_B)$	Alice's identity + Bob's signed prekey	Mutual authentication: both long-term keys are involved
$DH_2 = DH(EK_A, IK_B)$	Alice's ephemeral + Bob's identity	Sender authentication: proves Alice initiated
$DH_3 = DH(EK_A, SPK_B)$	Alice's ephemeral + Bob's prekey	Forward secrecy: when both ephemeral keys are deleted, the secret can't be recovered
$DH_4 = DH(EK_A, OPK_B)$	Alice's ephemeral + Bob's one-time prekey	Replay protection: each OPK is used once, preventing message replay

No single DH computation provides all these properties. Combining them gives:

• Authentication (from identity keys)

• Forward secrecy (from ephemeral keys)

• Replay protection (from one-time prekeys)

# === What if we omit one DH? ===

print('=== Security impact of omitting each DH ===')
print()
print('Without DH1 (no IK_A involvement):')
print('  -> No proof that Alice (the identity key holder) initiated')
print('  -> Anyone with Bob\'s public keys could start a session')
print()
print('Without DH2 (no IK_B involvement):')
print('  -> No assurance we\'re talking to the real Bob')
print('  -> A server could impersonate Bob using fake prekeys')
print()
print('Without DH3 (no ephemeral key):')
print('  -> No forward secrecy from ephemeral randomness')
print('  -> If long-term keys leak, session key is recoverable')
print()
print('Without DH4 (no one-time prekey):')
print('  -> Protocol still works (DH4 is optional in X3DH)')
print('  -> But replay protection is weakened')
print('  -> Attacker could replay Alice\'s initial message')

Concept Map: Module 05 in Signal

Module 05 Concept	Signal/X3DH Application
DH key exchange	Core of X3DH --- four DH computations combined
DLP hardness	Security of all key exchanges
Ephemeral keys	$EK_A$ provides forward secrecy
Multiple DH rounds	Each provides authentication, forward secrecy, or replay protection
Key derivation	KDF combines four DH outputs into one session key
Safe parameters	Signal uses Curve25519 (elliptic curve DH) for efficiency and safety

Summary

Concept	Key idea
Asynchronous key agreement	Alice can establish a shared secret even when Bob is offline, using Bob's prekeys published to a server.
Three (or four) DH computations	Each DH provides a distinct security property: authentication, forward secrecy, or replay protection.
DLP/CDH hardness	The same hardness assumption from Module 05 underpins every DH computation in X3DH.
Elliptic curve DH	Signal uses Curve25519 in practice, but the mathematical structure is identical to finite-field DH.
Double Ratchet	X3DH bootstraps the session, and then the Double Ratchet algorithm provides ongoing forward secrecy by continuously rotating keys.

Signal's X3DH protocol demonstrates the power of combining multiple DH computations to achieve authentication, forward secrecy, and replay protection simultaneously.

---

Back to Module 05: Discrete Log and Diffie-Hellman