up:: In the Protocols MOC

Cryptographic Interoperability

Cryptographic interoperability is the ability of two independently built systems to complete a cryptographic operation together, a handshake, a signature verification, a decryption, when they may support different algorithms, protocol versions, or encodings. In the post-quantum transition it is the property that decides whether a standardized algorithm actually protects a live connection or silently fails to, because a new algorithm secures nothing until both ends of a connection, and every device on the path between them, can advertise it, agree on it, and parse it the same way. This is why the genuinely hard part of PQC begins after the standards publish, when a network is running a mix of old implementations that have never heard of ML-KEM and new ones that lead with it, and the two have to coexist on the same wire.

The short version:

• Interoperability is the post-standards problem. FIPS 203 and FIPS 204 publishing doesn’t protect a single connection; a connection is protected only when both endpoints, and every middlebox between them, agree on the new algorithm and can parse its bytes.
• Old and new implementations have to run side by side for years, so every migration passes through a long window where a modern client meets a legacy server, a modern server meets a legacy client, and a legacy inspection box sits in between.
• Four failure modes account for almost all of it, an unknown-algorithm negotiation failure, an oversized handshake dropped by a middlebox, a mixed old-and-new pair falling back to classical, and a mismatched algorithm identifier or OID that a verifier rejects.
• Crypto-agility plus negotiation design is what keeps interoperability working, algorithms are advertised and chosen at connection time rather than hardcoded, so an endpoint that lacks the new one falls back cleanly instead of breaking outright.
• Fallback is silent. A connection that dropped to classical looks identical to one that went post-quantum, so interoperability is confirmed on the wire, not assumed from the fact that a config flag was set.

Picture two engineers who both speak fluent English but grew up with different dialects, meeting in a warehouse to move a crate together. If one says “ready” and waits for “ready” back, they lift in sync. If one has learned a new word for it that the other has never heard, the second engineer just stands there, and nothing moves, even though both are willing and able. Now add a supervisor at the door who was trained to wave through short instructions and stop long ones, and a perfectly good long instruction gets blocked before it ever reaches the floor. That warehouse is a post-quantum network. The cryptography works in the lab; getting two strangers and the doorman to agree in real time is the fight.

What is cryptographic interoperability?

Cryptographic interoperability is the property that two systems built by different people, at different times, on different libraries, can still perform a shared cryptographic operation because they can negotiate a common algorithm, exchange values in a format they both parse, and validate the result the same way. It sits underneath every protocol in applied cryptography, because TLS, IPsec, and SSH all begin by having two ends agree on which algorithms they will use before any protected data flows.

The reason it becomes the central problem of the post-quantum era, rather than a footnote, is timing. Cryptographic standards do not deploy everywhere at once. A new algorithm lands in a fresh library release, ships in that library’s next version, then propagates through the software and hardware that depend on it over a period of years, gated by upgrade cycles, vendor firmware schedules, and regulated-change windows. During that long propagation, the population of endpoints is heterogeneous by definition, some fluent in ML-KEM and some that predate it entirely. Interoperability is the set of rules and design choices that let those two populations keep talking without either a security downgrade nobody noticed or an outage nobody predicted.

Why does interoperability get harder after the standards publish?

Because publishing a standard is the start of the coexistence problem, not the end of it. The day FIPS 203 and FIPS 204 were finalized in August 2024, exactly zero deployed connections became post-quantum, because none of the billions of already-running clients, servers, load balancers, and appliances had the new code yet.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 2024, csrc.nist.gov.

What follows is a multi-year window in which old and new implementations must interoperate on the same networks. Three structural facts make that window the hard part:

1. The population is mixed for years. Upgrade cycles are slow and uneven, so a modern client will constantly meet a legacy server, a modern server will constantly meet a legacy client, and neither side controls what the other is running. Every one of those pairings has to resolve to a working connection.
2. The new artifacts are physically bigger. Post-quantum keys, ciphertexts, and signatures are roughly ten to forty times the size of their classical equivalents, and that size lands in the exact opening messages that decades of network equipment was tuned around. Interoperability now depends on gear that has nothing to do with cryptography, the middleboxes on the path.
3. Failures are quiet. Cryptographic negotiation is designed to fall back gracefully so that connections keep working, which means an interoperability failure usually shows up as a silent security downgrade or as an intermittent connection error from one network path, not as a clear “post-quantum failed here” message.

The cryptography itself was the tractable part. Getting a heterogeneous, partially-upgraded, middlebox-laden internet to agree on the new algorithms in real time is the work that standards publication hands to everyone downstream.

What are the interoperability failure modes in a PQC migration?

