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.