ML-KEM vs Traditional Key Exchange: What Changes at the Protocol Layer?
Post quantum cryptography is often discussed as an algorithm replacement problem.
Replace RSA. Replace elliptic curve cryptography. Deploy ML-KEM. Update TLS.
The reality is more complicated.
The transition from traditional public key key exchange to ML-KEM changes how endpoints establish shared secrets, how handshake messages are structured, how implementations manage larger cryptographic objects, and how protocols need to handle interoperability during migration.
That makes ML-KEM particularly interesting at the protocol layer.
NIST standardized ML-KEM in FIPS 203 as a post quantum key encapsulation mechanism based on the Module Learning With Errors problem. The standard defines ML-KEM-512, ML-KEM-768, and ML-KEM-1024, with increasing security strength and decreasing performance as the parameter set increases. (NIST Computer Security Resource Center)
But ML-KEM is not simply "the post quantum version of ECDH."
The underlying key establishment model is different.
Traditional Key Exchange: Diffie-Hellman and ECDH
Modern TLS 1.3 commonly uses ephemeral Diffie-Hellman mechanisms for key establishment, particularly X25519 and elliptic curve groups.
The basic idea is elegant.
Two parties independently generate private values and exchange corresponding public information. Through the mathematical properties of the chosen group, both sides can derive the same shared secret without transmitting that secret directly.
Conceptually:
Client private key + Server public key → Shared secret
and:
Server private key + Client public key → Same shared secret
The shared secret then feeds the TLS key schedule, which derives the symmetric traffic keys used to protect application data.
The important point is that the public key mechanism is primarily responsible for establishing shared keying material.
The actual application traffic is still protected using symmetric cryptography. This distinction is important because the security of a TLS connection depends on several cryptographic components working together, not simply on the strength of the encryption algorithm. For example, AES-256 provides strong symmetric protection, while the key exchange and authentication mechanisms introduce a separate set of security considerations.
The problem is that widely deployed public key mechanisms such as elliptic curve Diffie-Hellman are vulnerable to sufficiently capable quantum computers using algorithms such as Shor's algorithm.
That creates the motivation for post quantum key establishment.
ML-KEM Uses a Different Model
ML-KEM is a Key Encapsulation Mechanism, or KEM.
NIST defines a KEM as a set of algorithms that allows two parties to establish a shared secret over a public channel. The basic operations are KeyGen, Encaps, and Decaps. (NIST Computer Security Resource Center)
The model looks different from traditional Diffie-Hellman.
The recipient first generates:
Public encapsulation key + Private decapsulation key
The public key can be distributed openly.
A sender then uses the recipient's public key to perform encapsulation:
Encaps(public key) → Ciphertext + Shared secret
The ciphertext is sent to the recipient.
The recipient uses the private decapsulation key:
Decaps(private key, ciphertext) → Same shared secret
Both parties now possess the shared secret without transmitting the secret itself.
That shared secret can then be passed into a symmetric encryption mechanism.
So the conceptual flow becomes:
ML-KEM public key → Encapsulation → Ciphertext + Shared secret → TLS key schedule
This is one of the most important differences between ML-KEM and traditional Diffie-Hellman based key exchange.
What Actually Changes in TLS?
This is where the discussion becomes more interesting.
ML-KEM does not replace TLS.
It changes the key establishment mechanism used within the TLS handshake.
TLS 1.3 already separates the handshake from the symmetric encryption used for application traffic. This makes the protocol comparatively well suited to incorporating new key establishment mechanisms.
With a traditional X25519 exchange, the ClientHello contains a key share associated with the selected elliptic curve group.
With a post quantum or hybrid mechanism, the key exchange information becomes larger and follows the KEM-based construction defined by the relevant protocol specification.
That has practical consequences.
1. Handshake messages become larger
ML-KEM public keys and ciphertexts are considerably larger than the compact key exchange material associated with X25519.
This matters because TLS handshakes operate over real networks, not theoretical cryptographic channels.
Larger messages can affect:
Packet fragmentation
Network latency
Middlebox behavior
Memory consumption
CPU usage
Handshake performance
Cloudflare notes that its X25519MLKEM768 implementation can cause the TLS ClientHello to span multiple network packets, creating interoperability considerations for infrastructure that historically assumed smaller handshake messages. (Cloudflare Docs)
That is a protocol engineering issue, not merely an algorithmic one.
2. The Key Schedule Still Matters
Another misconception is that introducing ML-KEM means abandoning the existing TLS cryptographic architecture.
It does not.
The objective is still to establish keying material that feeds the TLS key schedule.
The symmetric cryptography used to protect application traffic remains critical.
This distinction matters because quantum computing does not affect every part of a TLS connection equally.
Public key mechanisms used for key establishment and authentication face a fundamentally different quantum threat from widely used symmetric primitives.
Therefore, PQC migration is primarily concerned with replacing vulnerable public key operations, while maintaining appropriate symmetric cryptography.
The architecture becomes:
Post quantum key establishment → TLS key schedule → Symmetric traffic encryption
rather than:
Post quantum algorithm → Encrypt all application data directly
That distinction is essential when designing migration strategies.
3. Hybrid Key Exchange Changes the Migration Strategy
Replacing X25519 completely with ML-KEM is not necessarily the first step organizations will take.
A more practical transition involves hybrid key agreement.
Instead of relying exclusively on either classical or post quantum key establishment, a hybrid mechanism combines both.
A commonly deployed example is:
X25519 + ML-KEM-768
Cloudflare currently supports X25519MLKEM768 as a hybrid key agreement and describes it as a transition mechanism that maintains the security properties of X25519 while adding post quantum protection. (Cloudflare Docs)
The important architectural idea is that the resulting key establishment incorporates both classical and post quantum components.
This provides a migration path without requiring every endpoint to immediately abandon existing cryptographic infrastructure.
But hybrid cryptography introduces its own engineering questions.
What happens if one endpoint supports only classical key exchange?
How are supported groups negotiated?
How is the combined secret incorporated into the TLS key schedule?
How are downgrade scenarios handled?
How are implementations tested across different TLS stacks?
These questions belong to the protocol layer, not merely the cryptographic library.
4. Compatibility Becomes a Major Engineering Problem
Traditional TLS deployments have spent years building around assumptions about packet sizes, extensions, supported groups, and handshake behavior.
PQC changes some of those assumptions.
A larger ClientHello may interact differently with:
Load balancers
Firewalls
WAFs
TLS inspection systems
Proxies
Network appliances
Legacy TLS implementations
Custom protocol parsers
This is an example of protocol ossification.
Systems that were technically compatible with the TLS specification may still behave incorrectly because they were implemented around assumptions that were never formally guaranteed.
This is one reason PQC testing needs to include the entire network path.
Testing only the client and server cryptographic libraries is insufficient.
5. ML-KEM Does Not Solve Authentication
There is another critical distinction.
ML-KEM provides key establishment. It does not replace digital signatures.
This means an organization adopting ML-KEM for TLS key agreement has not automatically solved its post quantum authentication problem.
TLS authentication can depend on digital signatures and certificates.
Those cryptographic mechanisms represent a separate migration path.
NIST standardized ML-DSA in FIPS 204 and SLH-DSA in FIPS 205 for post quantum digital signatures.
Therefore, a complete PQC architecture needs to consider at least two major categories:
Key establishment
ML-KEM and related mechanisms.
Authentication
Post quantum signature mechanisms such as ML-DSA or SLH-DSA.
This is one reason why saying "we have deployed PQC" without specifying which cryptographic function has been migrated can be misleading.
ML-KEM Parameter Sets Matter
FIPS 203 defines three ML-KEM parameter sets:Parameter setGeneral directionML-KEM-512Lower security strength, better performanceML-KEM-768Higher security strength, balanced performanceML-KEM-1024Highest security strength, lower performance
NIST describes these parameter sets as increasing in security strength and decreasing in performance from ML-KEM-512 through ML-KEM-1024. (NIST Computer Security Resource Center)
That means implementation decisions should not simply be:
"Use ML-KEM."
The actual engineering question is:
"Which parameter set provides the required security level without imposing unacceptable operational costs?"
The answer can depend on the protocol, workload, hardware, latency requirements, regulatory environment, and threat model.
Performance Needs to Be Measured at the Protocol Level
Benchmarking ML-KEM in isolation does not tell you how an application will behave.
A real TLS deployment has:
TCP connection → TLS ClientHello → Server response → Key establishment → Authentication → Key schedule → Application data
The relevant metric is therefore not just ML-KEM encapsulation time.
Security teams should measure:
Complete handshake latency
CPU utilization
Memory consumption
Packet count
ClientHello size
ServerHello behavior
HelloRetryRequest frequency
Connection failure rates
Middlebox compatibility
Throughput under load
Cloudflare's current deployment experience demonstrates why these details matter. Its automated key exchange system monitors connection behavior and can prefer X25519MLKEM768 when the origin supports it, while retaining classical alternatives where necessary. (Cloudflare Docs)
This is a good example of PQC being treated as an operational protocol problem, rather than simply a cryptographic library upgrade.
The Bigger Change: Cryptographic Agility
The most important lesson from ML-KEM may not actually be ML-KEM itself.
It is the need for cryptographic agility.
If an organization hard codes X25519 assumptions throughout its applications, proxies, appliances, libraries, and infrastructure, migrating to ML-KEM will be difficult.
If cryptographic mechanisms can be changed through controlled configuration, policy, libraries, and automated deployment, the migration becomes much more manageable.
This is why organizations should inventory:
TLS implementations
Supported groups
Cryptographic libraries
Certificate infrastructure
Trust stores
HSM and KMS integrations
Network appliances
Legacy clients
Third party dependencies
NIST's recommendations for KEMs also emphasize that KEMs should be implemented and used with appropriate security considerations rather than treated as isolated algorithmic components. (NIST Computer Security Resource Center)
ML-KEM Is a Protocol Transition, Not Just an Algorithm Upgrade
The important difference between ML-KEM and traditional key exchange is not simply that one is "quantum safe" and the other is not.
The underlying mechanics are different.
Traditional ECDH derives a shared secret through a mathematical key agreement operation.
ML-KEM establishes a shared secret through encapsulation and decapsulation.
When that mechanism enters TLS, it affects handshake structures, message sizes, negotiation, interoperability, performance, and migration architecture.
And when deployed in hybrid form, it introduces another layer of protocol engineering.
That is why PQC migration should not begin with:
"How do we replace X25519?"
A better question is:
"How does our protocol stack establish keys today, what systems depend on that behavior, and how can we introduce ML-KEM without creating new interoperability or operational failures?"
That is the level at which post quantum migration becomes a real engineering discipline.
ML-KEM is not simply a new cryptographic primitive. It changes the assumptions surrounding key establishment.
And those assumptions are embedded far deeper in modern infrastructure than most organizations realize.
