Signing Things That Must Outlive RSA: ML-DSA, Hybrid Signatures, and the Engineering of Long-Lived Trust

The key ceremony for a firmware signing root is a strange ritual to sit through once you start doing the arithmetic out loud. Four people in a windowless room generate an ECDSA P-384 key inside an HSM, split the backup among smartcards, sign the paperwork — and then the device that key protects ships into the field with a twenty-year service life. Grid meters, automotive ECUs, medical implants, rail signaling. The verifying half of that keypair gets burned into ROM, and the ROM does not take software updates. Whatever mathematics that public key relies on has to remain unbroken until the last unit is decommissioned, somewhere around 2046.

Ask the room whether P-384 will still be considered a signature algorithm in 2046 and you get uncomfortable silence, because everyone present has read the same estimates you have. A cryptanalytically relevant quantum computer breaks P-384 not by weakening it but by ending it — Shor’s algorithm recovers the private key from the public key in polynomial time¹. Nobody knows the year. NIST’s transition guidance has stopped waiting to find out: the draft roadmap in NIST IR 8547 deprecates RSA and ECDSA after 2030 and disallows them after 2035². Twenty-year firmware signed in 2026 with ECDSA is, by the standards body’s own timeline, signed with an algorithm that will be forbidden before half the fleet retires.

This post is about what to do instead — specifically about ML-DSA, the lattice signature NIST standardized as FIPS 204 in August 2024³, why the right way to deploy it in 2026 is alongside Ed25519 rather than instead of it, and how to think clearly about which of your signatures actually face a quantum deadline. That last question is where most discussion goes wrong, so we start there.

Two clocks, not one: HNDL applied precisely

“Harvest now, decrypt later” is the phrase that finally made post-quantum migration a budget line. It is also routinely misapplied to signatures, and the misapplication produces both panic where none is needed and complacency where it is.

For encryption and key exchange, the threat is retroactive. An adversary recording your TLS traffic today stores the ciphertext; when a quantum computer arrives, Shor’s algorithm recovers the ECDH shared secret and the recording decrypts. Confidentiality has a backwards-reaching failure mode, which is why the key-exchange migration deadline was effectively yesterday: every byte encrypted under classical ECDH is already in the adversary’s future-readable archive. The industry acted accordingly — Chrome enabled hybrid post-quantum key exchange in 2024, moving to the X25519MLKEM768 hybrid as ML-KEM finalized⁴; Signal shipped its PQXDH hybrid handshake in September 2023⁵; Cloudflare has carried double-digit percentages of human-originated traffic over post-quantum key exchange since 2024⁶.

Signatures fail forwards, not backwards. A signature is verified at a moment in time, and a verifier that checked an Ed25519 signature in 2026 learned something true in 2026. A quantum computer built in 2035 cannot reach back and make that 2026 verification retroactively wrong; there is nothing to “harvest” — the signature and message are usually public anyway. What the 2035 machine can do is derive your private key from your public key and forge new signatures that verify against it. So the question that determines your deadline is not “when is Q-day?” but:

Will anything still be verifying against this public key when a quantum computer exists?

Which yields the actual planning rule, a signature-flavored restatement of Mosca’s inequality⁷: if the verification lifetime of your artifacts plus your migration time exceeds the time to a cryptanalytically relevant quantum computer, you are already late. Concretely:

• A TLS server certificate lives ninety days and verifies interactively. Its migration deadline is roughly Q-day itself; you can swap the algorithm the year before and lose nothing. Relax.
• A JWT with a five-minute expiry is the easiest case in the industry. Relax entirely.
• A firmware verification key in mask ROM on a 2026-manufactured device verifies until the device dies. Its deadline is Q-day minus twenty years of fleet life — a number that may already be negative. Do not relax.
• A software license or entitlement token valid until 2040, verified offline by shipped binaries, is the sneaky middle case: it looks like a JWT and ages like firmware.
• Timestamped archival signatures (legal documents, notarization, transparency logs) have a subtler failure: after Q-day, a signature alone no longer proves the document existed before the break — only a pre-Q-day timestamp chain or re-signing under a PQ algorithm preserves the evidentiary value.

One more forward-looking wrinkle: signatures made before Q-day remain trustworthy only if verifiers can distinguish them from post-Q-day forgeries, which they generally cannot without timestamps. So “we’ll re-sign everything later” is a real strategy — but only for artifacts whose verifiers you can update. The ROM does not take updates. That asymmetry — rotatable verifier versus frozen verifier — is the entire risk taxonomy for signatures, and it is why this post keeps returning to firmware.

