Use of the HSS/LMS Hash-Based Signature Algorithm with CBOR Object Signing and Encryption (COSE)
Extracted elements (22)
A COSE Key Type Parameter for encoding the HSS/LMS private key and state tracking was deliberately not defined to prevent the ability to save the private key and state, generate signatures, and then restore to a prior state — such restoration provides disastrous opportunities for tree node reuse.
HSS/LMS is a post-quantum secure signature algorithm because it does not depend on the difficulty of discrete logarithm or factoring, unlike RSA, DSA, ECDSA, and EdDSA which are all vulnerable to large-scale quantum computers. Deploying HSS/LMS now enables authentication and integrity protection of future software even if advances break current digital-signature mechanisms.
The HSS/LMS signature value is designed as a large byte string for easy parsing: the HSS, LMS, and LM-OTS components include counters and type codes that indirectly provide all information needed to parse the byte string during signature validation without requiring out-of-band parameter negotiation.
HSS/LMS signatures are currently defined to use exclusively SHA-256, and the signature algorithm has small public keys and low computational cost but produces quite large signatures (the COSE_Sign1 example is 2552 bytes). The private key size trades off against signing computation time.
If the 'alg' field is present in the COSE key, it MUST be 'HSS-LMS'.
If the 'key_ops' field is present, it MUST include 'sign' when creating a hash-based signature and MUST include 'verify' when verifying a hash-based signature.
When using a COSE key for HSS/LMS, the 'kty' field MUST be 'HSS-LMS'.
LMS supports five tree sizes: LMS_SHA256_M32_H5, LMS_SHA256_M32_H10, LMS_SHA256_M32_H15, LMS_SHA256_M32_H20, and LMS_SHA256_M32_H25, where h is the tree height (number of levels minus one) and m=32 bytes for SHA-256.
The Hierarchical Signature System (HSS) uses a hierarchy of LMS trees. An HSS signature carries u32str(Nspk) followed by Nspk signed public keys (each an lms_signature over the child public key followed by the public key itself), followed by the final LMS signature over the message. For a stand-alone tree, the format is u32str(0) || lms_signature.
The HSS/LMS signature algorithm can only be used for a fixed number of signing operations determined by the tree size. When all LM-OTS signatures have been used, a new trust anchor must be established. Signers must maintain state across invocations to ensure no tree node is used to generate more than one signature.
The 'kid' field in the COSE key MAY be used to identify the top of the HSS tree; this identifier corresponds to 'I', the 16-byte identifier of the LMS public key for the top-level tree as defined in RFC 8554.
The LM-OTS algorithm has five parameters: n (hash output bytes, 32 for SHA-256), H (preimage-resistant hash function), w (Winternitz coefficient width in bits: 1, 2, 4, or 8), p (number of n-byte signature elements), and ls (left-shift bits for checksum). Four variants are defined: LMOTS_SHA256_N32_W1/W2/W4/W8.
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 string associated with the root of the LMS tree.
IANA added a new entry to the COSE Key Type Parameters registry for Key Type 5 (HSS-LMS): Name 'pub', Label -1, CBOR Type bstr, description 'Public key for HSS/LMS hash-based digital signature', referenced to RFC 8778.
IANA added HSS-LMS to the COSE Algorithms registry with value -46, description 'HSS/LMS hash-based digital signature', referenced to RFC 8778, and Recommended: Yes.
IANA added HSS-LMS to the COSE Key Types registry with value 5, description 'Public key for HSS/LMS hash-based digital signature', referenced to RFC 8778.
Implementations MUST protect the private keys and MUST keep track of which leaf nodes in the tree have been used. Loss of integrity of this tracking data can cause a one-time key to be used more than once, and virtual machine snapshotting or cloning poses a particular risk requiring careful consideration.
The generation of private keys and hash-based signatures relies on random numbers; use of inadequate PRNGs can result in little or no security. RFC 4086 guidance on randomness requirements is important for both key generation and signature generation.
When generating an LMS key pair, an implementation MUST generate each key pair independently of all other key pairs in the HSS tree, and MUST ensure that an LM-OTS private key is used to generate a signature only one time.
The HSS signature value for a tree with Nspk signed public keys is: u32str(Nspk) || signed_public_key[0] || ... || signed_public_key[Nspk-1] || lms_signature, where Nspk equals the number of hierarchy levels minus 1.
The LM-OTS signature value is: u32str(otstype) || C || y[0] || ... || y[p-1], where C is an n-byte random value generated at signing time and y[0]..y[p-1] is the sequence of hash values.
The LMS signature consists of four elements encoded as: u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1], where q is the leaf number, type is the LMS algorithm code, and path contains h sibling node values along the path from leaf to root.