Post-Quantum Hash-Based Signatures, in depth: Lamport, Winternitz, Merkle trees, stateful LMS and XMSS, and stateless SLH-DSA

Lamport: one key, one signature

Leslie Lamport's 1979 scheme signs one 256-bit digest. The secret key is 512 random 32-byte strings arranged as 256 pairs; the public key is the hash of each. To sign, hash the message, and for each bit i reveal the first secret of pair i if the bit is 0 and the second if it is 1. A verifier hashes each revealed value and compares it with the matching public value. Forging requires a preimage of some public hash, which the hash function's security rules out.

Two problems are obvious. The signature is 8 KB and the public key 16 KB. And the key is strictly one-time: after signing two different digests, an attacker holds both secrets for every bit where they differ and can mix them to sign new digests. Everything that follows is about shrinking the first problem and managing the second.

Winternitz chains and the checksum

Winternitz signatures trade hashing for size. Split the digest into base-w digits, say 4-bit digits with w = 16, so a 256-bit digest becomes 64 digits. For each digit position keep one secret and publish the result of hashing it w - 1 = 15 times. To sign digit value d, publish the secret hashed d times; the verifier hashes it another 15 - d times and checks that it lands on the public value.

On its own this is forgeable: anyone can hash a revealed value further and so sign a larger digit. The fix is a checksum: append the sum of (15 - d) over all digits, encoded in base w as well. Raising any message digit lowers the checksum, and lowering a checksum digit would require inverting the hash. For a 256-bit digest the checksum is at most 64 times 15 = 960, which fits in three 4-bit digits, so 67 chains in total. That number, 67, is exactly the p parameter of the LM-OTS variant with w = 4 in RFC 8554.

import hashlib, os

N, W = 32, 16                       # 32-byte values, base-16 digits
LEN1 = 64                           # digits of a 256-bit digest
LEN2 = 3                            # checksum digits: 64 * 15 = 960 < 16**3
H = lambda x: hashlib.sha256(x).digest()

def chain(x, steps):
    for _ in range(steps):
        x = H(x)
    return x

def digits(msg):
    d = H(msg)
    ds = [n for b in d for n in (b >> 4, b & 15)]   # 64 base-16 digits
    csum = sum(W - 1 - v for v in ds)
    ds += [(csum >> 8) & 15, (csum >> 4) & 15, csum & 15]
    return ds                        # 67 digits

def keygen():
    sk = [os.urandom(N) for _ in range(LEN1 + LEN2)]
    pk = [chain(s, W - 1) for s in sk]
    return sk, pk

def sign(sk, msg):
    return [chain(s, d) for s, d in zip(sk, digits(msg))]

def verify(pk, msg, sig):
    return all(chain(s, W - 1 - d) == p_ for s, d, p_ in zip(sig, digits(msg), pk))

The signature is 67 times 32 = 2,144 bytes instead of 8 KB, at the cost of up to 15 hashes per chain for each of signing and verifying. Standardised variants (WOTS+ in XMSS and SLH-DSA, LM-OTS in LMS) add per-chain masks or prefixes so that each hash call is domain-separated, which lets them prove security with shorter hashes, but the shape is the same.

Merkle trees: many one-time keys, one public key

A one-time key is useless as a long-term identity. Ralph Merkle's fix is to generate 2 to the h one-time key pairs, hash each public key into a leaf, and build a binary hash tree over the leaves. The root is the long-term public key, 32 bytes. A signature with leaf q contains q, the one-time signature, the one-time public key (or enough to recompute it), and the authentication path: the h sibling hashes needed to walk from leaf q to the root. The verifier recomputes the one-time public key from the signature, hashes up the path and compares with the root. The tree itself is explained in Merkle trees in distributed systems.

With h = 20 one key signs about a million messages, and the path adds only 20 times 32 = 640 bytes. Key generation, however, must compute every leaf to know the root: a million one-time public keys, each costing 67 chains of 15 hashes. That is about a billion hash calls, seconds to minutes on one core, which is why large trees are split into layers.

Stateful schemes: LMS and XMSS

LMS (RFC 8554) and XMSS (RFC 8391), both approved by NIST in SP 800-208, are Merkle schemes as described, with multi-tree variants (HSS and XMSS^MT) that stack trees so that the top tree signs the roots of lower trees and key generation only has to build one tree per layer up front. An LMS signature with n = 32 has size 4 + (4 + n + p times n) + 4 + h times n bytes:

Those are small, fast to verify and ideal for verifiers with little memory such as boot ROMs. The catch is the word stateful: the signer must never use a leaf twice. Using one twice publishes two one-time signatures from the same key, and the Winternitz forgery above becomes practical. The state is just a counter, but the counter must survive everything operations can do to it: a VM restored from a snapshot, an HSM backup restored to a second device, two signing servers behind a load balancer, a crash between producing a signature and persisting the new counter. Each of those silently reuses leaves.