Why everything falls together

The reason the migration is wholesale rather than incremental is that RSA, classical Diffie-Hellman, ECDSA, and Ed25519 all rest on two problems — integer factorization and discrete logarithms — that Shor’s 1994 algorithm solves in polynomial time on a sufficiently large fault-tolerant quantum computer¹. There is no parameter-size retreat: doubling the RSA modulus adds a constant factor against Shor, not an exponential one. Symmetric cryptography and hashes are in far better shape; Grover’s algorithm offers at most a quadratic speedup on brute force⁸, which AES-256 and SHA-384 absorb by design. This is why the post-quantum project is a public-key project, and why hash-based signatures (we will meet them below) are the conservative corner of it.

ML-DSA for working engineers

ML-DSA — the Module-Lattice-Based Digital Signature Algorithm — is the renamed, finalized CRYSTALS-Dilithium⁹, standardized as FIPS 204 on 13 August 2024, the same day as its sibling standards FIPS 203 (ML-KEM, key encapsulation) and FIPS 205 (SLH-DSA, hash-based signatures)³¹⁰¹¹. You do not need to implement it — you need enough of its shape to reason about parameters, failure modes, and costs.

The hardness assumption is the Module Learning With Errors problem (with a helping of Module-SIS): given a matrix A over a polynomial ring and the vector t = As₁ + s₂, where s₁, s₂ are secret vectors with small coefficients, recover the secrets. Without the smallness constraint this is linear algebra; with it, the best known attacks — classical and quantum — are lattice-reduction algorithms whose cost grows exponentially in the dimension. Quantum computers get no Shor-style shortcut here; that is the entire bet.

The signature construction is Fiat-Shamir with aborts, Lyubashevsky’s 2009 insight that made lattice signatures practical¹². The signer runs a Schnorr-like identification protocol made non-interactive by hashing, with one lattice-specific twist: a candidate signature whose distribution would leak information about the secret key is aborted and retried with fresh randomness. Rejection sampling, in effect, inside the signing loop. Two engineering consequences fall out:

1. Signing time is variable. ML-DSA-65 averages roughly four repetitions; the loop occasionally runs longer. Irrelevant for API servers, worth knowing for hard-real-time firmware contexts.
2. Verification is simple and fast — one matrix-vector product and norm checks, no rejection loop, no floating point. The asymmetry is friendly to exactly the constrained-verifier scenarios (bootloaders) where PQ signatures are most urgent.

FIPS 204 made two changes from the competition-era Dilithium worth knowing. Default signing is hedged: the signature incorporates fresh randomness and deterministic key-derived material, so a bad RNG degrades toward deterministic signing rather than toward key leakage (a deterministic mode remains available for environments without an RNG, at the cost of increased fault-attack exposure)³. And the standard defines pure ML-DSA over the raw message plus a pre-hash variant (HashML-DSA), with domain separation between them and support for a context string — small things that matter when you design protocols on top.

Parameters and the byte bill

(Sizes from FIPS 204, Table 2³.)

The column to internalize is ML-DSA-65: it is the parameter set most guidance converges on — category 3, comfortably above near-term lattice cryptanalysis estimates, without ML-DSA-87’s bulk — and it costs you a 1,952-byte public key and a 3,309-byte signature where Ed25519 charged 32 and 64. Two orders of magnitude. Bas Westerbaan’s early Cloudflare analysis of what such sizes do to the web’s signature-saturated handshakes — a TLS connection can carry half a dozen signatures and two public keys before any application byte moves — remains the clearest tour of why nobody is celebrating¹³. For a firmware header, 5 KB of signature-plus-key is usually absorbable. For a QR code, a DNSSEC response, or a JWT that rides in an HTTP header on every request, it is a redesign.

Speed, by contrast, is a non-problem and occasionally a gift. On modern x86, optimized ML-DSA-65 signs and verifies in tens of microseconds — competitive with or faster than Ed25519, and dramatically faster than RSA signing. Even in pure JavaScript, @noble/post-quantum clocks ML-DSA-65 around 270 signs and 550 verifies per second¹⁴ — slow only by cryptographic standards, invisible next to a network round trip. The migration tax is paid in bytes, not cycles.

Why hybrid, argued honestly

The obvious migration is to replace Ed25519 with ML-DSA and move on. The sane migration, for the next several years, is to sign with both and require both to verify. The argument has three legs.

Leg one: lattice cryptanalysis is young. The competition that produced ML-DSA also produced the two great cautionary tales of modern cryptography. Rainbow, a NIST Round 3 signature finalist, was broken by Ward Beullens in 2022 — key recovery for the category-1 parameters in fifty-three hours on a laptop¹⁵. SIKE, a Round 4 KEM candidate, fell the same year to Castryck and Decru’s key-recovery attack, running in about an hour on a single core¹⁶. Both schemes had survived years of expert scrutiny. Structured lattices have held up far better and far longer — but “far better and far longer” is a confidence statement, not a proof, and the honest posterior after 2022 assigns non-trivial probability to some PQ family losing security margin within a decade. A hybrid signature fails only if Ed25519 and ML-DSA both fall: an attacker needs either a quantum computer (kills Ed25519, not ML-DSA) or a lattice breakthrough (kills ML-DSA, not Ed25519) — and needs both at once.

Leg two: implementation maturity is asymmetric. Ed25519 implementations have had a decade of side-channel hardening, formal verification, and deployment scar tissue. ML-DSA implementations are three-ish years old as standardized artifacts; early Dilithium code saw fault-injection and side-channel papers in exactly the way young implementations always do. Hybrid means a bug in the new code cannot, alone, forge your signatures.

Leg three: the ecosystem is already voting this way — for key exchange, universally (X25519MLKEM768 everywhere⁴), and for signatures via the IETF’s composite work: draft-ietf-lamps-pq-composite-sigs defines ML-DSA paired with Ed25519, ECDSA, and RSA as single composite algorithms for X.509, with single OIDs, so a certificate carries one “signature” that is internally both¹⁷. Standalone ML-DSA in PKI is standardized too — RFC 9881 profiles ML-DSA in X.509 certificates and RFC 9882 in CMS, both published October 2025¹⁸¹⁹ — so pure-PQ and composite paths are both real; the composite draft exists precisely because much of the industry wants the both-must-verify property during the transition.

The counterargument deserves airtime: hybrids cost complexity, bytes (you pay both signatures), and a combinatorial testing surface, and the NSA’s CNSA 2.0 pointedly declines to require them, mandating standalone PQ algorithms for National Security Systems²⁰. That position makes sense for an actor confident in its cryptanalytic assessment of lattices and allergic to protocol complexity. For the rest of us — shipping artifacts whose verifiers we cannot update, into a decade where one more Rainbow-grade surprise is plausible — 3,373 bytes of combined signature instead of 3,309 is the cheapest insurance in security engineering. Sixty-four bytes buys you “an attacker must break two unrelated hard problems.” Take the deal.

One design rule if you compose signatures yourself rather than using the composite draft: AND-verification with domain separation. Both signatures must cover the same encoded message including a label binding them together as a composite (the IETF draft prefixes a domain separator and context before hashing¹⁷). A verifier that accepts either signature is strictly weaker than either algorithm alone — an attacker attacks whichever is easier. Never ship an OR.

What hybrid signing looks like in code

TypeScript first, because @noble/post-quantum and @noble/curves make the shape visible in a few lines — pure JS, audited, FIPS-204 test-vector conformant¹⁴:

import { ml_dsa65 } from "@noble/post-quantum/ml-dsa";
import { ed25519 } from "@noble/curves/ed25519";
import { sha512 } from "@noble/hashes/sha2";
import { randomBytes } from "@noble/post-quantum/utils";

// Domain separator: binds both signatures to this composite scheme,
// preventing cross-protocol reuse of either component signature.
const DOM = new TextEncoder().encode("example.com/hybrid-sig-v1:Ed25519+ML-DSA-65");

const toBeSigned = (msg: Uint8Array) => sha512(concat(DOM, msg));

export function keygen() {
  const edPriv = ed25519.utils.randomSecretKey();
  const mld = ml_dsa65.keygen(randomBytes(32));       // seed-based keygen
  return {
    publicKey:  { ed: ed25519.getPublicKey(edPriv), mld: mld.publicKey },
    privateKey: { ed: edPriv,                       mld: mld.secretKey },
  };
}

export function sign(priv, msg: Uint8Array) {
  const m = toBeSigned(msg);
  return {
    ed:  ed25519.sign(m, priv.ed),        //    64 bytes
    mld: ml_dsa65.sign(priv.mld, m),      // 3,309 bytes
  };
}

