Field notes · Hash-based signatures · Operations
Stateful signatures and the backup that ate your keys
LMS and XMSS are standardized, quantum-safe and fast. They also break catastrophically if a one-time key is used twice. Here's how ordinary operations cause that, and how to prevent it.
LMS (RFC 8554) and XMSS (RFC 8391) are among the most conservative post-quantum signature schemes available. They rely only on hash functions, NIST approved both in SP 800-208, and their signatures are small and fast to verify. They are an excellent fit for firmware and code signing.
They also have one sharp edge, and it’s operational rather than mathematical.
Why “stateful” matters
Both schemes are built from Winternitz-style one-time signatures arranged as the leaves of a Merkle tree. Each leaf may sign exactly one message. The signer must remember which leaves it has used, and that record is the state.
If the same leaf signs two different messages, an attacker who sees both signatures learns enough of the hash chains to forge signatures on other messages. There is no graceful degradation: one reused leaf can undermine the key.
How state gets lost in real life
Nobody reuses a leaf on purpose. It happens because ordinary infrastructure practices quietly assume keys are stateless:
- Restoring from backup. The signer is restored from last week’s backup, which records the leaf counter from last week. Every leaf used since then will be used again.
- Virtual machine snapshots and clones. Two copies of a signing VM each believe they own the next leaf.
- High-availability pairs. A failover signer starts from a replicated counter that lags the primary.
- Crashes between signing and saving. The signature leaves the box, but the incremented counter never reaches disk.
Designing it safely
SP 800-208 is direct about this: it calls for key generation and signing to happen inside hardware cryptographic modules that do not export private keys. Beyond that, a few patterns make stateful signing robust:
- Advance the state before signing. Write the incremented counter durably, then sign. A crash wastes a leaf instead of reusing one.
- Reserve ranges, don’t share counters. Give each signer an exclusive block of leaves (for example with HSS, the multi-tree form of LMS) so no two devices can ever pick the same one.
- Make private keys impossible to back up. If the key can’t be restored, it can’t be restored to an old state. Plan for loss with a second, independent key instead.
- Monitor for duplicates. Log every leaf index used, and alert on any repeat. It should never happen, so any occurrence is an incident.
When to choose something else
If you can’t guarantee those properties, choose a stateless scheme. SLH-DSA (FIPS 205) uses the same hash-based building blocks without state, at the cost of larger signatures, and ML-DSA (FIPS 204) offers small, fast lattice-based signatures. Many organizations will end up using a stateful scheme for a few tightly controlled roots and a stateless one everywhere else.
If you’re planning firmware or code signing with LMS or XMSS and want a second pair of eyes on the state handling, we can help.