Stateful Hash Signatures (LMS/XMSS)
Master hash-based digital signatures — the most conservative post-quantum signature schemes, standardized in NIST SP 800-208.
Why Stateful Hash-Based Signatures?
derive their security solely from the properties of cryptographic hash functions — the most conservative and well-understood assumption in cryptography. Unlike or schemes, they require no new hardness assumptions. security rests on collision and second-preimage resistance; has a tighter proof requiring only second-preimage resistance — a weaker assumption that provides a stronger theoretical guarantee.
“LMS, HSS, XMSS, and XMSS^MT are approved for use by federal agencies for the protection of sensitive information when implemented in accordance with this recommendation.”
— : Recommendation for Stateful Hash-Based Signature Schemes (October 2020)
Security relies only on hash function properties — no lattices, no codes, no isogenies. Decades of cryptanalysis on SHA-256.
SP 800-208 standardized LMS/HSS (RFC 8554) and XMSS/XMSS^MT (RFC 8391) for federal use before the main PQC competition concluded.
NSA mandates LMS/XMSS for firmware and software signing in national security systems, ahead of ML-DSA adoption. Phased timeline:
- • 2025: New software/firmware should support & prefer CNSA 2.0
- • 2030: All deployed NSS must use CNSA 2.0 signatures
- • 2033–35: Full quantum-resistant enforcement
Merkle Tree Signatures
The core idea is a of key pairs. Each leaf contains the hash of a unique OTS public key. The tree root is the overall public key. To sign, you use the next unused OTS leaf and provide an authentication path from that leaf to the root.
Green = next available OTS key. Each leaf can only be used ONCE.
Each OTS key pair (e.g., ) can sign exactly one message. Reusing an OTS key leaks the private key, enabling forgeries.
The signature includes the OTS signature plus the sibling hashes needed to recompute the path from the used leaf to the root. Verifiers check that the path produces the known root.
Each OTS secret key is a set of random values. To sign, each value is hashed a number of times based on the message digest — revealing an intermediate chain value. The public key is the fully hashed end of each chain.
Signing message A reveals H³(sk); signing message B (different digit) reveals H&sup5;(sk). An attacker who sees both can compute the full chain and forge arbitrary messages — this is why OTS reuse is a complete break, not a partial leak. The checksum field prevents attackers from simply “advancing” the chain to forge messages with higher digit values.
LMS / HSS
The Leighton-Micali Signature Scheme (LMS) is defined in RFC 8554. It uses a single Merkle tree with LM-OTS (Leighton-Micali OTS) at the leaves. The Hierarchical Signature System (HSS) extends LMS with multiple levels of trees, where each non-leaf tree signs the root of the tree below it.
- • Tree heights: H = 5, 10, 15, 20, 25
- • Winternitz parameter: W = 1, 2, 4, 8
- • Max signatures = 2^H (32 to 33M)
- • Small public key: 56 bytes
- • Signature size: 1.3 – 9.3 KB depending on H, W
- • Up to 8 levels of LMS trees
- • Max signatures = 2^(H1 + H2 + ... + Hn)
- • Top-level tree signs sub-tree roots
- • Enables huge signing capacity
- • 2-level HSS with H10 trees = 2^20 = 1M sigs
Security note: W has zero impact on security level. It only controls the size / speed trade-off. Security is determined by the hash function and n (hash output length), not by W.
NIST SP 800-208 originally required that key generation and signing be performed inside a hardware cryptographic module with no private key export. with atomic state management are therefore not merely a best-practice — they are the basis of the standard’s security model.
XMSS / XMSS^MT
The eXtended Merkle Signature Scheme (XMSS) is defined in RFC 8391. It shares the same Merkle tree approach as LMS but adds features like a bitmask-based tree hash construction (for multi-target attack resistance) and a different OTS scheme (WOTS+). XMSS^MT is the multi-tree variant, analogous to HSS.
| Feature | LMS / HSS | XMSS / XMSS^MT |
|---|---|---|
| Standard | RFC 8554, NIST SP 800-208 | RFC 8391, NIST SP 800-208 |
| Tree Hash | Simple iterative | Bitmask-based (multi-target resistant) |
| Implementation | Simpler, fewer parameters | More complex, stronger security proof |
| Key Generation | Fast | Slower (bitmask computation) |
| Signature Size | Slightly larger | Slightly smaller at same tree height |
| No | Yes — past signatures stay secure even if current key is compromised | |
| Adoption | NSA CNSA 2.0, broader industry | (Germany), European preference |
XMSS internals: Two key constructions distinguish XMSS from LMS. An L-tree compresses the WOTS+ public key (up to 67 hash values) into a single leaf via an unbalanced binary tree. RAND_HASH randomizes each internal node by XOR’ing inputs with PRF-derived bitmasks before hashing, providing domain separation and multi-target attack resistance. These add ~4× the hash computations of LMS but yield the tighter second-preimage-only security proof.
Both LMS and XMSS are approved by NIST SP 800-208. Regulatory preference: NSA CNSA 2.0 favors LMS/HSS; BSI guidelines favor XMSS/XMSS^MT.
The State Problem
The critical operational challenge with stateful schemes is that the signer MUST track which OTS keys have been used. Each leaf index can be used exactly once. If state is lost, reset, or duplicated, the same OTS key may be used twice — completely breaking the signature scheme.
If a one-time signature key is reused (signing two different messages with the same leaf), an attacker can compute enough of the OTS private key to forge arbitrary signatures. This is not a theoretical weakness — it is a complete break of the scheme. There is no recovery; the entire key must be revoked.
- • Persisted to non-volatile storage before signing
- • Atomic — counter update and sign are one operation
- • Never cloned — VM snapshots, backups are dangerous
- • Never rolled back — no restoring from backup
- • Use HSMs with built-in monotonic counters
- • Reserve leaf ranges (batch allocation)
- • Write-ahead logging for state updates
- • Dedicated signing servers with no VM snapshots
| Property | LMS / XMSS | SLH-DSA (FIPS 205) |
|---|---|---|
| State required | Yes — monotonic counter | No — fully stateless |
| Signature size | Small (1.3 – 9 KB) | Large (8 – 49 KB) |
| Signing speed | Fast | Slow (many hash rounds) |
| Max signatures | Bounded by 2^H (plan ahead) | Effectively unlimited |
| CNSA 2.0 | Required for firmware/software | Not included in CNSA 2.0 |
| Best for | Firmware, code signing, secure boot (controlled) | TLS, general-purpose, distributed signing |
LMS/XMSS and SLH-DSA are complementary, not competing. Stateful schemes win on size and speed in controlled environments; SLH-DSA wins wherever state management is impractical.
Related Resources
Explore LMS and XMSS key generation, compare parameter sets, and simulate state management.