RFC 10033

Hash-Based Signatures: State and Backup Management

📅 published September 2026, from ietf

Okay bestie, RFC 10033 is here and it's giving cryptography realness 💅✨

This one is Request for Comments: 10033 🎀, titled Hash-Based Signatures: State and Backup Management 🦋. The IETF published it in September 2026 under ISSN 2070-1721. It's categorised as Informational 💖, so it's not an Internet Standards Track spec. It's published "for informational purposes" and that's it 🌸. The title block lists no Obsoletes or Updates entries, so it doesn't claim to replace or update any other RFC 🙈.

The authors are T. Wiggers from PQShield, K. Bashiri from BSI, S. Kölbl from Google, J. Goodman from Crypto4A Technologies, and S. Kousidis from BSI. Two of them are from BSI, which is very team-BSI energy 💜.

Abstract

Okay so Stateful Hash-Based Signature Schemes (Stateful HBS), like Leighton-Micali Signature (LMS), Hierarchical Signature System (HSS), eXtended Merkle Signature Scheme (XMSS), and XMSS^MT, are literally the main character of quantum-resistant signatures 👑. They combine Merkle trees with One-Time Signatures (OTSs) so the signatures hold up against attacks from large-scale quantum computers 🔮.

Here's the plot twist 🙀: unlike regular stateless digital signatures, Stateful HBS need a state to keep track of which OTS keys have already been used. That's because double-signing with the same OTS key lets forgers in, and nobody wants that 💀.

This document gives guidance and catalogs security considerations for the operational and technical side of running systems that depend on Stateful HBS 🧚. Managing that state, including any handling of redundant key material, is a seriously sensitive topic 😭. The doc describes some approaches for dealing with those challenges, and it also explains what needs to be sorted out before certain approaches should be considered 🫶.

Status of This Memo

This document is not an Internet Standards Track specification 🙅‍♀️. It's published for informational purposes.

This document is a product of the Internet Engineering Task Force (IETF) 🌈. It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not every document the IESG approves is a candidate for any level of Internet Standard, so check Section 2 of RFC 7841 if you want the details ✨.

You can find out the current status of this document, any errata, and how to send feedback at https://www.rfc-editor.org/info/rfc10033 💌.

Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved 🔒.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as they're in effect on the publication date. Please actually read these, because they spell out your rights and restrictions for this document 📜. Code Components extracted from this document must include Revised BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Revised BSD License 🎀.

Table of Contents

   1.  Introduction
     1.1.  When are Stateful HBS Appropriate?
   2.  Specific Terminology in the Context of Stateful HBS
     2.1.  Private Key Components
     2.2.  State Management
     2.3.  Backup Management
     2.4.  Key Export, Key Import, and Key Transfer
   3.  Operational Considerations
     3.1.  Assessing Operational Costs
     3.2.  Ensuring Long-Lived Resilient Solutions
     3.3.  Training and Skills
     3.4.  Configurable Warning Thresholds
     3.5.  Selection of Appropriate Parameter Set
     3.6.  External Dependencies
   4.  Requirements for Secure State Management
   5.  Potential State Management Approaches
     5.1.  Multiple Public Keys (SP 800-208)
     5.2.  Distributed Multi-trees (SP 800-208)
     5.3.  Sectorization
     5.4.  Key/State Transfer
     5.5.  Key Rotation
     5.6.  Variable-Length Signature Chains
     5.7.  Pre-Assigning States
     5.8.  Time-Based State Management
     5.9.  Interval-Based Approaches
   6.  Backup Management Beyond NIST SP 800-208
   7.  Security Considerations
   8.  IANA Considerations
   9.  References
     9.1.  Normative References
     9.2.  Informative References
   Acknowledgments
   Contributors
   Authors' Addresses

1. Introduction ✨

Stateful HBS (Stateful Hash-Based Signature Schemes), such as LMS, HSS, XMSS, and XMSS^MT, mix Merkle trees with One-Time Signatures (OTSs) to make digital signatures that stay secure even once large-scale quantum computers show up 🔮. Their theoretical security is well understood, and it depends only on the security of the underlying hash function 💅. That makes Stateful HBS an important building block for quantum-resistant information and communication technology 🫶. They're specified in [RFC8391], [RFC8554], and NIST [SP.800-208], and we recommend Sections 1 and 3 of [SP.800-208] as background reading for this doc 📚.

Here's the tea 🍵: the private key of a Stateful HBS is a finite collection of OTS keys (usually generated on-demand from a seed) plus an associated data structure that keeps track of which OTS keys have been used. That data structure is typically a simple counter, often called an index, and this document calls it the state of the private key. Each Stateful HBS private key can sign a finite number of messages, and the state must be updated with every single generated signature 💀.

Rule number one: one must not reuse any OTS key that is part of a Stateful HBS private key 🚫. If an attacker gets signatures for two different messages made with the same OTS key, it's computationally feasible for them to create forgeries [BH16] [Fluhrer23] 😱.

