LMS: Hash-Based Stateful Signatures Explained

What Makes LMS Different from Every Other Signature Algorithm

Every digital signature algorithm you have probably heard of works the same basic way: you generate a key pair, and you can use that key pair to sign as many things as you want, forever. RSA works this way. Ed25519 works this way. ML-DSA, the primary post-quantum signature standard, works this way. You generate the key once, and it never wears out.

LMS (Leighton-Micali Signatures) is fundamentally different. It is stateful. Every time you create a signature, you use up one "slot" in the key. The key has a fixed number of slots (determined when the key is created), and once they are all used, the key is permanently exhausted. You cannot sign anything else with it. It is like a book of tickets: tear one out each time you sign, and when the book is empty, it is done.

This sounds like a serious limitation, and it is. So why would anyone choose a signature algorithm with an expiration counter? Because LMS has the most conservative security guarantee in all of post-quantum cryptography: its safety depends only on SHA-256 being a secure hash function. Nothing else. No lattice math. No number theory. No error-correcting codes. No algebraic structure of any kind. Just hashing.

That guarantee is so strong that the NSA's CNSA 2.0 suite (the algorithm requirements for U.S. national security systems) specifically requires LMS or its relative XMSS for firmware signing and code signing. When you are signing the bootloader that starts a nuclear submarine's navigation computer, you want the most conservative security guarantee available, even if it means keeping track of a counter.

The One-Time Pad Analogy

To understand why stateful signatures work, it helps to think about one-time pads. A one-time pad is an encryption method where you use a random key that is exactly as long as the message, and you never reuse any part of the key. A one-time pad provides perfect, mathematically provable secrecy. It is literally unbreakable, not just hard to break, but information-theoretically impossible to break. The tradeoff is that you need to generate, distribute, and track a key as long as every message you will ever send, and you can never reuse any portion of it.

LMS follows a similar philosophy. Each individual signature uses a one-time signature (OTS) key that is used exactly once and then discarded. Because each OTS key is only used once, the security proof is extremely simple and relies on minimal assumptions. The tradeoff, just like with one-time pads, is state management: you must track which OTS keys have been used and never reuse one.

How Merkle Trees Make One-Time Signatures Practical

The concept of one-time signatures has been known since 1979, when Leslie Lamport proposed the first OTS scheme. The idea is simple: start with a secret value, hash it, and publish the hash as your public key. To sign a "0" bit, reveal one pre-image; to sign a "1" bit, reveal a different pre-image. Anyone can verify by hashing the revealed values and checking against the published hash. But each secret can only be revealed once; reveal it twice for different messages, and an attacker can mix and match the revealed values to forge signatures on new messages.

The problem with plain one-time signatures is that you need a new public key for every single signature. If you want to sign 1,000 documents, you need to distribute 1,000 public keys in advance. This is impractical.

Ralph Merkle solved this problem in 1979 with the Merkle tree (also called a hash tree). A Merkle tree is a binary tree where each leaf contains the hash of an OTS public key, and each internal node contains the hash of its two children. The root of the tree is a single hash value that represents all the OTS keys simultaneously.

Here is how it works in LMS:

1. Key generation: Generate a large number of OTS keypairs (one for each leaf in the tree). Hash each OTS public key to form the leaves. Build the tree by hashing pairs of nodes up to the root. The root hash is your public key. This single value is what you distribute to verifiers.
2. Signing: To sign a message, pick the next unused leaf. Sign the message with that leaf's OTS key. Include the "authentication path" in the signature: the sequence of sibling hashes from that leaf up to the root. The authentication path allows anyone to verify that the OTS key belongs to the tree.
3. Verification: The verifier checks the OTS signature against the leaf's OTS public key, then hashes up the authentication path to the root. If the computed root matches the known public key, the signature is valid. This proves that the OTS key was part of the tree, and the OTS signature proves the message is authentic.
4. State update: Mark that leaf as used. Move to the next leaf for the next signature. Never go back.

The beauty of this construction is that a single, short public key (the root hash, just 32 bytes for SHA-256) can authenticate thousands or millions of individual one-time signatures. The security proof is straightforward: if SHA-256 is secure (meaning you cannot find collisions or pre-images), then no one can forge a valid authentication path, and therefore no one can forge a signature.

Why "Hash-Only" Security Matters

Every other post-quantum signature algorithm relies on a mathematical assumption that could, in principle, be broken by a future algorithm or mathematical insight:

• ML-DSA relies on the hardness of the Module Learning With Errors (MLWE) problem. Lattice problems have been studied since the late 1990s, but they are relatively new to cryptography compared to hash functions.
• FN-DSA relies on the hardness of the NTRU problem. NTRU has been studied since 1996, which is solid, but it is still an algebraic assumption.
• SLH-DSA is also hash-based, but it uses a more complex stateless construction (hypertrees, FORS, WOTS+ chaining) that results in much larger signatures (17-50 KB vs 2.5-5 KB for LMS).

LMS strips the problem down to its absolute minimum. The security proof goes roughly like this: if you can forge an LMS signature, then you can either find a SHA-256 collision (two inputs that hash to the same output) or find a SHA-256 pre-image (an input that hashes to a specific target output). Both of these are believed to be computationally infeasible. Grover's algorithm on a quantum computer provides only a quadratic speedup against hash functions, reducing SHA-256 from 256-bit to 128-bit security, which is still extremely strong.

This is why the NSA's CNSA 2.0 (Commercial National Security Algorithm Suite) specifically requires LMS or XMSS (a closely related stateful hash-based scheme) for firmware and code signing. The NSA's position is: for the things that matter most (the code that boots your secure systems, the firmware that runs your hardware), use the algorithm with the absolute minimum number of assumptions.

The Critical Danger: State Reuse

There is one thing that can break LMS security completely, and it has nothing to do with math or quantum computers. It is an operational mistake: reusing a one-time signature leaf.

Here is the scenario. You have an LMS key. You back it up. You then sign 5 documents, advancing the leaf counter from position 100 to position 105. Now you restore from the backup. The backup thinks the counter is still at 100. The next 5 signatures will reuse leaves 100 through 104.

When an attacker observes two different signatures from the same OTS leaf (signed over two different messages), they can combine information from both signatures to recover the OTS private key for that leaf. With the OTS private key, they can forge signatures for any message using that leaf. This is not a theoretical concern; it is a direct, practical attack described in RFC 8554 Section 9.1 and SP 800-208 Section 6.

This is the fundamental tradeoff of stateful signatures: you get the strongest possible security guarantee, but you must be absolutely disciplined about state management. Specifically:

• Never restore an LMS key from backup if any signatures have been created since the backup was made.
• Never copy an LMS key to a second machine and use it from both machines.
• Never use LMS in a cluster where multiple instances might sign with the same key simultaneously, unless you have a robust distributed state coordination mechanism.
• Always persist the updated state to durable storage before returning the signature to the caller.

QNSQY handles state management with atomic updates. After every signature, the key file is updated on disk before the signature is returned. The implementation follows this sequence:

1. Read the current leaf index from the key file.
2. Increment the index and write the updated state to a temporary file.
3. Call fsync on the temporary file to ensure it is fully written to disk.
4. Atomically rename the temporary file over the original key file.
5. Only then compute and return the signature.

This write-then-rename pattern guarantees that no partial writes or power failures can cause leaf reuse. If the process crashes after step 4, the leaf is consumed but no signature is emitted (safe; the leaf is "wasted" but not reused). If it crashes before step 4, the old state is intact and the leaf is still available (also safe).

Real-World Deployment: Firmware and Bootloaders

The most natural use case for LMS is signing firmware, bootloaders, and software updates. These are situations where you know in advance roughly how many signatures you will need over the key's lifetime, and the consequences of a forged signature are catastrophic.

Consider a hardware manufacturer that ships a router with a secure boot process. The router checks a digital signature on its firmware every time it starts up. If an attacker can forge that signature, they can replace the firmware with malicious code that intercepts all network traffic, installs backdoors, or recruits the router into a botnet. This is not hypothetical; firmware attacks on network equipment have been documented by multiple security research teams and government agencies.

The manufacturer might release firmware updates once a month for a 10-year product lifecycle. That is approximately 120 signatures. An LMS key with a tree height of 10 (1,024 leaves) provides more than eight times the needed capacity. The hash-only security guarantee means that even if lattice-based cryptography is completely broken in 2035, the firmware signatures remain valid and unforgeable. For critical infrastructure, this assurance is worth the state management overhead.

The CNSA 2.0 guidance from the NSA recognizes this explicitly. It requires LMS or XMSS for firmware and software signing in national security systems because these are exactly the situations where the strongest possible security guarantee matters most, and the bounded signature count is acceptable.

LMS vs XMSS: Two Stateful Cousins

NIST SP 800-208 standardizes two stateful hash-based signature schemes: LMS and XMSS. Both use Merkle trees over one-time signatures. Both have hash-only security. Both have the same critical state management requirement. The differences are in the details:

