Post-Quantum Cryptography: Migrating to ML-KEM, ML-DSA, and a Crypto-Agile Future

TL;DR: Shor's algorithm breaks every public-key primitive you deploy today: RSA, ECDH, ECDSA, Ed25519. The threat is not "when quantum computers arrive" but "when adversaries record your traffic." Harvest-now-decrypt-later means any secret that must stay confidential past roughly 2035 is already at risk. NIST finalized three post-quantum standards in August 2024: ML-KEM (FIPS 203) for key exchange, ML-DSA (FIPS 204) for signatures, and SLH-DSA (FIPS 205) as a conservative hash-based backup^[1]. The correct deployment mode for 2025 to 2030 is hybrid (classical + PQC), where the session key is safe if either half holds. Start with a cryptographic inventory, deploy X25519MLKEM768 for TLS, and plan signature migration for long-lived trust anchors.

Learning Objectives#

After this module, you will be able to:

• Explain harvest-now-decrypt-later and why PQC timelines are tighter than CRQC timelines
• Compare ML-KEM, ML-DSA, and SLH-DSA parameter sizes and when to use each
• Design a hybrid (classical + PQC) TLS handshake and reason about its performance cost
• Build a migration framework: inventory, crypto-agility, prioritization, phased rollout
• Distinguish KEM urgency from signature urgency and prioritize accordingly

Intuition#

You keep a diary. Every night you write in it, lock it with a padlock, and leave it on your porch. Your neighbor photographs the locked diary every day. The padlock is strong today, but a new tool is coming that will open any padlock instantly. Your neighbor does not need the tool yet. They just need patience and a camera.

That is harvest-now-decrypt-later. Nation-state adversaries are recording encrypted traffic right now, storing petabytes of ciphertext, and waiting for a cryptographically relevant quantum computer (CRQC) to decrypt it all at once. The data does not expire. Medical records, diplomatic cables, trade secrets, and long-lived authentication keys all have confidentiality requirements that extend 10 to 30 years into the future.

The fix is not to wait for the CRQC and then panic. The fix is to change the padlock today, before the tool arrives, so that even if your neighbor has years of photographs, they are useless. In cryptographic terms: migrate key exchange to post-quantum algorithms now, while classical algorithms still hold, so recorded ciphertext remains safe even after a CRQC exists.

Networking Fundamentals introduced TLS 1.3 and its key-exchange mechanism. mTLS and Service Authentication covered certificate chains and mutual authentication. This chapter extends both into the post-quantum era: what changes, what breaks, and how to migrate without downtime.

Theory#

Threat timeline and the HNDL model#

Shor's algorithm factors large integers and computes discrete logarithms in polynomial time on a quantum computer^[2]. This breaks RSA, finite-field Diffie-Hellman, ECDH (X25519, P-256), ECDSA, and EdDSA. Grover's algorithm offers a quadratic speedup on symmetric search, but NIST and published resource analysis confirm that AES-128 remains safe without doubling key sizes^[3]. The post-quantum transition is a public-key transition.

Current quantum hardware is not a CRQC. IBM Condor (1,121 physical qubits, 2023)^[4] and Google Willow (105 high-fidelity qubits with below-threshold error correction, December 2024) demonstrate scaling trajectories but remain millions of logical qubits short of running Shor's on production key sizes^[5]. Estimates for a CRQC range from 2030 to beyond 2045 depending on the source.

The urgency comes from the attack model, not the hardware timeline. An adversary who records your TLS session today can decrypt it the moment a CRQC becomes available. If the secret must remain confidential for 10 years, and a CRQC might arrive in 10 years, you are already late.

Harvest-now-decrypt-later: the adversary captures ciphertext today and waits for a CRQC to decrypt it. Any secret with a confidentiality window extending past the CRQC arrival date is already compromised.

NIST FIPS 203, 204, and 205#

On August 13, 2024, NIST approved three Federal Information Processing Standards for post-quantum cryptography after an 8-year open competition that started with 69 submissions^[1:1]:

• ML-KEM (FIPS 203) is a lattice-based key-encapsulation mechanism derived from CRYSTALS-Kyber. Three parameter sets: ML-KEM-512, ML-KEM-768 (the production default), and ML-KEM-1024.
• ML-DSA (FIPS 204) is a lattice-based digital signature from CRYSTALS-Dilithium. Three parameter sets: ML-DSA-44, ML-DSA-65, ML-DSA-87.
• SLH-DSA (FIPS 205) is a stateless hash-based signature from SPHINCS+. Conservative: relies only on hash security, no lattice assumptions.

A fourth algorithm, FN-DSA (Falcon), is in draft as FIPS 206. HQC, a code-based backup KEM, was selected in March 2025 with a draft expected in 2026.

The cautionary tale: SIKE, an isogeny-based KEM that was a NIST Round 4 candidate, was broken by Castryck and Decru in July 2022 in about ten minutes on a single core for SIKEp434 (the Category 1 parameter set); higher parameter sets fell in hours to roughly a day^[6]. This vindicated the hybrid-deployment instinct: never bet everything on a single new scheme.

