NIST SP 800-208, "Recommendation for Stateful Hash-Based Signature Schemes," approves two families of post-quantum digital signatures: LMS and its hierarchical variant HSS (RFC 8554), and XMSS and its multi-tree variant XMSS^MT (RFC 8391). Their quantum resistance comes entirely from the security of the underlying hash function — there is no factoring or discrete-log assumption for Shor's algorithm to attack. That gives them unusually well-understood, conservative security, which is why they were standardized years ahead of the lattice-based signature schemes.
Why it matters
Stateful HBS filled a gap that mattered for one specific, high-stakes problem: signing the firmware and software that will still be running — and still needs to verify — a decade or more from now. A signature you generate today with RSA or ECDSA can be forged once a cryptographically relevant quantum computer exists; a boot loader or update chain that trusts it inherits that risk. Because their assurance rests on hashing alone, LMS and XMSS were a defensible answer before the stateless standards matured. NSA's CNSA 2.0 approves LMS and XMSS specifically for code and firmware signing, which is why they appear in national-security supply-chain requirements today.
What makes them stateful
A stateful HBS key is a fixed collection of one-time signing keys, and each one may be used to sign exactly once. The signer must persist state that records which one-time keys are already spent and never reuse one. This is the defining property of the scheme and the reason its approved use is deliberately narrow:
- State management is mandatory and non-optional — the private key mutates on every signature, unlike any classical scheme where the key is static.
- A single one-time-key reuse can be catastrophic: reusing a key can leak enough information to enable existential signature forgery.
- The number of signatures a key can ever produce is bounded and fixed at key-generation time (the tree height), so capacity must be planned up front.
- Approved settings are firmware/software signing and similar low-volume, disciplined-signer environments — not general-purpose signing, where the stateless SLH-DSA (FIPS 205) removes the state burden entirely.
State reuse is an operational failure, not a cryptographic one
The dangerous reuse rarely comes from a coding bug — it comes from infrastructure. A VM snapshot or backup rollback that restores an earlier signing state, or a clustered/duplicated signer where two instances share one key, will silently reuse one-time keys and open the door to forgery. Mitigate with hardware-enforced state (HSM-managed counters), hierarchical schemes (HSS, XMSS^MT) that isolate reservoirs of one-time keys, and an ironclad rule that a signing key is never copied.
How quantakrypto helps
The hard part of stateful HBS is never the mathematics — it is proving that state can never be duplicated across the real backup, clustering, and disaster-recovery topology you actually run. We inventory where long-lived signing keys live and how their state is persisted (audit), plan and stage the move to LMS/HSS or XMSS/XMSS^MT for firmware and code signing without a reuse window (migration), and verify that the deployed signer enforces single-use state under snapshot, failover, and rollback — the exact conditions that break it (certification).
Frequently asked questions
Why is SP 800-208 restricted to firmware and software signing?
Because the schemes are stateful. Every one-time key may sign only once, and a single reuse can enable forgery, so approved use is limited to settings with a bounded signature count and a disciplined, controlled signer — firmware and software signing being the canonical example. General-purpose, high-volume signing is not an approved use; FIPS 205 SLH-DSA is the stateless alternative for that.
What is the difference between stateful HBS and stateless SLH-DSA?
Both are hash-based and post-quantum. SP 800-208's LMS/HSS and XMSS/XMSS^MT are stateful: the signer must track spent one-time keys and never reuse one. FIPS 205 SLH-DSA is stateless — it carries no reuse hazard and needs no state management — at the cost of larger signatures and slower signing. Choose stateful HBS for controlled firmware signing and SLH-DSA when state management is impractical.
What actually happens if a one-time key is reused?
Reusing a one-time key can reveal enough of the underlying one-time signature structure to let an attacker forge signatures on messages the legitimate signer never approved. In practice this is triggered operationally — a restored backup, a rolled-back VM snapshot, or a duplicated signer sharing one key — rather than by the algorithm itself, which is why state persistence and non-duplication are the security-critical controls.
Does CNSA 2.0 allow LMS and XMSS?
Yes. NSA's CNSA 2.0 approves LMS and XMSS for software and firmware signing, consistent with SP 800-208's intended use. For national-security systems doing code/firmware signing, stateful HBS is an accepted post-quantum option alongside the broader CNSA 2.0 algorithm set.
Work with us on SP 800-208 (stateful HBS)
Related reading
References
- NIST: SP 800-208 — Recommendation for Stateful Hash-Based Signature Schemes (the normative approval of LMS/HSS and XMSS/XMSS^MT and their usage constraints).
- IETF: RFC 8554 — Leighton-Micali Hash-Based Signatures (LMS/HSS).
- IETF: RFC 8391 — XMSS: eXtended Merkle Signature Scheme (XMSS/XMSS^MT).