As noted in [MCGREW] and [ETSI-TR-103-692], extreme care should be taken to avoid the risk that an OTS key gets reused by accident 🙈. [MCGREW] identifies the fundamental failure modes of Stateful HBS and proposes architectural strategies, such as a reservation approach. [ETSI-TR-103-692] provides a broad analysis of state management challenges and risks. This document complements both by cataloging concrete operational patterns in Section 5, and by addressing backup and recovery considerations in Section 6 that aren't covered in prior work 🦋.

So why is careful state and backup management so essential? The challenges below explain it 👇:

  • Implementers must ensure that each creation of a signature updates the state correctly 🎯.
  • If the Stateful HBS private key is distributed to multiple signers at the same time, implementers must ensure that they never use the same OTS key. This may require synchronization between all signers 🔄.
  • Extra operational complexity shows up when part of the available OTSs are allocated to different devices (partial state transfer), or when state from different devices needs merging. These introduce risks of overlap and failure, and they require careful coordination 😵‍💫.
  • If key backups are required, implementers must ensure that any backup mechanism cannot lead to re-using a previously used OTS key 🥺.

The following sections present, recall, and discuss various strategies for correct state and backup management for Stateful HBS 🌟.

1.1. When are Stateful HBS Appropriate? 🌸

The state management issues above, plus (for most parameter sets) the limited number of signatures, lead to new requirements that most developers won't be familiar with and that need careful handling in practice. Stateful HBS are not general-purpose signature schemes 🙅‍♀️. Most applications, especially those that may produce unrestricted numbers of signatures, should use stateless hash-based signature schemes like SLH-DSA [FIPS205], which use the same security assumptions, or schemes based on other assumptions, such as ML-DSA [FIPS204] 💖.

However, if run time, implementation size, or signature or key sizes of stateless alternatives are prohibitive, and the specific use case allows very tight control of the signing environment, using Stateful HBS may be an appropriate solution ✨. It seems likely that in many scenarios, it's only possible to meet the requirements set out in Section 4 when using purpose-designed hardware, such as hardware-security modules 🔐.

Stateful HBS are already profiled or discussed in several deployment-focused specifications and guidance documents. For example, [RFC9802] discusses suitable use cases for stateful HBS in X.509, including firmware/software signing and CA certificates 📜. [CRYPTO-IoT] defines an asymmetric profile that uses HSS-LMS, giving an interoperability target for software/firmware update IoT ecosystems 🤖. And the NSA [CNSA2.0] allows LMS (and XMSS) in specific application scenarios, such as firmware/software signing 🇺🇸.

2. Specific Terminology in the Context of Stateful HBS 💅

This section defines the key notions that matter in the context of Stateful HBS 📖.

2.1. Private Key Components 🔑

This section describes the two conceptual components that make up the private key material used in Stateful HBS 🧩.

private key: The static, long-lived secret(s) from which the underlying OTS private keys are derived. This material is stateless. Given the scheme parameters, it deterministically defines the set of OTS private keys, but it doesn't change over time 🪨.

state: The dynamically updated data structure that records which OTS key indices have been consumed (often a monotone counter). This material is mutable and must change on every successful signature 🔄.

Conceptually, the private key and the state are distinct, and they should be handled accordingly. The private key is a static secret, while the state is mutable, evolves with each signature, and must be maintained with integrity and correctness 🛡️. In some implementations, these two components may be packaged together and not directly separable. In those cases, this document's guidance applies to the combined artifact 🫂.

2.2. State Management 🌙

In this document, state management refers to the handling and implementation of the state of the private key 🎀.

This includes mechanisms that aim to:

  • securely update the state before the signature is released,
  • set up Stateful HBS where the state is separated into distinct, non-overlapping parts, so that signatures can be generated from either part without risk of state reuse,
  • enable partial transfer of unused signature capacity between devices, and optionally merging state fragments without overlap,
  • enable effective but secure handling of private key and state backup material, and
  • guarantee the availability of both the private key and its state across the lifetime of the key 🗝️.

In particular, the state and private key might be inseparable in implementations of Stateful HBS or in alternative signature mechanisms. For example, puncturable schemes [BSW16] are one such alternative. They're research-level constructions and are not (at the time of writing) standardized or deployed in practice 🔬. Even so, this document's guidance should still apply in these scenarios 💜.

2.3. Backup Management 🎀

okay so, to protect against stuff like the device holding your key material dying (and to make disaster recovery less of a nightmare), backups of private keys and their associated states should be considered as part of a security architecture. 🫶

In this document, backup management refers to all mechanisms surrounding the goal of guaranteeing the availability of the private key and state. The big twist is the special care it takes to avoid state reuse, which means never rolling back to a state where already-used OTS keys are still available. Not me getting a do-over that breaks everything 💀

These mechanisms include procedures and protocols that aim to:

  • securely store this private key and state material outside the in-use signing device,
  • import an externally stored private key and state to a newly initiated signing device, and
  • allow practicing with backup recovery and to ensure backups are valid.