export function verify(pub, msg: Uint8Array, sig): boolean {
  const m = toBeSigned(msg);
  const okEd  = ed25519.verify(sig.ed, m, pub.ed);
  const okMld = ml_dsa65.verify(pub.mld, m, sig.mld);
  return okEd && okMld;                    // AND. Never OR.
}

The same construction in Go, with Cloudflare’s CIRCL supplying ML-DSA²¹:

import (
    "crypto/ed25519"
    "github.com/cloudflare/circl/sign/mldsa/mldsa65"
)

type HybridSig struct{ Ed, Mld []byte }

func Sign(edPriv ed25519.PrivateKey, mldPriv *mldsa65.PrivateKey,
          tbs []byte) HybridSig {
    mldSig := make([]byte, mldsa65.SignatureSize)
    if err := mldsa65.SignTo(mldPriv, tbs, nil, false, mldSig); err != nil {
        panic(err)
    }
    return HybridSig{Ed: ed25519.Sign(edPriv, tbs), Mld: mldSig}
}

func Verify(edPub ed25519.PublicKey, mldPub *mldsa65.PublicKey,
            tbs []byte, sig HybridSig) bool {
    okEd := ed25519.Verify(edPub, tbs, sig.Ed)
    okMld := mldsa65.Verify(mldPub, tbs, nil, sig.Mld)
    return okEd && okMld
}

Serialization discipline matters more than it looks: version-tag the composite (v1 = Ed25519+ML-DSA-65) so a future v2 can drop the classical leg without ambiguity, and store both public keys under a single logical key ID — operationally this is one signing identity with two mathematical components, and your key-management tooling should treat it that way (one rotation event, one revocation event, one audit trail).

The hash-based lane: firmware’s conservative option

For software and firmware signing specifically, there is an older, stranger, and in one precise sense safer answer: hash-based signatures. LMS and XMSS — standardized for U.S. government use in NIST SP 800-208²² — build signatures from nothing but hash functions and Merkle trees. Their security reduces to the collision- and preimage-resistance of SHA-256: no lattices, no number theory, assumptions so minimal and so battle-tested that a break would take most of cryptography down with it. This is why the NSA’s CNSA 2.0 suite, published September 2022, named LMS and XMSS as the algorithms for software and firmware signing and set the most aggressive timeline in the whole document: support preferred by 2025, exclusive use by 2030²⁰.

The catch is the word stateful. An LMS/XMSS private key is a finite tree of one-time keys, and the signer must never reuse a leaf — signing twice from the same state is not a weakness but a catastrophic key compromise. State management is trivial on a whiteboard and treacherous in real infrastructure: restore a signer from backup, fail over between HSM replicas, or clone a VM, and you can silently rewind the counter. SP 800-208 consequently confines key generation and signing to hardware modules²². For a firmware pipeline that signs a few hundred releases a year from one HSM-backed ceremony, this is manageable and arguably ideal. For anything resembling high-volume or distributed signing, it is an outage generator.

SLH-DSA (FIPS 205, the standardized SPHINCS+) removes the state at the price of bulk and speed: ~7.9 KB signatures at category 1 (128s) and signing costs orders of magnitude above ML-DSA¹¹. The resulting decision table for firmware teams is mercifully short: LMS/XMSS if you must satisfy CNSA 2.0 or want minimal assumptions and can enforce HSM-bound state; SLH-DSA if you want minimal assumptions without state risk and can afford the bytes; ML-DSA (hybrid) for everything general-purpose. Whichever you choose, the architecture question outranks the algorithm question: RFC 9019’s firmware-update architecture assumes verification keys and manifest formats can evolve — build your bootloader with algorithm agility and slots for two verification keys now, even if the second slot ships empty, because the device you manufacture this year is the one you will otherwise be unable to save²³.

Where you need this today — and where you genuinely don’t

Applying the two-clock analysis from the top of this post:

Need it now (frozen or long-lived verifiers):

• Firmware and secure-boot roots for devices with 10+ year lives. The ROM key outlives the algorithm’s legal lifetime under IR 8547, full stop².
• Root and intermediate CAs, trust anchors, code-signing roots. A root minted in 2026 wants a 15–25 year life; RFC 9881 and the composite draft exist precisely so new hierarchies can be PQ or hybrid from birth¹⁸¹⁷.
• Long-validity licenses, entitlements, and offline tokens. Anything your shipped binaries verify offline for years. These are small, numerous, and forgettable — inventory them first, because nobody remembers the license checker until it is the last ECDSA verifier in the fleet.
• Archival and legal signatures. Pair with trusted timestamping now; plan re-signing ceremonies for anything whose evidentiary value must survive Q-day.

