Post-Quantum Migration Strategy, in depth: Mosca's inequality, a cryptographic inventory, hybrid key exchange, the signature problem and crypto-agility

What breaks and what does not

Shor's algorithm solves integer factoring and discrete logarithms in polynomial time, which removes the hardness assumption behind RSA (see RSA in depth) and behind every Diffie-Hellman and elliptic-curve scheme (see Diffie-Hellman in depth). Larger keys do not help; the attack scales gently with key size.

Symmetric cryptography is in a different position. Grover's algorithm gives at best a square-root speed-up for brute-force key search, and in practice it parallelises poorly. AES with 128-bit keys is not considered in urgent danger, and AES-256 and SHA-256 or stronger hashes leave a large margin, which is why many programmes simply standardise on AES-256. The migration is overwhelmingly about public-key operations: key exchange, key wrapping, signatures and certificates.

Two threats follow, with different clocks. Harvest now, decrypt later targets confidentiality: an adversary records encrypted traffic or steals ciphertext today and decrypts it once a quantum computer exists. Anything protected by a classical key exchange is already exposed if its secrecy must outlive that day. Forgery targets authenticity: a quantum attacker could sign as you, but only from the day the machine exists. Signatures that must be trusted for a long time, such as root certificates, firmware and code-signing keys and legal records, are the exception; their verification keys are distributed long before they are used.

The standards and their costs

NIST published the first three post-quantum standards in August 2024: FIPS 203 (ML-KEM, the module-lattice key-encapsulation mechanism derived from CRYSTALS-Kyber), FIPS 204 (ML-DSA, lattice signatures derived from CRYSTALS-Dilithium) and FIPS 205 (SLH-DSA, stateless hash-based signatures derived from SPHINCS+). In March 2025 NIST selected HQC, a code-based scheme, as a backup KEM built on different mathematics, and a Falcon-based signature standard (FN-DSA) is in progress. Stateful hash-based signatures (LMS and XMSS) were already approved in SP 800-208. NIST's draft transition report, IR 8547 (initial public draft, November 2024), proposes deprecating 112-bit-security RSA and elliptic-curve algorithms after 2030 and disallowing them after 2035; treat those dates as a proposal and check the final text and any sector rules that apply to you.

The cost of the new schemes is mostly size, not speed. ML-KEM key generation and encapsulation are fast, often faster than an elliptic-curve exchange; what changes is how many bytes cross the wire and sit in certificates.

A TLS server certificate chain carries several public keys and signatures, so replacing ECDSA with ML-DSA adds kilobytes to every full handshake. That is the main reason signature migration lags key exchange across the industry.

Ranking with Mosca's inequality

Michele Mosca's inequality turns the uncertainty into a ranking. Let x be how long the data or trust must last, y how long migrating the system will take, and z how long until a cryptographically relevant quantum computer exists. If x + y > z, the system is already late: data encrypted near the end of the migration will still need to be secret after the machine arrives.

You do not know z, so do not pretend to. Use a pessimistic value that your risk owners sign off on, and rank systems by slack z - (x + y); the lowest slack goes first. The formula is crude, but it forces two useful questions per system: how long does this secret really live, and how long would it take us to change this code?

from dataclasses import dataclass

@dataclass
class Asset:
    name: str
    shelf_life_years: float      # x: how long the secret or signature must hold
    migration_years: float       # y: estimated effort, including vendors
    exposure: str                # "network" (harvestable) or "internal"

def rank(assets, z_years):
    """Lowest slack first; harvestable assets break ties."""
    def key(a):
        slack = z_years - (a.shelf_life_years + a.migration_years)
        return (slack, 0 if a.exposure == "network" else 1)
    return [(a.name, round(z_years - a.shelf_life_years - a.migration_years, 1))
            for a in sorted(assets, key=key)]

Building the inventory

Nothing in this list can be migrated until it has been found, and the inventory is always the slowest step. Build it from several sources, because each one sees a different slice.

• Network scans of TLS, SSH and VPN endpoints: negotiated groups, certificate key types, protocol versions. They show what is reachable, not what is hidden behind it.
• Code scanning for cryptographic API calls and key-type strings, across your own repositories and dependency trees.
• Certificate and key stores: the private CA, cloud key managers, HSMs, and secrets vaults, with key type, size and expiry.
• Data at rest: which stores wrap data keys with RSA or ECDH, and how long that data is retained.
• Vendors and devices: products that terminate TLS or sign updates for you, and whether their roadmaps include ML-KEM and ML-DSA.

Record the results as a cryptographic bill of materials (CycloneDX added a cryptography-asset model in version 1.6) so the inventory is machine-readable and can be diffed between scans. A first-pass code scanner is a regex job; it over-reports, which is the right failure for an inventory.

import re, pathlib

PATTERNS = {
    "RSA":   r'getInstance\("RSA|rsa\.generate_private_key|RSA_generate_key|"RS256"',
    "ECDSA": r'getInstance\("EC"|SHA256withECDSA|ec\.generate_private_key|"ES256"',
    "ECDH":  r'KeyAgreement\.getInstance\("(?:ECDH|X25519)|X25519PrivateKey',
    "DH":    r'KeyAgreement\.getInstance\("DH"|dh\.generate_parameters',
}

def scan(root, exts=(".java", ".py", ".go", ".ts", ".kt")):
    hits = []
    for path in pathlib.Path(root).rglob("*"):
        if path.suffix not in exts or not path.is_file():
            continue
        text = path.read_text(errors="ignore")
        for algo, pat in PATTERNS.items():
            for m in re.finditer(pat, text):
                line = text.count("\n", 0, m.start()) + 1
                hits.append({"file": str(path), "line": line, "algorithm": algo})
    return hits

