Post-Quantum TLS Migration: Stop Paying the 150ms Retry Tax

TL;DR A post-quantum TLS migration is what cut Cloudflare’s handshake retries from 52% to 3.7% — proactively scanning each origin to pick the correct key-exchange group, including the hybrid X25519MLKEM768, before a client ever guesses wrong. Any origin running OpenSSL 3.5+, BoringSSL, or rustls 0.23+ can capture the same win directly: test with openssl s_client -groups X25519MLKEM768, confirm the handshake completes in one round trip, and the ~150ms retry tax disappears from every new connection. The migration itself is five checks, not a rewrite.

What Is Post-Quantum TLS, and Why Is X25519MLKEM768 Different From Kyber768?

Post-quantum TLS means the key-exchange step of a TLS 1.3 handshake no longer relies solely on elliptic-curve math that a large enough quantum computer could eventually break. X25519MLKEM768 is a hybrid group: it runs classical X25519 and post-quantum ML-KEM768 in parallel and combines both results into the session key, so an attacker has to break both primitives, not just one, to recover the connection.

The naming matters more than it looks. Kyber768 was the NIST Round 3 finalist algorithm that implementations experimented with under the draft codepoint X25519Kyber768Draft00. ML-KEM is the standardized descendant of Kyber, finalized in NIST’s FIPS 203 publication in August 2024 with small but protocol-breaking differences from the draft. A client offering the draft codepoint and a server that only understands the standardized one will not negotiate post-quantum key exchange at all — they’ll silently fall back to a classical group, which is exactly the kind of failure this checklist exists to catch before it ships.

Why the “Retry Tax” Exists — and Why Post-Quantum Made It Worse

TLS 1.3 was designed to save a round trip: the client guesses which key-exchange group the server prefers and sends a key share for that guess in its very first message. When the guess is right, the handshake finishes in one round trip. When it’s wrong, the server has to respond with a HelloRetryRequest naming the group it actually wants, the client tries again, and the connection pays for a full extra round trip before a single byte of application data moves.

Before Cloudflare built active origin scanning, it defaulted every connection to guessing X25519 — a reasonable bet for a classical-only world, but a bet that failed roughly 52% of the time against real-world origins. Post-quantum connections had it worse: a cold guess of a post-quantum group was even less likely to match what an origin supported, so post-quantum users paid the retry tax on close to every connection.

After Cloudflare started scanning origins ahead of time and ranking their real capabilities, the retry rate fell to 3.7%, latency dropped by more than 150ms at the 90th percentile, and 99.2% of post-quantum TLS 1.3 connections now complete in a single round trip. That’s across more than 45 billion post-quantum connections a day, up from roughly 25 billion, on a scan covering over a million domains — about a third of which now prefer X25519MLKEM768 outright.

How a TLS 1.3 Hello Retry Request Actually Works

The mechanics are worth tracing once, because they explain why the fix is “scan first,” not “guess better.” A TLS 1.3 ClientHello carries a key_share extension: a named group plus the client’s public key for that group. If the server’s supported list doesn’t include the guessed group, it can’t just proceed — TLS 1.3 has no mechanism to negotiate a group after the fact within the same flight of messages. So it sends HelloRetryRequest, naming the group it wants, and the client sends a second ClientHello with a fresh key share for that group. Two full messages become four, and one network round trip becomes two.

Post-quantum key shares make a wrong guess more expensive even before the round trip lands: an ML-KEM768 public key is 1184 bytes, against X25519’s 32 bytes. A guessed-wrong post-quantum key share is close to 40x the wasted bytes of a guessed-wrong classical one, on a message that was going to be thrown away regardless. Scanning an origin ahead of time and caching what it actually supports — which is what Cloudflare’s Automatic Key Exchange does, re-checked daily — turns every one of those guesses into a known answer instead of a bet.

How to Check Whether Your Origin Already Supports X25519MLKEM768

Run this against any origin you control, whether or not it sits behind a CDN:

openssl s_client -connect yourhost:443 -groups X25519MLKEM768 -tls1_3 < /dev/null

Look for the Negotiated TLS1.3 group: line in the output. If it reads X25519MLKEM768, that endpoint is already there. If the handshake instead negotiates a classical group, or the connection fails, your TLS-terminating software either lacks the group or isn’t configured to offer it — and that’s the endpoint to fix first.

This matters even for domains that sit behind Cloudflare, because Automatic Key Exchange only optimizes the leg it controls — client-to-edge, and edge-to-your-origin. It has no visibility into TLS you terminate somewhere else: an internal load balancer in front of a database proxy, a service mesh sidecar, or an API your own clients call directly without going through the CDN at all. Cloudflare Radar’s public quantum-safe adoption data is a useful sanity check for how far the ecosystem has moved, but it can’t tell you anything about infrastructure Cloudflare never sees.

The Post-Quantum TLS Migration Checklist

1. Inventory every TLS-terminating point — reverse proxies, load balancers, service-mesh sidecars, and application servers, not just the public-facing edge. Post-quantum support has to land on each one independently.

2. Check each one’s TLS library version against the table below, since ML-KEM768 support arrived on different timelines across the ecosystem.