There are four failure modes that account for nearly every real-world post-quantum interoperability problem, and each has a distinct root cause and a distinct fix. Reading them as a set is the fastest way to understand where a migration breaks.

Failure mode	What actually happens	Root cause	What prevents it
Unknown-algorithm negotiation failure	An endpoint offers only a post-quantum algorithm to a peer that has never heard of it, and with no common algorithm the handshake aborts outright	A peer configured post-quantum-only, or too old to know the new algorithm, with no shared fallback	Advertising both a classical and a post-quantum option so a common algorithm always exists during the transition
Oversized-handshake middlebox drop	Both endpoints support the new algorithm, but a load balancer, firewall, or inspection box on the path silently drops the larger handshake	Protocol ossification, middleboxes hardwired to the old single-packet handshake size	Testing the whole network path, and the negotiation escape hatches that shrink the first message
Mixed old-and-new fallback	A modern endpoint meets a legacy one, they find a common classical algorithm, and the connection succeeds while quietly staying quantum-vulnerable	Heterogeneous endpoint population plus fallback-by-design	Coverage across every endpoint plus wire-level verification of the negotiated algorithm
Format or OID mismatch	A signature or certificate is cryptographically valid, but the verifier rejects it because it doesn’t recognize the algorithm identifier or OID	A verifier whose library predates the identifier assignment, or a pre-standard codepoint mistaken for the final one	Every verifier upgraded to know the standardized identifier before issuers start using it

Sources: E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.3,” RFC 8446, §4.2.7, rfc-editor.org. Cloudflare, “Defending against future threats: Cloudflare goes post-quantum,” blog.cloudflare.com. NIST Computer Security Objects Register, “Algorithm Registration,” csrc.nist.gov.

What happens when a client offers ML-KEM to a server that doesn’t recognize it?

The handshake either falls back to a classical algorithm or fails outright, and which one happens depends entirely on whether a common algorithm exists. In TLS the client advertises the key-exchange groups it supports in the supported_groups extension of its opening message, in preference order, and the server selects one that appears on both sides.

Source: E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.3,” RFC 8446, §4.2.7, rfc-editor.org.

Two cases follow, and the difference between them is the whole design of a safe transition:

1. The client offers both. If the client lists a post-quantum group like X25519MLKEM768 alongside a classical group like X25519, and the server only knows the classical one, there is still an overlap. The server picks the classical group, the connection succeeds, and it runs quantum-vulnerable. This is the graceful path, and it’s exactly why interoperability doesn’t cause mass outages, at the cost of a silent downgrade.
2. The client offers post-quantum only. If the client is configured to offer only ML-KEM and the server has never heard of it, there is no overlap at all. RFC 8446 is explicit that in this case the server “MUST abort the handshake with a ‘handshake_failure’ or an ‘insufficient_security’ alert.” The connection breaks.

Source: E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.3,” RFC 8446, §4.1.1 (Cryptographic Negotiation), rfc-editor.org.

This is the core interoperability tension in one picture. Offering both algorithms keeps everything talking but hides downgrades, and offering the new algorithm alone guarantees post-quantum protection but breaks the connection to any peer that hasn’t upgraded. Managing that tension across a real estate, knowing which endpoints can safely go post-quantum-only and which still need the classical fallback advertised, is what a coexistence plan actually is.

Why does a larger post-quantum handshake get dropped by legacy middleboxes?

Because the new algorithms produce artifacts far bigger than the classical ones, and that size crosses a boundary that decades of network equipment quietly assumed would never move. A classical X25519 key share is 32 bytes. An ML-KEM-768 hybrid share pushes the opening TLS message past a kilobyte, and for most of TLS’s history that first message fit inside a single network packet. A long tail of load balancers, firewalls, and deep-packet-inspection appliances was built assuming it always would.

This is protocol ossification, the ecosystem calcifying around an assumption that held for years until a new algorithm made it false. When the post-quantum handshake spills across two packets, some of that older equipment mishandles or simply drops a message it cannot buffer. Cloudflare, testing post-quantum key exchange at internet scale, observed sharp cliffs where connections failed once the handshake grew past specific sizes, direct evidence that particular middleboxes cannot process handshakes beyond a fixed length.

Source: Cloudflare, “Defending against future threats: Cloudflare goes post-quantum,” blog.cloudflare.com.

The interoperability lesson is that the failure lives in neither endpoint. The client supports the new algorithm, the server supports the new algorithm, and a third box on the path that neither party controls refuses the larger handshake. Protocols carry escape hatches for exactly this, TLS can advertise the post-quantum group while sending a small classical key share first and completing the larger exchange on a second round trip, and IPsec carries its oversized post-quantum value in a dedicated intermediate exchange (RFC 9242) rather than the first packet.

