idnits 2.17.1 draft-housley-cms-mts-hash-sig-09.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 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (11 June 2018) is 2146 days in the past. Is this intentional? 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 97, but not defined -- Looks like a reference, but probably isn't: '0' on line 216 -- Looks like a reference, but probably isn't: '1' on line 178 -- Looks like a reference, but probably isn't: '2' on line 135 == Missing Reference: 'Nspk-2' is mentioned on line 137, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 138, but not defined == Missing Reference: 'Nspk' is mentioned on line 138, but not defined == Unused Reference: 'RFC2219' is defined on line 363, but no explicit reference was found in the text == Unused Reference: 'PQC' is defined on line 423, 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 (==), 8 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: 11 December 2018 11 June 2018 6 Use of the Hash-based Merkle Tree Signature (MTS) Algorithm 7 in the Cryptographic Message Syntax (CMS) 8 10 Abstract 12 This document specifies the conventions for using the Merkle Tree 13 Signatures (MTS) digital signature algorithm with the Cryptographic 14 Message Syntax (CMS). The MTS algorithm is one form of hash-based 15 digital signature. 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. MTS Digital Signature Algorithm Overview . . . . . . . . . . . 3 59 2.1. Hierarchical Signature System (HSS) . . . . . . . . . . . 3 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 . . . . . . . . . . . . . . . . . . . 6 64 5. Security Considerations . . . . . . . . . . . . . . . . . . . 7 65 5.1. Implementation Security Considerations . . . . . . . . . . 7 66 5.2. Algorithm Security Considerations . . . . . . . . . . . . 7 67 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 68 7. Normative References . . . . . . . . . . . . . . . . . . . . . 8 69 8. Informative References . . . . . . . . . . . . . . . . . . . . 8 70 Appendix: ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . 10 71 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 11 73 1. Introduction 75 This document specifies the conventions for using the Merkle Tree 76 Signatures (MTS) digital signature algorithm with the Cryptographic 77 Message Syntax (CMS) [CMS] signed-data content type. The MTS 78 algorithm is one form of hash-based digital signature that can only 79 be used for a fixed number of signatures. The MTS algorithm is 80 described in [HASHSIG]. The MTS algorithm uses small private and 81 public keys, and it has low computational cost; however, the 82 signatures are quite large. 84 1.1. ASN.1 86 CMS values are generated using ASN.1 [ASN1-B], using the Basic 87 Encoding Rules (BER) and the Distinguished Encoding Rules (DER) 88 [ASN1-E]. 90 1.2. Terminology 92 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 93 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 94 "OPTIONAL" in this document are to be interpreted as described in 95 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 96 capitals, as shown here. 98 2. MTS Digital Signature Algorithm Overview 100 Merkle Tree Signatures (MTS) are a method for signing a large but 101 fixed number of messages. An MTS system depends on a one-time 102 signature method and a collision-resistant hash function. 104 This specification makes use of the MTS algorithm specified in 105 [HASHSIG], which is the Leighton and Micali adaptation [LM] of the 106 original Lamport-Diffie-Winternitz-Merkle one-time signature system 107 [M1979][M1987][M1989a][M1989b]. It makes use of the LM-OTS one-time 108 signature scheme and the SHA-256 one-way hash function [SHS]. 110 2.1. Hierarchical Signature System (HSS) 112 The MTS system specified in [HASHSIG] uses a hierarchy of trees. The 113 Hierarchical N-time Signature System (HSS) allows subordinate trees 114 to be generated when needed by the signer. Otherwise, generation of 115 the entire tree might take weeks or longer. 117 An HSS signature as specified in specified in [HASHSIG] carries the 118 number of signed public keys (Nspk), followed by that number of 119 signed public keys, followed by the LMS signature as described in 120 Section 2.2. Each signed public key is represented by the hash value 121 at the root of the tree, and the signature over that public key is an 122 LMS signature as described in Section 2.2. 124 The elements of the HSS signature value for a stand-alone tree can be 125 summarized as: 127 u32str(0) || 128 lms_signature_on_message 130 The elements of the HSS signature value for a tree with Nspk levels 131 can be summarized as: 133 u32str(Nspk) || 134 lms_signature_on_public_key[0] || public_key[1] || 135 lms_signature_on_public_key[1] || public_key[2] || 136 ... 137 lms_signature_on_public_key[Nspk-2] || public_key[Nspk-1] || 138 lms_signature_on_public_key[Nspk-1] || public_key[Nspk] || 139 lms_signature_on_message 141 2.2. Leighton-Micali Signature (LMS) 143 Each tree in the system specified in [HASHSIG] uses the Leighton- 144 Micali Signature (LMS) system. LMS systems have two parameters. The 145 first parameter is the height of the tree, h, which is the number of 146 levels in the tree minus one. The [HASHSIG] specification supports 147 five values for this parameter: h=5; h=10; h=15; h=20; and h=25. 148 Note that there are 2^h leaves in the tree. The second parameter is 149 the number of bytes output by the hash function, m, which the amount 150 of data associated with each node in the tree. The [HASHSIG] 151 specification supports only the SHA-256 hash function [SHS], with 152 m=32. 154 Five tree sizes are specified in [HASHSIG]: 156 LMS_SHA256_M32_H5; 157 LMS_SHA256_M32_H10; 158 LMS_SHA256_M32_H15; 159 LMS_SHA256_M32_H20; and 160 LMS_SHA256_M32_H25. 162 An LMS signature consists of four elements: a typecode indicating the 163 particular LMS algorithm, the number of the leaf associated with the 164 LM-OTS signature, an LM-OTS signature as described in Section 2.3, 165 and an array of values that is associated with the path through the 166 tree from the leaf associated with the LM-OTS signature to the root. 167 The array of values contains the siblings of the nodes on the path 168 from the leaf to the root but does not contain the nodes on the path 169 itself. The array for a tree with height h will have h values. The 170 first value is the sibling of the leaf, the next value is the sibling 171 of the parent of the leaf, and so on up the path to the root. 173 The four elements of the LMS signature value can be summarized as: 175 u32str(q) || 176 ots_signature || 177 u32str(type) || 178 path[0] || path[1] || ... || path[h-1] 180 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) 182 Merkle Tree Signatures (MTS) depend on a one-time signature method. 183 [HASHSIG] specifies the use of the LM-OTS. An LM-OTS has five 184 parameters. 186 n - The number of bytes associated with the hash function. 187 [HASHSIG] supports only SHA-256 [SHS], with n=32. 189 H - A preimage-resistant hash function that accepts byte strings 190 of any length, and returns an n-byte string. 192 w - The width in bits of the Winternitz coefficients. [HASHSIG] 193 supports four values for this parameter: w=1; w=2; w=4; and 194 w=8. 196 p - The number of n-byte string elements that make up the LM-OTS 197 signature. 199 ls - The number of left-shift bits used in the checksum function, 200 which is defined in Section 4.5 of [HASHSIG]. 202 The values of p and ls are dependent on the choices of the parameters 203 n and w, as described in Appendix A of [HASHSIG]. 205 Four LM-OTS variants are defined in [HASHSIG]: 207 LMOTS_SHA256_N32_W1; 208 LMOTS_SHA256_N32_W2; 209 LMOTS_SHA256_N32_W4; and 210 LMOTS_SHA256_N32_W8. 212 Signing involves the generation of C, an n-byte random value. 214 The LM-OTS signature value can be summarized as: 216 u32str(type) || C || y[0] || ... || y[p-1] 218 3. Algorithm Identifiers and Parameters 220 The algorithm identifier for an MTS signature is id-alg-mts-hashsig: 222 id-alg-mts-hashsig OBJECT IDENTIFIER ::= { iso(1) member-body(2) 223 us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 } 225 When the id-alg-mts-hashsig algorithm identifier is used for a 226 signature, the AlgorithmIdentifier parameters field MUST be absent 227 (that is, the parameters are not present; the parameters are not set 228 to NULL). 230 The signature values is a large OCTET STRING. The signature format 231 is designed for easy parsing. Each format includes a counter and 232 type codes that indirectly providing all of the information that is 233 needed to parse the value during signature validation. The first 4 234 octets of the signature value contains the number of signed public 235 keys (Nspk) in the HSS. The first 4 octets of each LMS signature 236 value contains type code, which tells how to parse the remaining 237 parts of the signature value. The first 4 octets of each LM-OTS 238 signature value contains type code, which tells how to parse the 239 remaining parts of the signature value. 241 4. Signed-data Conventions 243 As specified in [CMS], the digital signature is produced from the 244 message digest and the signer's private key. If signed attributes 245 are absent, then the message digest is the hash of the content. If 246 signed attributes are present, then the hash of the content is placed 247 in the message-digest attribute, the set of signed attributes is DER 248 encoded, and the message digest is the hash of the encoded 249 attributes. In summary: 251 IF (signed attributes are absent) 252 THEN md = Hash(content) 253 ELSE message-digest attribute = Hash(content); 254 md = Hash(DER(SignedAttributes)) 256 Sign(md) 258 When using [HASHSIG], the fields in the SignerInfo are used as 259 follows: 261 digestAlgorithms SHOULD contain the one-way hash function used to 262 compute the message digest on the eContent value. Since the 263 hash-based signature algorithms all depend on SHA-256, it is 264 strongly RECOMMENDED that SHA-256 also be used to compute the 265 message digest on the content. 267 Further, the same one-way hash function SHOULD be used to 268 compute the message digest on both the eContent and the 269 signedAttributes value if signedAttributes are present. Again, 270 since the hash-based signature algorithms all depend on 271 SHA-256, it is strongly RECOMMENDED that SHA-256 be used. 273 signatureAlgorithm MUST contain id-alg-mts-hashsig. The algorithm 274 parameters field MUST be absent. 276 signature contains the single HSS signature value resulting from 277 the signing operation as specified in [HASHSIG]. 279 5. Security Considerations 281 5.1. Implementation Security Considerations 283 Implementations must protect the private keys. Compromise of the 284 private keys may result in the ability to forge signatures. Along 285 with the private key, the implementation must keep track of which 286 leaf nodes in the tree have been used. Loss of integrity of this 287 tracking data can cause an one-time key to be used more than once. 288 As a result, when a private key and the tracking data are stored on 289 non-volatile media or stored in a virtual machine environment, care 290 must be taken to preserve confidentiality and integrity. 292 An implementation must ensure that a LM-OTS private key is used to 293 generate a signature only one time, and ensure that it cannot be used 294 for any other purpose. 296 The generation of private keys relies on random numbers. The use of 297 inadequate pseudo-random number generators (PRNGs) to generate these 298 values can result in little or no security. An attacker may find it 299 much easier to reproduce the PRNG environment that produced the keys, 300 searching the resulting small set of possibilities, rather than brute 301 force searching the whole key space. The generation of quality 302 random numbers is difficult. RFC 4086 [RANDOM] offers important 303 guidance in this area. 305 When computing signatures, the same hash function SHOULD be used for 306 all operations. In this specification, only SHA-256 is used. Using 307 only SHA-256 reduces the number of possible failure points in the 308 signature process. 310 5.2. Algorithm Security Considerations 312 At Black Hat USA 2013, some researchers gave a presentation on the 313 current sate of public key cryptography. They said: "Current 314 cryptosystems depend on discrete logarithm and factoring which has 315 seen some major new developments in the past 6 months" [BH2013]. 316 They encouraged preparation for a day when RSA and DSA cannot be 317 depended upon. 319 A post-quantum cryptosystem is a system that is secure against 320 quantum computers that have more than a trivial number of quantum 321 bits. It is open to conjecture when it will be feasible to build 322 such a machine. RSA, DSA, and ECDSA are not post-quantum secure. 324 The LM-OTP one-time signature, LMS, and HSS do not depend on discrete 325 logarithm or factoring, as a result these algorithms are considered 326 to be post-quantum secure. 328 Today, RSA is often used to digitally sign software updates. This 329 means that the distribution of software updates could be compromised 330 if a significant advance is made in factoring or a quantum computer 331 is invented. The use of MTS signatures to protect software update 332 distribution, perhaps using the format described in [FWPROT], will 333 allow the deployment of software that implements new cryptosystems. 335 6. IANA Considerations 337 This document has no actions for IANA. 339 7. Acknowledgements 341 Many thanks to Panos Kampanakis, Jim Schaad, and Sean Turner for 342 their careful review and comments. 344 8. Normative References 346 [ASN1-B] ITU-T, "Information technology -- Abstract Syntax Notation 347 One (ASN.1): Specification of basic notation", ITU-T 348 Recommendation X.680, 2015. 350 [ASN1-E] ITU-T, "Information technology -- ASN.1 encoding rules: 351 Specification of Basic Encoding Rules (BER), Canonical 352 Encoding Rules (CER) and Distinguished Encoding Rules 353 (DER)", ITU-T Recommendation X.690, 2015. 355 [CMS] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, 356 RFC 5652, DOI 10.17487/RFC5652, September 2009, 357 . 359 [HASHSIG] McGrew, D., M. Curcio, and S. Fluhrer, "Hash-Based 360 Signatures", Work in progress. 363 [RFC2219] Bradner, S., "Key words for use in RFCs to Indicate 364 Requirement Levels", BCP 14, RFC 2119, DOI 365 10.17487/RFC2119, March 1997, . 368 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in 369 RFC 2119 Key Words", BCP 14, RFC 8174, DOI 370 10.17487/RFC8174, May 2017, . 373 [SHS] National Institute of Standards and Technology (NIST), 374 FIPS Publication 180-3: Secure Hash Standard, October 375 2008. 377 9. Informative References 379 [BH2013] Ptacek, T., T. Ritter, J. Samuel, and A. Stamos, "The 380 Factoring Dead: Preparing for the Cryptopocalypse", August 381 2013. 384 [CMSASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for 385 Cryptographic Message Syntax (CMS) and S/MIME", RFC 5911, 386 DOI 10.17487/RFC5911, June 2010, . 389 [CMSASN1U] Schaad, J. and S. Turner, "Additional New ASN.1 Modules 390 for the Cryptographic Message Syntax (CMS) and the Public 391 Key Infrastructure Using X.509 (PKIX)", RFC 6268, DOI 392 10.17487/RFC6268, July 2011, . 395 [FWPROT] Housley, R., "Using Cryptographic Message Syntax (CMS) to 396 Protect Firmware Packages", RFC 4108, DOI 397 10.17487/RFC4108, August 2005, . 400 [LM] Leighton, T. and S. Micali, "Large provably fast and 401 secure digital signature schemes from secure hash 402 functions", U.S. Patent 5,432,852, July 1995. 404 [M1979] Merkle, R., "Secrecy, Authentication, and Public Key 405 Systems", Stanford University Information Systems 406 Laboratory Technical Report 1979-1, 1979. 408 [M1987] Merkle, R., "A Digital Signature Based on a Conventional 409 Encryption Function", Lecture Notes in Computer Science 410 crypto87, 1988. 412 [M1989a] Merkle, R., "A Certified Digital Signature", Lecture Notes 413 in Computer Science crypto89, 1990. 415 [M1989b] Merkle, R., "One Way Hash Functions and DES", Lecture Notes 416 in Computer Science crypto89, 1990. 418 [PKIXASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for the 419 Public Key Infrastructure Using X.509 (PKIX)", RFC 5912, 420 DOI 10.17487/RFC5912, June 2010, . 423 [PQC] Bernstein, D., "Introduction to post-quantum 424 cryptography", 2009. 425 428 [RANDOM] Eastlake 3rd, D., Schiller, J., and S. Crocker, 429 "Randomness Requirements for Security", BCP 106, RFC 4086, 430 DOI 10.17487/RFC4086, June 2005, . 433 Appendix: ASN.1 Module 435 MTS-HashSig-2013 436 { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) 437 id-smime(16) id-mod(0) id-mod-mts-hashsig-2013(64) } 439 DEFINITIONS IMPLICIT TAGS ::= BEGIN 441 EXPORTS ALL; 443 IMPORTS 444 PUBLIC-KEY, SIGNATURE-ALGORITHM, SMIME-CAPS 445 FROM AlgorithmInformation-2009 -- RFC 5911 [CMSASN1] 446 { iso(1) identified-organization(3) dod(6) internet(1) 447 security(5) mechanisms(5) pkix(7) id-mod(0) 448 id-mod-algorithmInformation-02(58) } 449 mda-sha256 450 FROM PKIX1-PSS-OAEP-Algorithms-2009 -- RFC 5912 [PKIXASN1] 451 { iso(1) identified-organization(3) dod(6) 452 internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) 453 id-mod-pkix1-rsa-pkalgs-02(54) } ; 455 -- 456 -- Object Identifiers 457 -- 459 id-alg-mts-hashsig OBJECT IDENTIFIER ::= { iso(1) member-body(2) 460 us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 } 462 -- 463 -- Signature Algorithm and Public Key 464 -- 466 sa-MTS-HashSig SIGNATURE-ALGORITHM ::= { 467 IDENTIFIER id-alg-mts-hashsig 468 PARAMS ARE absent 469 HASHES { mda-sha256 } 470 PUBLIC-KEYS { pk-MTS-HashSig } 471 SMIME-CAPS { IDENTIFIED BY id-alg-mts-hashsig } } 473 pk-MTS-HashSig PUBLIC-KEY ::= { 474 IDENTIFIER id-alg-mts-hashsig 475 KEY MTS-HashSig-PublicKey 476 PARAMS ARE absent 477 CERT-KEY-USAGE 478 { digitalSignature, nonRepudiation, keyCertSign, cRLSign } } 480 MTS-HashSig-PublicKey ::= OCTET STRING 481 -- 482 -- Expand the signature algorithm set used by CMS [CMSASN1U] 483 -- 485 SignatureAlgorithmSet SIGNATURE-ALGORITHM ::= 486 { sa-MTS-HashSig, ... } 488 -- 489 -- Expand the S/MIME capabilities set used by CMS [CMSASN1] 490 -- 492 SMimeCaps SMIME-CAPS ::= { sa-MTS-HashSig.&smimeCaps, ... } 494 END 496 Author's Address 498 Russ Housley 499 Vigil Security, LLC 500 918 Spring Knoll Drive 501 Herndon, VA 20170 502 USA 504 EMail: housley@vigilsec.com