Backup management can be viewed as a more specific type of state management. The document makes this distinction to clarify the aims of our recommendations. ✨

2.4. Key Export, Key Import, and Key Transfer 🦋

okay this section is about the ways key and state material can move around: export, import, and transfer. These notions get defined more precisely so nobody gets confused, which is very much giving clarity 💅

key export: A mechanism of exporting secret data, which yields private key and state material, from the signing device to external storage.

key import: A mechanism of importing secret data, which loads private key and state material, from external storage to the signing device.

key transfer: A cryptographically protected transfer of ownership of private key and state material from one signing device to another.

Systems and architectures relying on key transfer are generally expected to require fewer operational and manually-executed steps and checks to avoid state reuse. Why? Because the transfer mechanism can provide controlled handover of key and state material, instead of relying on separate export, storage, and re-import procedures. Lowkey so smart 🧚

Note that, at times, secure variants of the aforementioned primitives may be required (e.g., securely importing/exporting the key). In these situations, cryptographic mechanisms should be utilized to provide assurances related to the confidentiality (e.g., utilizing symmetric or asymmetric encryption mechanisms) and/or integrity/authenticity (e.g., utilizing digital signatures, hash functions, and keyed message authentication codes) of the associated operations. 🔐

3. Operational Considerations ✨

3.1. Assessing Operational Costs 💸

An important aspect of evaluating the various HBS state and backup management options is considering the operational costs attached to each one. Main character budgeting energy 💅

In the past, a conventional trust infrastructure solution could use straightforward archival procedures to make copies of the keys. Those copies could then be distributed geographically to ensure their availability and deliver a sufficiently resilient solution, all while enforcing whatever security protocols and procedures were required. Unfortunately, Stateful HBS introduce an additional constraint: they need to ensure the state is never reused. 😭 So archival procedures used for conventional trust infrastructures have to be amended (including redesigned) before they can be viable options.

3.2. Ensuring Long-Lived Resilient Solutions 🌈

One of the most problematic parts of a long-lived resilient solution is simply managing the physical media on which the keys and state are stored externally (i.e., outside of the signing device) throughout the course of their lifetime.

Physical media and devices degrade over time, and the more complex the media or device is, the more likely it is to fail at some point (e.g., data stored on a CD vs. data stored on a USB drive vs. data stored in a Hardware Security Module). Now combine that with the long lifetimes associated with Stateful HBS keys (e.g., 10-20+ years) and the difficulties of transferring keys between devices. You end up with a seriously perplexing set of challenges that has to be accounted for in any state selection process for a proper state and backup management solution. 🙈

Compounding all of this, any resilient state management system should also provide some means to verify the integrity of these long-lived backups. That way they will be valid when they are required, and the operators know how to execute the necessary recovery procedures. 🫶

3.3. Training and Skills 🎓

Many of the prescribed state management options require a high degree of operator involvement, so one should consider the costs associated with training the operator element. This training is needed to ensure processes and procedures are adhered to, and that failures are caught early and corrected before a catastrophic loss of security can occur (e.g., accidentally instantiating multiple instances of a Stateful HBS key/state). Yikes, one oopsie and it's over 😱

Training is not a fixed one-time cost either, as long lifetimes will necessitate succession planning amongst the operator element and training of each successive generation of participants. Mechanisms should be put in place to mitigate the ever-present insider threat. These include M-of-N controls, least-privileges amongst participants, and a separation of duties, which ensure that an attack would require collusion by multiple parties. 🕵️‍♀️ The separation of duties must persist across successive generations to ensure participants do not acquire multiple roles over time, thereby undermining the intended separation. Nobody gets to be the whole squad 👑

3.4. Configurable Warning Thresholds ⭐

In addition to the state management, implementers may consider implementing mechanisms to prevent abrupt signature exhaustion. Think of it as a heads-up before the tea runs out 🍵

Implementations may consider providing a configurable warning threshold, M, which is triggered when M signatures remain. When the number of available signatures reaches this threshold, the system should return a 'signatures nearing exhaustion' warning. This warning condition should require explicit acknowledgment from the user through a mechanism that cannot be trivially skipped. No sneaky click-through, bestie 🙅‍♀️

In distributed or partitioned deployments (e.g., sectorized or multi-tree architectures), warning thresholds may apply per device, per sector, or per subtree rather than globally. In such systems, coordination mechanisms may be required if a global exhaustion condition must be detected. In centrally managed deployments, warnings may be directed to system operators or management services rather than end users. The mechanism for acknowledging or acting upon such warnings therefore depends on the operational model and need not involve the end signer directly. 🦋

3.5. Selection of Appropriate Parameter Set 🧩

Another important consideration when deploying Stateful HBS is selecting an appropriate parameter set. 💖