Property	LMS (RFC 8554)	XMSS (RFC 8391)
OTS scheme	LM-OTS (Leighton-Micali OTS)	WOTS+ (Winternitz OTS Plus)
Multi-tree support	HSS (Hierarchical Signature System)	XMSS-MT (Multi-Tree)
Hash function	SHA-256	SHA-256 or SHAKE256
Implementation complexity	Simpler	Slightly more complex
Adoption	More widely deployed in practice	Strong academic backing

For most practical purposes, LMS and XMSS provide equivalent security and comparable performance. LMS is somewhat simpler to implement and has seen broader industry adoption. Both are accepted under CNSA 2.0.

Parameter Sets and Capacity Planning

When you create an LMS key, you choose a tree height that determines how many signatures the key can produce. This is a permanent, irrevocable choice. QNSQY supports four parameter sets:

Parameter	Tree Height	Max Signatures	Typical Use Case
lms-sha256-h5-w1	5	32	Testing, small key sets
lms-sha256-h10-w2	10	1,024	Document signing
lms-sha256-h15-w4	15	32,768	Code signing, CI/CD pipelines
lms-sha256-h20-w8	20	1,048,576	Long-term CA use, high-volume firmware

The tree height h gives 2^h leaves. A height-20 tree provides just over one million signatures. If you sign 100 firmware images per day, that key will last about 28 years. If you sign 1,000 per day, it lasts about 2.8 years. Plan accordingly.

The w parameter (Winternitz parameter) controls a tradeoff within each one-time signature. Higher w values produce smaller signatures but require more hash computations during signing and verification. Lower w values are faster but produce larger signatures. For most applications, the default is fine.

Capacity planning is essential. Once you create an LMS key, you cannot change its tree height. If you underestimate how many signatures you will need, you will have to generate a new key and distribute a new public key to all verifiers, which is disruptive. It is better to overestimate by a comfortable margin. A height-15 tree (32,768 signatures) or height-20 tree (over 1 million signatures) provides generous capacity for most realistic deployment scenarios.

When to Use LMS vs ML-DSA

LMS is not a general-purpose replacement for ML-DSA. They are designed for different jobs:

Property	ML-DSA (FIPS 204)	LMS (SP 800-208)
Signature count	Unlimited	Limited (2h)
State management	None required	Critical (must track leaf index)
Security basis	Module lattice (MLWE)	Hash function only (SHA-256)
Primary use case	General-purpose signing	Firmware, code, and bootloader signing
CNSA 2.0 requirement	Approved for general use	Required for firmware and software signing
Signature size	2,420 - 4,627 bytes	~2,500 - 5,000 bytes (varies by parameters)

Use LMS when:

• You need the absolute most conservative security assumption: hash-only, zero algebraic structure.
• You are signing firmware, bootloaders, or software updates where the total signature count is bounded and predictable.
• Compliance requires NIST SP 800-208. CNSA 2.0 mandates LMS or XMSS for firmware and code signing.
• You can commit to rigorous state management and will never restore from backup or copy keys between machines.

Use ML-DSA when:

• You need unlimited signatures from a single key.
• You are signing documents, emails, API requests, or user-facing content at high volume.
• You do not want the operational complexity of tracking key state.
• General-purpose post-quantum signing is sufficient for your threat model.

Using LMS in QNSQY

LMS is available in the QNSQY Business tier. Generate an LMS keypair:

qnsqy keygen-sign -o lms-key -n "Firmware Signing" --algorithm lms-sha256-h10-w2

This creates a key with 1,024 available signatures (height 10). Sign a firmware binary:

qnsqy sign -i firmware.bin -k lms-key

After signing, the key file is atomically updated on disk. The leaf index advances by one. No additional command is needed; state management is handled automatically. If you attempt to sign after exhausting all leaves, QNSQY refuses with a clear error message rather than silently reusing a leaf.

Sources

1. NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes, October 2020
2. RFC 8554: Leighton-Micali Hash-Based Signatures, April 2019
3. RFC 8391: XMSS - eXtended Merkle Signature Scheme, May 2018
4. NSA CNSA 2.0: Commercial National Security Algorithm Suite 2.0, September 2022
5. SPHINCS+ / SLH-DSA Project Homepage (stateless hash-based contrast)
6. NIST FIPS 205: Stateless Hash-Based Digital Signature Standard (SLH-DSA), August 2024

Related Articles

• ML-DSA vs SLH-DSA: Which to Choose
• Post-Quantum Cryptography for Government and Defense
• NIST FIPS 203/204/205: The Complete Guide