Hash-Based Signatures: When XMSS and LMS Beat ML-DSA

Most post-quantum migration guidance directs organisations to ML-DSA for all signature needs. That advice is correct for most cases. For firmware signing pipelines, long-lived code signing infrastructure, and document archiving with 50-year retention requirements, however, defaulting to ML-DSA without evaluating the alternatives leaves a technically superior option on the table. XMSS and LMS are not legacy candidates awaiting retirement. They are mature, standardised algorithms that produce smaller signatures than ML-DSA-87 and carry the most conservative security assumption available in any deployed signature scheme today.

This article identifies the specific use cases where XMSS and LMS are the more appropriate choice, explains why, and shows what the trade-offs look like in concrete bytes. It is written for security architects who are already evaluating algorithm selection for signing applications and need a technically precise case for or against the hash-based family.

What XMSS and LMS Are

Both schemes are stateful hash-based signature schemes defined in IETF RFCs. XMSS (eXtended Merkle Signature Scheme) is specified in RFC 8391 (April 2018). LMS (Leighton-Micali Hash-Based Signatures) is specified in RFC 8554 (April 2019). Both are approved for US federal use under NIST SP 800-208 (October 2020). Neither is experimental, and neither has been deprecated.

The construction: each scheme builds a Merkle tree of one-time signature keys. Each leaf is used exactly once to sign a message. The public key is the root of the tree. Signature verification involves reconstructing the root from the signature and a path of hash values through the tree. Security reduces entirely to the second-preimage resistance of the underlying hash function, SHA-256 in the primary instantiations for both schemes. There are no lattice assumptions, no algebraic structure assumptions, no pairing assumptions. If SHA-256 is secure against second-preimage attacks by a quantum adversary (Grover's algorithm halves the effective bit strength; SHA-256 degrades to approximately 128 bits of quantum security), the signature is secure.

The operational constraint: each leaf can be used only once. Signing requires maintaining state, specifically the current leaf index. Reusing a leaf breaks the scheme. If the signing state is lost, corrupted, or duplicated due to a VM snapshot restore or a backup restore, the security guarantee fails. SP 800-208 is explicit about this and recommends hardware security module (HSM) state management for high-assurance environments. This constraint is not a minor caveat. It is the reason ML-DSA is the general recommendation. The rest of this article identifies where the constraint is manageable.

LMS uses the Leighton-Micali one-time signature scheme (LM-OTS) at each leaf. XMSS uses a Winternitz-based OTS construction. LMS is simpler to implement and more widely supported in existing FIPS 140-3 validated modules. XMSS^MT (multi-tree) supports substantially larger signature counts than a single LMS tree. For most deployment scenarios, LMS is the practical starting point; XMSS^MT is the choice when total signature capacity requirements exceed what a single LMS tree provides.

The Signature Size Advantage

Signature size is where the case for LMS and XMSS becomes concrete. The table below shows the comparison across the full family of relevant algorithms.

LMS sizes are approximate. Exact sizes depend on parameter set and hash function output length; see RFC 8554 size calculation tables for precise values. ML-DSA sizes are from FIPS 204, Table 2. SLH-DSA sizes are from FIPS 205, Table 2.

The comparison worth dwelling on: an LMS H25 single-tree signature is approximately 1,116 bytes. ML-DSA-65 is 3,309 bytes. ML-DSA-87 is 4,627 bytes. SLH-DSA-128s, the smallest NIST-standardised stateless hash-based signature, is 7,856 bytes. LMS H25 is roughly one-third the size of ML-DSA-65 and one-seventh the size of SLH-DSA-128s.

SLH-DSA (FIPS 205) deserves a direct note here. It is the NIST-standardised stateless hash-based alternative. Organisations that need hash-only security but cannot manage state should use SLH-DSA. The cost is signature size: SLH-DSA-128s at 7,856 bytes is seven times larger than an LMS H25 signature. That is not a rounding error; it is a meaningful constraint for applications where header space is bounded.

Firmware signing is the clearest example. A device with a firmware header that allocates 2 KB for cryptographic material can accommodate an LMS signature. It cannot accommodate SLH-DSA-128s at 7,856 bytes, ML-DSA-87 at 4,627 bytes, or in some constrained configurations even ML-DSA-65 at 3,309 bytes. For those systems, the choice is not "stateful vs stateless" in the abstract. It is "the system works with LMS" or "the system does not work with anything else."

The Three Use Cases Where XMSS and LMS Win

Firmware Signing for Embedded and Air-Gapped Systems

A device receives firmware updates from a controlled build server over a bounded lifecycle. Signing is performed by a single build pipeline backed by an HSM. Signature count is predictable: if a device receives at most one firmware update per month over a 20-year operational life, it needs 240 signatures. An LMS HBS:SHA256/M32/H13 tree (2^13 = 8,192 signatures) handles that with headroom. An H15 tree (32,768) is more comfortable. Either fits the lifecycle. Either produces a signature well under 2 KB. The statefulness constraint is manageable because the signing environment is a single, controlled build server, not a distributed system. No VM restores, no concurrent instances, no backup restore scenarios that would duplicate leaf indices.

NIST SP 800-208, Section 5 (Parameter Selection) recommends sizing trees conservatively: overestimate signature count requirements rather than underestimate. For firmware signing, the calculation is straightforward. Do it at deployment time, size the tree with headroom, and document the tree capacity in the system security plan.

Code Signing for Bounded-Lifecycle Software

A software product line with a defined support period and a centralised, HSM-backed build pipeline is a strong fit. The key conditions: total signature count is bounded (N releases per year, known support lifecycle), signing infrastructure is centralised (no multi-device or concurrent signing), and signature size matters for distribution channels or embedded verification environments. A defence software programme with ten releases per year over a 15-year support period needs 150 signatures. A single LMS H8 tree (256 leaves) handles it. For higher-volume programmes, a two-level LMS HSS (hierarchical signature system) provides substantially greater capacity while maintaining manageable signature sizes.

SP 800-208 explicitly addresses LMS in DoD firmware and code signing contexts. LMS is more widely supported in existing UEFI secure boot and firmware signing toolchains than XMSS, making it the practical first choice for UEFI and similar embedded signing environments.

Long-Term Document Archiving and Legal Notarisation

Archive systems designed for 50 to 100-year retention present a specific threat model. For a national archive, a legal registry, or a regulatory filing system, the question is not just "will this signature be verifiable in 20 years?" but "will the security assumption underpinning this signature scheme still be sound in 2070?" ML-DSA's security depends on the hardness of the Module Learning With Errors (MLWE) problem, a well-studied lattice assumption with no known efficient quantum attacks. But "well-studied as of 2026" is a different statement from "mathematically proven secure for half a century." Hash function second-preimage resistance has a longer track record and no known structural weaknesses, classical or quantum. For 50-year retention scenarios, the hash-only security assumption of LMS is a more conservative anchor.

RFC 3161 (Internet X.509 PKI Time-Stamp Protocol) provides the mechanism for cryptographic timestamps. Long-term archive systems that currently rely on RSA or ECDSA timestamps should migrate those timestamps to hash-based schemes. LMS provides the smallest and most conservative option for this specific application.

When Not to Use XMSS or LMS

The statefulness constraint eliminates XMSS and LMS from a significant range of applications. Be specific about where they are wrong choices:

• Multi-device or multi-party signing. If two build servers, two signing appliances, or two team members can sign from the same key, the leaf index cannot be safely maintained without a centralised, HSM-backed state arbiter. Duplicate leaf use breaks the scheme.
• Cloud-hosted or containerised signing services. Container orchestration systems that may run concurrent instances create duplicate-state risk. VM snapshot and restore operations duplicate the signing state. Both scenarios are incompatible with stateful hash-based signatures without considerable additional engineering.
• Signing applications where signature count is unpredictable. Tree exhaustion requires a key rollover. If the maximum number of signatures cannot be reliably estimated, tree sizing becomes a liability rather than an asset. An undersized tree triggers a rollover at an unpredictable point in the system lifecycle.
• General-purpose or high-frequency signing pipelines. TLS certificate signing, log signing, telemetry signing, and any application generating thousands of signatures per minute are better served by ML-DSA's stateless design.

ML-DSA (FIPS 204) is the correct choice for these applications. For general enterprise PQC migration, ML-DSA-65 at 3,309 bytes is the recommended starting point. ML-DSA-87 at 4,627 bytes is required for US National Security Systems under CNSA 2.0. Neither requires state management.

Implementation Notes: HSMs and SP 800-208 Compliance

SP 800-208 recommends HSM-based state management for XMSS and LMS in high-assurance environments. The HSM maintains the current leaf index and prevents reuse. This is an additional procurement requirement: the HSM must support XMSS or LMS key generation and state management, not simply key storage. Not all FIPS 140-3 validated HSMs currently support XMSS or LMS key management operations. Verify vendor capability before committing to a platform. An alternative for lower-assurance environments is to store the leaf index in tamper-evident storage with increment-only properties, such as a TPM NV index.

LMS is included in the NIST Cryptographic Algorithm Validation Programme (CAVP) testing suite. For federal use under SP 800-208, FIPS 140-3 validated modules are required in high-assurance applications. Verify the NIST CMVP list for current LMS module support before selecting a hardware platform.

NIST IR 8547 (Initial Public Draft, November 2024) deprecates classical signature schemes including RSA, ECDSA, and EdDSA. It does not deprecate XMSS or LMS. Both remain approved for their defined use cases under SP 800-208. IR 8547's deprecation timeline applies to RSA and ECDSA; it does not affect the status of hash-based schemes. A firmware signing system migrating from ECDSA P-384 to LMS is moving in the correct direction under both SP 800-208 and IR 8547.

The Algorithm Selection Framework

Three questions narrow the selection:

Is signature count bounded and predictable? If yes, tree sizing is deterministic and LMS or XMSS is viable. If no, ML-DSA is safer.

Is signing infrastructure centralised, with HSM-backed state management? If yes, statefulness is manageable. If no, the risk of leaf reuse is too high for production use.

Does signature size matter? For firmware headers, embedded verification environments, and archive timestamps, the difference between 1,116 bytes and 4,627 bytes is not academic. For general enterprise applications, it usually is.

The decision matrix compresses to this: bounded signature count, plus centralised signing infrastructure, plus size-constrained environment equals LMS or XMSS. General-purpose, stateless, concurrent-capable signing equals ML-DSA. Hash-only security required but statefulness unacceptable equals SLH-DSA, at the signature size cost shown in the table above.

For background on why post-quantum digital signatures are needed in the first place, see the post-quantum digital signatures explained article. For the underlying threat that drives the migration, why Shor's algorithm breaks RSA and ECC covers the mechanics in detail. QSECDEF professional membership includes access to technical workshops on algorithm selection and PQC migration programme design; details at QSECDEF professional membership.