ML-KEM-768 public keys are 37x larger than X25519. ML-DSA-65 signatures are 51x larger than Ed25519. These numbers reshape every protocol that carries public keys or signatures on the wire.

Hybrid key exchange and X25519MLKEM768#

Hybrid key agreement concatenates a classical keyshare and a PQC keyshare in one handshake. The session secret is derived from both, so the connection is safe if either half remains unbroken^[7].

In TLS 1.3, the client sends a combined X25519 + ML-KEM-768 keyshare (IETF codepoint 0x11EC)^[8]. The server performs X25519 key agreement and ML-KEM encapsulation, returning its own X25519 keyshare plus the ML-KEM ciphertext. HKDF-Extract mixes both shared secrets into the session key.

Hybrid TLS 1.3 handshake with X25519MLKEM768: the session key mixes both a classical and a post-quantum shared secret, so an attacker must break both algorithms to recover plaintext.

The same hybrid pattern appears in messaging. Signal shipped PQXDH in September 2023, combining X3DH Diffie-Hellman with a Kyber-768 KEM encapsulation^[9]. Apple iMessage PQ3 (February 2024) goes further: hybrid initial key establishment plus a periodic Kyber KEM ratchet every 50 messages or 7 days^[10]. Both refuse pure-PQC until ML-KEM has more cryptanalysis behind it.

The cost: the client keyshare grows from 32 bytes to 1,216 bytes, frequently pushing ClientHello past one network packet. Middleboxes that assumed fixed-size ClientHellos drop the connection. Cloudflare measured 0.34% of origin servers breaking outright when the client sends a PQ keyshare first^[7:1].

Signatures versus KEMs: urgency differs#

KEM migration is HNDL-urgent. Recording today's key exchange is sufficient to decrypt later. Signature migration is less urgent because forging a classical signature requires an active attacker running a CRQC at the time of the handshake, not afterward.

However, long-lived authentication anchors cannot wait:

• A root CA issued in 2022 with 10-year validity is still a classical RSA key in the trust store in 2032. A CRQC can forge signatures under it and issue rogue certificates.
• Firmware signing keys protect devices for 20+ years. They cannot be rotated after deployment.
• Code-signing keys for package managers and OS updates have multi-year trust windows.

Signatures also dominate TLS handshake size. ML-DSA-44 alone adds approximately 17 KB to a full certificate chain (six signatures and two public keys). Cloudflare's 2021 experiment showed measurable connection failures when certificate chains cross 10 KB and 30 KB boundaries^[11]. Google is pursuing Merkle Tree Certificates rather than PQ signatures in X.509 for Chrome, acknowledging that post-quantum certificates are not yet practical for the web PKI.

Crypto-agility and migration frameworks#

Crypto-agility is the architectural property that cryptographic algorithms can be swapped via configuration, protocol negotiation, or library upgrade without rewriting callers. JWT Deep Dive demonstrated this with the alg header and JWKS key rotation. TLS cipher negotiation, COSE algorithm registries, and X.509 OIDs all provide the same capability at different layers.

The migration framework:

1. Inventory. Find every classical key exchange and signature: TLS, VPN, SSH, S/MIME, JWT signing, mTLS between services, package signing, backup encryption, HSM key labels. OMB M-23-02 required US federal agencies to produce prioritized inventories and update annually through 2035^[12]. Industry experience suggests that manual inventories commonly miss a significant fraction of cryptographic usage.
2. Prioritize by longevity. Secrets that must remain confidential past 2035 migrate first. Session keys for ephemeral web traffic migrate last.
3. Crypto-agile refactor. If swapping an algorithm requires an application redeploy, fix that first. Named cipher suites, algorithm registries, and abstraction layers are prerequisites.
4. Hybrid rollout. Deploy X25519MLKEM768 for inbound TLS, then outbound. Shadow mode first, then default.
5. Classical sunset. NIST IR 8547 deprecates RSA-2048 and ECC-256 after 2030 and disallows them by 2035. NSA CNSA 2.0 mandates pure PQC for national-security systems by 2035^[12:1].

gantt
    title Post-quantum migration timeline
    dateFormat YYYY
    section Inventory
    Cryptographic inventory       :done, inv, 2024, 2025
    Crypto-agile refactor         :active, agile, 2025, 2026
    section Deploy
    Non-prod canary (hybrid)      :2025, 2026
    Prod shadow (hybrid)          :2026, 2027
    Hybrid default (inbound TLS)  :2026, 2029
    Hybrid default (origins)      :2027, 2029
    section Sunset
    NIST deprecates RSA-2048      :milestone, 2030, 1d
    Retire classical-only leaf    :2030, 2033
    NIST disallows RSA/ECC        :milestone, 2035, 1d
    CNSA 2.0 full PQ deadline     :milestone, 2035, 1d

A realistic 5-year PQC migration path anchored to NIST IR 8547 and NSA CNSA 2.0 deadlines. Inventory and crypto-agility come first; hybrid deployment fills the middle years; classical sunset aligns with regulatory dates.