Can wait, deliberately (rotatable, short-lived verifiers):

• TLS server certificates. Ninety-day lifetimes and updatable clients mean the WebPKI can swap algorithms late; the constraint is handshake bytes, and the ecosystem is taking its time on purpose while key exchange (the actual HNDL emergency) is already migrated⁶.
• Session tokens, short-lived JWTs, API request signing. Minutes-to-days lifetimes. Swap when your libraries make it a config change.

The pattern: the urgency of PQ signatures is inversely proportional to how often the signature is made and directly proportional to how long the verifier lives. The industry’s attention gravitates to TLS because TLS is where cryptographers live; your actual exposure is more likely in a bootloader repo nobody has touched since 2021.

The library landscape, mid-2026

The tooling crossed the production threshold over the last eighteen months. What I would actually build on today:

• liboqs (C, with wrappers for Python, Java, Rust, .NET) — the Open Quantum Safe project’s kitchen-sink library, now developed under the Linux Foundation’s Post-Quantum Cryptography Alliance, which gives it the governance and funding story it previously lacked. The reference choice for evaluation and for reaching algorithms beyond the FIPS trio²⁴.
• OpenSSL 3.5 (April 2025, LTS) — ML-KEM, ML-DSA, and SLH-DSA in the default provider. This is the release that makes PQ signatures boring for the vast middle of the industry: openssl req -newkey mldsa65 and your existing PKI tooling mostly follows²⁵.
• CIRCL (Go) — Cloudflare’s production library; ML-DSA-44/65/87 with a clean API, deployed at Cloudflare scale. The pragmatic Go answer while the standard library’s ML-DSA work (an internal FIPS 204 implementation landed in the Go 1.26 cycle, with a public crypto/mldsa package under proposal) makes its way out²¹.
• @noble/post-quantum (TypeScript/JavaScript) — Paul Miller’s zero-dependency, audited implementation of ML-KEM, ML-DSA, and SLH-DSA, conformant to FIPS test vectors; the noble family’s track record on auditability makes it the default for Node and browser code¹⁴.
• Bouncy Castle (JVM/.NET) carries the FIPS-final algorithms for the Java world; AWS-LC and BoringSSL cover the cloud-provider C stacks.

Interoperability is the remaining rough edge, and it is a protocol rough edge rather than a primitive one: pure versus pre-hash ML-DSA modes, context strings, and composite encodings are exactly the places two conformant implementations can disagree. Test cross-library verification early — sign in CIRCL, verify in OpenSSL and noble — and pin the encodings in your own spec. The RFC-level pieces (9881, 9882, the composite draft) are recent enough that library defaults still drift¹⁸¹⁷.

Closing: sign like the verifier is watching from 2040

The post-quantum conversation spent a decade sounding like eschatology, and engineers learned to tune it out — reasonably, since “someday a computer might exist” is not an actionable ticket. What changed is that the vague future acquired specific dates from unsentimental institutions: FIPS 204 is published³, IR 8547 draws the line at 2030 and 2035², CNSA 2.0 wants firmware signing fully post-quantum by 2030²⁰, and the X.509 plumbing shipped as RFCs last October¹⁸. The remaining uncertainty — when a cryptanalytically relevant quantum computer arrives, or whether lattices hold — no longer changes the engineering decision, because the decision was never really about predicting Q-day. It was about the gap between how long your signatures must be believed and how fast you can change what does the believing.

That gap is why the precise version of harvest-now-decrypt-later matters. Your encrypted traffic was the emergency, and the industry has largely handled it. Your signatures are a slower fuse burning toward a smaller set of targets: the ROM key, the root CA, the license verifier in a binary you shipped to customers who will run it for a decade. For those, ML-DSA-65 hybridized with Ed25519 is not a bet on quantum computers arriving — it is the refusal to bet either way, purchased for a few kilobytes an artifact from libraries you can npm install today. Rainbow and SIKE taught us what betting everything on one young assumption looks like¹⁵¹⁶; Shor taught us what betting everything on the old ones looks like¹. The hybrid signature is what not betting looks like.

The signing ceremony in the windowless room will keep its ritual — the smartcards, the witnesses, the paperwork. The only change worth insisting on is the question asked before anyone touches the HSM: who verifies this, and until when? If the answer reaches past 2035, the key that comes out of that room should already be one that RSA’s mathematics cannot drag down with it. The things we sign are promises with dates attached. Start making promises you can keep.

References