hybrid-tls-post-quantum.ipynb

Kernel: SageMath 10.0

Connect: Hybrid TLS with Post-Quantum Key Exchange

Module 08 | Real-World Connections

Chrome, Cloudflare, and the world's biggest CDNs are already shipping lattice-based key exchange --- combined with classical ECDH as a safety net.

Introduction

A sufficiently powerful quantum computer could break every Diffie-Hellman and elliptic curve key exchange deployed today. Shor's algorithm solves the discrete logarithm problem in polynomial time, making ECDH (Module 06) and classical DH (Module 05) vulnerable.

But quantum computers capable of breaking 256-bit ECC do not exist yet. And the post-quantum alternatives (ML-KEM, based on lattice problems from this module) are newer and less battle-tested.

The solution: hybrid key exchange. Combine a classical scheme (X25519) with a post-quantum scheme (ML-KEM-768) so that:

• If ML-KEM turns out to have a flaw, X25519 still protects you.

• If a quantum computer arrives, ML-KEM protects you.

• Security is the maximum of both schemes, not the minimum.

This is not hypothetical. Chrome enabled X25519Kyber768 by default in Chrome 124 (April 2024). Cloudflare supports it on all domains. AWS, Apple, and Signal have also deployed post-quantum hybrid key exchange.

The Hybrid Approach

In a hybrid TLS 1.3 handshake, the client and server perform two independent key exchanges in a single flight:

1. X25519 (classical ECDH on Curve25519, from Module 06):

   • Client sends an X25519 public key share

   • Server responds with its X25519 public key share

   • Both derive a 32-byte shared secret $K_{\text{classical}}$

2. ML-KEM-768 (post-quantum, from this module):

   • Client sends an ML-KEM encapsulation key (public key)

   • Server encapsulates a shared secret and sends the ciphertext

   • Client decapsulates to recover the 32-byte shared secret $K_{\text{PQ}}$

3. Combine: The final shared secret is derived by feeding both shared secrets into a Key Derivation Function (KDF):

$$K_{\text{final}} = \text{KDF}(K_{\text{classical}} \| K_{\text{PQ}})$$

An attacker must break both X25519 and ML-KEM to recover the session key. A classical attacker cannot break X25519; a quantum attacker (presumably) cannot break ML-KEM. So the combined scheme is secure against both.

# === Simulating the Classical Component: ECDH on a Small Curve ===
#
# Real TLS uses X25519 (Curve25519). We simulate with a small elliptic
# curve to show the mechanics. The concepts are identical to Module 06.

# Small curve y^2 = x^3 + 2x + 3 over F_97
p_ec = 97
E = EllipticCurve(GF(p_ec), [2, 3])
G_ec = E.gens()[0]  # generator point
order_ec = G_ec.order()

print('=== Classical Component: ECDH ===')
print(f'Curve: y^2 = x^3 + 2x + 3 over F_{p_ec}')
print(f'Generator G = {G_ec}')
print(f'Order = {order_ec}')
print(f'(Real TLS uses Curve25519 with 2^255 - 19 base field)')
print()

# Alice's ECDH key pair
set_random_seed(42)
a_ecdh = ZZ.random_element(1, order_ec)
A_ecdh = a_ecdh * G_ec

# Bob's ECDH key pair
b_ecdh = ZZ.random_element(1, order_ec)
B_ecdh = b_ecdh * G_ec

# Shared secret (x-coordinate of shared point)
shared_point_alice = a_ecdh * B_ecdh
shared_point_bob = b_ecdh * A_ecdh
K_classical = ZZ(shared_point_alice.xy()[0])  # x-coordinate

print(f'Alice public share: A = {A_ecdh}')
print(f'Bob public share:   B = {B_ecdh}')
print(f'Shared point (Alice): {shared_point_alice}')
print(f'Shared point (Bob):   {shared_point_bob}')
print(f'K_classical = {K_classical} (x-coordinate of shared point)')
print(f'Match: {shared_point_alice == shared_point_bob}')

# === Simulating the Post-Quantum Component: Toy ML-KEM ===
#
# Real TLS uses ML-KEM-768. We use the same toy Kyber from the
# NIST PQC notebook: n=8, q=17, k=2.

n_kem = 8
q_kem = 17
k_kem = 2

Zq_kem = Zmod(q_kem)
Px_kem.<x> = PolynomialRing(Zq_kem)
Rq_kem.<xbar> = Px_kem.quotient(x^n_kem + 1)

def small_poly_kem(bound=1):
    return Rq_kem([ZZ.random_element(-bound, bound + 1) for _ in range(n_kem)])

def uniform_poly_kem():
    return Rq_kem([ZZ.random_element(0, q_kem) for _ in range(n_kem)])

def poly_coeffs_kem(p):
    lifted = p.lift()
    return [lifted[i] for i in range(n_kem)]

