idnits 2.17.1 draft-ietf-lamps-cms-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 : ---------------------------------------------------------------------------- ** 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 (31 August 2018) is 2064 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) == Missing Reference: 'RFC2119' is mentioned on line 102, but not defined -- Looks like a reference, but probably isn't: '1' on line 198 -- Looks like a reference, but probably isn't: '2' on line 147 == Missing Reference: 'Nspk-1' is mentioned on line 149, but not defined == Missing Reference: 'Nspk' is mentioned on line 150, but not defined -- Looks like a reference, but probably isn't: '0' on line 239 == Missing Reference: 'RFC4086' is mentioned on line 332, but not defined == Unused Reference: 'RFC2219' is defined on line 404, but no explicit reference was found in the text == Unused Reference: 'PQC' is defined on line 464, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'ASN1-B' -- Possible downref: Non-RFC (?) normative reference: ref. 'ASN1-E' -- Possible downref: Non-RFC (?) normative reference: ref. 'HASHSIG' -- Possible downref: Non-RFC (?) normative reference: ref. 'SHS' Summary: 1 error (**), 0 flaws (~~), 7 warnings (==), 9 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: 4 March 2019 31 August 2018 6 Use of the HSS/LMS Hash-based Signature Algorithm 7 in the Cryptographic Message Syntax (CMS) 8 10 Abstract 12 This document specifies the conventions for using the the HSS/LMS 13 hash-based signature algorithm with the Cryptographic Message Syntax 14 (CMS). The HSS/LMS algorithm is one form of hash-based digital 15 signature; it is described in [HASHSIG]. 17 Status of this Memo 19 This Internet-Draft is submitted to IETF in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF), its areas, and its working groups. Note that 24 other groups may also distribute working documents as Internet- 25 Drafts. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 The list of current Internet-Drafts can be accessed at 33 http://www.ietf.org/1id-abstracts.html 35 The list of Internet-Draft Shadow Directories can be accessed at 36 http://www.ietf.org/shadow.html 38 Copyright and License Notice 40 Copyright (c) 2018 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 1.1. ASN.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. HSS/LMS Hash-based Signature Algorithm Overview . . . . . . . 3 59 2.1. Hierarchical Signature System (HSS) . . . . . . . . . . . 4 60 2.2. Leighton-Micali Signature (LMS) . . . . . . . . . . . . . 4 61 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) . . 5 62 3. Algorithm Identifiers and Parameters . . . . . . . . . . . . . 6 63 4. Signed-data Conventions . . . . . . . . . . . . . . . . . . . 7 64 5. Security Considerations . . . . . . . . . . . . . . . . . . . 7 65 5.1. Implementation Security Considerations . . . . . . . . . . 7 66 5.2. Algorithm Security Considerations . . . . . . . . . . . . 8 67 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 68 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 69 8. Normative References . . . . . . . . . . . . . . . . . . . . . 9 70 9. Informative References . . . . . . . . . . . . . . . . . . . . 10 71 Appendix: ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . 11 72 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 13 74 1. Introduction 76 This document specifies the conventions for using the HSS/LMS hash- 77 based signature algorithm with the Cryptographic Message Syntax (CMS) 78 [CMS] signed-data content type. The Leighton-Micali Signature (LMS) 79 system provides a one-time digital signature that is a variant of 80 Merkle Tree Signatures (MTS). A Hierarchical Signature System (HSS) 81 built on top of the LMS system to efficiently scale for a larger 82 numbers of signatures. The HSS/LMS algorithm is one form of hash- 83 based digital signature, and it is described in [HASHSIG]. The 84 HSS/LMS signature algorithm can only be used for a fixed number of 85 signing operations. The HSS/LMS signature algorithm uses small 86 private and public keys, and it has low computational cost; however, 87 the signatures are quite large. 89 1.1. ASN.1 91 CMS values are generated using ASN.1 [ASN1-B], using the Basic 92 Encoding Rules (BER) and the Distinguished Encoding Rules (DER) 93 [ASN1-E]. 95 1.2. Terminology 97 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 98 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 99 "OPTIONAL" in this document are to be interpreted as described in 100 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 101 capitals, as shown here. 103 2. HSS/LMS Hash-based Signature Algorithm Overview 105 Merkle Tree Signatures (MTS) are a method for signing a large but 106 fixed number of messages. An MTS system depends on a one-time 107 signature method and a collision-resistant hash function. 109 This specification makes use of the hash-based algorithm specified in 110 [HASHSIG], which is the Leighton and Micali adaptation [LM] of the 111 original Lamport-Diffie-Winternitz-Merkle one-time signature system 112 [M1979][M1987][M1989a][M1989b]. 114 As implied by the name, the hash-based signature algorithm depends on 115 a collision-resistant hash function. The hash-based signature 116 algorithm specified in [HASHSIG] currently uses only the SHA-256 one- 117 way hash function [SHS], but it also establishes an IANA registry to 118 permit the registration of additional one-way hash functions in the 119 future. 121 2.1. Hierarchical Signature System (HSS) 123 The MTS system specified in [HASHSIG] uses a hierarchy of trees. The 124 Hierarchical N-time Signature System (HSS) allows subordinate trees 125 to be generated when needed by the signer. Otherwise, generation of 126 the entire tree might take weeks or longer. 128 An HSS signature as specified in specified in [HASHSIG] carries the 129 number of signed public keys (Nspk), followed by that number of 130 signed public keys, followed by the LMS signature as described in 131 Section 2.2. Each signed public key is represented by the hash value 132 at the root of the tree, and it also contains information about the 133 tree structure. The signature over the public key is an LMS 134 signature as described in Section 2.2. 136 The elements of the HSS signature value for a stand-alone tree can be 137 summarized as: 139 u32str(0) || 140 lms_signature /* signature of message */ 142 The elements of the HSS signature value for a tree with Nspk levels 143 can be summarized as: 145 u32str(Nspk) || 146 signed_public_key[1] || 147 signed_public_key[2] || 148 ... 149 sigend_public_key[Nspk-1] || 150 signed_public_key[Nspk] || 151 lms_signature_on_message 153 where, as defined in Section 7 of [HASHSIG], a signed_public_key is 154 the lms_signature over the public key followed by the public key 155 itself. 157 2.2. Leighton-Micali Signature (LMS) 159 Each tree in the system specified in [HASHSIG] uses the Leighton- 160 Micali Signature (LMS) system. LMS systems have two parameters. The 161 first parameter is the height of the tree, h, which is the number of 162 levels in the tree minus one. The [HASHSIG] specification supports 163 five values for this parameter: h=5; h=10; h=15; h=20; and h=25. 164 Note that there are 2^h leaves in the tree. The second parameter is 165 the number of bytes output by the hash function, m, which the amount 166 of data associated with each node in the tree. The [HASHSIG] 167 specification supports only the SHA-256 hash function [SHS], with 168 m=32. 170 Currently, the [HASHSIG] specification supports five tree sizes: 172 LMS_SHA256_M32_H5; 173 LMS_SHA256_M32_H10; 174 LMS_SHA256_M32_H15; 175 LMS_SHA256_M32_H20; and 176 LMS_SHA256_M32_H25. 178 The [HASHSIG] specification establishes an IANA registry to permit 179 the registration of additional tree sizes in the future. 181 An LMS signature consists of four elements: the number of the leaf 182 associated with the LM-OTS signature, an LM-OTS signature as 183 described in Section 2.3, a typecode indicating the particular LMS 184 algorithm, and an array of values that is associated with the path 185 through the tree from the leaf associated with the LM-OTS signature 186 to the root. The array of values contains the siblings of the nodes 187 on the path from the leaf to the root but does not contain the nodes 188 on the path itself. The array for a tree with height h will have h 189 values. The first value is the sibling of the leaf, the next value 190 is the sibling of the parent of the leaf, and so on up the path to 191 the root. 193 The four elements of the LMS signature value can be summarized as: 195 u32str(q) || 196 ots_signature || 197 u32str(type) || 198 path[0] || path[1] || ... || path[h-1] 200 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) 202 Merkle Tree Signatures (MTS) depend on a one-time signature method. 203 [HASHSIG] specifies the use of the LM-OTS. An LM-OTS has five 204 parameters. 206 n - The number of bytes associated with the hash function. 207 [HASHSIG] supports only SHA-256 [SHS], with n=32. 209 H - A preimage-resistant hash function that accepts byte strings 210 of any length, and returns an n-byte string. 212 w - The width in bits of the Winternitz coefficients. [HASHSIG] 213 supports four values for this parameter: w=1; w=2; w=4; and 214 w=8. 216 p - The number of n-byte string elements that make up the LM-OTS 217 signature. 219 ls - The number of left-shift bits used in the checksum function, 220 which is defined in Section 4.5 of [HASHSIG]. 222 The values of p and ls are dependent on the choices of the parameters 223 n and w, as described in Appendix A of [HASHSIG]. 225 Currently, the [HASHSIG] specification supports four LM-OTS variants: 227 LMOTS_SHA256_N32_W1; 228 LMOTS_SHA256_N32_W2; 229 LMOTS_SHA256_N32_W4; and 230 LMOTS_SHA256_N32_W8. 232 The [HASHSIG] specification establishes an IANA registry to permit 233 the registration of additional variants in the future. 235 Signing involves the generation of C, an n-byte random value. 237 The LM-OTS signature value can be summarized as: 239 u32str(otstype) || C || y[0] || ... || y[p-1] 241 3. Algorithm Identifiers and Parameters 243 The algorithm identifier for an HSS/LMS hash-based signature is 244 id-alg-hss-lms-hashsig: 246 id-alg-hss-lms-hashsig OBJECT IDENTIFIER ::= { iso(1) 247 member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) 248 smime(16) alg(3) 17 } 250 When the id-alg-hss-lms-hashsig algorithm identifier is used for a 251 signature, the AlgorithmIdentifier parameters field MUST be absent 252 (that is, the parameters are not present; the parameters are not set 253 to NULL). 255 Note that the id-alg-hss-lms-hashsig algorithm identifier is also 256 referred to as id-alg-mts-hashsig. This synonym is based on the 257 terminology used in an early draft of the document that became 258 [HASHSIG]. 260 The signature values is a large OCTET STRING. The signature format 261 is designed for easy parsing. Each format includes a counter and 262 type codes that indirectly providing all of the information that is 263 needed to parse the value during signature validation. 265 4. Signed-data Conventions 267 As specified in [CMS], the digital signature is produced from the 268 message digest and the signer's private key. If signed attributes 269 are absent, then the message digest is the hash of the content. If 270 signed attributes are present, then the hash of the content is placed 271 in the message-digest attribute, the set of signed attributes is DER 272 encoded, and the message digest is the hash of the encoded 273 attributes. In summary: 275 IF (signed attributes are absent) 276 THEN md = Hash(content) 277 ELSE message-digest attribute = Hash(content); 278 md = Hash(DER(SignedAttributes)) 280 Sign(md) 282 When using [HASHSIG], the fields in the SignerInfo are used as 283 follows: 285 digestAlgorithms SHOULD contain the one-way hash function used to 286 compute the message digest on the eContent value. Since the 287 hash-based signature algorithms all depend on SHA-256, it is 288 strongly RECOMMENDED that SHA-256 also be used to compute the 289 message digest on the content. 291 Further, the same one-way hash function SHOULD be used to 292 compute the message digest on both the eContent and the 293 signedAttributes value if signedAttributes are present. Again, 294 since the hash-based signature algorithms all depend on 295 SHA-256, it is strongly RECOMMENDED that SHA-256 be used. 297 signatureAlgorithm MUST contain id-alg-hss-lms-hashsig. The 298 algorithm parameters field MUST be absent. 300 signature contains the single HSS signature value resulting from 301 the signing operation as specified in [HASHSIG]. 303 5. Security Considerations 305 5.1. Implementation Security Considerations 307 Implementations must protect the private keys. Compromise of the 308 private keys may result in the ability to forge signatures. Along 309 with the private key, the implementation must keep track of which 310 leaf nodes in the tree have been used. Loss of integrity of this 311 tracking data can cause an one-time key to be used more than once. 312 As a result, when a private key and the tracking data are stored on 313 non-volatile media or stored in a virtual machine environment, care 314 must be taken to preserve confidentiality and integrity. 316 An implementation must ensure that a LM-OTS private key is used to 317 generate a signature only one time, and ensure that it cannot be used 318 for any other purpose. 320 The generation of private keys relies on random numbers. The use of 321 inadequate pseudo-random number generators (PRNGs) to generate these 322 values can result in little or no security. An attacker may find it 323 much easier to reproduce the PRNG environment that produced the keys, 324 searching the resulting small set of possibilities, rather than brute 325 force searching the whole key space. The generation of quality 326 random numbers is difficult. RFC 4086 [RANDOM] offers important 327 guidance in this area. 329 The generation of hash-based signatures also depends on random 330 numbers. While the consequences of an inadequate pseudo-random 331 number generator (PRNGs) to generate these values is much less severe 332 than the generation of private keys, the guidance in [RFC4086] 333 remains important. 335 When computing signatures, the same hash function SHOULD be used for 336 all operations. In this specification, only SHA-256 is used. Using 337 only SHA-256 reduces the number of possible failure points in the 338 signature process. 340 5.2. Algorithm Security Considerations 342 At Black Hat USA 2013, some researchers gave a presentation on the 343 current sate of public key cryptography. They said: "Current 344 cryptosystems depend on discrete logarithm and factoring which has 345 seen some major new developments in the past 6 months" [BH2013]. 346 They encouraged preparation for a day when RSA and DSA cannot be 347 depended upon. 349 A post-quantum cryptosystem is a system that is secure against 350 quantum computers that have more than a trivial number of quantum 351 bits. It is open to conjecture when it will be feasible to build 352 such a machine. RSA, DSA, and ECDSA are not post-quantum secure. 354 The LM-OTP one-time signature, LMS, and HSS do not depend on discrete 355 logarithm or factoring, as a result these algorithms are considered 356 to be post-quantum secure. 358 Today, RSA is often used to digitally sign software updates. This 359 means that the distribution of software updates could be compromised 360 if a significant advance is made in factoring or a quantum computer 361 is invented. The use of HSS/LMS hash-based signatures to protect 362 software update distribution, perhaps using the format described in 363 [FWPROT], will allow the deployment of software that implements new 364 cryptosystems. 366 6. IANA Considerations 368 SMI Security for S/MIME Module Identifier (1.2.840.113549.1.9.16.0) 369 registry, change the reference for value 64 to point to this 370 document. 372 In the SMI Security for S/MIME Algorithms (1.2.840.113549.1.9.16.3) 373 registry, change the description for value 17 to 374 "id-alg-hss-lms-hashsig" and change the reference to point to this 375 document. Also, add the following note at the top of the registry: 377 Value 17, "id-alg-hss-lms-hashsig", is also referred to as 378 "id-alg-mts-hashsig". 380 7. Acknowledgements 382 Many thanks to Panos Kampanakis, Jim Schaad, and Sean Turner for 383 their careful review and comments. 385 8. Normative References 387 [ASN1-B] ITU-T, "Information technology -- Abstract Syntax Notation 388 One (ASN.1): Specification of basic notation", ITU-T 389 Recommendation X.680, 2015. 391 [ASN1-E] ITU-T, "Information technology -- ASN.1 encoding rules: 392 Specification of Basic Encoding Rules (BER), Canonical 393 Encoding Rules (CER) and Distinguished Encoding Rules 394 (DER)", ITU-T Recommendation X.690, 2015. 396 [CMS] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, 397 RFC 5652, DOI 10.17487/RFC5652, September 2009, 398 . 400 [HASHSIG] McGrew, D., M. Curcio, and S. Fluhrer, "Hash-Based 401 Signatures", Work in progress. 402 404 [RFC2219] Bradner, S., "Key words for use in RFCs to Indicate 405 Requirement Levels", BCP 14, RFC 2119, DOI 406 10.17487/RFC2119, March 1997, . 409 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in 410 RFC 2119 Key Words", BCP 14, RFC 8174, DOI 411 10.17487/RFC8174, May 2017, . 414 [SHS] National Institute of Standards and Technology (NIST), 415 FIPS Publication 180-3: Secure Hash Standard, October 416 2008. 418 9. Informative References 420 [BH2013] Ptacek, T., T. Ritter, J. Samuel, and A. Stamos, "The 421 Factoring Dead: Preparing for the Cryptopocalypse", August 422 2013. 425 [CMSASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for 426 Cryptographic Message Syntax (CMS) and S/MIME", RFC 5911, 427 DOI 10.17487/RFC5911, June 2010, . 430 [CMSASN1U] Schaad, J. and S. Turner, "Additional New ASN.1 Modules 431 for the Cryptographic Message Syntax (CMS) and the Public 432 Key Infrastructure Using X.509 (PKIX)", RFC 6268, DOI 433 10.17487/RFC6268, July 2011, . 436 [FWPROT] Housley, R., "Using Cryptographic Message Syntax (CMS) to 437 Protect Firmware Packages", RFC 4108, DOI 438 10.17487/RFC4108, August 2005, . 441 [LM] Leighton, T. and S. Micali, "Large provably fast and 442 secure digital signature schemes from secure hash 443 functions", U.S. Patent 5,432,852, July 1995. 445 [M1979] Merkle, R., "Secrecy, Authentication, and Public Key 446 Systems", Stanford University Information Systems 447 Laboratory Technical Report 1979-1, 1979. 449 [M1987] Merkle, R., "A Digital Signature Based on a Conventional 450 Encryption Function", Lecture Notes in Computer Science 451 crypto87, 1988. 453 [M1989a] Merkle, R., "A Certified Digital Signature", Lecture Notes 454 in Computer Science crypto89, 1990. 456 [M1989b] Merkle, R., "One Way Hash Functions and DES", Lecture Notes 457 in Computer Science crypto89, 1990. 459 [PKIXASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for the 460 Public Key Infrastructure Using X.509 (PKIX)", RFC 5912, 461 DOI 10.17487/RFC5912, June 2010, . 464 [PQC] Bernstein, D., "Introduction to post-quantum 465 cryptography", 2009. 466 469 [RANDOM] Eastlake 3rd, D., Schiller, J., and S. Crocker, 470 "Randomness Requirements for Security", BCP 106, RFC 4086, 471 DOI 10.17487/RFC4086, June 2005, . 474 Appendix: ASN.1 Module 476 MTS-HashSig-2013 477 { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) 478 id-smime(16) id-mod(0) id-mod-mts-hashsig-2013(64) } 480 DEFINITIONS IMPLICIT TAGS ::= BEGIN 482 EXPORTS ALL; 484 IMPORTS 485 PUBLIC-KEY, SIGNATURE-ALGORITHM, SMIME-CAPS 486 FROM AlgorithmInformation-2009 -- RFC 5911 [CMSASN1] 487 { iso(1) identified-organization(3) dod(6) internet(1) 488 security(5) mechanisms(5) pkix(7) id-mod(0) 489 id-mod-algorithmInformation-02(58) } 490 mda-sha256 491 FROM PKIX1-PSS-OAEP-Algorithms-2009 -- RFC 5912 [PKIXASN1] 492 { iso(1) identified-organization(3) dod(6) 493 internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) 494 id-mod-pkix1-rsa-pkalgs-02(54) } ; 496 -- 497 -- Object Identifiers 498 -- 500 id-alg-hss-lms-hashsig OBJECT IDENTIFIER ::= { iso(1) member-body(2) 501 us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 } 503 -- 504 -- Signature Algorithm and Public Key 505 -- 507 sa-HSS-LMS-HashSig SIGNATURE-ALGORITHM ::= { 508 IDENTIFIER id-alg-hss-lms-hashsig 509 PARAMS ARE absent 510 HASHES { mda-sha256 } 511 PUBLIC-KEYS { pk-HSS-LMS-HashSig } 512 SMIME-CAPS { IDENTIFIED BY id-alg-hss-lms-hashsig } } 514 pk-HSS-LMS-HashSig PUBLIC-KEY ::= { 515 IDENTIFIER id-alg-hss-lms-hashsig 516 KEY HSS-LMS-HashSig-PublicKey 517 PARAMS ARE absent 518 CERT-KEY-USAGE 519 { digitalSignature, nonRepudiation, keyCertSign, cRLSign } } 521 HSS-LMS-HashSig-PublicKey ::= OCTET STRING 523 -- 524 -- Expand the signature algorithm set used by CMS [CMSASN1U] 525 -- 527 SignatureAlgorithmSet SIGNATURE-ALGORITHM ::= 528 { sa-HSS-LMS-HashSig, ... } 530 -- 531 -- Expand the S/MIME capabilities set used by CMS [CMSASN1] 532 -- 534 SMimeCaps SMIME-CAPS ::= { sa-HSS-LMS-HashSig.&smimeCaps, ... } 536 END 538 Author's Address 540 Russ Housley 541 Vigil Security, LLC 542 918 Spring Knoll Drive 543 Herndon, VA 20170 544 USA 546 EMail: housley@vigilsec.com