ML-KEM (Kyber) Deep Dive — Lattice-Based Key Encapsulation Explained

ML-KEM is the workhorse PQ algorithm. Every TLS handshake, every IPsec session, every SSH KEX in the post-quantum world will go through this or its successors. Understanding its mechanics — even at a high level — is non-optional for senior security engineers.

What lattice-based crypto is

A lattice is a discrete grid of points in n-dimensional space, generated by linear combinations of basis vectors. The problem: given a “hard basis” (badly-conditioned vectors) describing the same lattice, find a “good basis” (short, nearly-orthogonal vectors). This is the Shortest Vector Problem (SVP); it’s NP-hard in worst case and believed hard in average case.

Cryptographic schemes encode the secret as a “good basis” or vector close to a known lattice point. Adversary sees only the “hard” public version and must solve SVP-related problems to recover the secret. Quantum computers don’t break lattice problems known today (no Shor-equivalent for SVP), so lattice crypto is PQ-resistant.

The Learning With Errors (LWE) problem

LWE is the specific lattice problem ML-KEM uses. Setup:

• Public: matrix A (n × n, random over Z_q), vector b (n × 1).
• Promise: there exists secret vector s such that b ≈ A·s + e, where e is a small “error” vector.
• Problem: given A and b, find s. Equivalent: distinguish (A, A·s + e) from (A, random vector).

Without the error e, this is just linear algebra (Gaussian elimination, trivial). With small e, classical algorithms struggle. Best known classical: lattice reduction (LLL, BKZ) — exponential time in the lattice dimension. Best known quantum: same exponential time (no Shor-style speedup).

ML-KEM uses Module-LWE, a structured variant where the matrix A has algebraic structure (it’s over a polynomial ring) — this dramatically reduces key size while preserving security.

ML-KEM at the protocol level

Standard KEM API:

1. KeyGen() → (public key pk, secret key sk).
2. Encap(pk) → (ciphertext ct, shared secret K). The sender generates a random K, encrypts to pk.
3. Decap(sk, ct) → K. The receiver recovers K using sk.

K (typically 32 bytes) is then used as the symmetric key for AES-256-GCM or similar. The two parties have agreed on K without ever transmitting it — same goal as RSA-KEM or ECDH, but with PQ-resistant math.

Three security levels

ML-KEM-768 is the recommended default. Cloudflare and Google ship it as the production PQ KEM in hybrid mode. Equivalent to AES-192 against quantum adversaries — comfortable margin.

Hybrid mode in TLS 1.3

The current TLS 1.3 PQ deployment uses a hybrid keyshare: classical X25519 + ML-KEM-768. The handshake message contains both public keys; the shared secret is HKDF-derived from both ECDH and ML-KEM secrets.

Wire format (RFC 9180 / draft-ietf-tls-hybrid-design):

NamedGroup: x25519_kyber768   (0x6399)  // hybrid
KeyShareEntry:
  group: x25519_kyber768
  key_exchange:
    classical_pk: 32 bytes (X25519)
    ml_kem_pk:    1184 bytes (ML-KEM-768)

The HKDF combination: shared_secret = HKDF-Extract(ecdh_shared || mlkem_shared). Adversary breaking either component still doesn’t get the session key without the other.

Performance: ~2-3 ms additional handshake time (typical) on commodity hardware. Bandwidth: ~2.4 KB additional. Most users don’t notice.

Deploying ML-KEM today — concrete recipes

Cloudflare: enabled by default for origins that opt in. Dashboard → SSL/TLS → Edge Certificates → Post-Quantum.

nginx with OpenSSL 3.5: configure ssl_ecdh_curve x25519_kyber768:X25519:secp256r1;

Apache with mod_ssl + OpenSSL 3.5: SSLOpenSSLConfCmd Curves x25519_kyber768:X25519:secp256r1

HAProxy 2.9+: native hybrid support; tune.ssl.default-dh-param 2048 remains; ssl-default-bind-ciphersuites stays.

AWS ELB / ALB: hybrid PQ available on the FIPS-validated TLS 1.3 cipher suite as of late 2024. Toggle in the LB target-group security policy.

Caddy 2.7+: enabled by default if compiled with caddyserver/caddy/v2/modules/caddytls/postquantum.

What to test before production rollout

1. Client compatibility: Chrome 124+, Firefox 132+, Safari 17.4+ negotiate hybrid. Older clients fall back to classical X25519. Don’t break old clients with mandatory PQ.
2. Middlebox compatibility: some legacy WAFs and load balancers fail on the larger ClientHello (1.4+ KB) with the PQ keyshare. RFC 8446 already requires support for big ClientHello; legacy gear may not.
3. Performance: handshake latency p50/p95 with PQ enabled vs disabled. Should be <5ms additional under normal conditions.
4. CDN / cache: confirm your CDN handles hybrid; if you’re behind Cloudflare or Fastly, they manage this automatically.

FAQ

Should we use ML-KEM-1024 instead of 768 for higher security?

For most data, 768 (L3, AES-192-equivalent) is sufficient. Migrate to 1024 (L5) only for data with relevance horizon >30 years and concrete reasons to expect more aggressive future quantum capability.

Can we go pure-PQ (no classical) yet?

Not recommended in production. Hybrid is the conservative path. If a side-channel or implementation flaw is discovered in ML-KEM, classical X25519 still protects you. Move to pure-PQ around 2030 once implementations have been hardened.

Does ML-KEM affect API rate limits or proxies?

The handshake is bigger; proxies that buffer entire ClientHello bytes need slightly more memory. Most modern proxies (Envoy, nginx, HAProxy) handle this without configuration changes.

What’s the relationship between Kyber and ML-KEM?

Same algorithm. NIST renamed CRYSTALS-Kyber to ML-KEM in FIPS 203. Implementations are interchangeable; documentation transitioning gradually.

Is ML-KEM patented?

No royalty-bearing patents apply to current ML-KEM specification. NIST published with explicit royalty-free terms. Safe to deploy commercially.

⚖️ Module 6 of 20. Intermediate. Module 7 covers ML-DSA (signatures); Module 8 covers SLH-DSA (hash-based conservative alternative).