Stateful Hash-Based Signatures: LMS, XMSS And Why Firmware Goes First

Before NIST finished its main post-quantum standards, it had already approved two signature schemes that resist quantum attack. NIST SP 800-208, published in October 2020, approves the Leighton-Micali Signature system (LMS) and the eXtended Merkle Signature Scheme (XMSS), along with their multi-tree versions HSS and XMSS^MT.¹ They are built on the IETF specifications RFC 8554 and RFC 8391.

These schemes are unusual. They are among the most trusted post-quantum signatures, yet NIST says they are not suitable for general use. This article explains that apparent contradiction and why firmware signing is the place most organisations will meet them first.

How Hash-Based Signatures Work

A one-time signature can be built from nothing more than a hash function. The signer publishes hashes of some secret values, then reveals a selection of those secrets to sign a message. Anyone can check the revealed values against the published hashes. The catch is in the name: each one-time key can safely sign only one message.

LMS and XMSS make this practical by generating a large batch of one-time keys and arranging their public parts in a Merkle tree, a structure where hashes are combined in pairs up to a single root. That root becomes the long-term public key. Each signature includes one one-time signature plus the path through the tree that links it to the root.

The height of the tree fixes how many signatures a key can ever produce. For LMS, SP 800-208 allows heights from 5 to 25, which means anything from 32 to about 33 million signatures per tree. The multi-tree versions, HSS and XMSS^MT, stack trees in layers: one-time keys in the top tree sign the roots of the trees below, and those lower trees sign the messages. SP 800-208 notes that this layering also makes it easier to spread one-time keys across several hardware modules.¹

Because security depends only on the hash function, NIST describes these schemes as relying on the difficulty of finding preimages or second preimages, problems that large quantum computers are not expected to break.¹

Why State Is Dangerous

In LMS and XMSS, the private key is really a large set of one-time keys, and the signer must never use any of them twice. SP 800-208 warns that if an attacker sees two different messages signed with the same one-time key, forging further signatures can become feasible.¹

That makes the signer’s state, a record of which keys are used, part of the security. Restoring a backup, cloning a virtual machine, running two signing servers from the same key, or losing power just after signing can each cause reuse. For this reason SP 800-208 requires key generation and signing to take place in hardware cryptographic modules that do not allow the private keys to be exported, even in encrypted form.¹

Why Firmware Goes First

SP 800-208 describes the ideal use case as one where a signature scheme is needed soon, the implementation will last a long time, and changing it after deployment would be impractical. It gives firmware updates for constrained devices that may stay in service for decades as an example.¹

The NSA makes the same argument for US national security systems. Its CNSA 2.0 suite lists LMS and XMSS for signing software and firmware, and its FAQ explains why that use is urgent: the code that checks firmware signatures is often hard to update, so a quantum-resistant root of trust may be needed years before the rest of a system changes.² The NSA prefers LMS with SHA-256/192, does not allow the multi-tree variants HSS and XMSS^MT for those systems, and has encouraged vendors to start now rather than wait for validated ML-DSA.²

European agencies agree on the special status of hash-based signatures. France’s ANSSI, which otherwise expects post-quantum algorithms to be combined with classical ones, made that combination optional in 2023 for products whose post-quantum protection relies only on hash-based signatures such as LMS, XMSS or SPHINCS+.³ Its current FAQ keeps the same exception for SLH-DSA, XMSS and LMS.⁴ Germany’s BSI likewise states that hash-based signatures can in principle be used alone, provided their implementation security is handled carefully.⁵

Choosing A Hash-Based Or Lattice Signature

LMS and XMSS are not the only post-quantum signatures. SLH-DSA (FIPS 205) is also hash-based but stateless, so it avoids the reuse problem at the cost of larger signatures. ML-DSA (FIPS 204) is lattice-based, with smaller signatures and no state. The NSA notes that ML-DSA can be the better choice when a signing workload needs more signatures than a single LMS or XMSS key can provide, or when signing is distributed across many systems.² SLH-DSA, despite being hash-based, is not part of CNSA 2.0.² Outside national security systems, it remains a reasonable choice for organisations that want hash-based assurance but cannot manage state, provided they can accept signatures of several kilobytes or more.