Stateful Hash-Based Signature Schemes – Hidden Champions of Post Quantum Cryptography

A light introduction to stateful hash-based signatures, their suitability for quantum-resistance and how to solve the state handling challenge.  

The development of quantum computers is shaking up the crypto world: with traditional asymmetric algorithms such as RSA no longer considered secure in the long-term, leading institutions like NIST are in the process of defining new standards for alternative algorithms. For more information on this topic, see our article - The Quantum Revolution vs. Cybersecurity.  

This blog post discusses stateful hash-based signature schemes, a category of post quantum cryptography, their recommendations for PQC and how to solve the state handling challenge.

Stateful Hash-Based Signature Schemes – Status Quo and Algorithms

In addition to the PQC standardization process, NIST, BSI, and the CNSA 2.0 already recognize two mature algorithms as quantum-proof. In its Special Publication 800-208, NIST approved two stateful hash-based signatures schemes for post quantum cryptography:

• XMSS and the multi-tree variant XMSS-MT
• LMS and the multi-tree variant HSS

XMSS and LMS both are Merkle signature schemes.  

Curious about how stateful hash-based signatures can revolutionize your use case? Reach out to us today!

How It Works: The Basic Principle of Stateful Hash-Based Signature Schemes

Hash-based cryptography relies on hash functions to generate a public key by hashing a value x₀ several times, e.g. up to x₃.  

^{Using an array of hash values to generate a Private and Public Key Pair for One Time Signatures – Basic Idea}

Working with this array of hash values, the signer, knowing all the values, can use x₁ as the private key and sign a message with it. Knowing x₃ - the public key - the recipient can verify if the private key is valid by hashing x₁ and checking if it turns out to be x₃. However, this signature can only be used once, so the scheme is a One Time Signature (OTS) scheme.

^{Signing and Verifying message “1” using the hash string – Basic Idea}

Because it is more convenient to have only one public key and multiple private keys, Merkle signatures are built up on a tree structure:

_{Merkle tree with several One Time Signatures – Reduced Structure}

This structure allows to sign a limited number of messages to be verified with the same public key. The number of messages must be a power of two (such as 2, 4, 8, etc.). The height of the tree is logarithmic in the number of keys (many keys that form a relatively flat tree).

• To create the public key, first several private/public key pairs of a one-time signature method are generated.  
• Then, you calculate hash values of the public key for each key pair.  
• Next, a hash tree (or Merkle tree) is built using these hash values. The hash values are the leaves of the tree and combined in pairs and hashed repeatedly to form a binary tree. The whole tree can be made public (with exception of the private keys of course.) The public key is the tree's root, and its nodes serve as necessary information and are appended to the signature.
• The recipient can then verify a signature with only the pub key (because the helper data is part of the signature).

Stateful hash-based signatures have the greatest maturity of all PQC signatures and are therefore recommended for post quantum security by NIST, NSA and the German Federal Office for Information Security:

• NIST: Special Publication 800-208  
• NSA: Commercial National Security Security Algorithm
• BSI: Quantum-safe cryptography – fundamentals, current development and recommendations

Advantages and Disadvantages of Stateful Hash-based Signatures  

If stateful hash-based signature schemes are already mature, standardized, and quantum-proof, why is there any need for other alternatives that are currently being evaluated and selected in the NIST PQC standardization process?  

Well, the truth is that there are pros and cons for these signature schemes, and they will not be suitable for every use case.  

Advantages of stateful hash-based signature schemes:

• Mature and proven algorithms
• High level of security  
• Relatively small key sizes make them simple, fast, and efficient
• Signing and verification require minimal computation effort  
• Can be used as standalone algorithm (no need for a hybrid implementation)

For these reasons, stateful hash-based signature algorithms such as LMS or XMSS are ideal for use cases where digital signatures need to be quantum-proof already today.  

Disadvantages of stateful hash-based signature schemes:

