Automatic Key Exchange: faster, post-quantum secure origin handshakes for 45 billion daily connections (and counting)

Cloudflare cut p90 origin handshake latency by over 150 ms while scaling post-quantum encryption to 45 billion daily connections, simply by stopping guessing what key exchange algorithm servers wanted. 👇

In TLS 1.3, the client must commit to a key agreement algorithm in the very first packet (`ClientHello`). If the server prefers a different algorithm, it replies with a `HelloRetryRequest` (HRR) and forces the connection to restart, wasting a full network round trip. For years, Cloudflare statically guessed `X25519` for every origin connection on the Internet. That safe default meant over 50% of scanned origin connections wasted time on retries, either because the origin preferred a different classical curve or supported new post-quantum algorithms. Cloudflare couldn't just blindly send larger post-quantum key shares first, either, as that broke roughly 0.34% of legacy middleboxes and servers.

To fix this, Cloudflare built Automatic Key Exchange. The system actively probes origin servers out-of-band to map their capabilities, then dynamically picks the optimal key share for the very first packet—prioritizing post-quantum protection without risking outages.

The pipeline maps and applies key exchange preferences through a continuous loop:

Out-of-band active scanning: Cloudflare runs lightweight TLS handshakes against origins outside of production traffic, offering specific individual curves (`X25519`, `P-256`, `P-384`, `P-521`, and `X25519MLKEM768`) to map exact server support. Traffic-weighted aggregation: Because subdomains on a single domain often point to different backends, Cloudflare probes subdomains individually and weights algorithm preferences by live HTTP traffic volume. Strict preference ordering: The system selects the strongest supported key exchange, placing post-quantum hybrids (`X25519MLKEM768`) first, then falling back to the fastest classical curve the origin accepts. Canary validation: Cloudflare rolls out the selected key share to a small slice of origin traffic while monitoring error and HRR rates, automatically rolling back if retries spike above baseline. Daily rescans: Scanners re-evaluate every origin daily, immediately upgrading traffic to post-quantum encryption the moment an origin stack updates.

Across scanned origins, the `HelloRetryRequest` rate plummeted from 52% to 3.7%. Shaving off that retry eliminated an entire round trip during connection setup, cutting p90 handshake latency by over 150 ms. Now, 99.2% of post-quantum TLS 1.3 connections to scanned origins complete on the first try, securing 45 billion daily connections against future quantum attacks automatically.