Key Takeaways
- Hash-based signatures are a conservative and well-understood post-quantum digital signature approach.
- Stateful schemes require careful state management to prevent key reuse.
- New IETF guidance helps organizations deploy stateful hash-based signature schemes more securely.
- Backup strategies and long-term operational planning are essential for successful deployment.
- PQShield contributed to the development of practical deployment guidance through the IETF draft.
Thinking openly: an IETF draft to help deploy stateful hash-based signature schemes
Sometimes you’re in a room with a group of people, thinking about some problem in the world, thinking: “Wouldn’t it be nice if someone wrote about how to solve these problems?”
In this case, it was September 2023, the room was the PQShield–co-organized Oxford Post-Quantum Cryptography summit, and the problem was how to practically manage the state of stateful hash-based post-quantum signatures. We asked. But this time, the people in the room really did sit down to write…
Hash-based signatures
Hash-based signature schemes are a class of quantum-safe digital signature schemes. Because their security only relies on that of secure hash functions (such as SHA2 or SHAKE/SHA3), which is very well-understood, they are a very attractive, conservative option.
Security considerations
The most important security downside is that the most basic building block of these schemes is a one-time signature. That means that we must carefully avoid using them more than once.
In stateful schemes, this re-use is avoided through simply counting the number of signatures produced: the first message is signed with key 1, the second is signed with key 2, and so on. However, accurately keeping track of this counter immediately becomes extremely important as a single mistake will result in key re-use.
Stateless hash-based signature schemes use some tricks to avoid having to keep track of the state, but the most important factor is that they just have so many keys that the probability of randomly picking the same one twice is very small. The downside is that stateless schemes have much larger signature sizes.
Standards and deployment considerations
US standards authority NIST and Internet standards organization IETF both already standardized stateful hash-based signature schemes XMSS and LMS [1, 5, 6], and stateless scheme SPHINCS+ will be standardized as SLH-DSA in FIPS 205, the draft version of which has been available for comments for some time now [4].
The US National Security Agency’s “Commercial National Security Algorithm Suite 2.0” (CNSA 2.0) [7] recommends using stateful schemes for firmware and software signing, and pushes an aggressive timeline: they recommend organizations start signing new software and firmware as soon as 2025.
This aggressive timeline also means that one bound by CNSA 2.0 cannot wait for the stateless ML-DSA (Dilithium, [3]) and SLH-DSA (SPHINCS+, [4]) standards to be finalised. However, if you are not, stateless schemes are probably much safer and easier to deploy (we will describe the challenges posed by stateless schemes below) and as the authors of this document, we recommend using these alternatives if possible.
State management
Because keeping track of the state in stateful hash-based signatures is so important, deploying stateful hash-based signatures must be done very carefully. Although the abstract idea of “do not sign twice with the same key” is easily understandable, it turns out that the systems on which we typically run software make this very hard in practice.
McGrew et al. [2] already described that the way that caches on regular hard-drives work may result in write operations (i.e., updates to the counter) getting lost if the computer loses power, even if the computer was instructed to commit the operation to disk.
For these and other reasons, the NIST standard that specifies XMSS and LMS, SP800-208 [1], requires that they are implemented in purpose-designed hardware security modules (HSMs) and that the key and state information must never be permitted to leave the device (i.e., a ban on key export).
The challenges with SP800-208
NIST’s restrictions present challenges to many organizations. Requiring HSMs is not useful for those who cannot afford them, even if it is a sensible recommendation.
In addition, the prohibition on key export makes reliable deployments significantly more difficult because it effectively prevents traditional backup strategies. At the same time, because state must be carefully tracked, state management and backup procedures are inherently complex.
Recommendations for state management and backups in stateful hash-based signature schemes
This leads us back to the room of people at the PQC summit in Oxford. We got together to write down how to solve some of these problems with state management and backups, and also document what types of problems one faces when trying to design alternative ways of state management, such as:
- Using external counters: mapping software version numbers onto the one-time-use keys
- Selecting the one-time-key based on the current time: handling time in software turns out to be very difficult
Approaches within and beyond SP800-208
We make explicit which approaches can be done within the current constraints of SP800-208, as well as making suggestions to those designing systems that go beyond it.
One important takeaway from the document is that the nature of stateful hash-based signature schemes requires one to consider the complete lifetime of the system relying on them in advance. This even includes training staff to operate the HSMs that were initialized with the keys maybe 10 years ago.
The new IETF draft
This document, draft-wiggers-hbs-state – Hash-based Signatures: State and Backup Management, has now been submitted to the Internet Engineering Task Force (IETF).
Though PQShield’s Thom Wiggers’ name is part of the handle of this document as the designated herder of cats, we would like to emphasise the contributions of:
- German federal information security office BSI’s Kaveh Bashiri and Stavros Kousidis
- Crypto4A’s Jim Goodman and Bruno Couillard
- Google’s Stefan Kölbl and Jeff Anderson
- All those with whom we had discussions in Oxford and afterwards
Open collaboration
The IETF gives us a public forum to further discuss these problems and collect even more guidance for those looking to deploy stateful hash-based signature schemes. The IETF is extremely open (participating is simply joining a mailing list!) and we welcome those who have comments to submit them either on one of the mailing lists or through our project’s GitHub repository.
Learn more about hash-based signatures
If you’d like to learn more about hash-based signatures or how PQShield can help your organization prepare for post-quantum cryptography, get in touch with our team.
Frequently Asked Questions
What are hash-based signatures?
Hash-based signatures are quantum-safe digital signature schemes whose security relies on well-established cryptographic hash functions. They are considered one of the most conservative approaches to post-quantum digital signatures.
Why are stateful hash-based signature schemes difficult to deploy?
They require careful tracking of every signature produced. Reusing a one-time signing key can compromise security, making reliable state management essential.
Why does NIST recommend using HSMs?
NIST SP800-208 recommends hardware security modules because they securely manage both signing keys and state information, reducing the risk of key reuse or state corruption.
What is the purpose of the IETF draft on state management?
The draft provides practical guidance for deploying stateful hash-based signature schemes, covering state management, backup strategies and operational best practices.
How can PQShield help with post-quantum cryptography?
PQShield provides expertise, software and hardware solutions that help organizations prepare for post-quantum cryptography and implement standards-based quantum-safe cryptography securely.
References
1. Cooper, D.A., Apon, D.C., Dang, Q.H., Davidson, M.S., Dworkin, M.J., Miller, C.A.: Recommendation for stateful hash-based signature schemes. National Institute of Standards and Technology (2020). https://doi.org/10.6028/nist.sp.800-208.
2. Huelsing, A., Butin, D., Gazdag, S.-L., Rijneveld, J., Mohaisen, A.: RFC 8391: XMSS: eXtended Merkle Signature Scheme, https://datatracker.ietf.org/doc/html/rfc8391, last accessed 2024/02/20.
3. McGrew, D., Curcio, M., Fluhrer, S.: RFC 8554: Leighton-Micali Hash-Based Signatures, https://datatracker.ietf.org/doc/html/rfc8554, last accessed 2024/02/20.
4. National Institute of Standards and Technology: Stateless hash-based digital signature standard. National Institute of Standards and Technology, Gaithersburg, MD (2023). https://doi.org/10.6028/nist.fips.205.ipd.
5. National Institute of Standards and Technology: Module-Lattice-Based Digital Signature Standard. National Institute of Standards and Technology, Gaithersburg, MD (2023). https://doi.org/10.6028/nist.fips.204.ipd.
6. McGrew, D., Kampanakis, P., Fluhrer, S., Gazdag, S.-L., Butin, D., Buchmann, J.: State Management for Hash-Based Signatures. In: 3rd International Conference on Research in Security Standardization (SSR 2016). Springer LNCS (2016). https://eprint.iacr.org/2016/357