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

Summary

Cloudflare’s Automatic Key Exchange addresses extra TLS 1.3 handshake latency and the difficulty of enabling post-quantum origin connections without manual configuration. Cloudflare previously sent an X25519 keyshare as its first guess; origins preferring another group returned a HelloRetryRequest, while sending X25519MLKEM768 indiscriminately risked oversized, split ClientHello messages and legacy compatibility failures. The system reuses Automatic SSL/TLS scanning to run lightweight handshakes for each supported group, map every origin’s capabilities and preferences, and tailor the initial keyshare, preferring X25519MLKEM768 when supported. During rollout, HelloRetryRequests dropped from roughly 52% to 3.7%, cutting more than 150 ms from p90 handshake latency, while hundreds of thousands of domains gained post-quantum origin connections without configuration. Cloudflare says it plans to extend scanning to post-quantum authentication, including ML-DSA certificates and future Merkle Tree Certificates.

Takeaways

1. 1

   HelloRetryRequests fell from roughly 52% to 3.7% during rollout, reducing p90 connection handshake latency by more than 150 ms.

2. 2

   X25519MLKEM768 keyshares are 1,216 bytes versus 32 bytes for X25519, which can split ClientHello messages across packets and expose compatibility issues with legacy middleboxes or origin servers.

3. 3

   The share of origins supporting post-quantum key agreement rose from 0.5% in 2023 to 12.8%, while hundreds of thousands of domains received post-quantum origin connections without manual setup.