FIPS 203 ML-KEM Explained: The New Standard for Key Encapsulation

FIPS 203 is the federal standard that replaces RSA and ECDH for key establishment. Published by NIST in August 2024, it standardizes ML-KEM (Module Lattice-based Key Encapsulation Mechanism), the algorithm formerly known as CRYSTALS-Kyber. ML-KEM is the mechanism by which two parties establish a shared secret in a quantum-resistant manner. Understanding FIPS 203 is essential for any organization that needs to protect the confidentiality of data in transit against future quantum computers.

What Key Encapsulation Replaces

Today, when your browser connects to a website over HTTPS, the TLS handshake establishes a shared secret using either RSA key transport or Diffie-Hellman key exchange (typically ECDHE with X25519 or P-256). This shared secret is then used to derive symmetric keys (AES-128 or AES-256) that encrypt the actual application data.

Shor's algorithm breaks both RSA key transport (by factoring the RSA modulus) and ECDHE (by solving the elliptic curve discrete logarithm problem). When a quantum computer runs Shor's algorithm, every TLS session that used these mechanisms becomes decryptable. ML-KEM replaces these mechanisms with a key establishment protocol based on the Module Learning With Errors (MLWE) problem, which Shor's algorithm does not solve.

The Lattice Problem Simplified

ML-KEM's security is based on the hardness of the Module Learning With Errors problem. The intuition behind MLWE can be explained without the full mathematical formalism.

Imagine a system of equations where you know the approximate answers but not the exact ones. Each equation has a small random error added to it. If you know the exact system (the secret key), you can solve the equations and recover the shared secret. If you do not know the secret, the errors make it computationally infeasible to solve the system, even approximately.

More precisely, MLWE works in polynomial rings. The secret key is a vector of polynomials with small coefficients. The public key is computed as a noisy product of the secret key with a public matrix. The "noise" (error term) is small enough that the legitimate receiver can correct it and recover the shared secret, but large enough that an adversary cannot distinguish the public key from random noise without knowing the secret.

The key insight is that this problem remains hard for quantum computers. Shor's algorithm exploits the periodic structure of modular exponentiation and elliptic curve group operations. Lattice problems do not have this periodic structure, so Shor's algorithm does not apply. Grover's algorithm provides only a modest speedup for lattice problems (roughly square root), which is compensated for by choosing appropriately large parameters.

The Three Parameter Sets

FIPS 203 defines three parameter sets, each targeting a different NIST security level.

ML-KEM-512 (NIST Level 1): Targets security equivalent to AES-128. Public key: 800 bytes. Ciphertext: 768 bytes. Shared secret: 32 bytes. This is the smallest and fastest parameter set. Suitable for applications where Level 1 security is acceptable and bandwidth is constrained.

ML-KEM-768 (NIST Level 3): Targets security equivalent to AES-192. Public key: 1,184 bytes. Ciphertext: 1,088 bytes. Shared secret: 32 bytes. This is the recommended parameter set for most applications. It provides a comfortable security margin and is the default choice for TLS hybrid key exchange in Chrome and other browsers.

ML-KEM-1024 (NIST Level 5): Targets security equivalent to AES-256. Public key: 1,568 bytes. Ciphertext: 1,568 bytes. Shared secret: 32 bytes. This is specified by CNSA 2.0 for National Security Systems. It provides the highest security margin at the cost of larger keys and ciphertexts.

How ML-KEM Works: The Three Operations

ML-KEM defines three operations: key generation, encapsulation, and decapsulation.

Key Generation (KeyGen)

The server generates a public key and a private key. The private key consists of a vector of polynomials with small coefficients. The public key is computed as a noisy linear function of the private key. The public key is published (sent to the client in the TLS handshake); the private key is kept secret.

Encapsulation (Encaps)

The client takes the server's public key and generates two outputs: a ciphertext and a shared secret. The ciphertext is sent to the server. The shared secret is kept by the client. The encapsulation process uses the public key to encode the shared secret in a way that can only be decoded with the private key.

Decapsulation (Decaps)

The server takes the ciphertext and its private key and recovers the shared secret. If the ciphertext was correctly generated using the server's public key, the recovered shared secret matches the one generated by the client. Both parties now share the same secret, which is used to derive symmetric encryption keys.

Performance Characteristics

ML-KEM is fast. On modern hardware, key generation takes approximately 30-60 microseconds. Encapsulation takes 40-80 microseconds. Decapsulation takes 40-80 microseconds. These times are comparable to or faster than RSA-2048 key operations and within an order of magnitude of ECDH X25519 operations.

The bandwidth cost is the more significant consideration. An ML-KEM-768 key exchange adds approximately 2.3 KB to the TLS handshake compared to X25519. In hybrid mode (X25519 + ML-KEM-768), the total key exchange data is approximately 2.6 KB, compared to 64 bytes for X25519 alone.

For most applications, this bandwidth increase is negligible. On a 10 Mbps connection, 2.6 KB adds 0.2 milliseconds. On modern broadband and mobile networks, the impact is imperceptible. For applications with extremely high connection rates and minimal data per connection (high-frequency trading, CDN edge nodes), the impact should be measured but is unlikely to be a barrier.

What Changed from CRYSTALS-Kyber to ML-KEM

ML-KEM is the standardized version of CRYSTALS-Kyber, the algorithm submitted to NIST's post-quantum competition by a team of academic researchers. During the standardization process, NIST made several changes.

The name changed from CRYSTALS-Kyber to ML-KEM (Module Lattice-based Key Encapsulation Mechanism) to follow NIST's naming conventions and avoid trademark issues.

The parameter naming changed from Kyber-512/768/1024 to ML-KEM-512/768/1024. The underlying parameters (polynomial degree, modulus, error distribution) remain the same.

Minor implementation details changed, including the handling of certain edge cases in the decapsulation procedure and the specification of the random number generation requirements. These changes do not affect the security properties but do affect byte-level compatibility. Implementations must target the FIPS 203 specification, not the original Kyber specification.

Migration from RSA and ECDH

Migrating from RSA or ECDH to ML-KEM is primarily a TLS library upgrade. The application code does not change (it still calls "establish a TLS connection" and gets back a secure channel). The TLS library handles the ML-KEM operations internally.

For a step-by-step migration guide, the key steps are: upgrade the TLS library to a version that supports ML-KEM, configure the server to offer hybrid key exchange (X25519 + ML-KEM-768), verify that clients can successfully complete hybrid handshakes, and monitor for any performance or compatibility issues.

The H33 overlay approach provides an alternative path: add post-quantum attestation at the application layer without modifying the TLS configuration. This provides immediate post-quantum integrity protection while the TLS migration proceeds.

FIPS 203 is not a future standard. It is published, final, and mandatory for new federal procurements. The migration from RSA and ECDH to ML-KEM is the most impactful single step in post-quantum migration, because key exchange is the operation most vulnerable to harvest-now-decrypt-later. Every day without ML-KEM key exchange is a day of data exposure that cannot be retroactively fixed.