up:: The New Standards MOC

Stateful Hash-Based Signatures (XMSS - LMS)

Stateful hash-based signatures are a pair of quantum-safe digital signature schemes, LMS and XMSS, whose security rests only on the strength of a hash function, the oldest and most conservative assumption in cryptography. NIST standardized them in SP 800-208 in October 2020, ahead of the main lattice-based competition. The defining catch is in the name: they are stateful. Each private key can produce only a fixed number of signatures, and the signer must track which single-use keys have been spent, because signing twice with the same one-time key lets an attacker forge signatures at will. That hazard is why LMS and XMSS are reserved for low-volume, long-lived signing like firmware and software signing, where CNSA 2.0 approves them, while the stateless SLH-DSA is the general-purpose hash-based choice.

The short version:

1. LMS (Leighton-Micali Signature) and XMSS (eXtended Merkle Signature Scheme) are post-quantum signature schemes built entirely from hash functions, so a quantum computer running Shor’s algorithm doesn’t touch them.
2. NIST approved them in SP 800-208 (October 2020), roughly four years before the lattice signatures were finalized, which makes them the earliest standardized post-quantum signatures.
3. They are stateful: a key can sign only a fixed number of times (set when the key is generated), and the signer must remember which one-time keys are used up.
4. Reusing a single one-time key, from a restored backup, a cloned virtual machine, or a synchronization slip, lets an attacker forge arbitrary signatures. That’s the whole risk, and it’s why SP 800-208 requires signing to happen inside hardware.
5. Use them for firmware and software signing, roots of trust, and other slow, controlled, long-lived signing. For everything general-purpose, reach for the stateless SLH-DSA instead.

Picture a numbered pad of one-time wax seals with a logbook clipped to it. Each seal presses exactly one document, then you cross its number off in the log, because pressing the same seal on two different letters would leak enough of its shape for a forger to carve a copy. As long as the log is perfect, the system is unbreakable.

The danger is entirely in the bookkeeping. Restore an old copy of the pad from a drawer, or hand a duplicate to a second office, and now two people can press seal number 41 on two different letters, and the whole pad is compromised. Stateful hash-based signatures are the mathematical version of that pad. The security is superb, the math is the most trusted in the field, and the single thing that can go wrong is losing track of which seal you’ve already used.

What are stateful hash-based signatures?

Stateful hash-based signatures are digital signature schemes whose entire security reduces to a hash function, and whose private key carries a piece of changing internal state that records which portions of the key have been used. The two NIST-approved members are LMS and XMSS, each with a multi-tree variant that stacks trees to reach higher signing capacity:

1. LMS (Leighton-Micali Signature), and its multi-tree form HSS (Hierarchical Signature System).
2. XMSS (eXtended Merkle Signature Scheme), and its multi-tree form XMSS^MT (multi-tree XMSS).

They belong to hash-based cryptography, the same conservative family as the stateless SLH-DSA. What sets this branch apart is the statefulness. Under the hood, a hash-based signature is built from many one-time signature keys, each safe to use for exactly one message, whose public keys are hashed together pair by pair into a single Merkle-tree root that becomes the long-term public key. Because each leaf of that tree is a one-time key, the signer has to walk through them in order and never revisit one, and the “state” is precisely the counter tracking how far through the tree it has gone.

NIST specifies exactly which parameter sets are approved, all using SHA-256 or SHAKE256 with 192-bit or 256-bit outputs. LMS and XMSS were the first post-quantum signature schemes NIST put its name to, and the choice to standardize them early reflects how much confidence the field has in hash-based security.

Source: NIST, “Recommendation for Stateful Hash-Based Signature Schemes,” SP 800-208, October 2020, NIST SP 800-208.

How do LMS and XMSS work?

Both schemes are built in the same two layers, and the mechanism is worth understanding because it’s what forces the statefulness. Start at the bottom and build up:

1. One-time signature keys. The base building block is a one-time signature (LMS uses LM-OTS, XMSS uses WOTS+). Each such key is a bundle of secret random values whose hashes form the public key, and signing a message reveals a specific subset of those secrets chosen by the message digest. A verifier re-hashes the revealed secrets to confirm the match. The key is safe for one message only, because a second signature under it exposes more of the secret structure.
2. The Merkle tree. Publishing a separate public key per message would be unworkable, so many one-time public keys are hashed together, pair by pair, up to a single root. That root is the long-term public key, small and stable, that vouches for the entire batch of one-time keys beneath it.
3. A signature. To sign, the scheme takes the next unused one-time key, produces its one-time signature, and attaches the short authentication path of sibling hashes a verifier needs to recompute the root. If the recomputed root matches the published public key, the signature is valid.
4. The state update. After using leaf number N, the signer must advance its counter so the next signature uses leaf N+1 and never N again. That counter is the state, and keeping it correct is the entire operational burden.

