idnits 2.17.1 draft-ietf-cose-hash-sig-00.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 : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 5 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 187 has weird spacing: '...ication estab...' == Line 244 has weird spacing: '...ication estab...' -- The document date (15 January 2019) is 1925 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 252 -- Looks like a reference, but probably isn't: '1' on line 207 == Missing Reference: 'Nspk-2' is mentioned on line 156, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 157, but not defined == Unused Reference: 'PQC' is defined on line 450, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'HASHSIG' ** Obsolete normative reference: RFC 8152 (Obsoleted by RFC 9052, RFC 9053) -- Possible downref: Non-RFC (?) normative reference: ref. 'SHS' Summary: 2 errors (**), 0 flaws (~~), 6 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT R. Housley 3 Intended Status: Proposed Standard Vigil Security 4 Expires: 15 July 2019 15 January 2019 6 Use of the Hash-based Signature Algorithm with 7 CBOR Object Signing and Encryption (COSE) 8 10 Abstract 12 This document specifies the conventions for using the Leighton-Micali 13 Signature (LMS) algorithm for digital signatures with the CBOR Object 14 Signing and Encryption (COSE) syntax. 16 Status of this Memo 18 This Internet-Draft is submitted to IETF in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as Internet- 24 Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/1id-abstracts.html 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html 37 Copyright and License Notice 39 Copyright (c) 2018 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 3. LMS Digital Signature Algorithm Overview . . . . . . . . . . . 3 57 3.1. Hierarchical Signature System (HSS) . . . . . . . . . . . 4 58 3.2. Leighton-Micali Signature (LMS) . . . . . . . . . . . . . 5 59 3.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) . . 6 60 4. Hash-based Signature Algorithm Identifiers . . . . . . . . . . 7 61 5. Security Considerations . . . . . . . . . . . . . . . . . . . 7 62 5.1. Implementation Security Considerations . . . . . . . . . . 7 63 5.2. Algorithm Security Considerations . . . . . . . . . . . . 8 64 6. Operational Considerations . . . . . . . . . . . . . . . . . . 8 65 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 66 7.1. COSE Algorithms Registry Entry . . . . . . . . . . . . . . 9 67 7.2. COSE Key Types Registry Entry . . . . . . . . . . . . . . 9 68 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 69 8.1. Normative References . . . . . . . . . . . . . . . . . . . 10 70 8.2. Informative References . . . . . . . . . . . . . . . . . . 10 71 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 11 72 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 1. Introduction 76 Today, RSA is often used to digitally sign software updates. In 77 preparation for a day when RSA, DSA, and ECDSA cannot be depended 78 upon, a digital signature algorithm is needed that will remain secure 79 even if there are significant cryptoanalytic advances or a large- 80 scale quantum computer is invented. The hash-based digital signature 81 algorithm specified in [HASHSIG] is one such algorithm. The use of 82 hash-based signatures to protect software update distribution will 83 allow the deployment of software that implements new cryptosystems 84 even if such advances break current digital signature mechanisms. 86 This document specifies the conventions for using the Leighton-Micali 87 Signature (LMS) algorithm [HASHSIG] for digital signatures with the 88 CBOR Object Signing and Encryption (COSE) [RFC8152] syntax. The LMS 89 algorithm is one form of hash-based digital signature; it can only be 90 used for a fixed number of signatures. The LMS algorithm uses small 91 private and public keys, and it has low computational cost; however, 92 the signatures are quite large. 94 2. Terminology 96 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 97 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 98 "OPTIONAL" in this document are to be interpreted as described in 99 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 100 capitals, as shown here. 102 3. LMS Digital Signature Algorithm Overview 104 This specification makes use of the hash-based signature algorithm 105 specified in [HASHSIG], which is the Leighton and Micali adaptation 106 [LM] of the original Lamport-Diffie-Winternitz-Merkle one-time 107 signature system [M1979][M1987][M1989a][M1989b]. 109 The hash-based signature algorithm has three major components: 111 o Hierarchical Signature System (HSS) -- see Section 3.1; 113 o Leighton-Micali Signature (LMS) -- see Section 3.2; and 115 o Leighton-Micali One-time Signature Algorithm (LM-OTS) -- see 116 Section 3.3. 118 As implied by the name, the hash-based signature algorithm depends on 119 a collision-resistant hash function. The the hash-based signature 120 algorithm specified in [HASHSIG] currently makes use of the SHA-256 121 one-way hash function [SHS], but it also establishes an IANA registry 122 to permit the registration of additional one-way hash functions in 123 the future. 125 3.1. Hierarchical Signature System (HSS) 127 The hash-based signature algorithm specified in [HASHSIG] uses a 128 hierarchy of trees. The Hierarchical Signature System (HSS) allows 129 subordinate trees to be generated when needed by the signer. By 130 using trees-of-trees, a very large number of nodes can be 131 accommodated, where each node enables a single digital signature. 132 Without the HSS, the generation of such a large tree might take weeks 133 or longer. 135 An HSS signature as specified in [HASHSIG] carries the number of 136 signed public keys (Nspk), followed by that number of signed public 137 keys, followed by the LMS signature as described in Section 3.2. 138 Each signed public key is represented by the hash value at the root 139 of the tree, and it also contains information about the tree 140 structure. The signature over the public key is an LMS signature as 141 described in Section 3.2. 143 The elements of the HSS signature value for a stand-alone tree can be 144 summarized as: 146 u32str(0) || 147 lms_signature /* signature of message */ 149 The elements of the HSS signature value for a tree with Nspk levels 150 can be summarized as: 152 u32str(Nspk) || 153 signed_public_key[0] || 154 signed_public_key[1] || 155 ... 156 signed_public_key[Nspk-2] || 157 signed_public_key[Nspk-1] || 158 lms_signature /* signature of message */ 160 where, as defined in Section 3.3 of [HASHSIG], a signed_public_key is 161 the lms_signature over the public key followed by the public key 162 itself. Note that Nspk is the number of levels in the hierarchy of 163 trees minus 1. 165 3.2. Leighton-Micali Signature (LMS) 167 Each tree in the hash-based signature algorithm specified in 168 [HASHSIG] uses the Leighton-Micali Signature (LMS) system. LMS 169 systems have two parameters. The first parameter is the height of 170 the tree, h, which is the number of levels in the tree minus one. 171 The hash-based signature algorithm supports five values for this 172 parameter: h=5; h=10; h=15; h=20; and h=25. Note that there are 2^h 173 leaves in the tree. The second parameter is the number of bytes 174 output by the hash function, m, which is the amount of data 175 associated with each node in the tree. This specification supports 176 only SHA-256, with m=32. 178 Currently, the hash-based signature algorithm supports five tree 179 sizes: 181 LMS_SHA256_M32_H5; 182 LMS_SHA256_M32_H10; 183 LMS_SHA256_M32_H15; 184 LMS_SHA256_M32_H20; and 185 LMS_SHA256_M32_H25. 187 The [HASHSIG] specification establishes an IANA registry to permit 188 the registration of additional tree sizes in the future. 190 An LMS signature consists of four elements: the number of the leaf 191 associated with the LM-OTS signature, an LM-OTS signature as 192 described in Section 3.3, a typecode indicating the particular LMS 193 algorithm, and an array of values that is associated with the path 194 through the tree from the leaf associated with the LM-OTS signature 195 to the root. The array of values contains the siblings of the nodes 196 on the path from the leaf to the root but does not contain the nodes 197 on the path itself. The array for a tree with height h will have h 198 values. The first value is the sibling of the leaf, the next value 199 is the sibling of the parent of the leaf, and so on up the path to 200 the root. 202 The four elements of the LMS signature value can be summarized as: 204 u32str(q) || 205 ots_signature || 206 u32str(type) || 207 path[0] || path[1] || ... || path[h-1] 209 3.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) 211 The hash-based signature algorithm depends on a one-time signature 212 method. This specification makes use of the Leighton-Micali One-time 213 Signature Algorithm (LM-OTS) [HASHSIG]. An LM-OTS has five 214 parameters: 216 n - The number of bytes output by the hash function. This 217 specification supports only SHA-256 [SHS], with n=32. 219 H - A preimage-resistant hash function that accepts byte strings 220 of any length, and returns an n-byte string. This 221 specification supports only SHA-256 [SHS]. 223 w - The width in bits of the Winternitz coefficients. [HASHSIG] 224 supports four values for this parameter: w=1; w=2; w=4; and 225 w=8. 227 p - The number of n-byte string elements that make up the LM-OTS 228 signature. 230 ls - The number of left-shift bits used in the checksum function, 231 which is defined in Section 4.5 of [HASHSIG]. 233 The values of p and ls are dependent on the choices of the parameters 234 n and w, as described in Appendix A of [HASHSIG]. 236 Currently, the hash-based signature algorithm supports four LM-OTS 237 variants: 239 LMOTS_SHA256_N32_W1; 240 LMOTS_SHA256_N32_W2; 241 LMOTS_SHA256_N32_W4; and 242 LMOTS_SHA256_N32_W8. 244 The [HASHSIG] specification establishes an IANA registry to permit 245 the registration of additional variants in the future. 247 Signing involves the generation of C, which is an n-byte random 248 value. 250 The LM-OTS signature value can be summarized as: 252 u32str(otstype) || C || y[0] || ... || y[p-1] 254 4. Hash-based Signature Algorithm Identifiers 256 The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two 257 signature algorithm schemes. This specification makes use of the 258 signature with appendix scheme for hash-based signatures. 260 The signature value is a large byte string. The byte string is 261 designed for easy parsing, and it includes a counter and type codes 262 that indirectly provide all of the information that is needed to 263 parse the byte string during signature validation. 265 When using a COSE key for this algorithm, the following checks are 266 made: 268 o The 'kty' field MUST be present, and it MUST be 'HSS-LMS'. 270 o If the 'alg' field is present, and it MUST be 'HSS-LMS'. 272 o If the 'key_ops' field is present, it MUST include 'sign' when 273 creating a hash-based signature. 275 o If the 'key_ops' field is present, it MUST include 'verify' 276 when verifying a hash-based signature. 278 o If the 'kid' field is present, it MAY be used to identify the 279 top of the HSS tree. In [HASHSIG], this identifier is called 280 'I', and it is the 16-byte identifier of the LMS public key 281 for the tree. 283 5. Security Considerations 285 5.1. Implementation Security Considerations 287 Implementations must protect the private keys. Use of a hardware 288 security module (HSM) is one way to protect the private keys. 289 Compromise of the private keys may result in the ability to forge 290 signatures. Along with the private key, the implementation must keep 291 track of which leaf nodes in the tree have been used. Loss of 292 integrity of this tracking data can cause a one-time key to be used 293 more than once. As a result, when a private key and the tracking 294 data are stored on non-volatile media or stored in a virtual machine 295 environment, care must be taken to preserve confidentiality and 296 integrity. 298 When a LMS key pair is generating a LMS key pair, an implementation 299 must must generate the key pair and the corresponding identifier 300 independently of all other key pairs in the HSS tree. 302 An implementation must ensure that a LM-OTS private key is used to 303 generate a signature only one time, and ensure that it cannot be used 304 for any other purpose. 306 The generation of private keys relies on random numbers. The use of 307 inadequate pseudo-random number generators (PRNGs) to generate these 308 values can result in little or no security. An attacker may find it 309 much easier to reproduce the PRNG environment that produced the keys, 310 searching the resulting small set of possibilities, rather than brute 311 force searching the whole key space. The generation of quality 312 random numbers is difficult. [RFC4086] offers important guidance in 313 this area. 315 The generation of hash-based signatures also depends on random 316 numbers. While the consequences of an inadequate pseudo-random 317 number generator (PRNGs) to generate these values is much less severe 318 than the generation of private keys, the guidance in [RFC4086] 319 remains important. 321 5.2. Algorithm Security Considerations 323 At Black Hat USA 2013, some researchers gave a presentation on the 324 current sate of public key cryptography. They said: "Current 325 cryptosystems depend on discrete logarithm and factoring which has 326 seen some major new developments in the past 6 months" [BH2013]. 327 They encouraged preparation for a day when RSA and DSA cannot be 328 depended upon. 330 A post-quantum cryptosystem is a system that is secure against 331 quantum computers that have more than a trivial number of quantum 332 bits. It is open to conjecture when it will be feasible to build 333 such a machine. RSA, DSA, and ECDSA are not post-quantum secure. 335 The LM-OTP one-time signature, LMS, and HSS do not depend on discrete 336 logarithm or factoring, as a result these algorithms are considered 337 to be post-quantum secure. 339 Today, RSA is often used to digitally sign software updates. This 340 means that the distribution of software updates could be compromised 341 if a significant advance is made in factoring or a quantum computer 342 is invented. The use of hash-based signatures to protect software 343 update distribution will allow the deployment of software that 344 implements new cryptosystems. 346 6. Operational Considerations 348 The public key for the hash-based signature is the key at the root of 349 Hierarchical Signature System (HSS). In the absence of a public key 350 infrastructure [RFC5280], this public key is a trust anchor, and the 351 number of signatures that can be generated is bounded by the size of 352 the overall HSS set of trees. When all of the LM-OTS signatures have 353 been used to produce a signature, then the establishment of a new 354 trust anchor is required. 356 To ensure that none of tree nodes are used to generate more than one 357 signature, the signer maintains state across different invocations of 358 the signing algorithm. Section 12.2 of [HASHSIG] offers some 359 practical implementation approaches around this statefulness. In 360 some of these approaches, nodes are sacrificed to ensure that none 361 are used more than once. As a result, the total number of signatures 362 that can be generated might be less than the overall HSS set of 363 trees. 365 7. IANA Considerations 367 IANA is requested to add entries for hash-based signatures in the 368 "COSE Algorithms" registry and hash-based public keys in the "COSE 369 Key Types" registry. 371 7.1. COSE Algorithms Registry Entry 373 The new entry in the "COSE Algorithms" registry has the following 374 columns: 376 Name: HASHSIG-HSS-LMS 378 Value: TBD (Value to be assigned by IANA) 380 Description: Hash-based digital signatures using HSS/LMS 382 Reference: This document (Number to be assigned by RFC Editor) 384 Recommended: Yes 386 7.2. COSE Key Types Registry Entry 388 The new entry in the "COSE Key Types" registry has the following 389 columns: 391 Name: HASHSIG-HSS-LMS 393 Value: TBD (Value to be assigned by IANA) 395 Description: Public key for hash-based digital signature using HSS/LMS 397 Reference: This document (Number to be assigned by RFC Editor) 399 8. References 401 8.1. Normative References 403 [HASHSIG] McGrew, D., M. Curcio, and S. Fluhrer, "Hash-Based 404 Signatures", Work in progress. 407 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 408 Requirement Levels", BCP 14, RFC 2119, DOI 409 10.17487/RFC2119, March 1997, . 412 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 413 RFC 8152, DOI 10.17487/RFC8152, July 2017, 414 . 416 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in 417 RFC 2119 Key Words", BCP 14, RFC 8174, DOI 418 10.17487/RFC8174, May 2017, . 421 [SHS] National Institute of Standards and Technology (NIST), 422 FIPS Publication 180-3: Secure Hash Standard, October 423 2008. 425 8.2. Informative References 427 [BH2013] Ptacek, T., T. Ritter, J. Samuel, and A. Stamos, "The 428 Factoring Dead: Preparing for the Cryptopocalypse", August 429 2013. 432 [LM] Leighton, T. and S. Micali, "Large provably fast and 433 secure digital signature schemes from secure hash 434 functions", U.S. Patent 5,432,852, July 1995. 436 [M1979] Merkle, R., "Secrecy, Authentication, and Public Key 437 Systems", Stanford University Information Systems 438 Laboratory Technical Report 1979-1, 1979. 440 [M1987] Merkle, R., "A Digital Signature Based on a Conventional 441 Encryption Function", Lecture Notes in Computer Science 442 crypto87, 1988. 444 [M1989a] Merkle, R., "A Certified Digital Signature", Lecture Notes 445 in Computer Science crypto89, 1990. 447 [M1989b] Merkle, R., "One Way Hash Functions and DES", Lecture Notes 448 in Computer Science crypto89, 1990. 450 [PQC] Bernstein, D., "Introduction to post-quantum 451 cryptography", 2009. 452 455 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 456 "Randomness Requirements for Security", BCP 106, RFC 4086, 457 DOI 10.17487/RFC4086, June 2005, . 460 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 461 Housley, R., and W. Polk, "Internet X.509 Public Key 462 Infrastructure Certificate and Certificate Revocation List 463 (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, 464 . 466 Acknowledgements 468 Thanks to Jim Schaad and Tony Putman for their valuable review and 469 insights. 471 Author's Address 473 Russ Housley 474 Vigil Security, LLC 475 516 Dranesville Road 476 Herndon, VA 20170 477 USA 479 EMail: housley@vigilsec.com