Summary

  • RFC 10033 separates long-lived secret material from the mutable state that records which one-time-signature indices have been consumed. A backup can be authentic and internally consistent yet unsafe because its state predates signatures already released.
  • Safe operation requires the release of a signature and the durable advancement of state to behave as one atomic act. Sectors, reserved intervals and time windows help partition capacity, but only if recovery preserves exclusive, non-overlapping ownership.
  • A successful HSM self-test or a cryptographically valid test signature proves that a device can sign. It does not prove that the device alone controls an unused part of the key space. Recovery therefore needs a custody receipt, not just a restore log.

The dangerous recovery begins with reassuring evidence. The backup decrypts. Its integrity tag verifies. The hardware security module imports the material and passes its self-tests. A test message receives a signature that validates under the expected public key. Every conventional signal says that the signer is healthy again.

For a stateful hash-based signature system, those checks can all be true while the recovery remains unsafe.

The reason is that the private key contains two different kinds of value. There is static secret material from which one-time signing keys or tree nodes are derived. There is also mutable state: the record of which one-time-signature, or OTS, indices have already been used. The static material answers, “Can this system make a valid signature?” The state must answer a harder question: “Which signing capacity is still exclusively unused?”

RFC 10033, published on the IETF stream as an Informational RFC, is a practical guide to that second question. Its premise follows the security condition in XMSS and LMS. Reusing a one-time key for different messages can disclose enough structure to make forgery computationally feasible. A signer therefore has to persist its advance to the next unused key before a completed signature can escape to its caller. RFC 8391 states that the XMSS private-key state must be updated before signature output; RFC 8554 imposes the corresponding discipline on LMS.

The authentic stale backup

Imagine that a signer creates a backup when the next available index is 40,000. It later releases 5,000 signatures and advances its live state to 45,000. A failure destroys the current state, and an operator restores the older, correctly authenticated image. The restored device can derive the right secrets and produce mathematically valid signatures. But it may begin again at 40,000. Those 5,000 positions have been consumed in the outside world even though the recovered system has forgotten them.

The failure is not counterfeit key material. It is temporal ambiguity. The copy is genuine but no longer authoritative about exclusivity.

That distinction explains why ordinary backup language is misleading. For a stateless key, another protected copy mainly changes the number of places from which the same secret can be exercised. For a stateful HBS key, every copy also carries a claim about remaining capacity. RFC 9802 makes the contrast explicit in its discussion of conventional backup: duplicating or restoring the private key without correct state coordination is likely to cause OTS reuse.

NIST takes an intentionally restrictive route for its approved stateful HBS profiles. SP 800-208 requires key and signature generation inside hardware cryptographic modules and does not permit exporting private keying material. That sharply limits conventional recovery choices. RFC 10033 also discusses mechanisms outside that NIST profile, but the two should not be blurred: an export-and-import procedure described for broader operational use is not evidence that a NIST-conforming module may export its private key.

Static secret and mutable state

State is often treated as a small counter beside the “real” key. Operationally, it is part of the key’s safety boundary. The counter, the mapping from indices to devices, the record of reserved but unused ranges, and evidence that a source signer has stopped are what prevent two valid devices from behaving as if the same one-time key belonged to each of them.

This turns a familiar integrity question into an exclusivity question. A checksum can prove that bytes were not altered. A digital signature can authenticate the backup producer. Neither proves that no later state exists, that no clone remains active, or that no signature left the system during a crash window. The control surface extends beyond the cryptographic module to caches, process forks, virtual-machine snapshots, queues, response paths and operator handoffs.

RFC 10033 therefore recommends designs that minimize the gap between completing a signature and securing the updated state. It describes the desired property using database language: signature release and state advancement should have atomicity, consistency, isolation and durability. If a crash leaves doubt, the safe response is not to reclaim uncertain capacity. It is to burn it.

Release and advancement as one act

The clean invariant is simple to state: no complete signature becomes observable outside the signer unless the corresponding index is already durably unavailable for every future signer.

Implementation makes it difficult. A signing process can persist state and then fail before returning the signature, wasting one index but preserving safety. The reverse ordering is worse: it can return a signature and fail before recording consumption. Caches can acknowledge writes that have not reached durable media. A virtual machine can be cloned after accepting work. Two recovery operators can activate the same generation in different facilities.

Waste is therefore asymmetric. Burning an uncertain OTS key reduces finite capacity. Reusing one can weaken the security of every relying decision under the public key. Recovery design should prefer measurable waste over invisible overlap.

Sectors, intervals and time windows

RFC 10033 describes several ways to divide the state space so that responsibility can move without moving everything at once.

Sectorization assigns independent fragments beneath a common public key to different signers. A sector can be transferred only if the source stops using it and its ownership is not duplicated. Preassigned ranges similarly give devices disjoint portions of the index space. Interval reservation lets a process claim a block before signing; if it crashes, the unused tail of the block is abandoned rather than offered to another process. Time-based allocation can bind capacity to a period, but recovery must never move the logical clock backwards. Unused capacity from elapsed windows has to be treated as spent.

These mechanisms change the unit of custody, not the underlying rule. A transfer must establish non-overlap among the recovered signer, the failed or quarantined source, any replicas, any offline copy and every previously assigned range. Partial transfers and later merges need the same accounting. A sector label or time window is not safe merely because its syntax is valid.

RFC 10033 also outlines, outside the NIST-approved non-exporting profile, a recovery method that prepares bottom-level trees in advance. A bottom-tree root is signed with an unused upper-level OTS key; the seed, signature, index and hash are exported; and the source copy is irreversibly deleted. Recovery imports the first unused package, regenerates the tree, verifies it against the recorded hash and removes the seed from backup media. The procedure is valuable because it makes ownership transitions explicit.

Its hardest verb is still “delete.” After a catastrophic failure or third-party custody event, deletion may be evidenced without being perfectly knowable.

Recovery custody receipt

RFC 10033 does not prescribe a universal recovery receipt. I propose one because the operational decision needs an object that can be reviewed after the emergency.

The receipt should identify the public key, algorithm and parameter set; signer and HSM identities; backup generation and creation time; restored state and highest index known to have been released; the sector, interval or time-window boundary; all reservations that are burned; source quiescence and deletion evidence; hashes of the imported package; the operator and approver; activation and reconciliation times; and the result of checking complete signatures visible in logs or relying systems for duplicate indices.

It should also state uncertainty. If the last durable index is 45,000 but a response queue may have released signatures through 45,127, recovery should begin beyond the entire uncertain range. If a failed source cannot be proven dead, its assigned sector should remain quarantined. If an offline backup cannot be recalled, it should be recorded as a standing overlap risk, not silently treated as harmless storage.

This is a custody record, not a proof produced by cryptography. Its purpose is to show why the operator believes the restored signer owns an unused, non-overlapping domain and which capacity was sacrificed to make that belief conservative.

Sources