Use of the HSS and XMSS Hash-Based Signature Algorithms in Internet X.509 Public Key Infrastructure
Extracted elements (25)
Root CA certificates are more appropriate for stateful HBS public keys than subordinate CA certificates because root CAs sign in more secure environments and issue fewer certificates, keeping signature counts well below the OTS key limit. A subordinate CA may use stateful HBS only if it matches root CA security and signature-count restrictions.
Stateful HBS schemes are primarily intended for applications that: (1) must deploy a digital signature scheme in the near future, (2) will have a long implementation lifetime, and (3) cannot practically transition to a different scheme once deployed. Appropriate use cases include firmware signing, software signing, and CA certificates, where operators tightly control the signing environment.
Stateful HBS schemes (HSS, XMSS, XMSS^MT) derive quantum-resistant security solely from the security of the underlying hash function, using Merkle trees combined with One-Time Signatures. Their theoretical security is well understood and does not depend on the hardness of factoring or discrete logarithm problems.
The LMS single-tree signature scheme is instantiated as HSS with the number of levels equal to 1, so the same OID (id-alg-hss-lms-hashsig) covers both HSS multi-tree and LMS single-tree use cases in X.509.
Conventional backup and restore strategies for stateless signature schemes (e.g., duplicating private key material or storing a copy for device recovery) will lead to OTS key reuse with high probability when applied to stateful HBS schemes, because correct state management cannot be guaranteed across independent copies. SP 800-208 Section 7 and draft-wiggers-hbs-state describe compliant availability strategies.
Key generation for XMSS and XMSS^MT MUST be performed according to Section 7.2 of NIST SP 800-208.
The AlgorithmIdentifier for an HSS public key MUST use the id-alg-hss-lms-hashsig OID.
The AlgorithmIdentifier for an XMSS^MT public key MUST use the id-alg-xmssmt-hashsig OID.
The AlgorithmIdentifier for an XMSS public key MUST use the id-alg-xmss-hashsig OID.
The parameters field of the AlgorithmIdentifier for HSS, XMSS, and XMSS^MT public keys MUST be absent.
When any of the three HBS algorithm identifiers appears in the SubjectPublicKeyInfo of an end-entity X.509 certificate, the keyUsage extension MUST contain at least one of digitalSignature, nonRepudiation, or cRLSign, and MUST NOT contain other values. The keyCertSign bit is excluded for end entities.
When HSS, XMSS, or XMSS^MT signature algorithm identifiers are used, no digest algorithm is applied to the message before signing; the full data is signed directly.
XMSS^MT signature generation MUST be performed according to Section 7.2 of NIST SP 800-208.
XMSS signature generation MUST be performed according to Section 7.2 of NIST SP 800-208.
The AlgorithmIdentifier for an HSS public key uses OID id-alg-hss-lms-hashsig (1.2.840.113549.1.9.16.3.17), also known as id-alg-mts-hashsig. The parameters field MUST be absent. This OID is defined in RFC 9708 and reused here.
The AlgorithmIdentifier for an XMSS^MT public key uses OID id-alg-xmssmt-hashsig (1.3.6.1.5.5.7.6.35). The parameters field MUST be absent. Hash function and tree height are identified within the public key and signature values themselves.
The AlgorithmIdentifier for an XMSS public key uses OID id-alg-xmss-hashsig (1.3.6.1.5.5.7.6.34). The parameters field MUST be absent. Hash function and tree height are identified within the public key and signature values themselves.
The ASN.1 module X509-SHBS-2024 (OID 1.3.6.1.5.5.7.0.114) defines PublicKeys and SignatureAlgs information objects extending RFC 5912's sets with pk-HSS-LMS-HashSig (imported from RFC 9708), pk-XMSS-HashSig, pk-XMSSMT-HashSig, sa-XMSS-HashSig, and sa-XMSSMT-HashSig.
IANA registered OID decimal 114 (id-mod-pkix1-shbs-2024) in the 'SMI Security for PKIX Module Identifier' registry (1.3.6.1.5.5.7.0) for the ASN.1 module defined in this document.
IANA registered two entries in the 'SMI Security for PKIX Algorithms' registry (1.3.6.1.5.5.7.6): decimal 34 for id-alg-xmss-hashsig and decimal 35 for id-alg-xmssmt-hashsig.
Correct state management for stateful HBS private keys is crucial. Recommended strategies include: logging OTS key indexes and checking before each signature release; limiting total signatures to a manageable count; and applying a state reservation strategy (reserving upcoming states in advance) to reduce synchronizations between nonvolatile and volatile memory.
The security requirements of NIST SP 800-208 MUST be taken into account. If an attacker obtains signatures for two different messages created with the same OTS key, it becomes computationally feasible to forge signatures. OTS key reuse is the critical threat unique to stateful HBS schemes and is a new requirement most developers will not be familiar with.
Users must be aware of the total number of signatures they intend to generate, as stateful HBS private keys can only generate a limited number of signatures; exhausting OTS keys renders the key unusable and may require key rollover.
HSS, XMSS, and XMSS^MT public keys are each encoded as an ASN.1 OCTET STRING (e.g., HSS-LMS-HashSig-PublicKey, XMSS-HashSig-PublicKey, XMSSMT-HashSig-PublicKey) with no additional ASN.1 wrapping. When placed in SubjectPublicKeyInfo, the OCTET STRING is mapped bit-for-bit into the subjectPublicKey BIT STRING.
Signatures for HSS, XMSS, and XMSS^MT are encoded directly as a BIT STRING in the signatureValue field of Certificate and CertificateList structures, with no additional ASN.1 wrapping. The AlgorithmIdentifier for the signature SHALL be a SEQUENCE of one component (the OID), with the parameters field omitted.