Summary

  • RFC 9708 specifies how HSS/LMS public keys and signatures appear in X.509 certificates, PKIX, CMS and related structures. The scheme is stateful: each LM-OTS private key is for one signature, and the signer must preserve which leaves have already been used.
  • A completed signature is not proof that the signer’s global state remained unique. A failed persistent write, virtual-machine snapshot rollback or clone can restore an already-consumed leaf and make later signatures unsafe.
  • The governing control is commit order: reserve and durably advance state before releasing a signature, keep one authoritative writer, prevent private-state export, and retain receipts that distinguish cryptographic verification from state-integrity assurance.

At 02:14 the signing service emits a valid signature. At 02:16 an operator restores a virtual-machine snapshot taken ten minutes earlier. The public key has not changed. The signature format has not changed. Every verifier can still follow the mathematics. Yet the restored machine believes a one-time signing key remains unused even though the outside world has already seen a signature made with it.

That is the operational boundary inside RFC 9708. Published on the Standards Track in January 2025, the document updates the use of the Hierarchical Signature System and Leighton–Micali Signature scheme in certificates and Cryptographic Message Syntax. It obsoletes RFC 8708, aligns the encoding with certificate practice, resolves recorded errata and adds parameter sets. Those are important interoperability changes. They sit on top of a more consequential property: HSS/LMS is a stateful signature system.

State here is not a cache that can be regenerated from the public key. RFC 8554, the underlying HSS/LMS specification, describes a private key whose state contains the next one-time-signature index. Signing produces both a signature and a successor private-key state. When the available leaves are exhausted, there is no next state. If the same secret-key state is used twice, the RFC says there are no cryptographic security guarantees; reuse can make forgery feasible.

The scarce asset is therefore not merely secret material. It is the pair of secret material and an accurate history of consumption.

A valid signature can coexist with an invalid history

LM-OTS is a one-time signature primitive. HSS/LMS arranges many such leaves in Merkle trees and may stack trees hierarchically, giving an installation a practical but fixed signing budget. Each signature identifies the leaf that participated. A verifier can check the signature against the public key and conclude that the submitted object is consistent with that key and algorithm.

The verifier cannot, from that object alone, know whether another signature elsewhere used the same leaf after a rollback or clone. That is a property of the signer’s history, not of one verification transaction. Two observations must remain separate:

Receipt What it establishes
public key accepted policy admitted a particular HSS/LMS key
algorithm identifier parsed the object uses a recognized encoding and parameter set
signature verified this message and signature satisfy the public-key verification procedure
leaf index observed this signature names a particular position in the tree
state reservation recorded a signer assigned that position before use
successor state persisted durable storage advanced beyond the reserved position
signature released bytes crossed the security boundary to a caller
uniqueness reconciled records show no other released signature used the same one-time state
business action completed a relying system acted on the signed content

The fourth row does not imply the eighth. Cryptographic validity is local to the object under test. State uniqueness is a global claim over every writer, backup, snapshot, failover path and exported copy capable of signing under the same key.

RFC 9708 says an implementation must track used leaves and warns that loss of tracking integrity can cause one-time-key reuse. Its examples are strikingly ordinary: persistent-storage writes can fail; a virtual machine can be snapshotted or cloned. These are not exotic attacks on hash functions. They are familiar infrastructure operations colliding with a cryptographic state machine.

The dangerous instant is signature release

The order of operations decides whether a crash is merely inconvenient or cryptographically destructive. Suppose a service computes a signature, returns it to the requester and only then writes the incremented leaf index. If power fails after the response leaves but before the write becomes durable, the recovered service may select the same leaf again. An acknowledgement from a storage API is also insufficient if data remains in a volatile cache that the crash can discard.

NIST Special Publication 800-208 treats this as the central difficulty of stateful hash-based signatures. Its profile requires a conforming module to increment the leaf identifier and persist that increment in nonvolatile storage before exporting the signature or accepting another signing request. The sequence is a state-commit protocol:

  1. choose or reserve the next permitted leaf;
  2. durably record that it can no longer be offered;
  3. compute or finalize the signature under controlled state;
  4. release the signature with a receipt linking it to the reservation;
  5. reconcile uncertain outcomes without ever returning the reservation to the free pool.

