Hybrid Certificates and Crypto-Agility: Implementing the First Phase of a PQC Migration

The first phase of a post-quantum migration is not replacing your cryptography. It is enabling a second, quantum-resistant algorithm alongside the one you already run, and proving you can turn algorithms on and off without breaking anything. That is a smaller, more tractable piece of work than most roadmaps imply, and it is the piece you can start now.

Most post-quantum guidance is written at the altitude of the timeline: harvest-now-decrypt-later, the 2035 horizon, the standards that landed in 2024. All true, none of it tells an engineering team what to do on Monday. The honest answer is that the first move is narrow and specific. You enable a hybrid key exchange on the connections that carry data worth stealing, you make your certificate and algorithm selection something you can change without a redeploy, and you find out where in your estate cryptography is pinned so hard that changing it is a project in itself. Everything else in the migration depends on getting that far.

Two migrations, and only one of them is urgent

The phrase “post-quantum migration” collapses two different problems that have different clocks. The first is confidentiality: the key exchange that protects a TLS session. If an adversary records that traffic today, a future quantum computer running Shor’s algorithm could recover the session key and read it. That is the harvest-now-decrypt-later threat, and it is live now for any data whose sensitivity outlasts the arrival of a cryptographically relevant quantum machine. The second is authentication: the digital signatures in your certificates and code-signing chain. A signature cannot be forged retroactively, so that threat only bites once quantum machines exist, not before.

This distinction decides sequencing. The confidentiality problem is urgent and has a clean, deployable answer today: hybrid key exchange using ML-KEM, NIST’s standardised key encapsulation mechanism (FIPS 203, the standard that superseded the algorithm formerly known as Kyber). The signature problem — migrating certificates and PKI to ML-DSA — is real but later, and is a separate track with its own ecosystem dependencies. Phase one is key exchange. Do not let a board conversation about “post-quantum certificates” fuse the two into one intractable programme.

Why hybrid, rather than pure PQC

A hybrid key exchange runs a classical algorithm and a post-quantum one together and combines both shared secrets, so the connection is secure unless both are broken. The dominant deployed construction pairs X25519 (the elliptic-curve exchange you almost certainly already use) with ML-KEM-768, published as the TLS group X25519MLKEM768 at IANA codepoint 0x11EC. Chrome, Cloudflare and others have carried it in production since 2024.

The reason to run hybrid rather than switching straight to pure ML-KEM is straightforward risk management. ML-KEM is new; the classical curves are decades-hardened. If an implementation flaw or cryptanalytic surprise lands on the post-quantum algorithm, the classical half still protects you, and vice versa against a quantum attack. You give up nothing except a few hundred bytes per handshake and get a hedge across the exact uncertainty that makes people nervous about migrating early. That is the pragmatic default for the transition period, and it is why the interim guidance across NIST, and the US CNSA 2.0 timeline, treats hybrid as acceptable rather than a stopgap to be apologised for.

What turning it on actually looks like

On a modern stack the change is a configuration line, not a rebuild. OpenSSL 3.5, released April 2025, is the first upstream release to ship ML-KEM as a built-in provider, so a front-end terminating TLS on OpenSSL 3.5 or later can offer the hybrid group by adding it to the group preference list. It is not enabled by default in your server config — you have to name it, ordered ahead of the classical fallback so capable clients negotiate hybrid and older clients quietly fall back.

# nginx, built against OpenSSL 3.5+ (check: nginx -V)
# Offer the hybrid group first; keep classical fallbacks for old clients.
# Despite the legacy name, ssl_ecdh_curve sets the TLS group list.
ssl_protocols        TLSv1.3;
ssl_ecdh_curve       X25519MLKEM768:X25519:P-256;

# Verify from a client with OpenSSL 3.5+:
#   openssl s_client -connect example.com:443 -groups X25519MLKEM768
# A successful hybrid handshake reports:
#   Negotiated TLS1.3 group: X25519MLKEM768

That is the whole mechanism for a reverse proxy or load balancer that owns TLS termination. The work is not the directive. The work is everything around it: confirming your build actually links a PQC-capable OpenSSL, establishing that clients negotiate as expected, and knowing what breaks when they do not.

The client-compatibility problem is the real work

Hybrid key shares are larger than classical ones, and the ML-KEM-768 share pushes the TLS ClientHello past the size some middleboxes and older TLS stacks tolerate. The failure mode is not a clean negotiation downgrade; it is a broken connection at a legacy proxy, a load balancer with a stale TLS library, or a client that mishandles an unrecognised group. This is the historical reason earlier post-quantum rollouts were staged carefully rather than flipped globally.

So pilot it as you would any change with a blast radius. Enable the hybrid group on one internet-facing service, ideally one whose clients you control or can observe. Instrument the handshake: capture which group each connection negotiated so you can see the hybrid uptake curve and, more importantly, spot the population that fails or falls back unexpectedly. Test against your actual client estate — old mobile apps, embedded devices, partner integrations pinned to a specific TLS profile — not just a current browser. Keep the classical fallback in place throughout; the point of hybrid is that you never have to choose between quantum resistance and reachability during the transition.

Crypto-agility is an inventory problem before it is a code problem

The reason a one-line config change is worth calling a “first phase” is that it forces the question the whole migration turns on: can you change a cryptographic algorithm without a project? For the edge proxy, yes. For the payment library with a hard-coded curve, the mutual-TLS between two internal services with the group baked into both sides, the hardware security module that only speaks the algorithms in its firmware, the IoT fleet that cannot be updated in the field — often no. Those are the places where cryptography is pinned, and you cannot migrate what you have not located.

So the deliverable of phase one is two things: a working hybrid pilot on the edge, and a cryptographic inventory that records where in the estate an algorithm is chosen, by what, and how hard it is to change. That inventory is the same abstraction-layer discipline that regulators are beginning to expect for other reasons — the crypto-agility a hybrid pilot and product-security duties both demand. Build it once and it serves both. The migration proper is then a prioritised worklist against a known map, not a search of an unknown estate under a deadline.

The 2035 horizon is not the reason to start. The reason to start is that the first phase is small, reversible and mostly diagnostic — and it tells you, before any of it is urgent, exactly which parts of your estate are going to be the expensive ones. For the board framing of why that ordering matters, the point is simple: the firms that struggle in 2034 will be the ones that never found out where their cryptography was pinned.