Given the flexibility of these schemes -- such as adjustable tree heights or Winternitz parameters -- there is a huge variety of possible configurations. These configurations offer many trade-offs between signature generation/verification time, signature size, and key generation time. Hence, careful attention during the design phase is essential so that the chosen parameter set lines up with the specific requirements of the intended use case. It's giving pick-your-own-adventure, but every choice matters 🌸

3.6. External Dependencies 🌐

Costs associated with any external dependencies a particular solution needs (e.g., access to a public ledger or transparency log, providing accurate time references and synchronization mechanisms, access to attestation facilities, etc.) must be accounted for as well. This is especially true if a system is operating in an offline mode, which makes delivering these extra capabilities even more complicated and expensive. 💜

4. Requirements for Secure State Management ✨

okay bestie, so if you're deploying Stateful HBS, you should fulfill some requirements so the state gets handled securely 🔐 The system must ensure that no two signing operations can ever be issued from the same state 🙅‍♀️ Also, making a signature and updating the state should look like an atomic transaction 💫 Translation: the system must not release a signature without irrevocably and correctly updating the state. no skipping the update, no cap 💅

State management systems should satisfy all ACID properties 💖

  • Atomicity: each operation on the state must be indivisible 🧩 It either commits completely or leaves the state unchanged.
  • Consistency: the state before and after each update must reflect a valid progression of available OTS indices, and no invalid or conflicting state is ever observable 👀
  • Isolation: concurrent or overlapping operations (e.g., from separate processes or devices) must not interfere in ways that could lead to state reuse 🙈
  • Durability: once a state transition (e.g., before issuing a signature) is committed, that transition must survive crashes, power loss, or device failure 💪

These requirements are a lot, and they put serious limits on the technical approach and on how carefully you implement the way state gets updated or synchronized 🫠 Modern abstraction layers can make it super hard to guarantee that no two versions of the same state exist. The main concerns are:

  • how the actual storage for the state is implemented,
  • how it is modified, and
  • how an accidental/intentional failure/glitch might affect the state security.

A system may keep a version of the private key in non-volatile memory (e.g., a disk) and load it into volatile memory (e.g., RAM) while it's processing. Here, an implementer must ensure that these are always perfectly synchronized [MCGREW], which means no other parts of the system are allowed to read any version of the key during procedures that are loading, writing, or modifying keys. It gets extra tricky if there are additional abstraction layers around, like extra caches that can affect reading and writing the state and where it might end up existing in multiple locations 🌀

Cloning is another big concern 😭 because it can easily lead to re-using the same state. This can happen, for instance, if a process that issues a signing operation gets forked and no proper synchronization is enforced in the implementation to guarantee a correct state update. Virtual Machine (VM) cloning is another potential security risk here, since both backing up a VM into non-volatile memory and live cloning a VM can easily lead to a state reuse [MCGREW]. And with users shifting workloads to cloud service providers, VM cloning may become more prevalent ☁️

Using dedicated cryptographic hardware is recommended to enforce these requirements, ensure correct behavior, and handle the complexity of state management 🔧 In particular, it enables implementing rollback resistant counters, which can be hard to pull off in a software-only fashion 🧚

On the verifier side, no state management is required 🎉 However, the verifier needs to trust the signer to not have reused the state. A verifier may want to check that no state reuse happened in the past by a signer before accepting a signature 🕵️‍♀️

In practice, this can be done if the verifier has access to all signatures issued by the signer. Since the signatures contain the index of the OTS key used, detecting if an index was used more than once becomes trivial 🧠 In practice, a (public) data structure that contains all signatures may already exist in some use cases (e.g., Certificate Transparency [RFC9162]), or it could be built. It's worth noting that trusting the signer to not reuse the state is a strong assumption 😬 but other signature schemes, like the Elliptic Curve Digital Signature Algorithm (ECDSA), introduce similar assumptions by requiring the signer to never reuse the nonce.

5. Potential State Management Approaches 🦋

There are a bunch of potential solutions, some proposed within the [SP.800-208] specification and some from external sources 📚 This section walks through a number of these approaches and their potential advantages and disadvantages.

Every approach comes with trade-offs in complexity, cost, and operational risk ⚖️ The goal here is to analyze those trade-offs, not to recommend one universally applicable solution. no single answer fits everyone, bestie 🫶

5.1. Multiple Public Keys (SP 800-208)

[SP.800-208] proposes generating multiple Stateful HBS key pairs and configuring devices and clients to accept signatures created by any of these keys 🔑 Secondary Stateful HBS keys can be kept in storage until the first keypair is exhausted or lost.

Accepting multiple public keys is kind of a downer for one of the best parts of Stateful HBS, because it increases the public key footprint within the client 📉 That can be a problem if the client has limited public key storage capacity. (Though public keys are typically equivalently sized to ECDSA, rather than the larger classical RSA keys we often still see today 🤏) [SP.800-208] tackles storage capacity concerns by suggesting a mechanism such as the one proposed in [RFC8649], which updates the stored public key by having the current key endorse the next key that is to be installed. Unfortunately, for many constrained devices the public key is embedded in immutable ROM or fuses for security reasons, so it cannot be updated this way 😤

