Case Study: Migrating a TLS Stack to Post-Quantum Cryptography

Executive Summary

Post-quantum migration is usually discussed as a policy question. It is an engineering project, and the engineering has a specific shape: the algorithms work fine and the packet sizes break things.

This case study migrates a real TLS deployment — 40 million handshakes a day, a mix of browsers, mobile apps, and embedded devices — to hybrid post-quantum key exchange. It finds the handshake growing past a network boundary that causes measurable failures, and works through the diagnosis and the fixes.

Skills applied

• Deploying hybrid key exchange in TLS 1.3 (§30.7).
• Quantifying handshake size increases and their network effects (§30.10).
• Diagnosing MTU and middlebox failures.
• Sequencing a migration by risk.

Phase 1: What changes

TLS 1.3 handshakes use ECDHE for key exchange and RSA or ECDSA certificates for authentication. Both are Shor-vulnerable, and they migrate on different timelines:

Key exchange first, decisively. A recorded handshake can be broken retroactively to decrypt the session; a signature can only be forged in real time, so a forged certificate in 2040 cannot retroactively compromise a 2026 session. This asymmetry sets the migration order and is frequently missed.

Phase 2: Hybrid key exchange

The deployed approach combines classical and post-quantum key exchange so that breaking either alone is insufficient:

X25519MLKEM768 = X25519 (classical ECDH) ‖ ML-KEM-768 (post-quantum)
shared_secret  = KDF(x25519_secret ‖ mlkem_secret)

Hybrid is the right choice during transition for two reasons: ML-KEM is young and could have an undiscovered weakness, and classical ECDH is well-understood but quantum-vulnerable. Together, an attacker must break both.

Configuration is a one-line change in modern stacks:

ssl_ecdh_curve X25519MLKEM768:X25519:secp256r1;

Phase 3: The size problem

The ClientHello grows from ~300 bytes to over 1,500 bytes — and that crosses a boundary that matters.

The 1,500-byte MTU. Standard Ethernet MTU is 1,500 bytes. A ClientHello that previously fit in one packet now requires two. Consequences:

• An extra round trip in some stacks, adding latency.
• Middlebox failures. Some firewalls, load balancers, and DPI appliances assume the ClientHello arrives in a single packet, and drop or mishandle split ones.
• QUIC amplification limits. QUIC restricts a server to sending 3× the bytes received before address validation; a larger ClientHello changes that arithmetic, generally favourably, but interacts with anti-amplification logic.

Phase 4: What actually broke

Rolling out to 5% of traffic:

Two real problems:

Embedded devices. Constrained TLS stacks with fixed buffers — often 2 KB — could not hold the larger ClientHello. Failure mode was a connection reset with no useful error. These devices are field-deployed, some without remote update.

Corporate middleboxes. A specific vendor's DPI appliance dropped fragmented ClientHellos. Failures clustered by source ASN, which is how the pattern was identified.

Phase 5: The fixes

For embedded devices: 1. Detect and exempt by client fingerprint, serving classical-only to known-constrained populations — a stopgap that must be time-bounded, or it becomes permanent. 2. Push firmware updates with larger buffers where possible. 3. Segment those devices onto a separate endpoint with its own migration timeline.

For middleboxes: identify the affected networks, notify the vendor, and exempt temporarily. The vendor shipped a fix, though enterprise upgrade cycles are slow.

General mitigations: - Serve the smallest adequate parameter set. ML-KEM-768 is the recommended level; ML-KEM-1024 costs more bytes for security most deployments do not need. - Ensure clean fallback. TLS negotiation should degrade to classical when the client cannot do hybrid — verified explicitly, not assumed. - Monitor by client population. Aggregate success rates hide 5.9% failures in a small segment.

Phase 6: The rollout that worked

Final state: 99.7% of handshakes use hybrid post-quantum key exchange; 0.3% fall back to classical, tracked as a burn-down list with owners and dates.

Performance: median handshake latency increased ~1.2 ms; CPU cost rose ~4%. ML-KEM is fast — often faster than ECDH — so the cost is bandwidth, not computation.

Discussion Questions

1. Key exchange migrates before authentication. Explain the asymmetry and why it is not merely a matter of convenience.
2. The failure was bandwidth, not compute. What does that suggest about where PQC migration difficulty actually lies?
3. Exempting constrained devices is a stopgap that tends to become permanent. How would you prevent that?
4. Aggregate success rate hid a 5.9% failure in one segment. What monitoring would have caught it in phase 1?

Your Turn: Extensions

• Configure a test server with hybrid key exchange and measure ClientHello size with openssl s_client and a packet capture.
• Measure handshake latency for classical, hybrid, and PQC-only configurations.
• Identify which of your clients have TLS buffers under 4 KB.
• Draft the migration plan for certificate authentication and compare its urgency to key exchange.

Key Takeaways

• Migrate key exchange first: recorded handshakes are retroactively breakable, while signatures can only be forged live.
• Hybrid schemes such as X25519MLKEM768 mean an attacker must break both the classical and post-quantum component.
• ML-KEM is computationally fast; the cost is size — the ClientHello crosses the 1,500-byte MTU and breaks assumptions in middleboxes and constrained devices.
• Real failures cluster in specific client populations, so monitor by segment rather than in aggregate.
• Roll out in stages with explicit gates, retain classical fallback, and treat exemptions as a time-bounded burn-down list.