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

Every time Cloudflare opens a new TLS 1.3 connection to an origin server, we have to make a guess: the protocol requires us to commit to a key agreement algorithm in the very first packet we send, before the origin has told us anything about itself or what it can support. If we guess right, the handshake completes in one round trip. Guess wrong, and the origin replies with a HelloRetryRequest, we start over, and the connection costs two round trips.For years, our guess was the same for every origin on the Internet: X25519. Widely supported, but as it turns out, suboptimal for roughly 30% of the origin connections we've since measured.Today we're announcing Automatic Key Exchange, an extension of Automatic SSL/TLS that replaces the guess with a measurement. We probe each origin to learn which key agreement algorithms it supports and prefers, then lead with that algorithm on the first try, preferring the post-quantum hybrid X25519MLKEM768 wherever the origin can speak it. With the ongoing rollout of Automatic Key Exchange across origin connections, HelloRetryRequests fell from roughly 52% to 3.7%, cutting more than 150 ms off connection handshake latency at p90. In addition, as part of our ongoing rollout, hundreds of thousands of domains now have post-quantum origin connections that nobody had to configure, with that number growing daily.While the milliseconds are important, that second part may matter more. Somewhere right now, an adversary is recording encrypted traffic it can't read yet, betting that it will be able to in the future (an attack known as harvest-now, decrypt-later). Cloudflare is sprinting to make the Internet quantum-secure by 2029, the year some industry experts estimate classical encryption algorithms could be breached. That day has a name: Q-Day. Meeting that deadline can't depend on millions of website operators each becoming expert cryptographers. It has to be automatic. Until today, preferring post-quantum connections required a manual setting: either you turn them on from Cloudflare’s side, or you have your origin server insist upon them. It was easy to get wrong. But today it’s just … automatic!TLS 1.3 handshake: guessing the key exchange algorithmEvery secure web connection starts with a TLS handshake, which authenticates the server and derives a shared secret key. Our previous Automatic SSL/TLS blog posts cover that process in detail.As Cloudflare operates as a reverse proxy, what appears to be a single secure connection is actually two: one between the visitor and Cloudflare, and a second between Cloudflare and the origin server. Each connection operates independently, with its own handshake, identity checks, and encryption keys.Automatic Key Exchange affects the second connection. When Cloudflare connects to the origin, Cloudflare acts as the TLS client and must begin the handshake. We initiate the connection by sending a ClientHello message containing the hostname and a list of supported key agreement algorithms.In the happy path, TLS 1.3 can establish a new encrypted connection in just one network round trip (shown on the left in the diagram above). In this case, Cloudflare sends a ClientHello listing its supported key agreement algorithms, along with one or more client keyshares. If the origin accepts that choice, it responds and the handshake completes. This predictive key exchange is an innovation of TLS 1.3, and a large part of why it’s faster than TLS 1.2.Otherwise, if the origin prefers a different option, it sends a HelloRetryRequest (HRR) and asks Cloudflare to try again (the flow on the right in the diagram above). Cloudflare then sends a second ClientHello, generating a new client keyshare based on the key agreement algorithm specified by the origin. The connection still succeeds, but the retry adds a full network round trip before Cloudflare can fetch content. This is like missing a shortcut in Mario Kart: you still reach the finish line, but you lose the time the shortcut was supposed to save.Either way, using the client keyshare, the server generates the shared key. The server then returns a server keyshare with which the client can also compute the shared key. This shared key is used to protect the rest of the connection using symmetric cryptography, such as AES.The cost of the safe guessFor years, our initial client keyshare guess for origin connections using TLS 1.3 was static; we'd always send X25519 while advertising support for other key agreement algorithms. This was a safe strategy because over 95% of origins support X25519, and any origins that didn’t could issue a HelloRetryRequest (HRR) without breaking the connection.However, X25519 is vulnerable to quantum computers. Since September 2023, we have advertised support of post-quantum key agreement to origins: first as X25519Kyber768Draft00 and today as X25519MLKEM768 (the standardized version of the algorithm). Crucially, advertising support differs from leading with a keyshare in the ClientHello. An X25519MLKEM768 keyshare is 1,216 bytes compared to X25519's 32 bytes, pushing the ClientHello past a single network packet. While the TLS standard allows multi-packet segments, some legacy middleboxes and origin servers can fail when receiving ClientHello messages split across multiple packets. In our previous study, around 0.34% of scanned origins failed to complete the TLS handshake when receiving a post-quantum keyshare first, while the vast majority of origins still relied on classical X25519.Therefore, to prevent any possible breakage of origin connections, we used HRR as a safety valve. We only advertised post-quantum support, sent a classical X25519 keyshare, and required capable origins to request a post-quantum exchange via retry. For origins that did not support the HRR flow, customers had the option to manually opt into leading with X25519MLKEM768 keyshare. Between 2023 and today, the percentage of origins supporting post-quantum key exchange algorithms grew from 0.5% to 12.8%, and we expect that to keep climbing as hosting stacks upgrade to PQ safe algorithms.While safe, this default of only upgrading to post-quantum secure connections via retry added unnecessary latency for two reasons:While all modern builds of OpenSSL, BoringSSL, and rustls support X25519MLKEM768, they handle a classical X25519 keyshare differently. Depending on the build, some older builds may accept it by default unless explicitly configured to prioritize the post-quantum secure keyshares, while newer builds will immediately issue an HRR to prioritize post-quantum connections.Over 6% of origins prefer either P-256 or P-384 over X25519, triggering an HRR round trip even for purely classical connections due to our static choice of initial client keyshare.To eliminate these wasted round trips, we began scanning origin servers to map their exact key agreement capabilities as part of Automatic SSL/TLS. Using these scan results, we automatically tailor our initial keyshare on a per-origin basis: maximizing post-quantum connections without risking site outages, all while making our connections faster for applicable domains.Extending Automatic SSL/TLS to the post-quantum ageAutomatic SSL/TLS now includes Automatic Key Exchange. Across millions of origins, guessing different keyshares carries operational risk, because we have no advance knowledge of how any individual origin is configured. So rather than infer capability, we measure it directly, reusing the scanning pipeline that already powers Automatic SSL/TLS.For a growing number of origins, this delivers post-quantum key agreement on the very first try at connection setup, without extra round trips and without requiring any manual setup.This is how it works: For each TLS 1.3 capable origin, we run a series of a few lightweight TLS handshakes, each offering exactly one key agreement group: X25519, P-256, P-384, P-521, or X25519MLKEM768. Together these probes tell us the full set of algorithms the origin supports. And because the active scanning happens outside your production traffic path, we confirm that both your origin and the network in between can handle connections with a stronger key agreement before any real traffic depends on it.A single domain often fronts multiple subdomains that may resolve to different origins with varying capabilities.