Using multiple Stateful HBS key pairs for a single instance also raises questions about how to establish that approach in existing public key infrastructures 🏗️ For example, issuing multiple certificates adds the storage needs of the certificate material to the public key footprint. If you wanted to issue multiple public keys encoded inside a single certificate instead, you'd need a standardized format, if interoperability is a concern 🎀

5.2. Distributed Multi-trees (SP 800-208)

[SP.800-208] also proposes creating multiple Stateful HBS keys across multiple cryptographic modules, using a distributed multi-tree approach. It's a variant of the standard hyper-tree-based Stateful HBS schemes, HSS and XMSS^MT 🌳

This architecture reflects the constraints in [SP.800-208], which does not permit export of private key material from cryptographic modules 🔒 The split between root and subordinate devices lets you comply with this non-export model while still keeping a hierarchical signing structure. so clean 😌

Trees get instantiated on a root device (HSM_root) and one or more subordinate devices (HSM_({sub_i})). The root tree is used to sign the root nodes of the subordinate trees, which synthesizes a multi-level Stateful HBS key 🧩 The root device is only ever used to sign subordinate device root nodes, while the subordinate devices are used to sign messages. This is relatively straightforward to do using HSS, and [SP.800-208] describes the necessary algorithmic modifications when using XMSS^MT ✨

One drawback is the increased signature size, since an additional OTS needs to be generated, effectively doubling the overall signature size 📈 Another concern is the single point of failure of relying on the root tree module to sign all of the subordinate trees. If the root tree device fails, no new subordinate trees can be signed 💀 [SP.800-208] suggested generating as many subordinate trees as possible during the initial root key generation and subordinate-signing procedure. Unfortunately, that can mean a huge capital expenditure to procure all the necessary devices, many of which may not get used for a long time, if ever 💸 The subordinate tree root node signing process also has to be managed really carefully: top-level trees should only ever be used to sign the root nodes of trusted/approved subordinate trees, so that no malicious signing request gets accepted. Otherwise a rogue entity could generate valid signatures, which would undermine the security of the entire system 🚨

Heads up, this one's serious: if a rogue entity gets a malicious signing request accepted, it can generate valid signatures and undermine the security of the whole system.

[SP.800-208] also suggests combining distributed multi-trees with multiple root public keys, as a way to mitigate some of the concerns about having a single point of failure in the root tree 🛡️ However, even if a system operator does everything right, use cases with exceptionally long lifetimes of 10-20+ years (e.g., automotive and aerospace/satellite applications) will require operators to rely on devices well beyond their expected lifetimes of 5-10 years. That may constitute an unacceptable business risk 🥺

5.3. Sectorization 🧩

Okay so distributed multi-trees split up a Stateful HBS signing space between multiple cryptographic modules by slicing it along the boundaries of the subordinate trees that get made during the multi-tree key generation process 🌸. A different approach (lowkey iconic too) uses the state reservation concept from Section 5 of [MCGREW]. You keep just a single tree and split its signature space along some power-of-2 that's less than the total number of leaves in the tree (e.g., 2^s for a tree of height h > s) 💅. That makes N = 2^(h-s) partitions, or sectors, and each one is set up as N height-s Merkle trees whose root nodes count as interior nodes of the overall height-h Merkle tree 🦋.

Here's the best part: there's no extra OTS needed to sign their root nodes! Their values get used as-is in the tree ascent mechanism of the underlying Stateful HBS scheme, so every sector ends up sharing one common public key (i.e., root node) ✨. Care must be taken to make sure each sector uses the same root tree identifier (i.e., the "I" value for HSS/LMS and "root" value for XMSS/XMSS^MT) 🎀. Don't skip this part bestie, it's a big deal 🙈

Each of the N sectors' OTS private key values can be generated pseudorandomly from a unique seed value, which comes from an appropriate source of randomness 🌈. The private keys from different sectors are independent when generated this way 💜.