3. Test the live handshake with openssl s_client -groups X25519MLKEM768:X25519 -tls1_3 — listing both groups confirms the post-quantum group is preferred while verifying a classical client can still fall back cleanly.

4. Enable it explicitly if your library requires it. Most releases from the last two years enable the group by default once it’s compiled in; a few still gate it behind an explicit cipher-suite or group list.

5. Roll out to a small traffic slice first and watch handshake failure rate and CPU. The larger ClientHello and the ML-KEM keygen/encapsulation step both cost slightly more per connection, and that cost only shows up at real connection volume.

What Breaks If You Enable Post-Quantum TLS Without Testing?

The largest ClientHello a hybrid handshake produces is still small in absolute terms, but it’s large enough to cross a single-packet assumption some older middleboxes and load balancers still make — a handshake that used to fit in one TCP segment can now span two, and hardware that fragments that badly instead of just accepting it will drop or mangle the connection. This is the failure mode canary rollout in step 5 exists to catch, and it shows up as a spike in handshake failures from a specific network path, not a global outage.

A fleet with mismatched library versions across nodes is the second common failure: one server negotiates the post-quantum group, a sibling behind the same load balancer still can’t, and the resulting inconsistency looks like random flakiness rather than the version skew it actually is. And if your environment needs FIPS-validated cryptography, note that ML-KEM768 is FIPS 203 approved while implementations still speaking the draft X25519Kyber768Draft00 codepoint are not — a detail worth confirming with whoever owns compliance before you rely on it in a regulated environment.

If you’re running containerized workloads and haven’t recently audited what’s actually consuming CPU during a TLS-heavy rollout, the same instrumentation habits from reducing a Rust struct’s memory footprint apply directly — measure before you optimize, and don’t guess at where the cost is. For the broader question of whether your infrastructure needs this level of edge sophistication at all, see the honest cost breakdown in Docker Swarm vs Kubernetes. And if the CVE-shaped worry here reminds you of dependency-driven security fire drills, the vLLM CVE-2025-9141 response is a good template for triaging a library-version problem calmly instead of patching blind.

FAQ

What is X25519MLKEM768?

It’s a hybrid TLS 1.3 key-exchange group that runs classical X25519 (elliptic-curve Diffie-Hellman) and post-quantum ML-KEM768 side by side, then combines both shared secrets into one session key. Breaking the connection requires breaking both algorithms, so a future flaw in ML-KEM alone — or in X25519 alone — doesn’t compromise the session. It’s the standardized successor to the earlier X25519Kyber768Draft00 codepoint used during NIST’s draft period.

Do I need to do anything if my site sits fully behind Cloudflare?

No — Cloudflare’s Automatic Key Exchange already scans your origin and picks the fastest mutually supported group for the Cloudflare-to-origin leg, and the client-to-Cloudflare leg is handled the same way for every domain on the network. This checklist matters for the TLS endpoints you run yourself: origins reachable directly from the internet, internal service-to-service TLS, and any load balancer or reverse proxy that terminates TLS outside Cloudflare’s edge.

Which TLS libraries support ML-KEM768 today?

OpenSSL added it as a default group starting with the 3.5 series, BoringSSL has carried it for over a year and is what Chrome uses, and rustls added support in the 0.23 line through its aws-lc-rs or ring crypto provider. Go’s standard library shipped experimental post-quantum key exchange in 1.23 and has continued hardening it in later releases. Always confirm the exact version installed on each machine — a fleet with mismatched library versions is the most common rollout failure.

Will post-quantum key exchange slow down my TLS handshake?

The cryptographic operations themselves are fast — ML-KEM was designed for speed, not just security margin — but the ClientHello grows by roughly 1.2KB because the ML-KEM768 public key is 1184 bytes versus X25519’s 32 bytes. On a healthy network that’s not perceptible; on paths with small MTUs or older middleboxes that assume a small handshake, it can trigger fragmentation issues worth testing for before a full rollout.

Is Kyber768 the same thing as ML-KEM768?

They’re closely related but not interchangeable at the protocol level. Kyber768 was the NIST Round 3 finalist algorithm; ML-KEM is the standardized version of it, finalized in NIST’s FIPS 203 publication in August 2024 with minor technical differences from the draft. TLS implementations that speak the draft codepoint X25519Kyber768Draft00 will not negotiate with a peer that only offers the standardized X25519MLKEM768, which is one more reason to check both ends explicitly rather than assume compatibility.

How do I test post-quantum TLS support from the command line?

Run openssl s_client -connect yourhost:443 -groups X25519MLKEM768 -tls1_3 against your own origin and read the “Negotiated TLS1.3 group” line in the output. If it names X25519MLKEM768, you’re done. If the connection falls back to a classical group or fails outright, your TLS stack either doesn’t support the group yet or isn’t configured to prefer it, and that’s your starting point for the checklist above.

Sources

• Cloudflare, Automatic Key Exchange: faster, post-quantum secure origin handshakes for 45 billion daily connections (and counting) — the origin-scanning mechanism and every retry-rate, latency, and connection-volume figure cited here.
• NIST, FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard — the finalized ML-KEM specification that superseded the Kyber draft.
• Cloudflare Radar, Adoption and usage trends — ongoing public data on post-quantum and TLS 1.3 adoption across the network.