idnits 2.17.1 draft-housley-cms-mts-hash-sig-05.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 (19 December 2016) is 2685 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 210 -- Looks like a reference, but probably isn't: '1' on line 175 -- Looks like a reference, but probably isn't: '2' on line 135 == Missing Reference: 'L-2' is mentioned on line 137, but not defined == Missing Reference: 'L-1' is mentioned on line 137, but not defined == Unused Reference: 'PQC' is defined on line 383, 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 (~~), 4 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: 22 June 2017 19 December 2016 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) 2016 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. An MTS 101 system is an N-time signature system, meaning that the private key 102 can be used to generate at most N signatures. 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 they are needed by the signer. Otherwise, 115 generation of the entire tree might take weeks or longer. 117 An HSS signature as specified in specified in [HASHSIG] carries the 118 number of levels minus one, followed by that number of signed public 119 keys, followed by the LMS signature as described in Section 2.2. 120 Each signed public key is represented by the hash value at the root 121 of the tree, and the signature over that public key is an LMS 122 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 L levels can 131 be summarized as: 133 u32str(L-1) || 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[L-2] || public_key[L-1] || 138 lms_signature_on_message 140 2.2. Leighton-Micali Signature (LMS) 142 Each tree in the system specified in [HASHSIG] uses the Leighton- 143 Micali Signature (LMS) system. LMS systems have two parameters. The 144 first parameter is the height of the tree, h, which is the number of 145 levels in the tree minus one. The [HASHSIG] specification supports 146 four values for this parameter: h=20; h=15; h=10; and h=5. Note that 147 there are 2^h leaves in the tree. The second parameter is the number 148 of bytes output by the hash function, n, which the amount of data 149 associated with each node in the tree. The [HASHSIG] specification 150 supports only the SHA-256 hash function [SHS], with n=32. 152 Four tree sizes are specified in [HASHSIG]: 154 LMS_SHA256_M32_H20; 155 LMS_SHA256_M32_H15 156 LMS_SHA256_M32_H10; and 157 LMS_SHA256_M32_H5. 159 An LMS signature consists of four elements: a typecode indicating the 160 particular LMS algorithm, the number of the leaf associated with the 161 LM-OTS signature, an LM-OTS signature as described in Section 2.3, 162 and an array of values that is associated with the path through the 163 tree from the leaf associated with the LM-OTS signature to the root. 164 The array of values contains the siblings of the nodes on the path 165 from the leaf to the root but does not contain the nodes on the path 166 itself. The array for a tree with height h will have h values. The 167 first value is the sibling of the leaf, the next value is the sibling 168 of the parent of the leaf, and so on up the path to the root. 170 The four elements of the LMS signature value can be summarized as: 172 u32str(type) || 173 u32str(q) || 174 ots_signature || 175 path[0] || path[1] || ... || path[h-1] 177 2.3. Leighton-Micali One-time Signature Algorithm (LM-OTS) 179 Merkle Tree Signatures (MTS) depend on a LM-OTS one-time signature 180 method. An LM-OTS has four parameters. 182 n - The number of bytes associated with the hash function, which 183 is the same as the LMS parameter. The [HASHSIG] 184 specification supports only one hash function: SHA-256 [SHS], 185 with n=32. 187 w - The width in bits of the Winternitz coefficients. The 188 [HASHSIG] specification supports four values for this 189 parameter: w=1; w=2; w=4; and w=8. 191 p - The number of n-byte string elements that make up the LM-OTS 192 signature. 194 ls - The number of left-shift bits used in the checksum function. 196 The values of p and ls are dependent on the choices of the parameters 197 n and w, as described in Appendix A of [HASHSIG]. 199 Four LM-OTS variants are defined in [HASHSIG]: 201 LMOTS_SHA256_N32_W1; 202 LMOTS_SHA256_N32_W2; 203 LMOTS_SHA256_N32_W4; and 204 LMOTS_SHA256_N32_W8. 206 Signing involves the generation of C, an n-byte random value. 208 The LM-OTS signature value can be summarized as: 210 u32str(type) || C || y[0] || ... || y[p-1] 212 3. Algorithm Identifiers and Parameters 214 The algorithm identifier for an MTS signature is id-alg-mts-hashsig: 216 id-alg-mts-hashsig OBJECT IDENTIFIER ::= { iso(1) member-body(2) 217 us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 } 219 When the id-alg-mts-hashsig algorithm identifier is used for a 220 signature, the AlgorithmIdentifier parameters field MUST be absent. 222 The signature values is a large OCTET STRING. The signature format 223 is designed for easy parsing. Each format includes a counter and 224 type codes that indirectly providing all of the information that is 225 needed to parse the value during signature validation. The first 4 226 octets of the signature value contains a count of levels minus one in 227 the HSS. The first 4 octets of each LMS signature value contains 228 type code, which tells how to parse the remaining parts of the 229 signature value. The first 4 octets of each LM-OTS signature value 230 contains type code, which tells how to parse the remaining parts of 231 the signature value. 233 4. Signed-data Conventions 235 digestAlgorithms SHOULD contain the one-way hash function used to 236 compute the message digest on the eContent value. Since the hash- 237 based signature algorithms all depend on SHA-256, it is strongly 238 RECOMMENDED that SHA-256 also be used to compute the message digest 239 on the content. 241 Further, the same one-way hash function SHOULD be used to compute the 242 message digest on both the eContent and the signedAttributes value if 243 signedAttributes are present. Again, since the hash-based signature 244 algorithms all depend on SHA-256, it is strongly RECOMMENDED that 245 SHA-256 be used. 247 signatureAlgorithm MUST contain id-alg-mts-hashsig. The algorithm 248 parameters field MUST be absent. 250 signature contains the single HSS signature value resulting from the 251 signing operation as specified in [HASHSIG]. 253 5. Security Considerations 255 5.1. Implementation Security Considerations 257 Implementations must protect the private keys. Compromise of the 258 private keys may result in the ability to forge signatures. Along 259 with the private key, the implementation must keep track of which 260 leaf nodes in the tree have been used. Loss of integrity of this 261 tracking data can cause an one-time key to be used more than once. 262 As a result, when a private key and the tracking data are stored on 263 non-volatile media or stored in a virtual machine environment, care 264 must be taken to preserve confidentiality and integrity. 266 An implementation must ensure that a LM-OTS private key is used to 267 generate a signature only one time, and ensure that it cannot be used 268 for any other purpose. 270 The generation of private keys relies on random numbers. The use of 271 inadequate pseudo-random number generators (PRNGs) to generate these 272 values can result in little or no security. An attacker may find it 273 much easier to reproduce the PRNG environment that produced the keys, 274 searching the resulting small set of possibilities, rather than brute 275 force searching the whole key space. The generation of quality 276 random numbers is difficult. RFC 4086 [RANDOM] offers important 277 guidance in this area. 279 When computing signatures, the same hash function SHOULD be used for 280 all operations. In this specification, only SHA-256 is used. Using 281 only SHA-256 reduces the number of possible failure points in the 282 signature process. 284 5.2. Algorithm Security Considerations 286 At Black Hat USA 2013, some researchers gave a presentation on the 287 current sate of public key cryptography. They said: "Current 288 cryptosystems depend on discrete logarithm and factoring which has 289 seen some major new developments in the past 6 months" [BH2013]. 290 They encouraged preparation for a day when RSA and DSA cannot be 291 depended upon. 293 A post-quantum cryptosystem is a system that is secure against 294 quantum computers that have more than a trivial number of quantum 295 bits. It is open to conjecture when it will be feasible to build 296 such a machine. RSA, DSA, and ECDSA are not post-quantum secure. 298 The LM-OTP one-time signature, LMS, and HSS do not depend on discrete 299 logarithm or factoring, as a result these algorithms are considered 300 to be post-quantum secure. 302 Today, RSA is often used to digitally sign software updates. This 303 means that the distribution of software updates could be compromised 304 if a significant advance is made in factoring or a quantum computer 305 is invented. The use of MTS signatures to protect software update 306 distribution, perhaps using the format described in [FWPROT], will 307 allow the deployment of software that implements new cryptosystems. 309 6. IANA Considerations 311 {{ RFC Editor: Please remove this section prior to publication. }} 313 This document has no actions for IANA. 315 7. Normative References 317 [ASN1-B] ITU-T, "Information technology -- Abstract Syntax Notation 318 One (ASN.1): Specification of basic notation", ITU-T 319 Recommendation X.680, 2015. 321 [ASN1-E] ITU-T, "Information technology -- ASN.1 encoding rules: 322 Specification of Basic Encoding Rules (BER), Canonical 323 Encoding Rules (CER) and Distinguished Encoding Rules 324 (DER)", ITU-T Recommendation X.690, 2015. 326 [CMS] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, 327 RFC 5652, DOI 10.17487/RFC5652, September 2009, 328 . 330 [HASHSIG] McGrew, D., M. Curcio, and S. Fluhrer, "Hash-Based 331 Signatures", Work in progress. 334 [KEYWORDS] Bradner, S., "Key words for use in RFCs to Indicate 335 Requirement Levels", BCP 14, RFC 2119, DOI 336 10.17487/RFC2119, March 1997, . 339 [SHS] National Institute of Standards and Technology (NIST), 340 FIPS Publication 180-3: Secure Hash Standard, October 341 2008. 343 8. Informative References 345 [BH2013] Ptacek, T., T. Ritter, J. Samuel, and A. Stamos, "The 346 Factoring Dead: Preparing for the Cryptopocalypse", August 347 2013. 350 [CMSASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for 351 Cryptographic Message Syntax (CMS) and S/MIME", RFC 5911, 352 DOI 10.17487/RFC5911, June 2010, . 355 [FWPROT] Housley, R., "Using Cryptographic Message Syntax (CMS) to 356 Protect Firmware Packages", RFC 4108, DOI 357 10.17487/RFC4108, August 2005, . 360 [LM] Leighton, T. and S. Micali, "Large provably fast and 361 secure digital signature schemes from secure hash 362 functions", U.S. Patent 5,432,852, July 1995. 364 [M1979] Merkle, R., "Secrecy, Authentication, and Public Key 365 Systems", Stanford University Information Systems 366 Laboratory Technical Report 1979-1, 1979. 368 [M1987] Merkle, R., "A Digital Signature Based on a Conventional 369 Encryption Function", Lecture Notes in Computer Science 370 crypto87, 1988. 372 [M1989a] Merkle, R., "A Certified Digital Signature", Lecture Notes 373 in Computer Science crypto89, 1990. 375 [M1989b] Merkle, R., "One Way Hash Functions and DES", Lecture Notes 376 in Computer Science crypto89, 1990. 378 [PKIXASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for the 379 Public Key Infrastructure Using X.509 (PKIX)", RFC 5912, 380 DOI 10.17487/RFC5912, June 2010, . 383 [PQC] Bernstein, D., "Introduction to post-quantum 384 cryptography", 2009. 385 388 [RANDOM] Eastlake 3rd, D., Schiller, J., and S. Crocker, 389 "Randomness Requirements for Security", BCP 106, RFC 4086, 390 DOI 10.17487/RFC4086, June 2005, . 393 Appendix: ASN.1 Module 395 MTS-HashSig-2013 396 { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) 397 id-smime(16) id-mod(0) id-mod-mts-hashsig-2013(64) } 399 DEFINITIONS IMPLICIT TAGS ::= BEGIN 401 EXPORTS ALL; 403 IMPORTS 404 SIGNATURE-ALGORITHM PUBLIC-KEY 405 FROM AlgorithmInformation-2009 -- RFC 5911 [CMSASN1] 406 { iso(1) identified-organization(3) dod(6) internet(1) 407 security(5) mechanisms(5) pkix(7) id-mod(0) 408 id-mod-algorithmInformation-02(58) } 409 mda-sha256 410 FROM PKIX1-PSS-OAEP-Algorithms-2009 -- RFC 5912 [PKIXASN1] 411 { iso(1) identified-organization(3) dod(6) 412 internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) 413 id-mod-pkix1-rsa-pkalgs-02(54) } ; 415 -- 416 -- Object Identifiers 417 -- 419 id-alg-mts-hashsig OBJECT IDENTIFIER ::= { iso(1) member-body(2) 420 us(840) rsadsi(113549) pkcs(1) pkcs9(9) smime(16) alg(3) 17 } 422 -- 423 -- Signature Algorithm and Public Key 424 -- 426 sa-MTS-HashSig SIGNATURE-ALGORITHM ::= { 427 IDENTIFIER id-alg-mts-hashsig 428 HASHES { mda-sha256, ... } 429 PUBLIC-KEYS { pk-MTS-HashSig } } 431 pk-MTS-HashSig PUBLIC-KEY ::= { 432 IDENTIFIER id-alg-mts-hashsig 433 KEY MTS-HashSig-PublicKey } 435 MTS-HashSig-PublicKey ::= OCTET STRING 437 HashSignatureAlgs SIGNATURE-ALGORITHM ::= { 438 sa-MTS-HashSig, ... } 440 END 442 Author's Address 444 Russ Housley 445 Vigil Security, LLC 446 918 Spring Knoll Drive 447 Herndon, VA 20170 448 USA 450 EMail: housley@vigilsec.com