Learn
0%
Build
0%

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 Stateful Hash-Based Signatures?

derive their security solely from the properties of cryptographic hash functions, which have a longer standardization history than or constructions. Unlike those 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)

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 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.

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., ) 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.

Learning module content can be inaccurate. Please double-check its information. Report inaccuracies in PQC Today GitHub Discussions.