Stateful Hash-Based Signatures (XMSS, LMS)

What stateful means

A stateful hash-based signature scheme uses a tree of one-time signature keys. Each leaf can sign exactly once. The signer must:

1. Track which leaves have been used.
2. Persist that state durably across reboots, backups, restores.
3. Never sign with the same leaf twice — the security proof collapses if it does.

Stateless schemes like SLH-DSA avoid this by selecting leaves pseudo-randomly and using larger trees with FORS few-time signatures at the bottom. The cost of statelessness is signature size (7-50 KB). Stateful schemes are 2-3 KB at comparable security, but require operational state-machine discipline.

XMSS — eXtended Merkle Signature Scheme

Standardization

RFC 8391, "XMSS: eXtended Merkle Signature Scheme," published May 2018 by Hülsing, Butin, Gazdag, Rijneveld, Mohaisen. NIST SP 800-208 (October 2020) approved XMSS for federal use in narrow scenarios.

Construction

XMSS is a Merkle tree of WOTS+ (Winternitz One-Time Signature) keys. The public key is the Merkle tree root. To sign:

1. Pick the next unused leaf (state-tracked counter).
2. Generate the WOTS+ keypair for that leaf deterministically from a master seed.
3. Sign the message hash with WOTS+.
4. The signature is the WOTS+ signature plus the Merkle authentication path to the root.

A single XMSS tree of height h supports 2^h signatures total. After that, the key is exhausted.

XMSS-MT (multi-tree)

XMSS-MT is a hyper-tree of XMSS trees: a top-level tree whose leaves sign the roots of mid-level trees, whose leaves sign the roots of bottom-level trees. This allows much larger signing capacity (2^60 or more) without huge keygen cost.

Parameter sets (RFC 8391)

Public keys are 64 bytes. Signatures grow linearly with tree height because of the longer authentication path.

LMS — Leighton-Micali Signatures

Standardization

RFC 8554, "Leighton-Micali Hash-Based Signatures," published April 2019 by McGrew, Curcio, Fluhrer. NIST SP 800-208 (October 2020) approved LMS alongside XMSS.

Construction

LMS is conceptually similar to XMSS — a Merkle tree of LM-OTS one-time signatures — but with simpler structure:

• LM-OTS: a Winternitz-like one-time signature.
• LMS: a Merkle tree of LM-OTS keys.
• HSS (Hierarchical Signature System): the LMS counterpart to XMSS-MT, layering LMS trees.

LMS prioritizes implementation simplicity and verification speed. It is slightly faster than XMSS in software and was the choice for several industry standards.

Parameter sets (RFC 8554)

LMS signatures are slightly smaller than XMSS at comparable parameters because of differences in the WOTS variant (LM-OTS vs WOTS+).

NIST SP 800-208 — what it requires

NIST SP 800-208 approves specified LMS/HSS and XMSS/XMSS-MT parameter sets. It requires key generation and signing in hardware cryptographic modules that do not export secret keying material. State must be maintained so that no one-time key signs two different messages.

Firmware and software signing are important applications. Suitability for another application depends on meeting the recommendation’s state-management and hardware requirements.

The state-management problem in detail

Reusing an index in XMSS or LMS is catastrophic. With two signatures on different messages from the same WOTS+ key, an attacker can usually forge signatures on a third message. The relevant attack:

Sign(m1, idx=k) → reveals certain hash chain values
Sign(m2, idx=k) → reveals different hash chain values
Combine: enough chain values exposed to forge sign(m3) where H(m3) is a coordinate-wise weak point

State is lost in many ways:

• Backup-and-restore. The signer ships its state to backup storage; later a restore brings back an earlier state, and the signer reuses leaves.
• VM snapshot. Cloning a VM gives two systems with identical signing state.
• Crash before persisting. The signer increments its in-memory counter, signs, then crashes before flushing to disk. On reboot it signs with the same counter again.
• Concurrent signers. Two threads or two replicas signing from the same key file.

Defenses

1. Hardware security module with non-cloneable state. The HSM enforces that the counter only ever increases, with anti-rollback hardware.
2. Counter persistence with fsync barriers. Increment counter, fsync, sign, fsync. Slow but robust.
3. Reserve-then-sign. Allocate a batch of leaves to a signer (idx 1000-1100), and the signer never touches anything outside that range.
4. Multi-tree with batch reservation. In XMSS-MT, allocate sub-trees to specific signers.
5. Don't use stateful. Use SLH-DSA if the operational discipline isn't available.

Real-world deployments

Linux kernel module signing

The Linux kernel community experimented with XMSS and LMS for module signing as an alternative to RSA-PSS, motivated by PQ migration. Discussion on linux-crypto and lkml has continued since 2020. Production adoption depends on state-management tooling.

Firmware signing

• Quantum-resistant firmware signing: Cisco, HPE, and others have piloted LMS for signed firmware. The signing infrastructure is one batch process per release; state can be tracked.
• AWS: published guidance on using LMS for AWS Nitro and Graviton firmware paths.

Code signing

• Microsoft Authenticode: PQ extensions under discussion include LMS as an option.
• Sigstore: SLH-DSA more likely than LMS because of the stateless property.

Government

• Germany / BSI: lists XMSS and LMS in its TR-02102-1 catalog for narrow applications.

Comparison with stateless SLH-DSA

The cryptographic assumption is the same. The difference is purely operational. If the signing environment is locked down, XMSS / LMS give you 4x smaller signatures. If not, use SLH-DSA.

Trade-offs

Strengths

• Hash-only assumption (same conservative footing as SLH-DSA).
• Signatures 4-5x smaller than SLH-DSA.
• Fast signing and verification.
• Standardized via stable RFCs (8391, 8554) and NIST SP 800-208.
• Well-suited to controlled signing pipelines.

Limitations

• Stateful. State corruption is catastrophic.
• Capacity is bounded by tree height.
• Operational complexity (counter persistence, backup discipline).
• NIST-approved use requires the hardware and state-management controls in SP 800-208.
• Not suitable for end-user signing (phones, laptops, browsers).

Attack surface

When to pick XMSS or LMS

Primary sources

• RFC 8391: XMSS
• RFC 8554: Leighton-Micali Hash-Based Signatures
• NIST SP 800-208: Stateful Hash-Based Signature Schemes
• XMSS - A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions
• Leighton and Micali: hash-based signature patent
• NIST SP 800-208: full recommendation