--- 1/draft-ietf-lamps-cms-hash-sig-08.txt 2019-08-10 10:13:11.036671190 -0700 +++ 2/draft-ietf-lamps-cms-hash-sig-09.txt 2019-08-10 10:13:11.068672001 -0700 @@ -1,27 +1,28 @@ INTERNET-DRAFT R. Housley Internet Engineering Task Force (IETF) Vigil Security Intended Status: Proposed Standard -Expires: 11 November 2019 10 May 2019 +Expires: 10 February 2020 10 August 2019 Use of the HSS/LMS Hash-based Signature Algorithm in the Cryptographic Message Syntax (CMS) - + Abstract - This document specifies the conventions for using the the HSS/LMS - hash-based signature algorithm with the Cryptographic Message Syntax - (CMS). In addition, the algorithm identifier and public key syntax - are provided. The HSS/LMS algorithm is one form of hash-based - digital signature; it is described in RFC 8554. + This document specifies the conventions for using the Hierarchical + Signature System (HSS) / Leighton-Micali Signature (LMS) hash-based + signature algorithm with the Cryptographic Message Syntax (CMS). In + addition, the algorithm identifier and public key syntax are + provided. The HSS/LMS algorithm is one form of hash-based digital + signature; it is described in RFC 8554. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. @@ -50,128 +51,115 @@ to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. ASN.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 - 1.3. Algorithm Considerations . . . . . . . . . . . . . . . . . 3 + 1.3. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 3 2. HSS/LMS Hash-based Signature Algorithm Overview . . . . . . . 4 2.1. Hierarchical Signature System (HSS) . . . . . . . . . . . 4 2.2. Leighton-Micali Signature (LMS) . . . . . . . . . . . . . 5 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) . . 6 3. Algorithm Identifiers and Parameters . . . . . . . . . . . . . 7 4. HSS/LMS Public Key Identifier . . . . . . . . . . . . . . . . 8 - 5. Signed-data Conventions . . . . . . . . . . . . . . . . . . . 9 - 6. Security Considerations . . . . . . . . . . . . . . . . . . . 10 + 5. Signed-data Conventions . . . . . . . . . . . . . . . . . . . 8 + 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 - 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 - 8.1. Normative References . . . . . . . . . . . . . . . . . . . 11 - 8.2. Informative References . . . . . . . . . . . . . . . . . . 12 + 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 + 8.1. Normative References . . . . . . . . . . . . . . . . . . . 10 + 8.2. Informative References . . . . . . . . . . . . . . . . . . 11 Appendix: ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . 13 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 14 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 14 1. Introduction - This document specifies the conventions for using the HSS/LMS hash- - based signature algorithm with the Cryptographic Message Syntax (CMS) - [CMS] signed-data content type. The Leighton-Micali Signature (LMS) - system provides a one-time digital signature that is a variant of - Merkle Tree Signatures (MTS). The Hierarchical Signature System - (HSS) is built on top of the LMS system to efficiently scale for a - larger numbers of signatures. The HSS/LMS algorithm is one form of - hash-based digital signature, and it is described in [HASHSIG]. The + This document specifies the conventions for using the Hierarchical + Signature System (HSS) / Leighton-Micali Signature (LMS) hash-based + signature algorithm with the Cryptographic Message Syntax (CMS) [CMS] + signed-data content type. The LMS system provides a one-time digital + signature that is a variant of Merkle Tree Signatures (MTS). The HSS + is built on top of the LMS system to efficiently scale for a larger + numbers of signatures. The HSS/LMS algorithm is one form of hash- + based digital signature, and it is described in [HASHSIG]. The HSS/LMS signature algorithm can only be used for a fixed number of signing operations. The number of signing operations depends upon the size of the tree. The HSS/LMS signature algorithm uses small public keys, and it has low computational cost; however, the signatures are quite large. The HSS/LMS private key can be very small when the signer is willing to perform additional computation at signing time; alternatively, the private key can consume additional - memory and provide a faster signing time. + memory and provide a faster signing time. The HSS/LMS signatures + [HASHSIG] are currently defined to use exclusively SHA-256 [SHS]. 1.1. ASN.1 CMS values are generated using ASN.1 [ASN1-B], using the Basic Encoding Rules (BER) and the Distinguished Encoding Rules (DER) [ASN1-E]. 1.2. Terminology 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. -1.3. Algorithm Considerations +1.3. Motivation There have been recent advances in cryptanalysis and advances in the development of quantum computers. Each of these advances pose a threat to widely deployed digital signature algorithms. - At Black Hat USA 2013, some researchers gave a presentation on the - current state of public key cryptography. They said: "Current - cryptosystems depend on discrete logarithm and factoring which has - seen some major new developments in the past 6 months" [BH2013]. Due - to advances in cryptanalysis, they encouraged preparation for a day - when RSA and DSA cannot be depended upon. + Recent advances in cryptoanalysis [BH2013] and progress in the + development of quantum computers [NAS2019] pose a threat to widely + deployed digital signature algorithms. As a result, there is a need + to prepare for a day that cryptosystems such as RSA and DSA that + depend on discrete logarithm and factoring cannot be depended upon. If large-scale quantum computers are ever built, these computers will be able to break many of the public-key cryptosystems currently in use. A post-quantum cryptosystem [PQC] is a system that is secure against quantum computers that have more than a trivial number of quantum bits (qu-bits). It is open to conjecture when it will be feasible to build such computers; however, RSA, DSA, ECDSA, and EdDSA are all vulnerable if large-scale quantum computers come to pass. The HSS/LMS signature algorithm does not depend on the difficulty of discrete logarithm or factoring, as a result these algorithms are - considered to be post-quantum secure. - - Hash-based signatures [HASHSIG] are currently defined to use - exclusively SHA-256 [SHS]. An IANA registry is defined so that other - hash functions could be used in the future. LM-OTS signature - generation prepends a random string as well as other metadata before - computing the hash value. The inclusion of the random value reduces - the chances of an attacker being able to find collisions, even if the - attacker has a large-scale quantum computer. - - Today, RSA is often used to digitally sign software updates. This - means that the distribution of software updates could be compromised - if a significant advance is made in factoring or a large-scale - quantum computer is invented. The use of HSS/LMS hash-based - signatures to protect software update distribution, perhaps using the - format described in [FWPROT], will allow the deployment of software - that implements new cryptosystems. + considered to be post-quantum secure. One use of post-quantum secure + signatures is the protection of software updates, perhaps using the + format described in [FWPROT], to enable deployment of software that + implements new cryptosystems. 2. HSS/LMS Hash-based Signature Algorithm Overview Merkle Tree Signatures (MTS) are a method for signing a large but fixed number of messages. An MTS system depends on a one-time signature method and a collision-resistant hash function. This specification makes use of the hash-based algorithm specified in [HASHSIG], which is the Leighton and Micali adaptation [LM] of the original Lamport-Diffie-Winternitz-Merkle one-time signature system [M1979][M1987][M1989a][M1989b]. As implied by the name, the hash-based signature algorithm depends on a collision-resistant hash function. The hash-based signature algorithm specified in [HASHSIG] currently uses only the SHA-256 one- - way hash function [SHS], but it also establishes an IANA registry to - permit the registration of additional one-way hash functions in the - future. + way hash function [SHS], but it also establishes an IANA registry + [IANA-LMS] to permit the registration of additional one-way hash + functions in the future. 2.1. Hierarchical Signature System (HSS) The MTS system specified in [HASHSIG] uses a hierarchy of trees. The Hierarchical N-time Signature System (HSS) allows subordinate trees to be generated when needed by the signer. Otherwise, generation of the entire tree might take weeks or longer. An HSS signature as specified in [HASHSIG] carries the number of signed public keys (Nspk), followed by that number of signed public @@ -182,156 +170,157 @@ tree signs the actual message. The signature over the public key and the signature over the actual message are LMS signatures as described in Section 2.2. The elements of the HSS signature value for a stand-alone tree (a top tree with no children) can be summarized as: u32str(0) || lms_signature /* signature of message */ + where, u32str() and || are used as defined in [HASHSIG]. + The elements of the HSS signature value for a tree with Nspk signed public keys can be summarized as: u32str(Nspk) || signed_public_key[0] || signed_public_key[1] || ... signed_public_key[Nspk-2] || signed_public_key[Nspk-1] || lms_signature /* signature of message */ - where, as defined in Section 3.3 of [HASHSIG], a signed_public_key is - the lms_signature over the public key followed by the public key - itself. Note that Nspk is the number of levels in the hierarchy of - trees minus 1. + where, as defined in Section 3.3 of [HASHSIG], the signed_public_key + structure contains the lms_signature over the public key followed by + the public key itself. Note that Nspk is the number of levels in the + hierarchy of trees minus 1. 2.2. Leighton-Micali Signature (LMS) Each tree in the system specified in [HASHSIG] uses the Leighton- Micali Signature (LMS) system. LMS systems have two parameters. The first parameter is the height of the tree, h, which is the number of levels in the tree minus one. The [HASHSIG] specification supports five values for this parameter: h=5; h=10; h=15; h=20; and h=25. Note that there are 2^h leaves in the tree. The second parameter is the number of bytes output by the hash function, m, which is the amount of data associated with each node in the tree. The [HASHSIG] specification supports only the SHA-256 hash function [SHS], with - m=32. - - The [HASHSIG] specification supports five tree sizes: + m=32. As a result, the [HASHSIG] specification supports five tree + sizes; they are identified as: LMS_SHA256_M32_H5; LMS_SHA256_M32_H10; LMS_SHA256_M32_H15; LMS_SHA256_M32_H20; and LMS_SHA256_M32_H25. - The [HASHSIG] specification establishes an IANA registry to permit - the registration of additional hash functions and additional tree - sizes in the future. + The [HASHSIG] specification establishes an IANA registry [IANA-LMS] + to permit the registration of additional hash functions and + additional tree sizes in the future. - The LMS public key is the string consists of four elements: the - lms_algorithm_type from the list above, the otstype to identify the - LM-OTS type as discussed in Section 2.3, the private key identifier - (I) as described in Section 5.3 of [HASHSIG], and the m-byte string - associated with the root node of the tree. + As specified in [HASHSIG], the LMS public key consists of four + elements: the lms_algorithm_type from the list above, the otstype to + identify the LM-OTS type as discussed in Section 2.3, the private key + identifier (I) as described in Section 5.3 of [HASHSIG], and the m- + byte string associated with the root node of the tree (T[1]). The LMS public key can be summarized as: u32str(lms_algorithm_type) || u32str(otstype) || I || T[1] - An LMS signature consists of four elements: the number of the leaf - (q) associated with the LM-OTS signature, an LM-OTS signature as - described in Section 2.3, a typecode indicating the particular LMS - algorithm, and an array of values that is associated with the path - through the tree from the leaf associated with the LM-OTS signature - to the root. The array of values contains the siblings of the nodes - on the path from the leaf to the root but does not contain the nodes - on the path itself. The array for a tree with height h will have h - values. The first value is the sibling of the leaf, the next value - is the sibling of the parent of the leaf, and so on up the path to - the root. + As specified in [HASHSIG], an LMS signature consists of four + elements: the number of the leaf (q) associated with the LM-OTS + signature, an LM-OTS signature as described in Section 2.3, a + typecode indicating the particular LMS algorithm, and an array of + values that is associated with the path through the tree from the + leaf associated with the LM-OTS signature to the root. The array of + values contains the siblings of the nodes on the path from the leaf + to the root but does not contain the nodes on the path itself. The + array for a tree with height h will have h values. The first value + is the sibling of the leaf, the next value is the sibling of the + parent of the leaf, and so on up the path to the root. The four elements of the LMS signature value can be summarized as: u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1] 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) - Merkle Tree Signatures (MTS) depend on a one-time signature method. - - [HASHSIG] specifies the use of the LM-OTS. An LM-OTS has five - parameters. + Merkle Tree Signatures (MTS) depend on a one-time signature method, + and [HASHSIG] specifies the use of the LM-OTS, which has five + parameters: - n - The number of bytes associated with the hash function. - [HASHSIG] supports only SHA-256 [SHS], with n=32. + n - The length in bytes of the hash function output. [HASHSIG] + supports only SHA-256 [SHS], with n=32. H - A preimage-resistant hash function that accepts byte strings of any length, and returns an n-byte string. w - The width in bits of the Winternitz coefficients. [HASHSIG] supports four values for this parameter: w=1; w=2; w=4; and w=8. p - The number of n-byte string elements that make up the LM-OTS signature. - ls - The number of left-shift bits used in the checksum function, - which is defined in Section 4.4 of [HASHSIG]. + ls - The number of bits that are left-shifted in the final step of + the checksum function, which is defined in Section 4.4 of + [HASHSIG]. The values of p and ls are dependent on the choices of the parameters n and w, as described in Appendix B of [HASHSIG]. The [HASHSIG] specification supports four LM-OTS variants: LMOTS_SHA256_N32_W1; LMOTS_SHA256_N32_W2; LMOTS_SHA256_N32_W4; and LMOTS_SHA256_N32_W8. - The [HASHSIG] specification establishes an IANA registry to permit - the registration of additional variants in the future. + The [HASHSIG] specification establishes an IANA registry [IANA-LMS] + to permit the registration of additional variants in the future. Signing involves the generation of C, an n-byte random value. The LM-OTS signature value can be summarized as the identifier of the - LM-OTS variant, the random value, and a sequence of hash values that - correspond to the elements of the public key as described in Section - 4.5 of [HASHSIG]: + LM-OTS variant, the random value, and a sequence of hash values (y[0] + through y[p-1]) that correspond to the elements of the public key as + described in Section 4.5 of [HASHSIG]: u32str(otstype) || C || y[0] || ... || y[p-1] 3. Algorithm Identifiers and Parameters The algorithm identifier for an HSS/LMS hash-based signatures is: id-alg-hss-lms-hashsig OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 } - When this object identifier is used for a HSS/LMS signature, the + When this object identifier is used for an HSS/LMS signature, the AlgorithmIdentifier parameters field MUST be absent (that is, the parameters are not present; the parameters are not set to NULL). The signature value is a large OCTET STRING. The signature format is designed for easy parsing. Each format includes a counter and type codes that indirectly providing all of the information that is needed to parse the value during signature validation. The signature value identifies the hash function used in the HSS/LMS tree. In [HASHSIG] only the SHA-256 hash function [SHS] is - supported, but it also establishes an IANA registry to permit the - registration of additional hash functions in the future. + supported, but it also establishes an IANA registry [IANA-LMS] to + permit the registration of additional hash functions in the future. 4. HSS/LMS Public Key Identifier The AlgorithmIdentifier for an HSS/LMS public key uses the id-alg- hss-lms-hashsig object identifier, and the parameters field MUST be absent. When this AlgorithmIdentifier appears in the SubjectPublicKeyInfo field of an X.509 certificate [RFC5280], the certificate key usage extension MAY contain digitalSignature, nonRepudiation, keyCertSign, @@ -359,30 +348,32 @@ u32str(L) || lms_public_key Note that the public key for the top-most LMS tree is the public key of the HSS system. When L=1, the HSS system is a single tree. 5. Signed-data Conventions As specified in [CMS], the digital signature is produced from the message digest and the signer's private key. The signature is - computed over different value depending on whether signed attributes - are absent or present. When signed attributes are absent, the - HSS/LMS signature is computed over the content. When signed - attributes are present, a hash is computed over the content using the - same hash function that is used in the HSS/LMS tree, and then a - message-digest attribute is constructed with the resulting hash - value, and then DER encode the set of signed attributes, which MUST - include a content-type attribute and a message-digest attribute, and - then the HSS/LMS signature is computed over the output of the DER- - encode operation. In summary: + computed over different values depending on whether signed attributes + are absent or present. + + When signed attributes are absent, the HSS/LMS signature is computed + over the content. When signed attributes are present, a hash is + computed over the content using the same hash function that is used + in the HSS/LMS tree, and then a message-digest attribute is + constructed to contain the resulting hash value, and then the result + of DER encoding the set of signed attributes (which MUST include a + content-type attribute and a message-digest attribute, and then the + HSS/LMS signature is computed over the DER-encoded output. In + summary: IF (signed attributes are absent) THEN HSS_LMS_Sign(content) ELSE message-digest attribute = Hash(content); HSS_LMS_Sign(DER(SignedAttributes)) When using [HASHSIG], the fields in the SignerInfo are used as follows: digestAlgorithm MUST contain the one-way hash function used to in @@ -404,26 +395,26 @@ signature contains the single HSS signature value resulting from the signing operation as specified in [HASHSIG]. 6. Security Considerations Implementations MUST protect the private keys. Compromise of the private keys may result in the ability to forge signatures. Along with the private key, the implementation MUST keep track of which leaf nodes in the tree have been used. Loss of integrity of this - tracking data can cause an one-time key to be used more than once. - As a result, when a private key and the tracking data are stored on - non-volatile media or stored in a virtual machine environment, care - must be taken to preserve confidentiality and integrity. + tracking data can cause a one-time key to be used more than once. As + a result, when a private key and the tracking data are stored on non- + volatile media or stored in a virtual machine environment, care must + be taken to preserve confidentiality and integrity. - When generating a LMS key pair, an implementation MUST generate each + When generating an LMS key pair, an implementation MUST generate each key pair independently of all other key pairs in the HSS tree. An implementation MUST ensure that a LM-OTS private key is used to generate a signature only one time, and ensure that it cannot be used for any other purpose. The generation of private keys relies on random numbers. The use of inadequate pseudo-random number generators (PRNGs) to generate these values can result in little or no security. An attacker may find it much easier to reproduce the PRNG environment that produced the keys, @@ -515,38 +506,46 @@ for the Cryptographic Message Syntax (CMS) and the Public Key Infrastructure Using X.509 (PKIX)", RFC 6268, DOI 10.17487/RFC6268, July 2011, . [FWPROT] Housley, R., "Using Cryptographic Message Syntax (CMS) to Protect Firmware Packages", RFC 4108, DOI 10.17487/RFC4108, August 2005, . + [IANA-LMS] IANA Registry for Leighton-Micali Signatures (LMS). + . + [LM] Leighton, T. and S. Micali, "Large provably fast and secure digital signature schemes from secure hash functions", U.S. Patent 5,432,852, July 1995. [M1979] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Stanford University Information Systems Laboratory Technical Report 1979-1, 1979. [M1987] Merkle, R., "A Digital Signature Based on a Conventional Encryption Function", Lecture Notes in Computer Science crypto87, 1988. [M1989a] Merkle, R., "A Certified Digital Signature", Lecture Notes in Computer Science crypto89, 1990. [M1989b] Merkle, R., "One Way Hash Functions and DES", Lecture Notes in Computer Science crypto89, 1990. + [NAS2019] National Academies of Sciences, Engineering, and Medicine, + "Quantum Computing: Progress and Prospects", The National + Academies Press, DOI 10.17226/25196, 2019. + [PKIXASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for the Public Key Infrastructure Using X.509 (PKIX)", RFC 5912, DOI 10.17487/RFC5912, June 2010, . [PQC] Bernstein, D., "Introduction to post-quantum cryptography", 2009. @@ -617,22 +616,23 @@ SMimeCaps SMIME-CAPS ::= { sa-HSS-LMS-HashSig.&smimeCaps, ... } END Acknowledgements Many thanks to Scott Fluhrer, Jonathan Hammell, Panos Kampanakis, - John Mattsson, Jim Schaad, Sean Turner, and Daniel Van Geest for - their careful review and comments. + John Mattsson, Jim Schaad, Sean Turner, Daniel Van Geest, Roman + Danyliw, Dale Worley, and Joe Clarke for their careful review and + comments. Author's Address Russ Housley Vigil Security, LLC 516 Dranesville Road Herndon, VA 20170 USA EMail: housley@vigilsec.com