Stateful Hash-Based Signatures Are Quantum-Safe and Easy to Break

NIST has standardized a few different options for quantum-safe digital signatures. Of these, hash-based signatures, such as LMS and XMSS, appear the safest since their security guarantees only rely on the quantum resistance of hash functions.

However, the fact that they're likely secure against quantum computers doesn't mean that they're safe. The security assumptions and requirements for these schemes make them very easy to mess up.

What "Stateful" Means

LMS and XMSS are stateful signature schemes that are recommended by the NSA for firmware signing. At the same time, NIST states that they aren't "suitable for general use."

The reason for this is that stateful signature schemes draw from a large pool of single-use private keys to generate digital signatures. In the event that one of these one-time keys is reused, an attacker gains the ability to forge valid digital signatures.

Where State Gets Lost

Using LMS and XMSS securely requires careful state tracking since the organization needs to ensure that keys are never reused. However, this is harder than it sounds. Some ways that state can be lost include:

• VM Snapshots and Restores: When a virtual machine (VM) is restored from a snapshot, it's restored to the exact state that it was in when the snapshot was created. If the VM manages XMSS or LMS keys, it will forget about any signatures generated and keys used up between the snapshot creation and the time when it was restored.
• Failover and Cloning: VMs, HSMs, containers, or CI runners can be used for state tracking but also have the ability to be replicated, cloned, or perform failover from a primary to secondary system. Without centralized coordination, this could mean that the two systems use the same one-time key twice.
• Crashes: A system may crash between generating a signature and recording that fact in the index. If so, it might reuse the same key after being restored from the crash.

To mitigate these issues, NIST imposes strict rules on how these signatures should be used. Cryptographic modules "shall" increment the index and write it to nonvolatile storage before releasing the signature (similar to the checks-effects-interactions pattern in Web3 reentrancy prevention). Additionally, key and signature generation should be implemented in hardware modules that don't allow keys to be exported, preventing the same key from being used independently in multiple locations.

Securely Implementing Stateful Quantum-Safe Signatures

LMS and XMSS are popular because they offer greater quantum security guarantees and often have smaller signatures than ML-DSA. However, they also have their limitations, such as finite key capacity (drawing from a fixed pool), uneven module support (HSM support for SP 800-208 depends on vendor and model), and the significant risks of key reuse.

When implementing XMSS or LMS, security best practices include:

• Track stateful signature schemes in the CBOM
• Single-signer architecture with HSM-based state tracking
• No snapshots, clones, or blind backup restores
• Test crash and failover behavior
• Use a stateless scheme (ML-DSA or SLH-DSA) if you can't guarantee accurate state tracking

Stateful signature schemes offer significant benefits in terms of signature length and quantum security. However, they're not worth the risk if you can't guarantee that poor state tracking won't enable forgeries.

Educational content, not legal, financial, investment, or professional security advice. Terms