Migrating to ML-KEM: A Guide to Post-Quantum TLS Handshakes

The cryptographic foundations of the internet are facing a silent deadline. While cryptographically relevant quantum computers (CRQCs) capable of breaking RSA and Elliptic Curve Cryptography (ECC) do not yet exist, the threat they pose is already active. This is due to a strategy known as "Harvest Now, Decrypt Later" (HNDL), where adversaries capture encrypted traffic today with the intention of decrypting it once quantum hardware matures.

For senior engineers managing service-to-service communication, the priority has shifted from "if" we migrate to "how" we migrate. NIST recently finalized the standards for Post-Quantum Cryptography (PQC), with ML-KEM (formerly known as Kyber) emerging as the primary mechanism for key encapsulation. This article explores the technical nuances of migrating TLS handshakes to ML-KEM and how to implement a hybrid approach that maintains security during the transition.

The Quantum Threat to Key Exchange

Most modern service-to-service communication relies on TLS 1.3, typically using Elliptic Curve Diffie-Hellman (ECDH) for key exchange. ECDH relies on the hardness of the elliptic curve discrete logarithm problem. Shor’s algorithm, when run on a sufficiently powerful quantum computer, can solve this problem in polynomial time.

If an attacker captures your current TLS handshakes, they possess the encrypted ephemeral keys. In a post-quantum world, those keys are easily recovered, exposing the entire data stream. To prevent this, we must transition to algorithms that are resistant to both classical and quantum attacks. Enter ML-KEM.

What is ML-KEM (Kyber)?

ML-KEM, or Module-Lattice-Based Key-Encapsulation Mechanism, is based on the "Learning with Errors" (LWE) problem over algebraic lattices. Unlike RSA or ECC, which rely on number theory, lattice-based cryptography relies on the geometric complexity of high-dimensional grids.

Key Differences from ECDH

1. Mechanism: ECDH is a Key Exchange (KX) protocol where both parties contribute to a shared secret. ML-KEM is a Key Encapsulation Mechanism (KEM). In a KEM, one party generates a shared secret and "encapsulates" it under the other party's public key.
2. Payload Size: ML-KEM public keys and ciphertexts are significantly larger than X25519. An X25519 public key is 32 bytes; an ML-KEM-768 public key is 1,184 bytes.
3. Computational Speed: Surprisingly, ML-KEM is often faster than ECDH in terms of CPU cycles, but the increased payload size introduces different latency bottlenecks.

The Hybrid Strategy: The Only Safe Path Forward

We are currently in a "transitional period." We cannot move 100% to ML-KEM yet because:

• ML-KEM is relatively new; if a classical vulnerability is found in the implementation, your entire system is exposed.
• Regulatory requirements (like FIPS) often require a proven, classical algorithm.

The industry standard for migration is the Hybrid Key Exchange. This involves performing a classical exchange (like X25519) and a quantum-resistant exchange (ML-KEM) simultaneously. The resulting shared secrets are concatenated and fed into a Key Derivation Function (KDF). If either algorithm remains secure, the resulting connection remains secure.

In the context of TLS 1.3, this is implemented using new named groups, such as X25519MLKEM768.

Implementing ML-KEM in Service-to-Service Communication

When migrating internal services (gRPC, REST over HTTPS, Service Meshes), the implementation happens at the TLS library level. Let’s look at how this looks in practice using modern stacks.

1. Library Selection

Not all libraries support PQC yet. For production-grade services, you generally look at:

• BoringSSL: Google’s fork of OpenSSL already has experimental support for Kyber (now ML-KEM) and is used in Chrome and internal Google services.
• liboqs: The Open Quantum Safe project provides a C library for quantum-resistant algorithms and integrates with OpenSSL 3.x via a provider.
• Go (crypto/tls): The Go team has been proactive. As of Go 1.23, experimental support for X25519MLKEM768 is available.

2. Practical Example: Go 1.23 Implementation

In Go, enabling a hybrid post-quantum handshake for a client and server is straightforward. Here is a conceptual implementation:

