Use of the HSS/LMS Hash-Based Signature Algorithm in the Cryptographic Message Syntax (CMS)
obsoleted by
- rfc-9708 — Use of the HSS/LMS Hash-Based Signature Algorithm in the Cryptographic Message Syntax (CMS)
Extracted elements (25)
HSS/LMS was chosen because it does not depend on the difficulty of discrete logarithms or factoring, making it post-quantum secure. RSA, DSA, ECDSA, and EdDSA are all vulnerable if large-scale quantum computers are developed, motivating the need for hash-based signatures.
The HSS hierarchy was introduced to scale LMS beyond the limits of a single tree. Without HSS, generating the entire tree for a large number of signatures might take weeks or longer; subordinate trees are generated on demand by the signer.
The HSS/LMS signature and public key formats are designed for easy parsing: each component (HSS, LMS, LM-OTS) includes an embedded counter and typecode so all information needed for signature validation can be derived without out-of-band parameters.
HSS/LMS currently exclusively uses SHA-256 as the hash function. IANA registries permit registration of additional hash functions and tree sizes in the future, so implementations should not hard-code SHA-256 as the only possibility.
The id-alg-hss-lms-hashsig OID is also referred to as id-alg-mts-hashsig, a synonym derived from early draft terminology. Implementations may encounter either name and should treat them as equivalent.
In SignerInfo, the digestAlgorithm field MUST contain the one-way hash function used in the HSS/LMS tree (currently SHA-256), and the signatureAlgorithm MUST contain id-alg-hss-lms-hashsig with absent parameters.
When an HSS/LMS AlgorithmIdentifier appears in the SubjectPublicKeyInfo of an X.509 certificate, the key usage extension MAY contain digitalSignature, nonRepudiation, keyCertSign, and cRLSign, but MUST NOT contain other values.
When computing signatures, the same hash function SHOULD be used to compute the message digest of the content and the signed attributes, if signed attributes are present, ensuring consistency across HSS/LMS tree and CMS digest operations.
When signed attributes are present, the DER-encoded set of signed attributes MUST include a content-type attribute and a message-digest attribute before the HSS/LMS signature is computed over them.
When the id-alg-hss-lms-hashsig object identifier is used for an HSS/LMS signature or public key, the AlgorithmIdentifier parameters field MUST be absent (not present and not set to NULL).
The algorithm identifier for HSS/LMS hash-based signatures is id-alg-hss-lms-hashsig with OID { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 }. It is also referred to as id-alg-mts-hashsig.
The LM-OTS algorithm supports four variants (LMOTS_SHA256_N32_W1, W2, W4, W8), all using SHA-256 with n=32. The Winternitz width w controls the trade-off between signature size and computational cost.
The LMS system supports five tree sizes (LMS_SHA256_M32_H5, H10, H15, H20, H25), all using SHA-256 with m=32 bytes of output per node. The tree height h determines the number of leaves as 2^h.
When signed attributes are absent the HSS/LMS signature is computed over the content directly; when signed attributes are present a hash is computed over the content, a message-digest attribute is built, and the signature covers the DER-encoded SignedAttributes (which MUST include content-type and message-digest attributes).
IANA updated the 'SMI Security for S/MIME Module Identifier' registry value 64 and the 'SMI Security for S/MIME Algorithms' registry value 17 (now labeled 'id-alg-hss-lms-hashsig', also known as 'id-alg-mts-hashsig') to reference this document.
An implementation MUST ensure that an LM-OTS private key is used to generate a signature only one time and cannot be used for any other purpose. Reuse of an LM-OTS key compromises the security of the hash-based signature scheme.
Implementations MUST protect private keys and MUST keep track of which leaf nodes in the tree have been used. Loss of integrity of leaf-tracking data can cause a one-time key to be used more than once, which breaks the one-time signature security guarantee.
The generation of private keys and signatures relies on random numbers; use of inadequate PRNGs can result in little or no security because an attacker can search the reduced PRNG output space. RFC 4086 guidance on randomness MUST be followed.
When generating an LMS key pair, an implementation MUST generate each key pair independently of all other key pairs in the HSS tree to prevent cross-tree key material dependencies.
When storing private keys and tracking data on non-volatile media or in virtual machine environments, failed writes, VM snapshotting, and cloning must be considered to ensure confidentiality and integrity of the leaf-use state.
The HSS/LMS public key value in CMS is encoded as u32str(L) || lms_public_key, where L is the number of levels in the HSS hierarchy and lms_public_key is the LMS public key of the topmost tree.
The HSS signature value for a standalone tree is u32str(0) || lms_signature. For a tree with Nspk signed public keys it is u32str(Nspk) || signed_public_key[0] || ... || signed_public_key[Nspk-1] || lms_signature, where Nspk is the number of hierarchy levels minus 1.
The LM-OTS signature value is encoded as u32str(otstype) || C || y[0] || ... || y[p-1], where C is an n-byte random value and y[0]..y[p-1] are hash values corresponding to public key elements.
The LMS public key is encoded as u32str(lms_algorithm_type) || u32str(otstype) || I || T[1], where I is the 16-byte private key identifier and T[1] is the m-byte root node hash.
The LMS signature encodes the leaf index, OTS signature, typecode, and Merkle path as: u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1], where the path array contains h sibling node values.