Multi-tree variants (HSS and XMSS^MT) chain trees together: a top tree’s one-time keys sign the roots of lower trees, and only the lowest trees sign actual messages. That’s how the schemes reach large signing capacities without one impractically tall tree. Everything in the construction is a hash, which is why Shor’s algorithm finds no algebraic structure to attack.

Source: R. Housley, “Leighton-Micali Hash-Based Signatures,” RFC 8554, April 2019, RFC 8554.

A. Huelsing et al., “XMSS: eXtended Merkle Signature Scheme,” RFC 8391, May 2018, RFC 8391.

What is the state, and why is it dangerous?

The state is the record of which one-time keys a private key has already spent, and it’s dangerous because a single duplicated use collapses the scheme’s security completely. The RFCs are blunt about it: the secret key changes over time, and if a secret key state is used twice, no cryptographic security guarantees remain. Reusing one one-time key on two different messages exposes enough of the underlying secrets that an attacker can forge signatures on arbitrary messages of their choosing. This is a total break, not a gradual weakening.

What makes the hazard sharp is that the ways to duplicate state are all ordinary IT operations that feel harmless:

1. Restoring from a backup. Roll a signing server back to last night’s snapshot and it resumes at a counter value it already passed, re-spending keys it used during the day.
2. Cloning a virtual machine or container. Two clones inherit the same counter and independently sign from the same position.
3. Syncing or load-balancing across nodes. Two instances that share a key but not a perfectly synchronized counter will eventually collide on a leaf.
4. Copying a key for redundancy. Any straightforward “make a spare copy of the private key” instinct reintroduces the exact reuse it was meant to guard against.

Because of this, SP 800-208 imposes an unusual conformance requirement for a signature standard: key and signature generation must be performed inside hardware cryptographic modules that never allow the secret keying material to be exported, even in encrypted form. The hardware boundary is what makes the “just copy the key” mistakes structurally impossible. A software-only LMS or XMSS deployment is out of compliance with the standard for exactly this reason, and it’s the single most common misunderstanding teams have about these schemes.

Source: NIST, “Recommendation for Stateful Hash-Based Signature Schemes,” SP 800-208, §1.2 and §8, October 2020, NIST SP 800-208.

How many times can one key sign?

A stateful key can sign a fixed number of times set when the key is generated, and once those signatures are exhausted the key pair is retired permanently. The number is determined by the tree height, and the approved parameter sets span a wide range:

Scheme	Approved capacity per key	Determined by
LMS (single tree)	2^5 to 2^25 signatures (32 up to about 33.5 million)	Tree height H of 5, 10, 15, 20, or 25
XMSS (single tree)	2^10, 2^16, or 2^20 signatures	Tree heights of 10, 16, or 20
HSS / XMSS^MT (multi-tree)	Up to 2^60 signatures	Total multi-tree height up to 60

The tradeoff is that a taller tree signs more times but costs more to generate and produces a slightly larger signature, so you size the tree to the job. For firmware signing, where a device might receive a handful of updates a year across a decade-long service life, even a modest tree has enormous headroom. The point of these numbers is planning: because the capacity is finite, an organization has to know roughly how many signatures a key will ever need before it generates it, which is a natural fit for low-volume signing and a poor fit for anything high-throughput.

Source: NIST, “Recommendation for Stateful Hash-Based Signature Schemes,” SP 800-208, Tables 2, 10, and 11, October 2020, NIST SP 800-208.

When should I use LMS/XMSS instead of SLH-DSA?

Reach for stateful LMS or XMSS when three conditions all hold: the signing volume is low and predictable, the environment can guarantee the state is never duplicated (typically an HSM), and you want the smaller signatures the stateful schemes give you. Reach for the stateless SLH-DSA when you want the same hash-based conservatism without carrying the state-management burden, and you can absorb its larger signatures. Both are current NIST standards aimed at different jobs.

The comparison across the hash-based portfolio, and against the stateless option, is the decision most teams actually face:

Property	LMS	XMSS	SLH-DSA
Standard	SP 800-208, RFC 8554	SP 800-208, RFC 8391	FIPS 205
Stateful?	Yes	Yes	No (stateless)
Key-reuse footgun	Reuse breaks security	Reuse breaks security	None
Signature size	Compact	Compact	Large (about 8 to 50 KB)
Signing hardware	Required by SP 800-208	Required by SP 800-208	Not required
Main use	Firmware and software signing	Firmware and software signing	General-purpose conservative signing

The practical rule most programs land on: if the signing lives inside a hardware module that can rigorously manage state, and the volume is low and long-lived, the compact stateful schemes are excellent. Everywhere else, the freedom from a reuse footgun makes stateless SLH-DSA the safer default, and its size cost is the price of removing the sharpest operational edge. The two are complementary tools in the hash-based branch, picked by whether you can manage state, and neither one does key establishment, which stays the job of ML-KEM.