Now the tea: each sector needs the path information for its own root node (that's all the off-path nodes between the sector root node and the top level node value) stored right alongside its private key at key generation time 🍓. Why? Because a sector won't know the seed information it would need to compute any of the other sectors' root nodes during the tree ascent phase of a signature generation operation 😭. So during signature generation, the signer appends the stored path information to the path information it computes to climb from the leaf OTS up to the sector's root node. It can compute that part itself since it knows its own seed value 🧚

So, sectorized key generation gives you a single public key value and 2^(h-s) private key values, and each of those can make 2^s signatures before the sectorized key is exhausted 👑.

Here's why this is so slay. Beyond not increasing the signature size, when unique seeds are used, sectorization breaks a Stateful HBS key/state into multiple independent fragments that can be managed as independent objects 🦋. That means system operators can spread sectors across multiple cryptographic devices, which gives you scalability through parallelization and better resiliency/availability ✨. Each sector is isolated from the others, so a compromise in one doesn't extend to the rest. That's real damage containment 🛡️. And operational robustness gets easier too, because there's no need for cross-device state coordination since each sector is restricted to its own signature space 💅.

5.4. Key/State Transfer 🚚

Okay, so Stateful HBS key/state transfer between cryptographic modules means having a way to migrate one instance of a Stateful HBS key/state from a source device to a separate destination device, while making sure any copy of that key/state gets deleted from the source device 🫶.

This can help with the earlier worry about running devices past their expected lifetimes 😩. Operators can move Stateful HBS key/state over to a newer device when the original one starts approaching its end-of-life. BUT (and this is a big but) it still leaves the operator exposed to the source device failing before the key/state gets transferred, which would basically mean losing the key/state entirely 💀. So it won't be much help with the single point of failure issue we talked about for root trees, though it may be useful for managing subordinate trees 🌸.

Besides complete key/state transfer, a device holding part of the total available OTSs can transfer some of its unused capacity to another device (that's partial state transfer) 🍓. In more advanced setups, state fragments from two devices may even get merged to reconstruct or continue signature operations 🧩. Not gonna lie, these operations are risky 😬. You have to make sure there's no overlap in used indices, keep the transfer or merge operations atomic, manage consistency, deal with possible conflicts, and keep the state durable across devices. These approaches need robust synchronization, auditability, and appropriate backup mechanisms to avoid double-signing or loss of capacity 🚨.

A more elaborate variant of key transfer goes beyond what [SP.800-208] allows. It's described in Section 6, where key transfer happens through a two-step export and import process with hash-based transfer validation, which gives you a more robust transfer mechanism 💖.

5.5. Key Rotation 🔄

Key rotation, like the one defined in [RFC8649], would generate new Stateful HBS keys on an as-needed basis. It gives you a way to switch the system over to the new Stateful HBS key while generating the next key in the chain, getting ready for a future rotation/update 🌈. However, ngl, this just shifts the problem over to the PKI and certificate handling 🙃.

In most use cases, key rotation isn't foolproof, because it requires redundancy to make sure there's at least one Stateful HBS signing key available to attest to newly generated keys 🫠. On top of that, for many applications, the device keys can't be updated because of engineering constraints or security reasons 🔐.

5.6. Variable-Length Signature Chains ⛓️

A variant of the key rotation approach is to have an available signing tree endorse a new subordinate tree when it's about to get exhausted. For example, it uses its final OTS to sign the root node of a new subordinate tree, which creates an {n+1}-layer multi-tree from an {n}-layer multi-tree 🦋. In theory, you can repeat this as many times as you need. BUT this means having a multi-tree scheme with a variable number of levels, and therefore variable-length signatures 😵. Dynamically extensible constructions like this are research-class and aren't currently standardized or deployed 🧪.

Also, this approach departs quite significantly from the current Stateful HBS specifications and [SP.800-208], and it has a bunch of significant challenges on both the engineering and operational fronts 🙈. Firstly, the variable-length nature of the signature can lead to variable-length verification of signatures, which can cause big issues for use cases with strict time constraints (e.g., secure booting of a semiconductor device) ⏱️. From an operational perspective, a subordinate tree's ability to sign either messages or new subordinate trees leads to severe security implications. The rigor around authorizing those two types of operations varies wildly, which means you end up with either a much more onerous message signing operation or a much riskier subordinate tree signing operation 💀. This approach may put the system operator in an untenable situation where no users are satisfied with the resulting solution, so it should not be considered as a viable solution 🚫.

5.7. Pre-Assigning States 📅

In some applications, individual one-time signatures (or states) can be pre-assigned to the to-be-signed objects 🎀. This may be possible if the signed objects are monotonically increasingly numbered, and software signing is one example of that kind of use case 💿. Basically, this solution externalizes the state management to the to-be-signed messages 🧠.

Let's expand on that software example 🍰. For software released with strictly increasing, simple, single-position version numbers (i.e., versions 1, 2, 3, ...), this can be trivially implemented 😌. Each version has a one-to-one correspondence to a Stateful HBS signing state, so operators have to make sure versions can only be minted a single time 🔒. That might mean skipping version numbers if a release process failed, just to avoid double-signing 🙈.

This scheme can be adapted to more complicated release schemes too 💫. For instance, minor update-releases 1.0 to 1.99 can be accommodated by assigning signatures 1-100 to these version numbers, while release 2.0-2.99 would get signatures 101-200 🌸. The assignments must be fixed as the scheme is set up, and operators should take into account that they're strictly limiting the number of update releases 📉. In this solution to state management, you have to move up a major release number after 99 minor releases, even if that would break, e.g., semantic versioning conventions 😭. Fair warning ⚠️.

A variant of pre-assigning signatures is doing this on the basis of time, which is described in the next section ⏰✨.

5.8. Time-Based State Management ⏰

okay so, as a twist on pre-assigning one-time signatures based on external counters, it's possible to pick the one-time signature indexes based on the current date and time 🕰️✨. For example, if a given Stateful HBS instance offers 1024 total signatures, they could be broken up into 8 groups of 128 OTS instances each. The first 128 are allowed in the first time window, the second 128 in the second window, and so on, until the signature space is effectively exhausted after 8 time windows 🍓. Heads up though: a time-based approach will "waste" any OTS keys that go unused in past time windows 💀. You must not try to use those keys after their window has gone by.

Any time-based approach has a very strict reliance on accurate timekeeping and synchronized clocks 🫶. Literally the whole thing depends on it. These are the engineering challenges we need to think about (at least):

  • Signing devices must have accurate timekeeping (which is a very challenging engineering problem [TIMEFALSEHOODS]).
  • Time on signing devices must not be allowed to ever move backwards, as this can cause double-signing. Time travel is not it, bestie 🙅‍♀️.
  • Within time windows, signers must track the number of signatures produced to ensure it does not exceed the number allowed within the window.
  • Signing devices must still operate consistently with the requirements of state keeping for Stateful HBS. The signature index within a time window should still appear to be updated atomically, and signatures must not be released before state changes have been recorded.
  • A system should be robust against exhaustion of the number of signatures available in a time window. In this case, it is required to wait until the next time window starts before new messages can be signed ⏳.
  • Time on signing devices should not be allowed to be moved forward maliciously or accidentally, which would allow for a simple denial-of-service attack by skipping over portions of the signature space 🚫.
  • If a signing device needs to be replaced, the replacement device must be set up with its time in sync with or ahead of the device it is to replace. This implies the current time on signing devices should be continuously recorded 📝.
  • Rate limiting may need to be considered, as exhausting the available signatures in a given time window may otherwise be easy 😬.
  • It may be necessary for signers to keep a separate clock for time-based state management, and another one for a not necessarily monotonically increasing "wall-time", e.g., if signed artifacts are expected to be time-stamped with real-world time ⏰.
⚠️ If these concerns cannot be sufficiently addressed, time-based state management as described in this paragraph should not be used. And note that this list is not exhaustive. Other, unmentioned, concerns may also be relevant to the security of a time-based solution 🙈.

Time-based systems can be backed up by simply recording the private keys and the configuration of the time windows 💾. If a signing device is lost, a time-based state management system can be recovered by using this information to bring a new device online in the next time window 🧚. This approach may also be used as a recovery mechanism in the case of (suspected) state consistency problems during a time window. However, the operator must not allow new signatures to be produced before the new time window starts, unless they know the exact state at which the previous device became unavailable and are able to set up the new device accordingly. Waiting until the start of the next time window avoids double signing, as the OTS keys assigned to future time windows are guaranteed to have not yet been used 🔒. However, this might incur significant downtime of the signing systems 😭. Downtime may be avoided by forcibly moving the signing device to the next time window by incrementing its clock. However, this induced clock drift will then need to be accounted for in the future. If clock drift is to be avoided, this approach should account for availability considerations 🎀.

5.9. Interval-Based Approaches 🦋

The State Reservation Strategy described in Section 5 of [MCGREW] is another way to manage state. It lets users reserve intervals of the signing space, marking the interval's associated OTS keys as used in the overall HBS state. That state is then written back to non-volatile memory prior to their usage. The OTS keys within the reservation interval are then consumed as-needed, without having to update the state again until they have all been consumed and additional OTS keys are required 🧁. Note that the reserved OTS keys are kept in dynamic memory, so they will be lost if the signing device loses power or is reset. That results in a reduction in the number of usable signatures for a given HBS instantiation 😵.

Over provisioning can be used to ensure a sufficient number of signatures is available in the presence of unexpected losses due to power loss or resets. Over provisioning will cause a minor increase between 2% and 12% on signature length, as the MTS validation paths increase to accommodate the increased Merkle tree height 📏. However, reservation eliminates the need to update the state after each OTS key is used, which minimizes the likelihood of state reuse due to state update failures and coherency issues 💅.

In theory, multiple signing devices can use reservation intervals to carve out portions of the signing space. That way, a single Stateful HBS key can be shared amongst multiple devices, leading to potential performance and disaster-recovery benefits 👑. However, great care must be taken to manage the reservations so there is no overlap or repeated reservation of a given interval, either in part or in whole 🧐.

6. Backup Management Beyond NIST SP 800-208 🎀

This section presents, in a generic form, an alternative backup mechanism for Stateful HBS. It makes the strategy applicable for both multi-tree instances XMSS^MT and HSS. However, following the same arguments as in Section 5.3, with minor modifications, the presented strategy is also applicable for single-tree instances such as XMSS and LMS 🌈.

The strategy presented in this section builds upon the multi-tree variant approach from [SP.800-208] and aims to mitigate its limitations, described in Section 5.2. Thus, it is assumed that a top-level Merkle tree (for signing the root-nodes of sub-trees) and several bottom-level Merkle trees (for signing messages) are already instantiated. These bottom-level trees may be implemented on different hardware modules in order to obtain redundancy and improve availability 🛡️. Let R be the number of these already initiated bottom-level trees. Let h_0 be the height of the top-level tree. It is assumed that R + 1 is strictly smaller than 2^(h_0), the number of leaves of the top-level tree.

In this new strategy, after the completed key generation procedure from the multi-tree variant approach from [SP.800-208], further bottom-level trees are generated, one by one, in one of the hardware modules. These new bottom-level trees are each generated from a different seed, which is chosen uniformly at random 🎲. The following notations are introduced for the sake of clarity:

  • S denotes the number of these newly generated bottom-level trees. Note that at most 2^(h_0) - R new bottom-level trees can be generated, i.e., S is lower or equal to 2^(h_0) - R. In the following we suppose that S is strictly smaller than 2^(h_0) - R.
  • I_new denotes the set of indices that belong to these newly generated bottom-level trees, i.e., I_new = {R, R+1, ..., R+S-1}. Bottom-level trees are indexed starting at 0.

For each new bottom-level tree, after it has been generated, the following steps must be performed 📋:

  • sign the corresponding root node with an unused OTS key from the top-level tree,
  • securely key export (as described in Section 2.4) the seed, which was used to generate the bottom-level tree,
  • export the signature of the root node, the corresponding OTS key index, and finally the hash of the seed, using appropriate domain separation (i.e., ensuring there is no domain overlap with the hashes in the Stateful HBS scheme, and that the hash of the seed includes the public key and leaf index to mitigate multi-target attacks), and
  • irreversibly delete the seed and the bottom-level tree from the hardware module.

The newly generated bottom-level trees (i.e., those bottom-level trees whose indices belong to I_new) are only used to guarantee availability in the worst-case scenario 😱. That's where, at the same time, both of the following conditions hold:

  • none of the R bottom-level Merkle trees (which were generated according to the multi-tree variant approach from [SP.800-208]) are available for signing messages, and
  • the top-level Merkle tree (which is used for signing the root-nodes of sub-trees) is also not available anymore.

For example, this scenario may happen if all hardware modules are broken at the same time 💥.

As soon as this worst-case scenario occurs, the newly generated bottom-level trees (i.e., those whose indices belong to I_new) need to be initiated in order to ensure availability. To do this, the following steps must be performed 🛠️:

  • initiate a new hardware module,
  • securely key import (as described in Section 2.4) the first unused seed into this hardware module,
  • generate the bottom-level tree corresponding to the seed,
  • irreversibly delete the seed from the backup medium, and
  • perform a correctness check by letting the hardware module output the hash of the seed.

Now this bottom-level tree can be used to sign messages ✍️. As soon as no more OTSs on the bottom-level tree are available, or as soon as the hardware module is broken, the above steps can be repeated with a new seed from the backup medium 🔁.

Note that the resulting signatures generated from these backed-up seeds do not require any special processing on the verifier side 🙌. The signature stored alongside the backed-up seed, and the signature generated from the bottom-level trees created from the backed-up seed, can be combined to match the format of a signature over the complete tree 🧩.

7. Security Considerations 🔐

Security considerations are given throughout this document. Further security considerations, which are not already covered in this document, are given in [SP.800-208], [MCGREW], [FIPS205], [RFC8391], and [RFC8554]. Seriously, bestie, do not skip these references 😤🔥.

8. IANA Considerations 🌸

This document has no IANA actions.

9. References ✨

9.1. Normative References ✨

okay these are the must-reads, bestie 📚💅 the spec leans on all three, so no skipping

9.2. Informative References ✨

these ones are the extra reading 🧚 the deep-dive shelf for when you're obsessed (same, honestly)

Acknowledgments ✨

this part is so sweet 🥹🫶

This document was inspired by discussions at the 2nd Oxford Post-Quantum Cryptography Summit 2023.

We gratefully acknowledge Melissa Azouaoui for her input to this document.

The abstract and the introduction are based on the introduction in [HBSX509]. Thanks go to the authors of that document. "Copying always makes things easier and less error prone." - [RFC8411]

Contributors ✨

the people who helped make it happen 💜

Jeff Andersen, Google

Bruno Couillard, Crypto4A Technologies

Stefan-Lukas Gazdag, genua GmbH

Authors' Addresses ✨

the legends behind the spec 🌈👑

Thom Wiggers, PQShield, Netherlands. Email: thom@thomwiggers.nl

Kaveh Bashiri, BSI, Germany. Email: kaveh.bashiri.ietf@gmail.com

Stefan Kölbl, Google, Switzerland. Email: kste@google.com

Jim Goodman, Crypto4A Technologies, Canada. Email: jimg@crypto4a.com

Stavros Kousidis, BSI, Germany. Email: kousidis.ietf@gmail.com

📦 where this page comes from