idnits 2.17.00 (12 Aug 2021) /tmp/idnits27521/draft-ietf-cose-hash-sig-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([HASHSIG]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 06, 2019) is 1172 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 280 -- Looks like a reference, but probably isn't: '1' on line 235 == Missing Reference: 'Nspk-2' is mentioned on line 183, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 184, but not defined == Outdated reference: draft-mcgrew-hash-sigs has been published as RFC 8554 ** Downref: Normative reference to an Informational draft: draft-mcgrew-hash-sigs (ref. 'HASHSIG') -- Possible downref: Non-RFC (?) normative reference: ref. 'SHS' Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Housley 3 Internet-Draft Vigil Security 4 Intended status: Standards Track March 06, 2019 5 Expires: September 7, 2019 7 Use of the Hash-based Signature Algorithm with CBOR Object Signing and 8 Encryption (COSE) 9 draft-ietf-cose-hash-sig-01 11 Abstract 13 This document specifies the conventions for using the HSS/LMS hash- 14 based signature algorithm with the CBOR Object Signing and Encryption 15 (COSE) syntax. The HSS/LMS algorithm is one form of hash-based 16 digital signature; it is described in [HASHSIG]. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on September 7, 2019. 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1. Algorithm Security Considerations . . . . . . . . . . . . 2 54 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. LMS Digital Signature Algorithm Overview . . . . . . . . . . 3 56 2.1. Hierarchical Signature System (HSS) . . . . . . . . . . . 4 57 2.2. Leighton-Micali Signature (LMS) . . . . . . . . . . . . . 5 58 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) . . 6 59 3. Hash-based Signature Algorithm Identifiers . . . . . . . . . 7 60 4. Security Considerations . . . . . . . . . . . . . . . . . . . 7 61 4.1. Implementation Security Considerations . . . . . . . . . 7 62 5. Operational Considerations . . . . . . . . . . . . . . . . . 8 63 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 64 6.1. COSE Algorithms Registry Entry . . . . . . . . . . . . . 9 65 6.2. COSE Key Types Registry Entry . . . . . . . . . . . . . . 9 66 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 67 7.1. Normative References . . . . . . . . . . . . . . . . . . 9 68 7.2. Informative References . . . . . . . . . . . . . . . . . 10 69 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 11 70 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11 72 1. Introduction 74 This document specifies the conventions for using the HSS/LMS hash- 75 based signature algorithm with the CBOR Object Signing and Encryption 76 (COSE) [RFC8152] syntax. The Leighton-Micali Signature (LMS) system 77 provides a one-time digital signature that is a variant of Merkle 78 Tree Signatures (MTS). The Hierarchical Signature System (HSS) is 79 built on top of the LMS system to efficiently scale for a larger 80 numbers of signatures. The HSS/LMS algorithm is one form of hash- 81 based digital signature, and it is described in [HASHSIG]. The HSS/ 82 LMS signature algorithm can only be used for a fixed number of 83 signing operations. The number of signing operations depends upon 84 the size of the tree. The HSS/LMS signature algorithm uses small 85 public keys, and it has low computational cost; however, the 86 signatures are quite large. The HSS/LMS private key can be very 87 small when the signer is willing to perform additional computation at 88 signing time; alternatively, the private key can consume additional 89 memory and provide a faster signing time. 91 1.1. Algorithm Security Considerations 93 At Black Hat USA 2013, some researchers gave a presentation on the 94 current sate of public key cryptography. They said: "Current 95 cryptosystems depend on discrete logarithm and factoring which has 96 seen some major new developments in the past 6 months" [BH2013]. 98 They encouraged preparation for a day when RSA and DSA cannot be 99 depended upon. 101 A post-quantum cryptosystem [PQC] is a system that is secure against 102 quantum computers that have more than a trivial number of quantum 103 bits. It is open to conjecture when it will be feasible to build 104 such a machine. RSA, DSA, and ECDSA are not post-quantum secure. 106 The HSS/LMS signature algorithm does not depend on discrete logarithm 107 or factoring, as a result these algorithms are considered to be post- 108 quantum secure. 110 Today, the RSA digital signature algorithm is often used to sign 111 software updates. In preparation for a day when RSA, DSA, and ECDSA 112 cannot be depended upon, a digital signature algorithm is needed that 113 will remain secure even if there are significant cryptoanalytic 114 advances or a large-scale quantum computer is invented. The HSS/LMS 115 hash-based digital signature algorithm specified in [HASHSIG] is one 116 such algorithm. The use of hash-based signatures to protect software 117 update distribution will allow the deployment of software that 118 implements new cryptosystems even if such advances break current 119 digital signature mechanisms. 121 1.2. Terminology 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 125 "OPTIONAL" in this document are to be interpreted as described in 126 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 127 capitals, as shown here. 129 2. LMS Digital Signature Algorithm Overview 131 This specification makes use of the hash-based signature algorithm 132 specified in [HASHSIG], which is the Leighton and Micali adaptation 133 [LM] of the original Lamport-Diffie-Winternitz-Merkle one-time 134 signature system [M1979][M1987][M1989a][M1989b]. 136 The hash-based signature algorithm has three major components: 138 o Hierarchical Signature System (HSS) -- see Section 2.1; 140 o Leighton-Micali Signature (LMS) -- see Section 2.2; and 142 o Leighton-Micali One-time Signature Algorithm (LM-OTS) -- see 143 Section 2.3. 145 As implied by the name, the hash-based signature algorithm depends on 146 a collision-resistant hash function. The the hash-based signature 147 algorithm specified in [HASHSIG] currently makes use of the SHA-256 148 one-way hash function [SHS], but it also establishes an IANA registry 149 to permit the registration of additional one-way hash functions in 150 the future. 152 2.1. Hierarchical Signature System (HSS) 154 The hash-based signature algorithm specified in [HASHSIG] uses a 155 hierarchy of trees. The Hierarchical Signature System (HSS) allows 156 subordinate trees to be generated when needed by the signer. By 157 using trees-of-trees, a very large number of nodes can be 158 accommodated, where each node enables a single digital signature. 159 Without the HSS, the generation of such a large tree might take weeks 160 or longer. 162 An HSS signature as specified in [HASHSIG] carries the number of 163 signed public keys (Nspk), followed by that number of signed public 164 keys, followed by the LMS signature as described in Section 2.2. 165 Each signed public key is represented by the hash value at the root 166 of the tree, and it also contains information about the tree 167 structure. The signature over the public key is an LMS signature as 168 described in Section 2.2. 170 The elements of the HSS signature value for a stand-alone tree can be 171 summarized as: 173 u32str(0) || 174 lms_signature /* signature of message */ 176 The elements of the HSS signature value for a tree with Nspk levels 177 can be summarized as: 179 u32str(Nspk) || 180 signed_public_key[0] || 181 signed_public_key[1] || 182 ... 183 signed_public_key[Nspk-2] || 184 signed_public_key[Nspk-1] || 185 lms_signature /* signature of message */ 187 where, as defined in Section 3.3 of [HASHSIG], a signed_public_key is 188 the lms_signature over the public key followed by the public key 189 itself. Note that Nspk is the number of levels in the hierarchy of 190 trees minus 1. 192 2.2. Leighton-Micali Signature (LMS) 194 Each tree in the hash-based signature algorithm specified in 195 [HASHSIG] uses the Leighton-Micali Signature (LMS) system. LMS 196 systems have two parameters. The first parameter is the height of 197 the tree, h, which is the number of levels in the tree minus one. 198 The [HASHSIG] includes support for five values of this parameter: 199 h=5; h=10; h=15; h=20; and h=25. Note that there are 2^h leaves in 200 the tree. The second parameter is the number of bytes output by the 201 hash function, m, which is the amount of data associated with each 202 node in the tree. This specification supports only SHA-256, with 203 m=32. An IANA registry is defined so that other hash functions could 204 be used in the future. 206 Currently, the hash-based signature algorithm supports five tree 207 sizes: 209 LMS_SHA256_M32_H5; 210 LMS_SHA256_M32_H10; 211 LMS_SHA256_M32_H15; 212 LMS_SHA256_M32_H20; and 213 LMS_SHA256_M32_H25. 215 The [HASHSIG] specification establishes an IANA registry to permit 216 the registration of additional tree sizes in the future. 218 An LMS signature consists of four elements: the number of the leaf 219 associated with the LM-OTS signature, an LM-OTS signature as 220 described in Section 2.3, a typecode indicating the particular LMS 221 algorithm, and an array of values that is associated with the path 222 through the tree from the leaf associated with the LM-OTS signature 223 to the root. The array of values contains the siblings of the nodes 224 on the path from the leaf to the root but does not contain the nodes 225 on the path itself. The array for a tree with height h will have h 226 values. The first value is the sibling of the leaf, the next value 227 is the sibling of the parent of the leaf, and so on up the path to 228 the root. 230 The four elements of the LMS signature value can be summarized as: 232 u32str(q) || 233 ots_signature || 234 u32str(type) || 235 path[0] || path[1] || ... || path[h-1] 237 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) 239 The hash-based signature algorithm depends on a one-time signature 240 method. This specification makes use of the Leighton-Micali One-time 241 Signature Algorithm (LM-OTS) [HASHSIG]. An LM-OTS has five 242 parameters: 244 n - The number of bytes output by the hash function. This 245 specification supports only SHA-256 {{SHS}}, with n=32. 247 H - A preimage-resistant hash function that accepts byte strings 248 of any length, and returns an n-byte string. This 249 specification supports only SHA-256 [SHS]. 251 w - The width in bits of the Winternitz coefficients. [HASHSIG] 252 supports four values for this parameter: w=1; w=2; w=4; and 253 w=8. 255 p - The number of n-byte string elements that make up the LM-OTS 256 signature. 258 ls - The number of left-shift bits used in the checksum function, 259 which is defined in Section 4.5 of [HASHSIG]. 261 The values of p and ls are dependent on the choices of the parameters 262 n and w, as described in Appendix A of [HASHSIG]. 264 Currently, the hash-based signature algorithm supports four LM-OTS 265 variants: 267 LMOTS_SHA256_N32_W1; 268 LMOTS_SHA256_N32_W2; 269 LMOTS_SHA256_N32_W4; and 270 LMOTS_SHA256_N32_W8. 272 The [HASHSIG] specification establishes an IANA registry to permit 273 the registration of additional variants in the future. 275 Signing involves the generation of C, which is an n-byte random 276 value. 278 The LM-OTS signature value can be summarized as: 280 u32str(otstype) || C || y[0] || ... || y[p-1] 282 3. Hash-based Signature Algorithm Identifiers 284 The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two 285 signature algorithm schemes. This specification makes use of the 286 signature with appendix scheme for hash-based signatures. 288 The signature value is a large byte string. The byte string is 289 designed for easy parsing, and it includes a counter and type codes 290 that indirectly provide all of the information that is needed to 291 parse the byte string during signature validation. 293 When using a COSE key for this algorithm, the following checks are 294 made: 296 o The 'kty' field MUST be present, and it MUST be 'HSS-LMS'. 298 o If the 'alg' field is present, and it MUST be 'HSS-LMS'. 300 o If the 'key_ops' field is present, it MUST include 'sign' when 301 creating a hash-based signature. 303 o If the 'key_ops' field is present, it MUST include 'verify' 304 when verifying a hash-based signature. 306 o If the 'kid' field is present, it MAY be used to identify the 307 top of the HSS tree. In [HASHSIG], this identifier is called 308 'I', and it is the 16-byte identifier of the LMS public key 309 for the tree. 311 4. Security Considerations 313 4.1. Implementation Security Considerations 315 Implementations must protect the private keys. Use of a hardware 316 security module (HSM) is one way to protect the private keys. 317 Compromise of the private keys may result in the ability to forge 318 signatures. Along with the private key, the implementation must keep 319 track of which leaf nodes in the tree have been used. Loss of 320 integrity of this tracking data can cause a one-time key to be used 321 more than once. As a result, when a private key and the tracking 322 data are stored on non-volatile media or stored in a virtual machine 323 environment, care must be taken to preserve confidentiality and 324 integrity. 326 When a LMS key pair is generating a LMS key pair, an implementation 327 must must generate the key pair and the corresponding identifier 328 independently of all other key pairs in the HSS tree. 330 An implementation must ensure that a LM-OTS private key is used to 331 generate a signature only one time, and ensure that it cannot be used 332 for any other purpose. 334 The generation of private keys relies on random numbers. The use of 335 inadequate pseudo-random number generators (PRNGs) to generate these 336 values can result in little or no security. An attacker may find it 337 much easier to reproduce the PRNG environment that produced the keys, 338 searching the resulting small set of possibilities, rather than brute 339 force searching the whole key space. The generation of quality 340 random numbers is difficult. [RFC4086] offers important guidance in 341 this area. 343 The generation of hash-based signatures also depends on random 344 numbers. While the consequences of an inadequate pseudo-random 345 number generator (PRNGs) to generate these values is much less severe 346 than the generation of private keys, the guidance in [RFC4086] 347 remains important. 349 5. Operational Considerations 351 The public key for the hash-based signature is the key at the root of 352 Hierarchical Signature System (HSS). In the absence of a public key 353 infrastructure [RFC5280], this public key is a trust anchor, and the 354 number of signatures that can be generated is bounded by the size of 355 the overall HSS set of trees. When all of the LM-OTS signatures have 356 been used to produce a signature, then the establishment of a new 357 trust anchor is required. 359 To ensure that none of tree nodes are used to generate more than one 360 signature, the signer maintains state across different invocations of 361 the signing algorithm. Section 12.2 of [HASHSIG] offers some 362 practical implementation approaches around this statefulness. In 363 some of these approaches, nodes are sacrificed to ensure that none 364 are used more than once. As a result, the total number of signatures 365 that can be generated might be less than the overall HSS set of 366 trees. 368 6. IANA Considerations 370 IANA is requested to add entries for hash-based signatures in the 371 "COSE Algorithms" registry and hash-based public keys in the "COSE 372 Key Types" registry. 374 6.1. COSE Algorithms Registry Entry 376 The new entry in the "COSE Algorithms" registry has the following 377 columns: 379 Name: HSS-LMS 381 Value: TBD (Value to be assigned by IANA) 383 Description: HSS/LMS hash-based digital signature 385 Reference: This document (Number to be assigned by RFC Editor) 387 Recommended: Yes 389 6.2. COSE Key Types Registry Entry 391 The new entry in the "COSE Key Types" registry has the following 392 columns: 394 Name: HSS-LMS 396 Value: TBD (Value to be assigned by IANA) 398 Description: Public key for HSS/LMS hash-based digital signature 400 Reference: This document (Number to be assigned by RFC Editor) 402 7. References 404 7.1. Normative References 406 [HASHSIG] McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based 407 Signatures", draft-mcgrew-hash-sigs-15 (work in progress), 408 January 2019. 410 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 411 Requirement Levels", BCP 14, RFC 2119, 412 DOI 10.17487/RFC2119, March 1997, 413 . 415 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 416 RFC 8152, DOI 10.17487/RFC8152, July 2017, 417 . 419 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 420 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 421 May 2017, . 423 [SHS] National Institute of Standards and Technology (NIST), 424 "Secure Hash Standard", FIPS Publication 180-3, 2008. 426 7.2. Informative References 428 [BH2013] Ptacek, T., Ritter, T., Samuel, J., and A. Stamos, "The 429 Factoring Dead: Preparing for the Cryptopocalypse", August 430 2013, . 433 [LM] Leighton, F. and S. Micali, "Large provably fast and 434 secure digital signature schemes from secure hash 435 functions", U.S. Patent 5,432,852, July 1995. 437 [M1979] Merkle, R., "Secrecy, Authentication, and Public Key 438 Systems", Stanford University Information Systems 439 Laboratory Technical Report 1979-1, 1979. 441 [M1987] Merkle, R., "A Digital Signature Based on a Conventional 442 Encryption Function", Lecture Notes in Computer 443 Science crypto87, 1988. 445 [M1989a] Merkle, R., "A Certified Digital Signature", Lecture Notes 446 in Computer Science crypto89, 1990. 448 [M1989b] Merkle, R., "One Way Hash Functions and DES", Lecture 449 Notes in Computer Science crypto89, 1990. 451 [PQC] Bernstein, D., "Introduction to post-quantum 452 cryptography", 2009, 453 . 456 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 457 "Randomness Requirements for Security", BCP 106, RFC 4086, 458 DOI 10.17487/RFC4086, June 2005, 459 . 461 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 462 Housley, R., and W. Polk, "Internet X.509 Public Key 463 Infrastructure Certificate and Certificate Revocation List 464 (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, 465 . 467 Appendix A. Acknowledgements 469 Many hanks to Jim Schaad and Tony Putman for their valuable review 470 and insights. 472 Author's Address 474 Russ Housley 475 Vigil Security, LLC 476 516 Dranesville Road 477 Herndon, VA 20170 478 US 480 Email: housley@vigilsec.com