HelloRetryRequests Dropped from 52% to 3.7%: Cloudflare's New Trick for Automatic Key Exchange

Hi, it's me, Shiichan! Today's topic from the Cloudflare Blog is a quiet but pretty serious one — it's about the plumbing that keeps the Internet's encryption fast and safe.

Cloudflare Blog blog.cloudflare.com

What was announced?

Cloudflare Blog introduced Automatic Key Exchange, a new system that probes each origin server's TLS 1.3 support to learn which key agreement algorithms it supports, then leads with the most secure option available. It's already running across 45 billion connections a day.

The story so far

In TLS 1.3, the client has to commit to a key agreement algorithm in its very first packet. For years, Cloudflare always guessed X25519. Measurements showed that guess wasn't optimal for roughly 30% of origins — and when the guess was wrong, it triggered a HelloRetryRequest (HRR), stretching what should be a one-round-trip handshake into two.

There's also a security angle: X25519 is vulnerable to quantum computers. The safer post-quantum hybrid, X25519MLKEM768, uses a 1,216-byte key versus X25519's 32 bytes, which splits the ClientHello across multiple packets. About 0.34% of origins couldn't handle a multi-packet ClientHello, so Cloudflare couldn't just flip everyone over to post-quantum overnight.

What changes

Automatic Key Exchange runs a handful of lightweight TLS handshakes against each origin, each one offering exactly one key agreement group — X25519, P-256, P-384, P-521, or X25519MLKEM768 — to learn what that origin actually supports. It then prioritizes the post-quantum hybrid when available, falling back to classical algorithms otherwise, and weighs each subdomain by its actual traffic volume so it can make smart choices even within a single domain.

The results are striking: the share of connections requiring an HRR dropped from roughly 52% to 3.7%, and p90 handshake latency dropped by more than 150ms. 99.2% of post-quantum TLS 1.3 connections now complete in a single round trip. Across a million scanned domains, roughly 64% still use X25519, about 33% upgraded to X25519MLKEM768, and the remaining 3% use other classical curves.

Dive Deep

Most users don't need to configure anything — it's automatic. For compliance needs, you can lock the behavior down from the dashboard, under SSL/TLS > Overview > Configure > Origin connection & post-quantum encryption:

• Post-quantum hybrid: restrict to X25519MLKEM768 only
• FIPS: restrict to FIPS-compliant algorithms only

One important caveat: enforcing post-quantum hybrid on an origin that doesn't support X25519MLKEM768 leaves no mutually supported algorithm, so all TLS connections to that origin will fail.

The rollout itself is cautious — new settings first apply to a small slice of an origin's traffic, with failure rates and HRR rates monitored, and Cloudflare rolls the change back automatically if things get worse. Daily rescans keep the system up to date as origins change their own configuration.

You can check whether your own origin supports post-quantum key exchange using the public Cloudflare Radar tool. If it doesn't, options include switching to Cloudflare Tunnel (cloudflared already supports post-quantum key agreement) or upgrading your TLS stack to a recent version of BoringSSL, OpenSSL, or rustls.

Looking ahead, Cloudflare plans to move from domain-level to per-subdomain/per-origin granularity, add on-demand rescans from the dashboard or API, and automate post-quantum authentication with ML-DSA certificates plus downgrade-attack protection.

Wrap-up

• Cloudflare launched Automatic Key Exchange, which automatically picks the best TLS 1.3 key agreement algorithm for each origin.
• The old approach always guessed X25519, which was suboptimal for about 30% of origins and caused HRRs on about 52% of connections.
• The new system cut HRRs to 3.7% and reduced p90 handshake latency by more than 150ms.
• It scans origins daily and prioritizes post-quantum hybrid (X25519MLKEM768) automatically when supported.
• You can lock in post-quantum-only or FIPS-only mode from the dashboard, but be careful — that can break connections if your origin isn't ready.
• Check your own origin's readiness on Cloudflare Radar if you work on TLS configuration or post-quantum migration.