RFC 9802: Use of the HSS and XMSS Hash-Based Signature Algorithms in Internet X.509 Public Key Infrastructure
- D. Van Geest,
- K. Bashiri,
- S. Fluhrer,
- S. Gazdag,
- S. Kousidis
Abstract
This document specifies algorithm identifiers and ASN.1 encoding formats for the following stateful Hash-Based Signature (HBS) schemes: Hierarchical Signature System (HSS), eXtended Merkle Signature Scheme (XMSS), and XMSSMT (a multi-tree variant of XMSS). This specification applies to the Internet X.509 Public Key Infrastructure (PKI) when digital signatures are used to sign certificates and certificate revocation lists (CRLs).¶
Status of This Memo
This is an Internet Standards Track document.¶
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). Further information on Internet Standards is available in Section 2 of RFC 7841.¶
Information about the current status of this document, any
errata, and how to provide feedback on it may be obtained at
https://
Copyright Notice
Copyright (c) 2025 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://
1. Introduction
Stateful Hash-Based Signature (HBS) schemes such as the Hierarchical Signature System (HSS), eXtended Merkle Signature Scheme (XMSS), and XMSSMT combine Merkle trees with One-Time Signatures (OTS). This is done in order to provide digital signature schemes that remain secure even when quantum computers become available. Their theoretic security is well understood and depends only on the security of the underlying hash function. As such, they can serve as an important building block for quantum computer resistant information and communication technology.¶
A stateful HBS private key consists of a finite collection of OTS keys, along with state information that tracks the usage of these keys to ensure the security of the scheme. Only a limited number of messages can be signed, and the private key's state must be updated and persisted after signing to prevent reuse of OTS keys. While the right selection of algorithm parameters would allow a private key to sign a virtually unbounded number of messages (e.g., 260), this is at the cost of a larger signature size and longer signing time. Because the private key in stateful HBS schemes is stateful and the number of signatures that can be generated is limited, these schemes may be unsuitable for use in interactive protocols. However, in some use cases, the deployment of stateful HBS schemes may be appropriate. Such use cases are described and discussed in Section 3.¶
2. Conventions and Definitions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
3. Use Cases of Stateful HBS Schemes in X.509
As described in the Security Considerations in Section 10, it is imperative that stateful HBS implementations do not reuse OTS signatures. This makes stateful HBS algorithms inappropriate for general use cases. The exact conditions under which stateful HBS certificates may be used is left to certificate policies [RFC3647]. However, the intended use of stateful HBS schemes as described by [SP800208] can be used as a guideline:¶
stateful HBS schemes are primarily intended for applications with the following characteristics: 1) it is necessary to implement a digital signature scheme in the near future; 2) the implementation will have a long lifetime; and 3) it would not be practical to transition to a different digital signature scheme once the implementation has been deployed.¶
In addition, since a stateful HBS private key can only generate a finite number of signatures, use cases for stateful HBS public keys in certificates should have a predictable range of the number of signatures that will be generated, falling safely below the maximum number of signatures that a private key can generate.¶
Use cases where stateful HBS public keys in certificates may be appropriate due to the relatively small number of signatures generated and the signer's ability to enforce security restrictions on the signing environment include:¶
In each of these cases, the operator tightly controls their secured signing environment and can mitigate OTS key reuse by employing state management strategies such as those in Section 10. Also, for secure private key backup and restoration, adequate mechanisms have to be implemented (see Section 11).¶
Generally speaking, stateful HBS public keys are not appropriate for
use in end-entity certificates, however, in the firmware and software
signing cases, signature generation will often be more tightly
controlled. Some manufactures use common and well
In general, root CAs [RFC4949] generate signatures in a more secure environment and issue fewer certificates than subordinate CAs [RFC4949]. This makes the use of stateful HBS public keys more appropriate in root CA certificates than in subordinate CA certificates. However, if a subordinate CA can match the security and signature count restrictions of a root CA, for example, if the subordinate CA only issues code-signing certificates, then using a stateful HBS public key in the subordinate CA certificate may be practical.¶
4. Algorithm Identifiers and Parameters
In this document, we define new Object Identifiers (OIDs) for identifying the different stateful hash-based signature algorithms. An additional OID is defined in [RFC9708] and repeated here for convenience.¶
The Algorithm
The fields in Algorithm
- algorithm:
- this identifies the cryptographic algorithm with an OID.¶
- parameters:
- these are optional and are the associated parameters for the algorithm identifier in the algorithm field.¶
The parameters field of the Algorithm
4.1. HSS Algorithm Identifier
The OID and public key algorithm identifier for HSS is defined in [RFC9708]. The definitions are repeated here for reference.¶
The Algorithm
Note that the id
The public key and signature values identify the hash function and
the height used in the HSS tree. [RFC8554] and [SP800208] define these values, and additional identifiers can be registered in the "Leighton
4.2. XMSS Algorithm Identifier
The Algorithm
The public key and signature values identify the hash function and
the height used in the XMSS tree. [RFC8391] and [SP800208] define these values, and additional identifiers can be registered in the "Leighton
4.3. XMSSMT Algorithm Identifier
The Algorithm
The public key and signature values identify the hash function and
the height used in the XMSSMT tree. [RFC8391] and
[SP800208] define these values, and additional identifiers can be registered in the "Leighton
5. Public Key Identifiers
Certificates conforming to [RFC5280] can convey a public key for any public key algorithm. The certificate indicates the algorithm through an algorithm identifier. An algorithm identifier consists of an OID and optional parameters.¶
[RFC8554] defines the encoding of HSS public keys, and
[RFC8391] defines the encodings of XMSS and XMSSMT
public keys. When used in a Subject
This document defines ASN.1 [X680] OCTET STRING types
for encoding the public keys when not used in a
Subject
5.1. HSS Public Keys
The HSS public key identifier is as follows:¶
The HSS public key is defined as follows:¶
[RFC8554] defines the encoding of an HSS public key
using the hss_public_key structure. See [SP800208] and [RFC8554] for more
information on the contents and format of an HSS public key. Note
that the Leighton-Micali Signature (LMS) single-tree signature
scheme is instantiated as HSS with the number of levels being equal
to 1.¶
5.2. XMSS Public Keys
The XMSS public key identifier is as follows:¶
The XMSS public key is defined as follows:¶
[RFC8391] defines the encoding of an XMSS public key using the
xmss_public_key structure. See [SP800208] and [RFC8391] for more information
on the contents and format of an XMSS public key.¶
5.3. XMSSMT Public Keys
The XMSSMT public key identifier is as follows:¶
The XMSSMT public key is defined as follows:¶
[RFC8391] defines the encoding of an XMSSMT public key using the
xmssmt structure. See [SP800208] and [RFC8391] for more information
on the contents and format of an XMSSMT public key.¶
6. Key Usage Bits
The intended application for the key is indicated in the keyUsage
certificate extension [RFC5280]. When
id
When id
7. Signature Algorithms
The same OIDs used to identify HSS, XMSS, and XMSSMT public keys are
also used to identify their respective signatures. When these algorithm
identifiers appear in the algorithm field of an Algorithm
When the signature algorithm identifiers described in this document are used to create a signature on a message, no digest algorithm is applied to the message before signing. That is, the full data to be signed is signed rather than a digest of the data.¶
The format of an HSS signature is described in Section 6.2 of [RFC8554]. The format of an XMSS signature
is described in Appendix B.2 of [RFC8391], and the format of an XMSSMT signature is described
in Appendix C.2 of [RFC8391]. The octet
string representing the signature is encoded directly in a BIT STRING
without adding any additional ASN.1 wrapping. For the Certificate and
CertificateList structures, the octet string is encoded in the
"signature
7.1. HSS Signature Algorithm
The id
See [SP800208] and [RFC8554] for more information on the contents and format of an HSS signature.¶
7.2. XMSS Signature Algorithm
The id
See [SP800208] and [RFC8391] for more information on the contents and format of an XMSS signature.¶
The signature generation MUST be performed according to Section 7.2 of [SP800208].¶
7.3. XMSSMT Signature Algorithm
The id
See [SP800208] and [RFC8391] for more information on the contents and format of an XMSSMT signature.¶
The signature generation MUST be performed according to Section 7.2 of [SP800208].¶
8. Key Generation
The key generation for XMSS and XMSSMT MUST be performed according to Section 7.2 of [SP800208].¶
9. ASN.1 Module
For reference purposes, the ASN.1 syntax is presented as an ASN.1 module here [X680]. Note that as per [RFC5280], certificates use the Distinguished Encoding Rules; see [X690]. This ASN.1 module builds upon the conventions established in [RFC5912]. This module imports objects from [RFC5912] and [RFC9708].¶
10. Security Considerations
The security requirements of [SP800208] MUST be taken into account.¶
As stateful HBS private keys can only generate a limited number of signatures, a user needs to be aware of the total number of signatures they intend to generate in their use case; otherwise, they risk exhausting the number of OTS keys in their private key.¶
For stateful HBS schemes, it is crucial to stress the importance of correct state management. If an attacker were able to obtain signatures for two different messages created using the same OTS key, then it would become computationally feasible for that attacker to create forgeries [BH16]. As noted in [MCGREW] and [ETSI-TR-103-692], extreme care needs to be taken in order to avoid the risk that an OTS key will be reused accidentally. This is a new requirement that most developers will not be familiar with and requires careful handling.¶
Various strategies for a correct state management can be applied:¶
11. Backup and Restore Management
Certificate authorities have high demands in order to ensure the availability of signature generation throughout the validity period of signing key pairs.¶
Some usual backup and restore strategies when using a stateless signature scheme (e.g., SLH-DSA) are to:¶
For stateful HBS schemes, such straightforward backup and restore strategies will lead to OTS reuse with high probability as a correct state management is not guaranteed. Strategies for maintaining availability and keeping a correct state are described in Section 7 of [SP800208] and [S-HBS].¶
12. IANA Considerations
IANA has registered the following OID for the ASN.1 module (see Section 9) in the "SMI Security for PKIX Module
Identifier"
IANA has registered the following entries in the "SMI Security for PKIX Algorithms"
13. References
13.1. Normative References
- [RFC2119]
-
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10
.17487 , , <https:///RFC2119 www >..rfc -editor .org /info /rfc2119 - [RFC5280]
-
Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, DOI 10
.17487 , , <https:///RFC5280 www >..rfc -editor .org /info /rfc5280 - [RFC5912]
-
Hoffman, P. and J. Schaad, "New ASN.1 Modules for the Public Key Infrastructure Using X.509 (PKIX)", RFC 5912, DOI 10
.17487 , , <https:///RFC5912 www >..rfc -editor .org /info /rfc5912 - [RFC8174]
-
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10
.17487 , , <https:///RFC8174 www >..rfc -editor .org /info /rfc8174 - [RFC8391]
-
Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10
.17487 , , <https:///RFC8391 www >..rfc -editor .org /info /rfc8391 - [RFC8554]
-
McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10
.17487 , , <https:///RFC8554 www >..rfc -editor .org /info /rfc8554 - [RFC9708]
-
Housley, R., "Use of the HSS/LMS Hash-Based Signature Algorithm in the Cryptographic Message Syntax (CMS)", RFC 9708, DOI 10
.17487 , , <https:///RFC9708 www >..rfc -editor .org /info /rfc9708 - [SP800208]
-
Cooper, D., Apon, D., Dang, Q., Davidson, M., Dworkin, M., and C. Miller, "Recommendation for Stateful Hash-Based Signature Schemes", NIST SP 800-208, DOI 10
.6028 , , <https:///nist .sp .800 -208 doi >..org /10 .6028 /NIST .SP .800 -208 - [X680]
-
ITU-T, "Information technology - Abstract Syntax Notation One (ASN.1): Specification of basic notation", ITU-T Recommendation X.680, ISO/IEC 8824-1:2021, , <https://
www >..itu .int /rec /T -REC -X .680 - [X690]
-
ITU-T, "Information technology: ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)", ITU-T Recommendation X.690, ISO/IEC 8825-1:2021, , <https://
www >..itu .int /rec /T -REC -X .690
13.2. Informative References
- [ANSSI]
-
Agence nationale de la sécurité des systèmes d'information (ANSSI), "ANSSI views on the Post-Quantum Cryptography transition (2023 follow up)", , <https://
cyber >..gouv .fr /sites /default /files /document /follow _up _position _paper _on _post _quantum _cryptography .pdf - [BH16]
-
Bruinderink, L. and S. Hülsing, "Oops, I did it again - Security of One-Time Signatures under Two-Message Attacks.", Cryptology ePrint Archive, Paper 2016/1042, , <https://
eprint >..iacr .org /2016 /1042 - [BSI]
-
Bundesamt für Sicherheit in der Informationstec
hnik (BSI) , "Quantum-safe cryptography - fundamentals, current developments and recommendations" , , <https://www >..bsi .bund .de /Shared Docs /Downloads /EN /BSI /Publications /Brochure /quantum -safe -cryptography .pdf - [CNSA2.0]
-
National Security Agency (NSA), "The Commercial National Security Algorithm Suite 2.0 and Quantum Computing FAQ", , <https://
media >..defense .gov /2022 /Sep /07 /2003071836 /-1 /-1 /0 /CSI _CNSA _2 .0 _FAQ _.PDF - [ETSI
-TR -103 -692] -
European Telecommunicati
ons Standards Institute (ETSI) , "CYBER; State management for stateful authentication mechanisms", ETSI TR 103 692 v1.1.1, , <https://www >..etsi .org /deliver /etsi _tr /103600 _103699 /103692 /01 .01 .01 _60 /tr _103692v010101p .pdf - [IANA-LMS]
-
IANA, "Leighton-Micali Signatures (LMS)", <https://
www >..iana .org /assignments /leighton -micali -signatures / - [IANA-XMSS]
-
IANA, "XMSS: Extended Hash-Based Signatures", <https://
iana >..org /assignments /xmss -extended -hash -based -signatures / - [MCGREW]
-
McGrew, D., Kampanakis, P., Fluhrer, S., Gazdag, S., Butin, D., and J. Buchmann, "State Management for Hash-Based Signatures", Cryptology ePrint Archive, Paper 2016/357, , <https://
eprint >..iacr .org /2016 /357 - [RFC3279]
-
Bassham, L., Polk, W., and R. Housley, "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 3279, DOI 10
.17487 , , <https:///RFC3279 www >..rfc -editor .org /info /rfc3279 - [RFC3647]
-
Chokhani, S., Ford, W., Sabett, R., Merrill, C., and S. Wu, "Internet X.509 Public Key Infrastructure Certificate Policy and Certification Practices Framework", RFC 3647, DOI 10
.17487 , , <https:///RFC3647 www >..rfc -editor .org /info /rfc3647 - [RFC4949]
-
Shirey, R., "Internet Security Glossary, Version 2", FYI 36, RFC 4949, DOI 10
.17487 , , <https:///RFC4949 www >..rfc -editor .org /info /rfc4949 - [RFC8410]
-
Josefsson, S. and J. Schaad, "Algorithm Identifiers for Ed25519, Ed448, X25519, and X448 for Use in the Internet X.509 Public Key Infrastructure", RFC 8410, DOI 10
.17487 , , <https:///RFC8410 www >..rfc -editor .org /info /rfc8410 - [RFC8411]
-
Schaad, J. and R. Andrews, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10
.17487 , , <https:///RFC8411 www >..rfc -editor .org /info /rfc8411 - [S-HBS]
-
Wiggers, T., Bashiri, K., Kölbl, S., Goodman, J., and S. Kousidis, "Hash-based Signatures: State and Backup Management", Work in Progress, Internet-Draft, draft
-wiggers , , <https://-hbs -state -02 datatracker >..ietf .org /doc /html /draft -wiggers -hbs -state -02 - [SMI-PKIX]
-
IANA, "SMI Security for PKIX Algorithms", <https://
www >..iana .org /assignments /smi -numbers
Appendix A. HSS X.509 v3 Certificate Example
This section shows a self-signed X.509 v3 certificate using HSS.¶
Appendix B. XMSS X.509 v3 Certificate Example
This section shows a self-signed X.509 v3 certificate using XMSS.¶
Appendix C. XMSSMT X.509 v3 Certificate Example
This section shows a self-signed X.509 v3 certificate using XMSSMT.¶
Acknowledgments
Thanks to Russ Housley, Panos Kampanakis, Michael StJohns, and Corey Bonnell for their helpful suggestions and reviews.¶
This document uses a lot of text from similar documents, including: [SP800208], [RFC3279] and [RFC8410], as well as [RFC9708]. Thanks goes to the authors of those documents. "Copying always makes things easier and less error prone" [RFC8411].¶