Library readiness (2025). OpenSSL 3.5 (released April 8, 2025, an LTS) is the first mainstream TLS stack with native ML-KEM, ML-DSA, and SLH-DSA^[13]. BoringSSL supports ML-KEM for Chrome 131+. Go 1.24 (February 2025) ships crypto/mlkem in the standard library. AWS-LC, Rustls, and wolfSSL followed. HSM vendors (Thales, Entrust, AWS CloudHSM) shipped ML-KEM firmware updates through 2024 and 2025, but FIPS 140-3 certification cycles remain a bottleneck.

Real-World Example#

Cloudflare terminates TLS for millions of domains at its edge. It enabled hybrid post-quantum key exchange (X25519+Kyber768, later renamed X25519MLKEM768) for inbound TLS in October 2022 and has been iterating ever since^[7:2].

Scale numbers:

• As of April 2026, over 65% of human-initiated TLS connections to Cloudflare use post-quantum key agreement (X25519MLKEM768)^[14].
• Client keyshare size: 1,216 bytes for the hybrid versus 32 bytes for X25519 alone.
• Throughput: approximately 11,000 ops/sec client-side for X25519+ML-KEM-768 versus 17,000 ops/sec for X25519 alone on Cloudflare hardware.
• 0.34% of origin servers break outright when the client sends a PQ keyshare first.

Architecture decision: HelloRetryRequest fallback. For outbound connections (edge to customer origin), Cloudflare advertises hybrid support but sends classical X25519 first. Origins that support hybrid negotiate up; origins that do not never see a split ClientHello. A scanner probes origins every 24 hours to learn support. This avoids breaking the 0.34% of origins that crash on oversized ClientHellos.

KyberSlash (late 2023). A timing side-channel affected multiple Kyber implementations including Cloudflare's Go code. TLS deployment was not exploitable because TLS reuses Kyber keys only ephemerally, but the episode reinforced the hybrid-first posture: if ML-KEM had been the sole key exchange and a more severe bug appeared, all sessions would be compromised. Hybrid means the classical half still protects you.

Goal: Cloudflare targets full PQ (inbound and outbound) by 2029.

Trade-offs#

Common Pitfalls#

Exercise#

Your organization's TLS uses X25519 for key exchange and Ed25519 for service-mesh mTLS (via mTLS and Service Authentication patterns). Root CAs are 10-year certificates issued in 2022. Design the migration to hybrid PQC: (1) sequence of changes to libraries, config, CA, leaf certs, and clients; (2) what breaks in client compatibility, handshake size, and HSM support; (3) SLA impact on p50 and p99 handshake latency. Bonus: you have a backup-encryption key that must still decrypt data in 2040. How do you protect that specific key today?

Key Takeaways#

• Harvest-now-decrypt-later makes PQC a today problem, even though CRQC is a tomorrow threat. Any secret with a confidentiality window past 2035 is already at risk.
• NIST standardized ML-KEM (FIPS 203), ML-DSA (FIPS 204), and SLH-DSA (FIPS 205) in August 2024. ML-KEM-768 is the production default for key exchange.
• Hybrid (classical + PQC) is the correct deployment mode for 2025 to 2030. You are safe if either half holds.
• KEMs are HNDL-urgent; signatures are less urgent except for long-lived trust anchors (root CAs, firmware signing, code signing).
• ML-KEM-768 public keys are 1,184 bytes versus 32 bytes for X25519. This inflates TLS ClientHellos past one packet and triggers middlebox failures.
• Crypto-agility is the real prerequisite. Organizations that hardcode algorithms will migrate twice.
• Do not waste migration budget doubling AES key sizes for Grover. AES-128 is safe. Spend that effort on ML-KEM deployment.

Further Reading#

• NIST FIPS 203 (ML-KEM) - The final KEM standard; sections 6 and 7 specify parameters and the encapsulation/decapsulation algorithms.
• Cloudflare: The state of the post-quantum Internet - The best single overview of real-world PQC TLS deployment, with scale numbers and middlebox breakage data.
• Signal: Quantum Resistance and the Signal Protocol (PQXDH) - How Signal combines X3DH with Kyber-768 for hybrid post-quantum forward secrecy in messaging.
• Apple: iMessage with PQ3 - The Level 3 messaging architecture with periodic Kyber ratchets and formal verification by Stebila and Basin.
• NIST IR 8547: Transition to Post-Quantum Cryptography Standards - The RSA/ECC deprecation timeline: deprecated by 2030, disallowed by 2035.
• OpenSSL 3.5 Final Release - The first mainstream LTS TLS stack with native ML-KEM, ML-DSA, and SLH-DSA support.
• Filippo Valsorda: Quantum Computers Are Not a Threat to 128-bit Symmetric Keys - The definitive explanation of why Grover does not halve AES security in practice.
• Castryck-Decru SIDH break (eprint 2022/975) - The cautionary tale: SIKEp434 broken in about 10 minutes on a single core, mid-NIST-round-4.

Flashcards#

References#