Back to DashboardSoftware InfrastructureFoundationsadvanced40 min

Stateful Hash Signatures (LMS/XMSS)

Master hash-based digital signatures — LMS and XMSS standardized in NIST SP 800-208, with security based on hash function properties rather than new hardness assumptions.

Why this matters: LMS/XMSS require tracking signing state correctly, forever — reuse a one-time key by accident and the scheme's entire security guarantee is gone, exactly the operational risk SLH-DSA was designed to eliminate.

Start here: Pick an LMS parameter set in LMS Key Generation: the Merkle tree structure, key sizes and signing capacity for that tree height are drawn, and with Live WASM mode on you can generate the key and sign.

For your role

Developer / Engineer: Explore LMS parameter sets and Merkle-tree structure, compare XMSS with LMS at equal security, simulate signing, key exhaustion and state loss, then generate real SLH-DSA keys over PKCS#11 for comparison.
Security Architect: The state-loss simulation is the design constraint: a reused one-time key voids the scheme, which decides where these keys may live; the Haystack coalition step shows distributed key control.
Researcher / Academic: The parameter explorer, the XMSS-versus-LMS comparison at equal security levels, and the Haystack coalition construction are the material to reproduce; the LMS tool runs cross-engine verification.
Certification & Validation Engineer: Simulate signing, key exhaustion and state loss, then compare XMSS with LMS at equal security: state management is what a module signing under SP 800-208 has to get right.
IT Ops / DevOps: The exhaustion and state-loss simulation shows the operational failure mode: state must be tracked correctly, forever, and backups cannot restore it.

Practice in the Simulation

Why Stateful Hash-Based Signatures?

derive their security solely from the properties of cryptographic hash functions, which have a longer standardization history than lattice-based or code-based constructions. Unlike those schemes, they require no new hardness assumptions. LMS security rests on collision and second-preimage resistance; XMSS 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.”

— NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes (October 2020)

Minimal Assumptions

Security relies only on hash function properties — no lattices, no codes, no isogenies. Decades of cryptanalysis on SHA-256.

NIST Approved

SP 800-208 standardized LMS/HSS (RFC 8554) and XMSS/XMSS^MT (RFC 8391) for federal use before the main PQC competition concluded.

CNSA 2.0 Required

NSA CNSA 2.0 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 Merkle tree of one-time signature (OTS) 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.

Merkle Signature Tree (height = 3, 8 leaves)

Root (Public Key)

↓

H(0,1)

H(2,3)

↓

H(0)

H(1)

H(2)

H(3)

↓

OTS-0

OTS-1

OTS-2

OTS-3

OTS-4

OTS-5

OTS-6

OTS-7

Green = next available OTS key. Each leaf can only be used ONCE.

One-Time Signatures (OTS)

Each OTS key pair (e.g., Winternitz OTS+) can sign exactly one message. Reusing an OTS key leaks the private key, enabling forgeries.

Authentication Path

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.

How Winternitz Hash Chains Work — and Why Reuse is Catastrophic

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.

sk→H¹(sk)→H²(sk)→ … →H&sup7;(sk) = pk

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.

LMS (Single Tree)

• 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 (RFC 8554)

HSS (Multi-Level)

• 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

Winternitz Trade-off: W parameter

W=1Sign: FastestSize: Largest (~8.7 KB)Verify: Fastest

W=2Sign: FastSize: Large (~4.5 KB)Verify: Fast

W=4Sign: ModerateSize: Medium (~2.4 KB)Verify: Moderate

W=8Sign: SlowestSize: Smallest (~1.3 KB)Verify: Slowest

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.

SP 800-208 Operational Recommendation

NIST SP 800-208 recommends that key generation and signing be performed inside a FIPS 140-validated hardware cryptographic module with no private key export. HSMs 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.

LMS vs XMSS Comparison

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
Forward Security	No	Yes — past signatures stay secure even if current key is compromised
Adoption	NSA CNSA 2.0, broader industry	BSI (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.

Catastrophic Failure Mode

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.

State Must Be...

• 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

Mitigation Strategies

• 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

Stateful (LMS/XMSS) vs Stateless (SLH-DSA / SPHINCS+)

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.