• Keeping track about which OTS values / keys have been used can be difficult (state handling)
• Accidental reuse of an OTS key could lead to forgery
• Risk of running out of keys (signatures)
• Number of signatures needed should be estimated in advance (higher efficiency, due to smaller key sizes)
• Not considered suitable for general use by NIST, only for applications where the use of the private key can be carefully controlled

The good news: There are ways on how to overcome most of the disadvantages.

Recommended Architecture Design for stateful hash-based signatures

Step 1: Solve the limitation factor

There are ways on how to solve the limitation challenge (If you already have a good estimate of how many signatures you need, this is not even necessary.)

Option 1: Build up a forest

Enhance the tree structure with another layer of keys (signing keys do not sign the message, but the key, that is the root of another key). This will, however, create larger signatures and thus lower efficiency.

Both LMS and XMSS offer proven multi-tree variants: HSS and XMSS-MT.

Option 2: Change the public key

Establish a secure and reliable procedure for key substitution of the public key.

Step 2: Solve the state handling challenge with a proper HSM architecture

Most of the drawbacks listed above are due to the challenge of state handling, i.e., keeping track of which OTS keys have already been used. In addition, backup management can get in the way of state tracking. When an old state is restored through a backup and restore process, old OTS keys may be restored even though they have already been used. If these are used again, forgery attacks are possible.

In effect, the backup must be adjusted each time a signature is created, by deleting the OTS keys or flag them as “used”.  This continuous adaptation can be very complex and is particularly challenging in distributed organizations.

If there would be a way to overcome these challenges, the stateful hash-based signature schemes would be very attractive to build quantum-proof solutions already today, given their maturity.  

Utimaco has developed a solution to reliably handle the states with an appropriate state handling mechanism using multiple HSMs: A set of OTS values can be distributed across distributes sites, to the respective HSM. By that, the HSMs and the individual sites are independent of each other without the need to constantly exchange information about which OTS values have already been used. And if one site runs out of OTS keys, a transfer can be triggered.

Further State handling design principles require:  

• Symmetric cryptography to be used for authentic and confidential end-to-end export and import of key / state information
• Establishment of a trusted connection between the HSMs  
• Prevent replays to keep the state up to date across all sites
• Prepare for offline data by allowing external key storage
• Separate keys and state information
• Establish asynchronous communication between HSMs

Following these principles, you will benefit from:

• Secure key transfer from one site (HSM) to the other minimizing the risk of key exhaustion
• Protection against attacks by blocking replay key transfers
• Minimizing risks by only importing small portions of the key and keeping the rest offline
• Loss is limited to a well-defined subset of the key

Contact our PQC expert team for a Proof of Concept

Conclusion – Stateful hash-based signature schemes provide robust quantum-resistant security  

Stateful hash-based signatures are an excellent and mature solution for implementing quantum-resistant digital signatures already today. By using Utimaco’s proper state handling architecture, several customers already successfully completed PQC migration projects for various use cases, from securing satellite communications to reliable firmware over the air updates.  

"The stateful hash based signatures (LMS and XMSS) provide the highest level of maturity. Hence, they are ideal candidates for use cases that require a high level of long term security or that have to be migrated as soon as possible.

Advisories such as the Commercial National Security Algorithm Suite 2.0 (CNSA2.0) by the US National Security Agency (NSA) recommend LMS and XMSS and highlight the urgency to migrate for specific use cases such as software and firmware signing from 2025 on.

With Utimaco, you have a partner that has already supported several early adopter organizations in their PQC migration with stateful hash-based signatures and lattice-based signature and encryption. And because our Hardware Security Modules are designed crypto-agile, we are already prepared for new algorithms and standards as they are released by NIST."

- Dr. Volker Krummel, PQC Chapter lead at Utimaco

Utimaco’s crypto agile u.trust General Purpose HSM Se-Series can be upgraded with proven PQC algorithms via the PQC extension Quantum Protect, which supports lattice and hash-based signatures schemes. We also follow the standards, participate in PQC working groups and committees, and continue to develop our solutions.  

Interested in how stateful hash-based signatures can be implemented for your use case? Contact us and we'll walk you through the technical details and see if it makes sense for your use case.