Source: V. Smyslov, “Intermediate Exchange in IKEv2,” RFC 9242, May 2022, datatracker.ietf.org.

Why does one un-migrated endpoint force a classical fallback?

Because these protocols negotiate their algorithms between two ends, and a connection can only use an algorithm that both ends, and every device on the path, support. This is the load-bearing rule of applied post-quantum cryptography, that a protocol is only as quantum-safe as its weakest deployed endpoint on the path, and interoperability is the mechanism that makes it true.

The consequence is that coverage matters more than capability. A modern browser that supports X25519MLKEM768 reaching a load balancer that doesn’t will negotiate down to classical key exchange, and the harvest-now-decrypt-later window stays open for everything behind that load balancer. One un-migrated reverse proxy, CDN edge, VPN gateway, or SSH bastion reopens the exposure for the whole population of systems it fronts. The migration is only as complete as its least-migrated node.

What makes this genuinely dangerous is that the fallback is designed to be seamless, so a connection that quietly dropped to classical is indistinguishable at a glance from one that went post-quantum. That’s why OpenSSH added a warning when a non-post-quantum key agreement is negotiated, and why the negotiated algorithm has to be confirmed on real traffic rather than inferred from a configuration.

Source: OpenSSH, “Post-Quantum Cryptography,” openssh.com/pq.html.

Tracking which endpoints negotiate which algorithms, across every surface including the vendor-controlled ones, is exactly what a cryptographic bill of materials captures, and it’s the artifact that turns “we enabled post-quantum” into a defensible, evidence-backed claim.

How do mismatched algorithm identifiers and OIDs break interoperability?

They break it at the parsing layer, where a signature or a key can be cryptographically perfect and still be rejected because the receiving system does not recognize the label attached to it. Cryptographic objects don’t carry the algorithm’s math on the wire, they carry an identifier, and both ends have to map that identifier to the same algorithm.

There are three distinct places this goes wrong in a post-quantum migration:

1. Certificate OIDs. An X.509 certificate names its signature algorithm by an object identifier. NIST assigned the OIDs for the new algorithms under its arc, for example id-ml-dsa-65 under the signature-algorithms branch and id-alg-ml-kem-768 under the key-encapsulation branch. A verifier whose library predates those assignments sees an unrecognized OID and rejects a certificate whose signature is entirely valid.

   Source: NIST Computer Security Objects Register, “Algorithm Registration,” csrc.nist.gov.

2. Token algorithm values. A JWT identifies its signature by a JOSE alg value, and post-quantum signing needs a registered value both the issuer and every verifier agree on. RFC 9964 registers the ML-DSA alg identifiers for JOSE and COSE, and until a verifier’s library knows them, it treats a validly signed post-quantum token as unverifiable.

   Source: M. Prorock, O. Steele, “ML-DSA for JOSE and COSE,” RFC 9964, May 2026, datatracker.ietf.org.

3. Pre-standard codepoints mistaken for final ones. Before FIPS 203 was final, browsers shipped an experimental TLS group called X25519Kyber768Draft00, built on the pre-standard Kyber, with a different codepoint from the standardized X25519MLKEM768. A system that only knows the draft identifier and a system that only knows the final one cannot interoperate, even though both believe they support “the same” thing.

   Source: Google Security Blog, “A new path for Kyber on the web,” September 2024, security.googleblog.com.

The through-line is that agreement on identifiers is as load-bearing as agreement on algorithms. A migration that upgrades signers before it upgrades every verifier will produce a wave of rejected-but-valid certificates and tokens, which is why verifier readiness leads issuer rollout in any sane sequence.

How do crypto-agility and negotiation design keep interoperability working?

They keep it working by making the algorithm a runtime choice instead of a fixed assumption, so that a heterogeneous population of endpoints can always find common ground or fail safely. Crypto-agility is the architectural property of being able to add, negotiate, and retire cryptographic algorithms without re-engineering the system around them, and it is the foundation every interoperable transition rests on.

Negotiation design is crypto-agility expressed on the wire, and it does three jobs at once:

1. It finds the strongest common algorithm. Because each side advertises an ordered menu and the responder picks from the overlap, two endpoints with partially different capabilities still converge on the best algorithm they share, which is what lets old and new coexist without a flag day.
2. It fails gracefully instead of catastrophically. When no post-quantum option is common, a well-designed negotiation falls back to a classical algorithm and keeps the connection alive, trading a security downgrade for availability, rather than dropping the connection. The tradeoff is deliberate, and it’s why the downgrade has to be monitored.
3. It lets endpoints migrate independently. Because the algorithm is chosen per connection, each endpoint can upgrade on its own schedule and immediately negotiate post-quantum with any already-upgraded peer, without a coordinated cutover across the whole estate.

