# NIST SP 800-208: Stateful Hash Signatures (LMS, XMSS) **Source**: https://quantumsequrity.com/blog/nist-sp-800-208-stateful **Category**: Standards --- [← Back to Blog](../../blog) Standards # NIST SP 800-208: Stateful Hash Signatures (LMS, XMSS) 8 min read NIST SP 800-208, "Recommendation for Stateful Hash-Based Signature Schemes", was published in October 2020, four years before the FIPS post-quantum standards. Stateful hash-based signatures are not new: the Leighton-Micali construction dates to the mid-1990s and XMSS was published in 2011. Both rely only on the security of hash functions, which is why NIST approved them early for uses that need quantum-resistant signatures soon. This walkthrough covers what SP 800-208 approves, why state is the central hazard, and the strict conformance rules most readers miss. ## Scope SP 800-208 specifies profiles of four schemes for US federal use: LMS and its multi-tree form HSS (from RFC 8554), and XMSS and its multi-tree form XMSS^MT (from RFC 8391). It approves some, but not all, of the parameter sets in those RFCs and defines some new ones. They sit alongside ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) as NIST-approved quantum-resistant signatures, with a much narrower intended use. ## Intended Applications SP 800-208 says stateful hash-based schemes are not suitable for general use, because they require careful state management that is often difficult to assure. It describes the intended applications as those where: 1. a digital signature scheme must be implemented in the near future, 2. the implementation will have a long lifetime, and 3. it would not be practical to move to a different signature scheme once deployed. Its example is authenticating firmware updates for constrained devices that will be in use for decades. NSA's CNSA 2.0 likewise names LMS and XMSS for software and firmware signing. ## Approved Parameter Sets The approved parameter sets use 192-bit or 256-bit outputs with either SHA-256 or SHAKE256. For LMS, SP 800-208 has sections for SHA-256, SHA-256/192, SHAKE256/256 and SHAKE256/192; XMSS and XMSS^MT have the same four families. For LMS with SHA-256 and 32-byte outputs, the tree heights are 5, 10, 15, 20 and 25, so a single tree supports 2^5 (32) to 2^25 (about 33.5 million) signatures. The one-time signatures underneath (LM-OTS) come with Winternitz parameters w = 1, 2, 4 and 8, which trade signature size against signing and verification time. Once every leaf of a tree has been used, the key is exhausted and must not sign again. HSS stacks LMS trees: a top-level tree signs the roots of lower trees, and only the bottom trees sign messages. This gives very large total capacity without one huge tree, at the cost of larger signatures, because a signature carries one LMS signature per level. XMSS^MT does the same for XMSS. ## Why State Is the Central Hazard An LMS or XMSS private key is a large set of one-time signature keys. If an attacker obtains signatures on two different messages made with the same one-time key, forging signatures on arbitrary messages becomes computationally feasible. The signer must therefore never reuse a leaf, across crashes, restores, clones and redundant signers. Restoring a key from an old backup, or running two copies of the same key, can silently reuse leaves. ## The Conformance Rules Section 8 of SP 800-208 is stricter than many implementers expect. For key generation and signature generation: - Implementations are validated only for use inside **hardware cryptographic modules**, validated to FIPS 140-2 or FIPS 140-3 **Level 3 or higher** physical security, with a non-modifiable or limited operational environment. - The module operates only in an approved mode, with no bypass mode. - The module must not allow **export of private keying material**, even in encrypted form. - The entropy source for its random bit generator must sit inside the module's physical boundary. - When it accepts a request to sign, the module must **increment the leaf index and store it in non-volatile storage before** it exports the signature or accepts another request, and it must never use a one-time key twice. Signature verification has no such hardware requirement. ## Running More Than One Signer Because private keys may not be exported, a conformant deployment cannot copy a key to a second device for redundancy. Section 7 of SP 800-208 describes two alternatives: create separate keys on different modules and configure verifiers to accept any of them, or create one HSS or XMSS^MT key whose lower-level trees are generated on different modules, each signed by the top-level tree. ## LMS or XMSS? Both rest on hash-function assumptions, and SP 800-208 approves both, together with their multi-tree forms. In practice the choice usually comes down to which one your libraries, hardware modules and protocols support. ## Signature Sizes Compared With ML-DSA LMS signature size depends mostly on the Winternitz parameter. For single-tree LMS with SHA-256 and 32-byte outputs, a signature is about 1.8 KB at height 20 with w = 8 and about 8.7 KB at height 5 with w = 1. ML-DSA signatures are 2,420 to 4,627 bytes. A single-tree LMS public key is only 56 bytes, and verification is fast, which suits devices that verify often and sign never. For very long-lived archives, LMS has the most conservative assumption (hash functions only); ML-DSA is stateless, far easier to operate, and more widely supported. ## How QNSQY Uses LMS QNSQY's Business plan offers LMS signatures with SHA-256 and four parameter sets, from tree height 5 with w = 1 to tree height 20 with w = 8. QNSQY saves the key state to disk durably (with fsync and an atomic rename) for every signature. QNSQY's LMS signing runs in software on a general-purpose computer, not inside a hardware cryptographic module, so it does not meet the SP 800-208 conformance requirements above, and QNSQY is not FIPS 140-3 validated. It is meant for teams that want hash-based signatures for their own files and archives, not as an SP 800-208 conformant signing service. For conformant firmware signing, use an HSM that implements LMS or XMSS under SP 800-208. The Free and Pro plans do not include LMS. For stateless signatures, QNSQY offers ML-DSA on every plan and SLH-DSA on Pro and Business. See our [LMS stateful signatures guide](lms-stateful-signatures) and [ML-DSA vs SLH-DSA](mldsa-vs-slhdsa). ## Frequently Asked Questions ### Why does NIST approve stateful signatures at all? Because they rely only on hash functions and were ready years before the FIPS post-quantum standards. SP 800-208 approves them for applications that need a quantum-resistant signature soon, will be in use for a long time, and cannot easily switch schemes later, such as firmware updates for long-lived devices. ### What happens if I reuse a leaf? An attacker who obtains signatures on two different messages from the same one-time key can feasibly forge signatures on arbitrary messages. Treat any reuse as a full compromise of the key. ### Can I implement SP 800-208 signing in software? Not in a conformant way. SP 800-208 validates key generation and signature generation only inside hardware cryptographic modules at FIPS 140 Level 3 or higher that never export the private key. Verification may run anywhere. ### Is SHA-3 allowed? Yes, in the form of SHAKE256. SP 800-208 approves parameter sets with SHA-256 or SHAKE256 at 192-bit or 256-bit output sizes. ### Is XMSS still approved? Yes. SP 800-208 approves LMS, HSS, XMSS and XMSS^MT. ## Sources 1. [NIST SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes](https://csrc.nist.gov/pubs/sp/800/208/final), NIST, October 2020 2. [RFC 8554, Leighton-Micali Hash-Based Signatures](https://www.rfc-editor.org/rfc/rfc8554), IRTF, April 2019 3. [RFC 8391, XMSS: eXtended Merkle Signature Scheme](https://www.rfc-editor.org/rfc/rfc8391), IRTF, May 2018 4. [FIPS 180-4, Secure Hash Standard (SHA)](https://csrc.nist.gov/pubs/fips/180-4/final), NIST, August 2015 5. [FIPS 202, SHA-3 Standard](https://csrc.nist.gov/pubs/fips/202/final), NIST, August 2015 ## Related Articles - [LMS stateful signatures](lms-stateful-signatures) - [LMS vs XMSS](lms-vs-xmss) - [ML-DSA vs SLH-DSA](mldsa-vs-slhdsa) - [Hybrid encryption](hybrid-encryption) - [NIST FIPS guide](nist-fips-guide) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing)