PQ News

Sometimes you’re in a room with a group of people, thinking about some problem in the world, thinking aloud: “Would it not be nice if someone sat down and wrote about how to solve these problems?”. In this case, “sometime” 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. Only this time, the people in the room actually sat down to write.

Hash-based signatures

Hash-based signature schemes are one of the classes 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. 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 one is that they just have so many keys that the chance that, when picking randomly, you pick the same one twice is very small. The downside is that stateless schemes have much larger signature sizes.

US standards authority NIST and internet standards organisation IETF both already standardised stateful hash-based signature schemes XMSS and LMS [1, 5, 6], and stateless scheme SPHINCS+ will be standardised 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 organisations start signing new software and firmware as soon as 2025.

This aggressive timeline also means that one bound by CNSA 2.0 can not 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 (as 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. Though 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 specially 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 organisations: requiring HSMs is not useful for those who can not afford one (even if the recommendation is very sensible and we suggest following it!), and the ban on key export makes deploying systems that rely on hash-based signatures very challenging: it makes ensuring reliability very difficult as it effectively bans backups. However, because we need to keep track of the number of signatures produced, state management and backups are very complicated anyway.

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 (for example, mapping software version numbers onto the one-time-use keys) or selecting the one-time-key based on the current time (handling time in software turns out to be very difficult). 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 initialised with the keys maybe 10 years ago.

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, and Google’s Stefan Kölbl and Jeff Anderson, as well as all those with whom we had discussions in Oxford and afterwards.

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.

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. Announcing the Commercial National Security Algorithm Suite 2.0. National Security Agency (2022). https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF
6. 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.
7. 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 Standardisation (SSR 2016). Springer LNCS (2016). https://eprint.iacr.org/2016/357