# Alice generates ML-KEM key pair
set_random_seed(77)
A_kem = matrix(Rq_kem, k_kem, k_kem, lambda i, j: uniform_poly_kem())
s_kem = vector(Rq_kem, [small_poly_kem() for _ in range(k_kem)])
e_kem = vector(Rq_kem, [small_poly_kem() for _ in range(k_kem)])
t_kem = A_kem * s_kem + e_kem

print('=== Post-Quantum Component: Toy ML-KEM ===')
print(f'Ring: Z_{q_kem}[x] / (x^{n_kem} + 1), module rank k={k_kem}')
print(f'(Real TLS uses n=256, q=3329, k=3 for ML-KEM-768)')
print(f'\nAlice\'s ML-KEM public key: (A, t = A*s + e)')
print(f'Alice\'s ML-KEM secret key: s')

# === Bob encapsulates a shared secret using Alice's ML-KEM public key ===

# Bob generates a random message to encode as the shared secret
msg_bits_kem = [ZZ.random_element(0, 2) for _ in range(n_kem)]
msg_poly_kem = Rq_kem([b * (q_kem // 2) for b in msg_bits_kem])

# Bob samples fresh noise
r_kem = vector(Rq_kem, [small_poly_kem() for _ in range(k_kem)])
e1_kem = vector(Rq_kem, [small_poly_kem() for _ in range(k_kem)])
e2_kem = small_poly_kem()

# Encapsulate
u_kem = A_kem.transpose() * r_kem + e1_kem
v_kem = sum(t_kem[i] * r_kem[i] for i in range(k_kem)) + e2_kem + msg_poly_kem

# Bob's shared secret is derived from the message bits
K_pq_bob = sum(b * 2^i for i, b in enumerate(msg_bits_kem))  # simple encoding

print('Bob encapsulates:')
print(f'  Random message bits: {msg_bits_kem}')
print(f'  Ciphertext (u, v) sent to Alice')
print(f'  K_PQ (Bob\'s view): {K_pq_bob}')

# === Alice decapsulates to recover the shared secret ===

# Alice computes: v - s^T * u = msg + noise
noisy_msg_kem = v_kem - sum(s_kem[i] * u_kem[i] for i in range(k_kem))

# Decode each coefficient
def decode_bit_kem(coeff, q):
    c = ZZ(coeff) % q
    dist_to_0 = min(c, q - c)
    dist_to_half = abs(c - q // 2)
    return 0 if dist_to_0 < dist_to_half else 1

recovered_bits_kem = [decode_bit_kem(c, q_kem)
                      for c in poly_coeffs_kem(noisy_msg_kem)]

K_pq_alice = sum(b * 2^i for i, b in enumerate(recovered_bits_kem))

print('Alice decapsulates:')
print(f'  Recovered bits: {recovered_bits_kem}')
print(f'  Original bits:  {msg_bits_kem}')
print(f'  K_PQ (Alice\'s view): {K_pq_alice}')
print(f'  PQ shared secrets match: {K_pq_alice == K_pq_bob}')

# === Combine both shared secrets with a KDF ===

import hashlib

# In real TLS, this is HKDF-Expand with the concatenated shared secrets.
# We simulate with SHA-256.

K_classical_bytes = K_classical.to_bytes(32, byteorder='big')
K_pq_bytes = K_pq_alice.to_bytes(32, byteorder='big')

# Concatenate and hash
K_combined = hashlib.sha256(K_classical_bytes + K_pq_bytes).hexdigest()

print('=== HYBRID KEY DERIVATION ===')
print(f'K_classical = {K_classical}')
print(f'K_PQ        = {K_pq_alice}')
print(f'\nK_final = SHA-256(K_classical || K_PQ)')
print(f'        = {K_combined}')
print(f'\nThis 256-bit key is used for AES-256-GCM to encrypt the TLS session.')
print(f'\nSecurity analysis:')
print(f'  - Classical attacker: must break X25519 (ECDLP hardness)')
print(f'  - Quantum attacker:   must break ML-KEM (lattice hardness)')
print(f'  - Both at once:       must break BOTH (defense in depth)')

The TLS 1.3 Hybrid Handshake

Here is how the hybrid handshake works in TLS 1.3:

Client                                           Server
------                                           ------
ClientHello
  + key_share: X25519 public (32 bytes)
  + key_share: ML-KEM-768 encaps key (1184 bytes)
  ------------------------------------------->
                                         ServerHello
                          + key_share: X25519 public (32 bytes)
                          + key_share: ML-KEM-768 ciphertext (1088 bytes)
  <-------------------------------------------

Both sides compute:
  K = HKDF(X25519_shared_secret || ML-KEM_shared_secret)

Encrypted application data flows using K.

The key observation: everything fits in a single round trip. The client sends both key shares in the ClientHello, and the server responds with both in the ServerHello. This means hybrid PQ adds zero extra round trips compared to classical TLS 1.3.

The cost is bandwidth: the ClientHello grows by about 1184 bytes (the ML-KEM encapsulation key), and the ServerHello grows by about 1088 bytes (the ML-KEM ciphertext). This is significant but manageable.

# === Bandwidth comparison: classical vs hybrid TLS ===

handshakes = [
    ('X25519 only (classical)',
     32,    # client key_share
     32),   # server key_share
    ('X25519 + ML-KEM-768 (hybrid)',
     32 + 1184,   # client: X25519 share + ML-KEM encaps key
     32 + 1088),  # server: X25519 share + ML-KEM ciphertext
    ('ML-KEM-768 only (PQ-only)',
     1184,   # client: ML-KEM encaps key
     1088),  # server: ML-KEM ciphertext
]

print('Handshake Client (bytes) Server (bytes) Total')for name, client, server in handshakes:
    print(f'{name} {client:>15,} {server:>15,} {client+server:>10,}')

print(f'\nThe hybrid approach adds ~2.2 KB total to the handshake.')
print(f'This is less than a typical web page favicon image.')
print(f'For most connections, this overhead is negligible.')

Why Hybrid? Defense in Depth

The hybrid approach is motivated by two kinds of uncertainty:

Uncertainty about quantum computers:

• We do not know when (or if) large-scale quantum computers will exist.

• If they never arrive, classical ECDH alone would have sufficed.

• But harvest-now, decrypt-later attacks are real: adversaries can record encrypted traffic today and decrypt it once quantum computers exist.

Uncertainty about post-quantum schemes:

• ML-KEM is based on Module-LWE, which has been studied for ~15 years.

• Classical schemes (RSA, ECDH) have been studied for 40+ years.

• What if someone finds a classical attack on Module-LWE? (Several early PQ candidates were broken classically, e.g., SIKE in 2022.)

The hybrid approach addresses both risks simultaneously:

Threat Model	X25519	ML-KEM	Hybrid
Classical attacker	Secure	Secure	Secure
Quantum attacker	Broken	Secure	Secure
Classical break of ML-KEM	Secure	Broken	Secure
Quantum + ML-KEM broken	Broken	Broken	Broken

The hybrid fails only if both schemes are broken simultaneously --- the least likely scenario.

Deployment Timeline

Post-quantum hybrid key exchange is already deployed at massive scale:

Date	Event
2022-10	Cloudflare and Google begin experimental X25519+Kyber deployment
2023-08	Signal deploys PQXDH (X25519 + Kyber-1024) for all new chats
2024-04	Chrome 124 enables X25519Kyber768 by default for all users
2024-08	NIST publishes FIPS 203 (ML-KEM), finalizing the standard
2024-09	AWS Key Management Service adds ML-KEM hybrid support
2024-11	Apple iMessage deploys PQ3 protocol with ML-KEM
2025+	Ongoing migration of TLS, SSH, VPN, and certificate infrastructure

The transition is happening now, driven by the harvest-now-decrypt-later threat. Organizations with long-lived secrets (government, healthcare, finance) are migrating first.

# === Concept Map: Module 08 concepts in hybrid TLS ===

concept_map = [
    ('ECDH (Module 06)',
     'Classical key exchange: X25519 component provides security against\n'
     'classical attackers. Relies on ECDLP hardness on Curve25519.'),
    ('LWE (08d)',
     'Hardness foundation: ML-KEM security reduces to Module-LWE.\n'
     'The noise term e is what makes the scheme quantum-resistant.'),
    ('Ring-LWE (08e)',
     'Efficiency: polynomial ring R_q = Z_q[x]/(x^256 + 1) compresses\n'
     'keys from megabytes to ~1 KB. NTT enables fast multiplication.'),
    ('LLL / Lattice reduction (08c)',
     'Parameter selection: dimensions chosen so that the best lattice\n'
     'reduction (BKZ) cannot find short enough vectors to break ML-KEM.'),
    ('Hybrid construction',
     'Defense in depth: K = KDF(K_ECDH || K_MLKEM) requires breaking\n'
     'both classical and post-quantum schemes simultaneously.'),
]

print('=== CONCEPT MAP: Module 08 in Hybrid TLS ===\n')
for concept, role in concept_map:
    print(f'  [{concept}]')
    for line in role.split('\n'):
        print(f'    {line}')
    print()

Summary

Concept	Key idea
Hybrid key exchange	Combines classical ECDH (X25519) with post-quantum ML-KEM (Kyber) in a single TLS 1.3 handshake
Defense in depth	The final key comes from both shared secrets, so an attacker must break both schemes simultaneously
Zero extra round trips	Both key shares fit in the existing ClientHello and ServerHello messages. The only cost is about 2.2 KB of additional bandwidth.
Already deployed	Chrome, Cloudflare, Signal, AWS, and Apple have all shipped post-quantum hybrid key exchange
Module 08 in practice	LWE is the hardness assumption, Ring-LWE is the efficiency mechanism, and lattice reduction determines the security parameters

---

Back to Module 08: Lattices and Post-Quantum Cryptography