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 run
{
    FileStateStore store = FileStateStore::Create(
        "signer.state", Params::TotalSignatures());

    Scheme::Signer signer(privKey, store);
    signer.SignMessage(rng, msg, sizeof(msg) - 1, sig);
    // The reservation is persisted before signature generation begins
}

// Later run, normally in a new process
{
    FileStateStore store = FileStateStore::Open(
        "signer.state", Params::TotalSignatures());

    Scheme::Signer signer(privKey, store);
}

The state store must outlive every signer bound to it. The signer holds a non-owning reference, so do not move or destroy the store while a signer still references it.

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. Finalise any backend bookkeeping after successful signature generation.

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.

If your application has a high failure rate during signing (bad RNG, resource exhaustion, interrupted operations), you will burn through capacity faster than planned. Include that in the capacity calculation.

Exhaustion

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

Capacity is the product of the per-level tree sizes; the Choosing LMS/HSS Parameters guide covers picking a configuration.

RemainingSignatures() returns the backend’s current view of usable capacity. Burned reservations are already excluded. A backend may return a conservative underestimate, but it must never overcount.

Verification

Verification is stateless. LMSVerifier and HSSVerifier use the conventional PK_Verifier interface. Verify as many times as you want, and share verifier instances across threads provided their public key is not modified.

4. FileStateStore

FileStateStore is a reference durable backend for single-writer local-filesystem use. It writes signing state to a 64-byte local file. Updates to an existing, durably created state file are flushed before a reservation is returned, so the counter survives restarts and crashes of a running signer. The initial Create() flushes the file itself but not the parent directory entry, so provisioning is not crash-safe until the private key and state file have both been durably committed; do not begin signing before then.

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 implements the simple local-file case.

The file

64 bytes, fixed size:

Little-endian integers. The layout is an implementation detail, not a supported format contract: applications must use Create() and Open() rather than parsing or modifying the file directly.

Write-ahead

ReserveNext() writes the updated state and flushes it using the platform’s durability primitive before returning the reservation. If the process dies between the write and the signature, one index is lost. Safe.

CommitReservation() and AbortReservation() do no further disk work. The state was already on disk at reservation time. Both methods verify that the reservation is still valid and was issued by this store, throwing SignerStateIntegrityFailure otherwise. Other backends may use these hooks for releasing locks or writing audit logs.

Crash behaviour

With one signing operation in flight, a crash burns at most that reservation. No index is reused.

Integrity keys

The file checks detect truncation and structural errors, while the HMAC detects accidental modification of the state record. A signer-specific integrity key can also detect attaching a valid state file from another signing identity:

SecByteBlock integrityKey(32);
// Load integrityKey from protected application storage.

FileStateStore store = FileStateStore::Create(
    "signer.state", Params::TotalSignatures(),
    integrityKey, integrityKey.size());

Use a separate integrity key associated with this signing identity, or a documented domain-separated derivation approved by your key-management design.

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

FileStateStore enforces single-writer access at the OS boundary. On POSIX it acquires flock(LOCK_EX | LOCK_NB) at open. On Windows it opens with no sharing via CreateFileW. A second process attempting to open the same file gets Exception::IO_ERROR.

This is cooperative locking, not universal protection. Removing or renaming the file defeats it. Some filesystems (NFS, network-mounted volumes) may not honour flock correctly. If your environment includes those, treat the lock as best-effort and use a backend with stronger filesystem semantics.

For FileStateStore, one active store and signer for each private key is the recommended model. The lock catches accidents, not adversaries.

Poisoned state

Integrity failure behaves differently depending on where it happens. If verification fails during Open(), no store object is returned; the open throws. A live store object becomes permanently poisoned when a state write fails during ReserveNext(), or when IsHealthy() re-reads the file and verification fails. Once poisoned: ReserveNext() and IsHealthy() throw SignerStateIntegrityFailure, IsExhausted() returns true, and RemainingSignatures() returns 0. CommitReservation() and AbortReservation() still validate their reservation but do not consult the poison flag; for a write-ahead store there is nothing left for them to protect.

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

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, and a repeated valid commit must succeed without side effects. 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. After detecting an integrity failure, the backend object must remain failed closed. 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 is not thread-safe, the caller must ensure that neither the signer nor the store is used concurrently. The signer does not provide internal serialisation.

Failure modes

Safe failures (lose capacity, keep security):

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

Unsafe failures (violate the contract):

• 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);

MakeReservation() captures this so the reservation is bound to your store. Reservations issued by one backend instance cannot be committed or aborted against another. To enforce this on the commit and abort paths, call the base-class helper rather than checking validity by hand:

void CommitReservation(const StateReservation &reservation) override
{
    if (!IsReservationValidForThis(reservation))
        throw SignerStateIntegrityFailure("MyBackend: invalid state reservation");
    // ... your commit work
}

IsReservationValidForThis() covers both IsValid() (catches moved-from tokens) and the issuer check (catches foreign-store tokens) in one call, so the two-part rule cannot drift apart.

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
• Moved-from and foreign-store reservations are rejected on commit and abort
• Zero capacity is rejected at construction

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 provides a conformance checklist; the included backends are tested against the contract.

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.

FileStateStore covers simple, single-writer local-file deployments. Where it does not fit your deployment, 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 RFC 8554 Appendix F Test Cases 1 and 2. All signing indices are consumed at reservation time, not at commit time. An SP 800-208-conformant signing deployment has additional hardware-module and key-handling requirements beyond this library; see the API reference.

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. It rejects concurrent opens on supported local filesystems; POSIX locking is advisory, and removing or renaming the file, bypassing the API, or filesystems with unreliable locking can defeat that protection (see Single writer).

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. HSS public keys encode as X.509 SubjectPublicKeyInfo in the RFC 9802 form; single-tree LMS public keys currently use a cryptopp-modern-specific wrapping under the same OID. The LMS/HSS API reference has the details.

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. This is fine for tests. It is unsafe for persistent production keys: a restart or independent store begins at index zero and can compromise the key through index reuse.

Using the same private key with multiple state stores

Two independent stores for the same key will both issue index 0, then both issue index 1: every signature from the second store reuses an index from the first. This is the catastrophic case, and independent stores cannot detect each other without shared coordination. One key, one store. FileStateStore rejects a second concurrent open of the same file, but that lock cannot protect against two different files, or copies of one file, fronting the same key.

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. These parameter sets are unsuitable for high-volume request signing. Check RemainingSignatures() and plan key rotation before you hit zero.

Assuming rollback protection

FileStateStore catches accidental corruption, not restoration of an older valid file copy (VM snapshot restore, backup clobber, hostile sysadmin). See Integrity keys; anti-rollback needs a hardware monotonic counter or an external 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.