// Server Configuration
config := &tls.Config{
    MinVersion: tls.VersionTLS13,
    CurvePreferences: []tls.CurveID{
        tls.X25519MLKEM768, // Hybrid PQC group
        tls.X25519,
    },
}

// Client Configuration
client := &http.Client{
    Transport: &http.Transport{
        TLSClientConfig: &tls.Config{
            CurvePreferences: []tls.CurveID{tls.X25519MLKEM768},
        },
    },
}

When the client initiates the handshake, it includes the X25519MLKEM768 key share in the ClientHello. The server, seeing this, performs the hybrid computation. If the server doesn't support ML-KEM, it falls back to standard X25519 because of the ordered preference list.

Performance and Infrastructure Considerations

Migrating to ML-KEM isn't just a code change; it impacts your infrastructure.

The MTU and Fragmentation Issue

Standard TLS handshakes with ECDH easily fit within a single TCP packet (typically ~1500 bytes MTU). A hybrid X25519MLKEM768 handshake adds over 1KB to the ClientHello.

If you have deep packet inspection (DPI), legacy firewalls, or load balancers that make assumptions about packet sizes or fragmentation, you may see dropped connections. It is critical to test your network path to ensure that larger ClientHello messages aren't being blocked by middleboxes.

CPU vs. Latency

In our benchmarks, ML-KEM-768 is highly efficient. The CPU overhead is negligible for modern servers. However, the increased bandwidth (an extra ~2KB per handshake) can add up in high-churn environments where connections are frequently opened and closed. Using TLS Session Resumption (PSKs) becomes even more critical in a PQC world to avoid the cost of the full hybrid handshake on every request.

Migrating Certificates: The Next Frontier

While this article focuses on the handshake (Key Exchange), the certificates themselves (Authentication) also need to become quantum-resistant. This is a harder problem.

PQC signatures (like ML-DSA/Dilithium) result in certificates that are significantly larger than RSA or ECDSA certificates. This can lead to "amplification attacks" and further fragmentation issues.

For service-to-service communication, we recommend a phased approach:

1. Phase 1 (Now): Implement Hybrid Key Exchange (ML-KEM + X25519). This protects against HNDL.
2. Phase 2 (Future): Transition internal Certificate Authorities (CAs) to issue hybrid or pure PQC certificates once library support for ML-DSA stabilizes.

Operational Roadmap for Engineering Teams

If you are responsible for the security architecture of a service-oriented environment, follow these steps:

Step 1: Inventory and Audit

Identify every point where TLS is terminated. This includes Load Balancers (ALBs/NLBs), Ingress Controllers (Nginx/Envoy), and sidecars in a service mesh (Istio/Linkerd).

Step 2: Enable Hybrid Groups in Development

Start by enabling X25519MLKEM768 in your development environments. Use tools like Wireshark to inspect the handshakes and verify that the key_share extension contains the hybrid payload.

Step 3: Monitor for Fragmentation Issues

Before a broad rollout, monitor for a spike in TLS handshake failures. Pay close attention to services communicating across different cloud regions or through VPN tunnels, as these often have lower effective MTUs.

Step 4: Update Internal SDKs

If your company maintains internal client libraries or SDKs, update their underlying TLS configurations to prefer hybrid PQC groups. This ensures that as services are redeployed, they automatically opt-in to the higher security standard.

Conclusion

Transitioning to ML-KEM is no longer a theoretical exercise for researchers; it is a practical necessity for maintaining long-term data integrity. By adopting a hybrid approach today, you leverage the battle-tested security of X25519 while layering on protection against the quantum threats of tomorrow.

Actionable Summary:

• Prioritize HNDL: Focus on Key Encapsulation (ML-KEM) first to protect current data from future decryption.
• Go Hybrid: Do not use ML-KEM in isolation. Always pair it with a classical algorithm like X25519.
• Check Your Middleboxes: Ensure your network infrastructure handles larger TLS handshake packets without dropping them.
• Update Your Stack: Target Go 1.23+, OpenSSL 3.4+, or the latest BoringSSL to gain native PQC support.