Stateful Signing with LMS/HSS

Everything you need to use LMS and HSS in cryptopp-modern, from first sign/verify through writing your own state backend.

1. What this is

LMS and HSS are hash-based signature schemes from NIST SP 800-208 and RFC 8554. They are post-quantum. Their security comes from hash functions, not lattices or number theory.

The catch is that they are stateful. Every other signer in this library lets you sign as many messages as you want without thinking about it. LMS/HSS does not. Each signature uses a one-time index. If that index gets reused, through a crash, a restore, or a bug, the key is compromised.

cryptopp-modern does not try to hide this. Stateful signers use PK_StatefulSigner instead of PK_Signer, and the two are deliberately not interchangeable. State tracking is externalised through SignerStateStore, so you pick or build the backend that fits your deployment. The library gives you the contract and the crypto. Your environment provides the durability.

LMS is the single-tree scheme (small capacity, simple). HSS stacks LMS trees in a hierarchy to get more signatures out of one key.

2. Quick start

LMS: sign and verify

#include <cryptopp/lms.h>
#include <cryptopp/stateful.h>
#include <cryptopp/osrng.h>

using namespace CryptoPP;

AutoSeededRandomPool rng;

// Generate key pair
LMSPrivateKey<LMS_SHA256_M32_H5, LMOTS_SHA256_N32_W8> privKey;
privKey.GenerateRandom(rng, g_nullNameValuePairs);

LMSPublicKey<LMS_SHA256_M32_H5, LMOTS_SHA256_N32_W8> pubKey;
privKey.MakePublicKey(pubKey);

// Testing only. Use a durable backend for real deployments.
InsecureMemoryStateStore store(LMS_SHA256_M32_H5::TOTAL_LEAVES);

// Sign
LMSSigner<LMS_SHA256_M32_H5, LMOTS_SHA256_N32_W8> signer(privKey, store);
SecByteBlock sig(signer.SignatureLength());
const byte msg[] = "Hello LMS";
signer.SignMessage(rng, msg, sizeof(msg) - 1, sig);

// Verify is stateless and uses the normal PK_Verifier interface
LMSVerifier<LMS_SHA256_M32_H5, LMOTS_SHA256_N32_W8> verifier(
    pubKey.GetPublicKeyBytePtr(), pubKey.GetPublicKeyByteLength());
bool valid = verifier.VerifyMessage(msg, sizeof(msg) - 1, sig, sig.size());

HSS: more capacity

#include <cryptopp/hss.h>
#include <cryptopp/stateful.h>
#include <cryptopp/osrng.h>

using namespace CryptoPP;
typedef HSS_SHA256_H5_W8_L2_Params Params;  // L=2, 1024 signatures
typedef HSS_SHA256_H5_W8_L2 Scheme;

AutoSeededRandomPool rng;

Scheme::PrivateKey privKey;
privKey.GenerateRandom(rng, g_nullNameValuePairs);

Scheme::PublicKey pubKey;
privKey.MakePublicKey(pubKey);

// Testing only. Use a durable backend for real deployments.
InsecureMemoryStateStore store(Params::TotalSignatures());
Scheme::Signer signer(privKey, store);
Scheme::Verifier verifier(
    pubKey.GetPublicKeyBytePtr(), pubKey.GetPublicKeyByteLength());

SecByteBlock sig(signer.SignatureLength());
const byte msg[] = "Hello HSS";
signer.SignMessage(rng, msg, sizeof(msg) - 1, sig);
bool valid = verifier.VerifyMessage(msg, sizeof(msg) - 1, sig, sig.size());

Persisting state across restarts

#include <cryptopp/stateful.h>

// First use: create a new state file
FileStateStore store = FileStateStore::Create("signer.state", 1024);

// Later: reopen the state file
FileStateStore store = FileStateStore::Open("signer.state", 1024);

// Works with any signer
Scheme::Signer signer(privKey, store);
signer.SignMessage(rng, msg, sizeof(msg) - 1, sig);
// Index is on disk before this call returns

3. The state contract

If you take one thing from this guide: no signing index may ever be reused.

How signing works

Every SignMessage() call does three things:

1. Reserve. The store issues the next index and advances its counter. Past this point, the index is consumed even if signing later fails.
2. Sign. Produce the signature.
3. Commit. Tell the store the signature is on its way.

If signing fails after reservation, the signer calls Abort. The index is burned. It is gone forever but safe. The alternative would be making it available again, which would be catastrophic.

What “burned” means