Where are stateful hash-based signatures approved for use?

The clearest guidance comes from CNSA 2.0, which names LMS and XMSS specifically for signing software and firmware in national security systems, rather than for general-purpose use. The reasoning fits everything above: firmware and software updates are signed infrequently by a controlled signing authority, they must stay verifiable for the many years or decades a device stays in the field, and that long-lived trust is exactly where the maximum-confidence hash-based foundation earns its keep. CNSA 2.0 goes further and reminds implementers that LMS and XMSS only stay secure if they meet all of SP 800-208, including managing signing state and performing the signing in hardware.

This is why the schemes show up first in the boot and firmware world. A secure-boot chain or a constrained device that will receive updates for a decade needs signatures that outlive the arrival of a quantum computer, gets them rarely, and can host its signing key inside a hardware module. That profile matches stateful hash-based signing almost perfectly, and it’s a poor match for high-volume, latency-sensitive surfaces like TLS, where the general-purpose lattice signature ML-DSA fits better.

Source: NSA, “Announcing the Commercial National Security Algorithm Suite 2.0,” September 2022, CNSA 2.0.

Common misconceptions

1. “LMS and XMSS are a drop-in signing swap.” They carry a hard requirement most signature schemes don’t: to stay secure and compliant they must meet all of SP 800-208, including state management and signing performed in hardware. A software-only implementation is out of compliance and unsafe.
2. “Stateless SLH-DSA replaced the stateful schemes.” All three are current NIST standards for different jobs. The stateful schemes stay in the toolkit precisely because they’re far more compact, which is what firmware signing wants when the signer can manage state safely.
3. “Reusing a key just weakens it a bit.” Signing two different messages with the same one-time key is a complete break: it exposes enough structure to forge arbitrary signatures. There’s no graceful degradation, which is the entire reason state management is treated so seriously.
4. “A key can sign forever.” Each key has a fixed, finite signing capacity set at generation by the tree height, from as few as 32 signatures up to 2^60 for the largest multi-tree sets. Once exhausted, the key is retired.
5. “Hash-based signing can also do key exchange.” This family signs and only signs. There’s no hash-based key-establishment mechanism, so confidentiality stays with ML-KEM.
6. “They’re newer and less proven than the lattice schemes.” They were standardized earlier, in 2020, and rest on the oldest and best-studied assumption in cryptography. The reason they aren’t the general-purpose default is the operational state burden, not any weakness in the security.

Questions people ask

Are LMS and XMSS finalized standards? Yes. NIST approved both in SP 800-208, published October 2020, which makes them the first standardized post-quantum signature schemes, ahead of the lattice-based ML-DSA and the stateless SLH-DSA finalized in August 2024.

What is the difference between LMS and XMSS? They’re closely related hash-based designs with different internal details, LMS built on LM-OTS and XMSS on WOTS+, and different standards bodies behind them (LMS in RFC 8554, XMSS in RFC 8391), both approved in SP 800-208. In practice the choice usually follows what your hardware vendor supports, since both deliver the same security model and the same state-management requirement.

Why do I have to sign in hardware? SP 800-208 requires it because hardware modules that never export the private key make the “restore a backup” and “copy the key” mistakes structurally impossible, which is the only reliable way to guarantee a one-time key is never reused. A software key sitting in a file is trivially cloned, and a single clone can lead to catastrophic reuse.

What happens if I do reuse a key? An attacker who sees two signatures made with the same one-time key can recover enough of the secret material to forge signatures on messages of their choosing. It’s a total compromise of that key, so the standard and the RFCs are built around preventing it rather than recovering from it.

Should most organizations use these or SLH-DSA? For general-purpose signing, the stateless SLH-DSA is usually the safer choice because it removes the state footgun entirely. LMS and XMSS make sense for firmware and software signing done inside an HSM, where the volume is low, the trust is long-lived, and their compact signatures are worth the discipline.

Do these change my key exchange? No. Stateful hash-based signatures do signatures only. Key establishment moves separately to ML-KEM, so a full post-quantum migration handles signing and key exchange as two different problems.

How many signatures can one key make? A fixed number set at key generation by the tree height: from 2^5 (32) up to 2^25 for single-tree LMS, 2^10 to 2^20 for single-tree XMSS, and up to 2^60 for the multi-tree HSS and XMSS^MT variants. You size the tree to the expected lifetime signing volume.

---

Everything here is the map, given freely. When your team needs to decide where LMS, XMSS, and SLH-DSA actually belong across your firmware, boot chains, and signing estate, that’s the work I do. Request an alignment briefing.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.