The endpoints that migrate cleanly are the crypto-agile ones, able to advertise a new group and retire an old one through configuration. The endpoints that stall a migration are the ones with an algorithm hardwired into firmware or a protocol version pinned in code, because they cannot negotiate anything new and have to be re-architected or replaced before they can interoperate at all. Interoperability in the post-quantum transition is, in the end, a measure of how crypto-agile the network already was.

Common misconceptions

• “Once the algorithm is standardized, systems just interoperate.” Standardization is where interoperability work begins. The algorithm has to reach both endpoints and every box between them, in software that agrees on its identifier and can parse its bytes, before a single connection is protected.
• “If both my endpoints support the new algorithm, the connection uses it.” A middlebox on the path that neither endpoint controls can drop the larger handshake, and a silent fallback can quietly pick a classical algorithm. Endpoint support is necessary and not sufficient; the whole path and the negotiated result both have to be checked.
• “A failed post-quantum handshake throws a clear error.” Usually it doesn’t. The common outcomes are a graceful downgrade to classical that looks like a healthy connection, or an intermittent failure that only appears on certain network paths. Both hide the real cause.
• “A valid signature always verifies.” Not if the verifier doesn’t recognize the algorithm identifier or OID. A cryptographically perfect post-quantum signature is rejected by any verifier whose library predates the identifier assignment, so verifiers have to be upgraded before signers start using the new algorithm.
• “Bigger keys just cost some bandwidth.” The size problem is an interoperability problem, not a performance one. The extra kilobytes cross packet boundaries that old middleboxes assumed were fixed, and the failure mode is a dropped connection, not a slow one.
• “X25519Kyber768Draft00 and X25519MLKEM768 interoperate.” They don’t. One is the pre-standard Kyber group and the other is the standardized ML-KEM group, with different codepoints, so systems knowing only one of them cannot negotiate with systems knowing only the other.

Questions people ask

Why is interoperability the hard part of post-quantum, if the math already works? Because the math was solved in a lab and the transition happens on a live, heterogeneous internet. A standardized algorithm protects nothing until both ends of a connection and every device between them can advertise it, agree on it, and parse it, and getting a partially-upgraded world to do that in real time is the multi-year problem the standards hand downstream.

What’s the difference between a fallback and a failure? A fallback is when two endpoints share a classical algorithm, so a negotiation that can’t agree on a post-quantum one drops to classical and the connection succeeds while staying quantum-vulnerable. A failure is when there’s no common algorithm at all, so the handshake aborts and the connection breaks. Fallback is the quiet risk; failure is the loud one.

Can I just turn on post-quantum-only everywhere to be safe? Only where you know every peer has already migrated. A post-quantum-only endpoint has no classical fallback to offer, so it will hard-fail every connection to any peer that hasn’t upgraded, which during the transition is most of them. Advertising both is the interoperable default until coverage is high enough.

How do I know a connection is actually using the new algorithm? Confirm the negotiated algorithm on the wire with a packet capture, and read the endpoint configuration for what it permits as a fallback. Because a downgraded connection looks identical to a protected one, the enabled-in-config claim and the used-on-the-wire claim are two different things, and only the second one counts.

Why do certificates and tokens fail even when the signature is valid? Because verification depends on two separate things, the receiver recognizing the algorithm identifier (the OID on a certificate or the alg value on a token) and the signature being mathematically correct. A cryptographically perfect post-quantum signature still gets rejected when the verifier’s library predates the standardized identifier, which is why every verifier has to learn the new identifier before any issuer starts using it.

Does interoperability apply to signatures too, or just key exchange? Both, on different clocks. Key exchange interoperability is the urgent one because it’s harvestable today, while signature interoperability, the ML-DSA and composite-certificate side, is Non-HNDL and slower-clocked but carries a large blast radius, since one issuer’s key underwrites every party that trusts it.

Is there a tool that just makes everything interoperate? No single switch. Interoperability is a property of the whole estate, produced by crypto-agile endpoints, careful negotiation configuration, verifier-before-signer sequencing, and path testing for oversized handshakes, and it’s tracked as evidence in a CBOM rather than solved by one product.

---

Everything here is the map, given freely. When your team needs its own estate assessed for where old and new cryptography will have to coexist, which endpoints can safely go post-quantum-only, which still need the classical fallback, and where an oversized handshake or an unrecognized identifier will break interoperability, that’s the work I do, and there’s an alignment briefing for it.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.