This ordering may waste a leaf if the process fails after the durable increment but before export. Wastage is recoverable capacity loss. Reuse is a security failure. A sound design prefers an unexplained gap in the sequence to two public signatures from the same one-time key.

The distinction resembles an irreversible financial ledger more than a stateless cryptographic API. Retrying “the same request” is not necessarily idempotent at the signing primitive. Restoring a database from backup is not necessarily recovery. Scaling a virtual-machine image is not necessarily horizontal elasticity. Every operation must preserve the single forward direction of signing state.

High availability can multiply the authority

Ordinary service design rewards replicas, warm standbys and rapid rollback. Stateful signing reverses some of those instincts. If two live instances hold the same private state and independently allocate leaves, each can create valid signatures while silently spending overlapping positions. A consensus database does not help if either signer can export a signature before the shared state commit is durable. A hardware module does not help if identical private state has been cloned into two modules without a non-overlapping allocation rule.

There are defensible architectures. One authoritative module can serialize all use. Separate signers can receive cryptographically and operationally disjoint subtrees. A monotonic hardware counter can make rollback visible or impossible within a defined boundary. A failover procedure can fence the old writer before a successor receives authority. But the evidence must name the boundary. “Backed by hardware” is not a receipt for exclusive state; “highly available” is not proof that only one writer existed.

NIST’s profile is intentionally stricter than the general IETF syntax: it confines approved parameter sets and requires key and signature generation in hardware cryptographic modules, with secret-key material not exported. That is useful implementation guidance, not evidence that every RFC 9708 deployment follows the NIST profile. RFC publication proves a specification exists. A product statement may prove a claimed feature. Neither proves the runtime preserved state through a particular crash, migration or restore.

RFC 9708 carries the key into wider trust systems

The document’s visible task is integration. It specifies an object identifier and an AlgorithmIdentifier whose parameters are absent, rather than a menu of ASN.1 parameters attached to each key. The HSS/LMS public key is carried without another ASN.1 wrapper. In an X.509 certificate, key-usage constraints must be consistent with signing rather than encryption or key agreement. The changes bring the representation into line with the certificate framework in RFC 5280 and the ASN.1 modules collected by RFC 5912.

For CMS, defined by RFC 5652, the bytes presented to the signature procedure depend on whether signed attributes are present. Without them, the content is signed directly. With them, the content is hashed and the DER encoding of SignedAttributes is what the signer signs; the attributes include content type and message digest. Firmware packaging in RFC 4108 and related signed-object ecosystems can therefore consume HSS/LMS through established containers.

These rules settle representation and verification. They do not move state integrity into the certificate. A certificate can bind a public key to a subject under an issuer’s policy. It cannot attest that no snapshot contains an older copy of the associated private state. A CMS verifier can validate the signed attributes. It cannot see a failed disk flush inside the signer. The wider the key travels through trust systems, the more tempting it becomes to treat algorithm acceptance as end-to-end assurance. The missing receipt remains at the signing boundary.

The budget is a governance object

Because the number of leaves is finite, capacity planning becomes security planning. An organization needs to know the parameter set, hierarchy, permitted signing rate, expected lifetime, reserve margin, replacement lead time and exhaustion behavior. A surprising burst can be abuse, a legitimate release event or a telemetry fault; in all three cases the remaining state matters. A signer that silently wraps, reinitializes or restores an earlier index is not extending capacity. It is falsifying the ledger.

The IANA LMS registry records standardized algorithm typecodes. The RFC Editor’s information page, canonical text and XML, together with the IETF document history and errata index, establish the specification’s public record. They do not report any operator’s remaining leaf count or recovery discipline.

This is where Heng Lu’s running-code test sharpens the question. The proof that matters is the executable transition that consumes state before output escapes. The minimum initial specification supplies a shared interoperability floor, while local deployments retain choices about modules, fencing, audit and capacity. The reality-layer discipline prevents a standards-track label, a verified object and a safe operating history from being collapsed into one status.

RFC 9708 is not an argument against HSS/LMS. It is a precise reminder that cryptographic strength can relocate operational responsibility rather than remove it. The hash-based construction may reduce dependence on assumptions threatened by a cryptographically relevant quantum computer. In exchange, the system asks its operator to keep an incorruptible memory of every one-time choice. The key is not just what the machine knows. It is what the machine can prove it will never forget.

Sources