Also mentioned
RSARSARivest, Shamir and AdlemanA widely used public-key algorithm for encryption and digital signatures whose security relies on the difficulty of factoring large numbers.Read the full entry, ECDSAECDSAElliptic Curve Digital Signature AlgorithmElliptic Curve Digital Signature Algorithm, a widely deployed signature scheme based on elliptic-curve cryptography, offering strong security with compact keys.Read the full entry, SLH-DSASLH-DSAStateless Hash-based Digital Signature AlgorithmStateless Hash-Based Digital Signature Algorithm, the NIST-standardized signature scheme derived from SPHINCS+ and specified in FIPS 205.Read the full entry, FIPSFIPSFederal Information Processing StandardFederal Information Processing Standards, publicly announced standards developed by NIST for use in U.S. government computer systems, including cryptographic algorithms and modules.Read the full entry, NISTNISTNational Institute of Standards and TechnologyThe U.S. National Institute of Standards and Technology, the agency that develops and publishes cryptographic standards, including the FIPS series and post-quantum algorithms.Read the full entry, CNSACNSACommercial National Security Algorithm SuiteThe Commercial National Security Algorithm Suite 2.0, the NSA's mandated algorithm set for US National Security Systems.Read the full entry are defined in the glossary.
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 need 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.
Proving the signer never reuses a one-time key
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, which are 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, with firmware and software signing 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, so 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, the eXtended Merkle Signature Scheme (XMSS/XMSS^MT).