Support for stateful-hash-based signature verification (HSS/LMS, XMSS, and XMSS^MT)

[athoelke]

Prior to the standardization of ML-DSA and SLH-DSA, stateful-hash-based signature algorithms were developed, and then described in NIST Special Publication 800-208. The algorithms are:

• LMS and its multi-level variant HSS/LMS. These are described in RFC 8554
• XMSS and its multi-level variant XMSS^MT. These are described in RFC 8391

These schemes are not vulnerable to quantum computing, and are based on the well-established security of cryptographic hash algorithms. They also have relatively small public keys and signatures (for PQC signature schemes), and relatively simple implementation requirements. However, they are based on one-time-signatures (OTS), and the security critically depends on never reusing any of the set of OTS private keys. This requirement is met by having a stateful private key, that records which OTS private keys have been used.

The implication of a stateful private key, is that deploying systems which use them have substantial system challenges related to throughput, resilience and redundancy. The security and footprint attributes of these schemes (compared to other PQC signatures) make them attractive for some specific use cases at this point in time. For example, authentication of initial stages of constrained system firmware, where the authenticating component and authentication public key are immutable.

The use case of firmware verification can be supported without needing an implementation to deal with the challenge of handling a stateful private key: the Crypto API could define suitable public-key types and signature algorithms, that can only be used with signature verification functions.

[athoelke]

The IETF LAMPS draft standards relating to these algorithms' use in X.509 and CMS, only define algorithm identifiers for HSS/LMS, XMSS, and XMSS^MT. There is no definitions for stand-alone LMS, but single-level HSS/LMS is a trivial wrapping of LMS.

See:

• https://datatracker.ietf.org/doc/draft-ietf-lamps-x509-shbs for the draft X.509 support for HSS and XMSS.
• https://datatracker.ietf.org/doc/draft-ietf-lamps-rfc8708bis for the draft CMS support for HSS/LMS

I propose to follow that approach, and not define key types or algorithm identifiers for just LMS.