A burned index is wasted capacity, not a security problem. You lose one signature you could have made. This happens when signing throws after reservation, when the process crashes mid-sign, or when a reservation is explicitly aborted.

This catches people more than you’d expect. If your application has a high failure rate during signing (bad RNG, resource exhaustion, interrupted operations), you will burn through capacity faster than you planned. Worth thinking about up front.

Exhaustion

Every key has a finite number of signatures. When they are gone, SignMessage() throws SignerExhausted.

RemainingSignatures() gives you a planning number. It never overcounts, but it might undercount if you have burned some indices along the way.

Verification

Verification is stateless. LMSVerifier and HSSVerifier use the conventional PK_Verifier interface. Verify as many times as you want, share verifier instances across threads, no state concerns.

4. FileStateStore

FileStateStore is a reference durable backend for single-writer desktop/server use. It writes signing state to a 64-byte local file so the counter survives restarts and crashes.

It is not the only way to persist state, and it is not trying to be. If you need multi-process coordination, hardware anti-rollback, or database-backed state, write your own backend (section 5 covers how). FileStateStore exists to prove the contract works and to handle the simple case well.

The file

64 bytes, fixed size:

Little-endian integers. It is a local file, not a wire format.

Write-ahead

ReserveNext() writes the new index to disk and calls fsync before returning the reservation. If the process dies between the write and the signature, one index is lost. Safe.

CommitReservation() and AbortReservation() are both no-ops. The state was already on disk at reservation time. They exist because the SignerStateStore interface requires them, and other backends might actually use them for things like releasing locks or writing audit logs.

Crash behaviour

At most one index lost. No index reused.

Integrity keys

The HMAC catches accidental corruption such as bit flips, truncation, or wrong file. You can optionally provide an integrity key to also catch wrong-key attachment:

const byte key[] = /* application-derived integrity key bound to this signer */;
auto store = FileStateStore::Create("signer.state", 1024, key, sizeof(key));

Without a key, you get a deterministic checksum. It catches accidents but not intentional tampering.

Neither mode prevents someone from restoring an older valid copy of the file. If that happens, the store reopens at the old index and starts reissuing. True anti-rollback needs hardware (TPM, RPMB) or an external monotonic counter, which is out of scope here.

Single writer

Two processes writing the same state file will silently reissue indices. There is no locking and no detection. This is a total security failure, not a subtle bug. One process, one file, one signer.

Poisoned state

If integrity verification fails (on open, on reserve, or on health check), the store object becomes permanently poisoned. All subsequent operations throw SignerStateIntegrityFailure. IsExhausted() returns true. RemainingSignatures() returns 0.

Poisoning is local to the object. You cannot clear it. Discard the object, figure out what happened, and only then consider opening a new instance. Don’t blindly recreate the state file: that starts from index 0 and reuses every index the old file had already consumed.

Platforms

This backend is for systems with real filesystems and meaningful flush semantics. Bare metal, RTOS, flash, and secure elements need their own SignerStateStore implementation.

5. Writing your own backend

If FileStateStore doesn’t fit, and for many real deployments it won’t, implement SignerStateStore directly. The interface is six methods:

class SignerStateStore {
public:
    virtual StateReservation ReserveNext() = 0;
    virtual void CommitReservation(const StateReservation &reservation) = 0;
    virtual void AbortReservation(const StateReservation &reservation) = 0;
    virtual bool IsExhausted() const = 0;
    virtual bool IsHealthy() const = 0;
    virtual uint64_t RemainingSignatures() const = 0;
};

IsHealthy() is not a passive probe. Backends should throw SignerStateIntegrityFailure when integrity can no longer be trusted, not quietly return false.

The rules

The one that matters most: no signing index may ever be reissued. Everything else follows from that.

ReserveNext() is the critical operation. Once it returns, that index is consumed, even if the caller never signs with it.

Commit must not advance state more than once for the same reservation. Your backend can use the commit call for other work such as audit logs or releasing a database lock, but it must not reissue the index. Abort confirms the burn: the index was consumed at reservation time, and abort just acknowledges that signing didn’t complete.

RemainingSignatures() may undercount. It must never overcount.

If your backend can’t guarantee uniqueness, whether from corruption, connection loss, or anything else, throw SignerStateIntegrityFailure and stop. Wasting capacity is acceptable. Reusing an index is not.

Thread safety is your responsibility. If your backend supports concurrent callers (a database store used from a thread pool, for instance), serialise ReserveNext() internally. If it doesn’t, document the single-caller assumption and let the signer enforce it.