Safe deployments therefore follow rules that look odd for software: advance and durably persist the counter before releasing a signature, never clone a key, and if you need several signers, give each a disjoint range of leaves or a separate subtree. That is why NIST restricts stateful schemes to cases where the signing environment is tightly controlled, typically in a hardware module, and why they fit firmware and code signing for long-lived devices, where CNSA 2.0 calls for LMS or XMSS, better than general-purpose signing.

Stateless: SLH-DSA

SPHINCS+ removes the state, and FIPS 205 standardises it as SLH-DSA (August 2024). The idea is to make the tree so large that the signer can pick a leaf at random and the chance of reusing one is negligible. A single tree of height 64 is too expensive to build, so SLH-DSA uses a hypertree: d layers of XMSS trees, each of height h/d, where every WOTS+ key in one layer signs the root of a tree in the layer below. Only the trees on the path to the chosen leaf are computed at signing time, derived deterministically from a secret seed.

The bottom of the hypertree signs not the message but a key of FORS, a few-time scheme: k small trees each with 2 to the a leaves, where the message digest picks one leaf in each tree. A FORS key can safely sign a handful of messages, so the rare event of two messages landing on the same bottom leaf only degrades security slightly rather than breaking it. The leaf index is computed from the message and a per-signature randomiser, so there is no counter to lose.

Each row exists in a SHA-2 and a SHAKE variant, twelve sets in total. The s sets use fewer, taller layers, giving smaller signatures but many more hash calls to sign; f sets use more, shorter layers and the reverse. Verification is fast in both since it only recomputes one path. NIST has presented work on additional smaller parameter sets for signers that issue few signatures; treat that as in progress, not as a standard you can deploy.

Worked example: signing firmware

Take a device vendor that signs firmware images for a ten-year product line, with a verifier in boot ROM that has 32 KB of RAM. Today it uses ECDSA P-256 with 64-byte signatures (see ECDSA). The candidates are:

• LMS, h = 20, w = 8: 1,772-byte signatures, a 56-byte public key, verification of about 34 chains of up to 255 hashes plus 20 path hashes, roughly 9,000 SHA-256 calls in the worst case. A million signatures covers decades of releases. The cost is an HSM-held key with a durable counter and a documented rule that the key is never exported.
• SLH-DSA-128s: 7,856-byte signatures and a 32-byte public key, verification of a few thousand hashes, and no state at all. Signing takes far longer, but a release pipeline signing a few images a day does not care.
• ML-DSA-44: a 2,420-byte signature and 1,312-byte public key, fast everywhere, but security rests on lattice assumptions that are younger than hash functions.

A sensible plan is LMS for the boot ROM, where the root of trust cannot be changed after manufacture and conservative assumptions matter most, with the signing key in an HSM and leaf ranges allocated per release pipeline. If the organisation cannot guarantee state discipline, SLH-DSA-128s is the safe alternative: the cost is 6 KB more per image, usually irrelevant next to the image itself.

Failure modes

• State rollback. Restoring a signer from backup, snapshot or a replicated database rewinds the counter. Persist the counter in the HSM, and on any restore skip ahead by a safety margin larger than the signatures possible since the backup.
• Concurrent signers. Two processes reading the same counter sign with the same leaf. Serialise on an atomic increment, or partition leaves per signer.
• Key exhaustion. A stateful key that runs out cannot sign. Alert at 50 and 90 percent of leaves used, and plan the next key's distribution before then.
• Size surprises. SLH-DSA signatures break assumptions such as a single UDP datagram, a 4 KB certificate field or a fixed-size firmware header. Measure every container they travel in.
• Fault attacks. A glitched hash computation during SLH-DSA signing can leak a WOTS+ signature on a wrong value and enable forgery. Signers in hostile physical environments should verify their own signature before releasing it.

Trade-offs

Compared with Ed25519, every hash-based scheme is large: 64-byte signatures become 1.7 to 50 KB. Compared with ML-DSA, hash-based schemes have smaller public keys and older assumptions but larger signatures (SLH-DSA) or operational state (LMS, XMSS). Hash speed dominates everything, so implementations with hardware SHA-256 or SHA-3 support, and the choice between the SHA-2 and SHAKE variants, affect signing time noticeably; the underlying functions are compared in the SHA family. The rule of thumb: stateful schemes for a small number of controlled signers with constrained verifiers, SLH-DSA where state cannot be trusted or where you want a conservative backup to a lattice scheme, and ML-DSA for high-volume signing such as TLS where size and speed matter most.

What to do next

1. List every place your organisation verifies a signature that cannot be updated later, such as boot ROMs and long-lived devices; those are hash-based candidates.
2. For each, measure the space available for a signature and a public key.
3. Pick LMS or XMSS only if the signer can live in an HSM with a durable, non-cloneable counter.
4. Otherwise prototype SLH-DSA-128s with your library and measure signing time in the release pipeline.
5. Write the state-handling runbook before generating a stateful key: restore, failover, exhaustion.
6. Run the Winternitz example above, then try reusing a key to see how a forgery is assembled.