Hybrid key exchange first

Key exchange migrates first because it addresses the threat that is live today, and because a hybrid design makes it low-risk. A hybrid exchange runs a classical exchange and ML-KEM together and derives the session key from both shared secrets, so the result is secure as long as either component holds. That hedges against a flaw in the young lattice schemes or their implementations.

On the web this is already deployed. The TLS group X25519MLKEM768 (codepoint 0x11EC) sends an ML-KEM-768 encapsulation key followed by an X25519 share, 1,216 bytes in the client's key share. Chrome switched to it from an earlier Kyber draft in version 131, and OpenSSL added it in 3.5. Turning it on for your own endpoints is mostly a library upgrade and a configuration change; see TLS 1.3 internals for where the key share sits in the handshake.

The ClientHello grows past a single typical network packet, and that is where deployments break: middleboxes and old servers that assumed a one-packet ClientHello. Roll out behind a flag, watch handshake failure rates by client and network, and keep the classical group available as a fallback during the transition.

Outside TLS, application protocols need the same construction. On Java, JDK 24 added ML-KEM (JEP 496) and ML-DSA (JEP 497) through the standard KEM and Signature APIs:

KeyPairGenerator g = KeyPairGenerator.getInstance("ML-KEM");
g.initialize(NamedParameterSpec.ML_KEM_768);
KeyPair kp = g.generateKeyPair();                 // receiver's long-term or ephemeral pair

KEM kem = KEM.getInstance("ML-KEM");
KEM.Encapsulated e = kem.newEncapsulator(kp.getPublic()).encapsulate();
byte[] ct = e.encapsulation();                    // 1,088 bytes, sent to the receiver
SecretKey pqSecret = e.key();

SecretKey same = kem.newDecapsulator(kp.getPrivate()).decapsulate(ct);
// Hybrid: run X25519 as well, then derive the session key from BOTH secrets,
// binding the public keys and ciphertexts, e.g.
// key = HKDF(ikm = pqSecret || x25519Secret, info = "app-v2" || hash(transcript))

Bind the transcript, meaning both public keys and the ciphertext, into the derivation. A combiner that hashes only the two secrets is a common design mistake, and protocol designers should follow a published combiner rather than inventing one.

Signatures and roots of trust

Signatures are harder for three reasons. They live in certificates, so the whole chain and every relying party must understand the new algorithm before it can be used. They are larger, as the table showed. And roots of trust last a long time: a device shipped today with a classical firmware-verification key may still be in service when that key can be forged.

That last point sets the priority order inside signatures: long-lived roots first. Firmware and boot-chain verification keys, offline root CAs and code-signing roots are where stateful hash-based schemes (LMS, XMSS) or SLH-DSA make sense: security rests only on hash functions, and verification is cheap. Stateful schemes have a sharp edge: signing twice with the same one-time key state breaks security, so they belong in HSMs that manage state, never in software that can be restored from a backup. Short-lived TLS leaf certificates can follow later, once ML-DSA support spreads through the CA ecosystem. Composite and dual-certificate approaches are still being standardised in the IETF; check their status before you design around one. ECDSA in depth covers the classical side you are replacing.

Crypto-agility

Crypto-agility means an algorithm change is a configuration and rollout task, not a code rewrite. Three habits get you most of the way. Label every stored or transmitted cryptographic object with an explicit algorithm identifier and version. Route all cryptographic calls through one internal library, so a policy change is one release. And keep the ability to re-encrypt or re-wrap data at rest by key id.

{
  "v": 2,
  "kem": "X25519MLKEM768",
  "aead": "AES-256-GCM",
  "kid": "kek-2026-10",
  "enc": "<base64 encapsulation>",
  "ct": "<base64 ciphertext>"
}

A reader that dispatches on kem and v can decrypt old and new envelopes during the transition and reject retired algorithms when policy says so. For data at rest, the cheapest win is usually re-wrapping data-encryption keys: the bulk data is already under AES, and only the key wrapping uses RSA or ECDH.

Worked example: ranking four systems

Illustrative numbers for a payments company, using a pessimistic z of 10 years agreed with the risk committee:

The ranking puts firmware and the archive first, and the public API is a quick win because it is a library upgrade. Without the inequality, teams tend to start with the API because it is visible, and leave the firmware signing key, the hardest change with the longest tail, until last.

Failure modes

• Inventory gaps. Vendor appliances and embedded clients are missed; they become the long tail.
• Middlebox ossification. Larger ClientHellos break old proxies; roll out with telemetry and fallback.
• Downgrade. A fallback to classical-only is useful during transition but must be removed, or an attacker can force it.
• Stateful signature reuse. Restoring an LMS or XMSS signer from backup reuses one-time keys.
• HSM and KMS support. Hardware without ML-KEM or ML-DSA support blocks a rollout; ask vendors early.
• Homemade combiners. Concatenate-and-hash without transcript binding; use a published design.
• Treating it as one project. Migration is a programme that ends with retiring classical-only paths, not with enabling the new ones.

What to do next

1. Appoint an owner and agree a pessimistic z with your risk committee.
2. Build a first inventory from network scans, code scans and key stores; store it as a CBOM.
3. Estimate x and y per system and rank by slack.
4. Enable hybrid X25519MLKEM768 on public TLS endpoints behind a flag, with failure telemetry.
5. Re-wrap long-retention data keys with ML-KEM or a hybrid KEM.
6. Plan hash-based or ML-DSA signatures for firmware, code signing and offline roots.
7. Add algorithm identifiers to every envelope and centralise cryptographic calls.
8. Ask every vendor for dated ML-KEM and ML-DSA support, then schedule retirement of classical-only paths.