Failure modes

Safe failures (lose capacity, keep security):

• Burned reservations after signing failure
• Undercounted remaining capacity
• Refusing to continue when in doubt

Unsafe failures (break everything):

• Reissuing a reserved index
• Silently repairing state in a way that risks reuse
• Claiming rollback protection you don’t actually have
• Allowing concurrent writers without explicit coordination

Creating reservations

Your backend creates StateReservation objects through the protected factory on the base class:

StateReservation reservation = MakeReservation(nextIndex);

Backends you might build

Conformance checklist

Run these before trusting a backend with real keys:

• ReserveNext() returns monotonically increasing indices
• ReserveNext() throws SignerExhausted when capacity is used up
• Double-commit succeeds without side effects
• Abort doesn’t make the index available again
• RemainingSignatures() never overcounts
• IsHealthy() catches corruption if applicable
• The backend survives process restart without reissuing (if durable)
• It fails closed on integrity doubt
• Concurrent access is either blocked or coordinated

6. What this library does and doesn’t do

The stateful signing framework and the LMS/HSS implementations are part of cryptopp-modern’s scope. The library defines the SignerStateStore contract, provides FileStateStore as a working reference for simple deployments, and gives you the conformance tests to validate your own backends.

What it doesn’t do is solve deployment-level storage for you. Embedded persistence, distributed coordination, hardware anti-rollback, multi-process locking: those depend on your environment and your threat model. The library can’t honestly promise to handle all of that, so it doesn’t pretend to.

FileStateStore ships because people need a working default, but it is a reference implementation for single-writer desktop/server use, not the centre of the project. If it doesn’t fit your deployment, that is expected. Write a backend that does.

A few specific points worth being explicit about:

LMS and HSS follow RFC 8554 and SP 800-208. HSS verification has been tested against the Cisco hash-sigs reference implementation (RFC 8554 Appendix F Test Case 1). All signing indices are consumed at reservation time, not at commit time.

FileStateStore does not provide anti-rollback across process restarts. If someone restores an old copy of the state file, it will reopen at the old index. Concurrent writers aren’t detected: two processes on the same file will silently reuse indices.

Private key encoding is library-internal PKCS#8 wrapping containing seed and identifier only. It is not an RFC-defined format, not portable across implementations, and does not include signing state. Public key encoding uses X.509 SubjectPublicKeyInfo (RFC 9802) and is standards-facing.

7. Common mistakes

Recreating a state file after corruption

If the integrity check fails, do not delete the state file and create a new one for the same key. That resets the counter to 0 and reuses every index the old file had already consumed.

Investigate what happened. If you have a backup, make sure it is at least as advanced as the last index that was actually used. Restoring an older snapshot reintroduces the same reuse risk. If you can’t be sure, retire the key.

Using InsecureMemoryStateStore in production

It doesn’t survive process exit. Every restart starts from index 0. This is fine for tests. It is a total key compromise in production.

Sharing a state file between processes

Two writers on the same file will both issue index 0, then both issue index 1. Every signature from the second writer reuses an index from the first. No locking, no detection, silent failure. Don’t do this.

Treating commit as a safety boundary

For write-ahead stores, commit is a no-op. The state advanced at reservation time. If you build application logic around “commit succeeded, therefore I’m safe” you are relying on something that isn’t actually doing any work. The safety boundary is the reservation.

Ignoring exhaustion

An H5 tree gives you 32 signatures. HSS L=2 H5 gives you 1,024. If you’re signing firmware images once a month, that’s fine. If you’re signing API responses, you’ll run out in minutes. Check RemainingSignatures() and plan key rotation before you hit zero.

Assuming rollback protection

FileStateStore catches accidental corruption. It does not catch someone replacing the file with an older valid copy. If your threat model includes filesystem-level rollback (VM snapshot restore, backup clobber, hostile sysadmin), you need a backend with a hardware monotonic counter or an external anti-rollback mechanism.

Loading a saved key without its state store

Private key encoding doesn’t include signing state. If you deserialise a key and create a fresh store for it, you’ll sign from index 0 again. The store is part of the key’s identity. Always pair a loaded key with its existing store.

Treating stateful signers as drop-in replacements

PK_StatefulSigner is not PK_Signer. They are separate types on purpose. You can’t pass an LMS signer where an ECDSA signer is expected, and the compiler will stop you from trying. Stateful signing has different operational requirements and the type system reflects that.