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