idnits 2.17.1 draft-fluhrer-lms-more-parm-sets-01.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (March 19, 2020) is 1491 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC5226' is defined on line 462, but no explicit reference was found in the text == Unused Reference: 'RFC8554' is defined on line 467, but no explicit reference was found in the text == Unused Reference: 'Grover96' is defined on line 473, but no explicit reference was found in the text ** Obsolete normative reference: RFC 3979 (Obsoleted by RFC 8179) ** Obsolete normative reference: RFC 4879 (Obsoleted by RFC 8179) ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) Summary: 3 errors (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group S. Fluhrer 3 Internet-Draft Cisco Systems 4 Intended status: Informational Q. Dang 5 Expires: September 20, 2020 NIST 6 March 19, 2020 8 Additional Parameter sets for LMS Hash-Based Signatures 9 draft-fluhrer-lms-more-parm-sets-01 11 Abstract 13 This note extends LMS (RFC 8554) by defining parameter sets by 14 including additional hash functions. Hese include hash functions 15 that result in signatures with significantly smaller than the 16 signatures using the current parameter sets, and should have 17 sufficient security. 19 This document is a product of the Crypto Forum Research Group (CFRG) 20 in the IRTF. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at https://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on September 20, 2020. 39 Copyright Notice 41 Copyright (c) 2020 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (https://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 57 1.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 2 58 2. Conventions Used In This Document . . . . . . . . . . . . . . 3 59 3. Additional Hash Function Definitions . . . . . . . . . . . . 3 60 3.1. 192 bit Hash Function based on SHA256 . . . . . . . . . . 3 61 3.2. 256 bit Hash Function based on SHAKE256 . . . . . . . . . 3 62 3.3. 192 bit Hash Function based on SHAKE256 . . . . . . . . . 4 63 4. Additional LM-OTS Parameter Sets . . . . . . . . . . . . . . 4 64 5. Additional LM Parameter Sets . . . . . . . . . . . . . . . . 5 65 6. Comparisons of 192 bit and 256 bit parameter sets . . . . . . 6 66 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 67 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 68 8.1. Note on the version of SHAKE . . . . . . . . . . . . . . 10 69 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 70 9.1. Normative References . . . . . . . . . . . . . . . . . . 10 71 9.2. Informative References . . . . . . . . . . . . . . . . . 11 72 Appendix A. Test Cases . . . . . . . . . . . . . . . . . . . . . 11 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 75 1. Introduction 77 Stateful hash based signatures have small private and public keys, 78 are efficient to compute, and are believed to have excellent 79 security. One disadvantage is that the signatures they produce tend 80 to be somewhat large (possibly 1k - 4kbytes). What this draft 81 explores are a set of parameter sets to the LMS (RFC8554) stateful 82 hash based signature method that reduce the size of the signature 83 significantly. 85 1.1. Disclaimer 87 This document is not intended as legal advice. Readers are advised 88 to consult with their own legal advisers if they would like a legal 89 interpretation of their rights. 91 The IETF policies and processes regarding intellectual property and 92 patents are outlined in [RFC3979] and [RFC4879] and at 93 https://datatracker.ietf.org/ipr/about. 95 2. Conventions Used In This Document 97 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 98 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 99 document are to be interpreted as described in [RFC2119]. 101 3. Additional Hash Function Definitions 103 3.1. 192 bit Hash Function based on SHA256 105 This document defines a SHA-2 based hash function with a 192 bit 106 output. As such, we define SHA256/192 as a truncated version of 107 SHA-256 [FIPS180]. That is, it is the result of performing a SHA-256 108 operation to a message, and then omitting the final 64 bits of the 109 output. It is the same procedure used to define SHA-224, except that 110 we use the SHA-256 IV (rather than using one dedicated to 111 SHA256/192), and you truncate 64 bits, rather than 32. 113 The following test vector may illustrate this: 115 SHA256("abc") = ba7816bf 8f01cfea 414140de 5dae2223 116 b00361a3 96177a9c b410ff61 f20015ad 117 SHA256/192("abc") = ba7816bf 8f01cfea 414140de 5dae2223 118 b00361a3 96177a9c 120 We use the same IV as the untruncated SHA-256, rather than defining a 121 distinct one, so that we can use a standard SHA-256 hash 122 implementation without modification. In addition, the fact that you 123 get partial knowledge of the SHA-256 hash of a message by examining 124 the SHA256/192 hash of the same message is not a concern for this 125 application. Each message that is hashed is randomized. Any message 126 being signed includes the C randomizer which varies per message; in 127 addition, all hashes include the I identifier, which varies depending 128 on the public key. Therefore, signing the same message by SHA256 and 129 by SHA256/192 will not result in the same value being hashed, and so 130 the latter hash value is not a prefix of the former one. 132 3.2. 256 bit Hash Function based on SHAKE256 134 This document defines a SHAKE-based hash function with a 256 bit 135 output. As such, we define SHAKE256-256 as a hash where you submit 136 the preimage to the SHAKE256 XOF, with the output being 256 bits, see 137 FIPS 202 [FIPS202] for more detail. 139 3.3. 192 bit Hash Function based on SHAKE256 141 This document defines a SHAKE-based hash function with a 192 bit 142 output. As such, we define SHAKE256-192 as a hash where you submit 143 the preimage to the SHAKE-256 XOF, with the output being 192 bits, 144 see FIPS 202 [FIPS202] for more detail. 146 4. Additional LM-OTS Parameter Sets 148 Here is a table with the LM-OTS parameters defined that use the above 149 hashes: 151 +---------------------+--------------+----+---+-----+----+-------+ 152 | Parameter Set Name | H | n | w | p | ls | id | 153 +---------------------+--------------+----+---+-----+----+-------+ 154 | LMOTS_SHA256_N24_W1 | SHA256/192 | 24 | 1 | 200 | 8 | TBD1 | 155 | | | | | | | | 156 | LMOTS_SHA256_N24_W2 | SHA256/192 | 24 | 2 | 101 | 6 | TBD2 | 157 | | | | | | | | 158 | LMOTS_SHA256_N24_W4 | SHA256/192 | 24 | 4 | 51 | 4 | TBD3 | 159 | | | | | | | | 160 | LMOTS_SHA256_N24_W8 | SHA256/192 | 24 | 8 | 26 | 0 | TBD4 | 161 | | | | | | | | 162 | LMOTS_SHAKE_N32_W1 | SHAKE256-256 | 32 | 1 | 265 | 7 | TBD5 | 163 | | | | | | | | 164 | LMOTS_SHAKE_N32_W2 | SHAKE256-256 | 32 | 2 | 133 | 6 | TBD6 | 165 | | | | | | | | 166 | LMOTS_SHAKE_N32_W4 | SHAKE256-256 | 32 | 4 | 67 | 4 | TBD7 | 167 | | | | | | | | 168 | LMOTS_SHAKE_N32_W8 | SHAKE256-256 | 32 | 8 | 34 | 0 | TBD8 | 169 | | | | | | | | 170 | LMOTS_SHAKE_N24_W1 | SHAKE256-192 | 24 | 1 | 200 | 8 | TBD9 | 171 | | | | | | | | 172 | LMOTS_SHAKE_N24_W2 | SHAKE256-192 | 24 | 2 | 101 | 6 | TBD10 | 173 | | | | | | | | 174 | LMOTS_SHAKE_N24_W4 | SHAKE256-192 | 24 | 4 | 51 | 4 | TBD11 | 175 | | | | | | | | 176 | LMOTS_SHAKE_N24_W8 | SHAKE256-192 | 24 | 8 | 26 | 0 | TBD12 | 177 +---------------------+--------------+----+---+-----+----+-------+ 179 Table 1 181 The id is the IANA-defined identifier used to denote this specific 182 parameter set, and which appears in both public keys and signatures. 184 The SHA256_N24, SHAKE_N32, SHAKE_N24 in the parameter set name denote 185 the SHA256/192, SHAKE256-256 and SHAKE256-192 hash functions defined 186 in Section 3. 188 Remember that the C message randomizer (which is included in the 189 signature) is the size of the hash n, and so it shrinks from 32 bytes 190 to 24 bytes for those the parameter sets that use either SHA256/192 191 or SHAKE256-192. 193 5. Additional LM Parameter Sets 195 Here is a table with the LM parameters defined that use SHA259/192, 196 SHAKE256-256 and SHAKE256-192 hash functions: 198 +--------------------+--------------+----+----+-------+ 199 | Parameter Set Name | H | m | h | id | 200 +--------------------+--------------+----+----+-------+ 201 | LMS_SHA256_M24_H5 | SHA256/192 | 24 | 5 | TBD13 | 202 | | | | | | 203 | LMS_SHA256_M24_H10 | SHA256/192 | 24 | 10 | TBD14 | 204 | | | | | | 205 | LMS_SHA256_M24_H15 | SHA256/192 | 24 | 15 | TBD15 | 206 | | | | | | 207 | LMS_SHA256_M24_H20 | SHA256/192 | 24 | 20 | TBD16 | 208 | | | | | | 209 | LMS_SHA256_M24_H25 | SHA256/192 | 24 | 25 | TBD17 | 210 | | | | | | 211 | LMS_SHAKE_M32_H5 | SHAKE256-256 | 32 | 5 | TBD18 | 212 | | | | | | 213 | LMS_SHAKE_M32_H10 | SHAKE256-256 | 32 | 10 | TBD19 | 214 | | | | | | 215 | LMS_SHAKE_M32_H15 | SHAKE256-256 | 32 | 15 | TBD20 | 216 | | | | | | 217 | LMS_SHAKE_M32_H20 | SHAKE256-256 | 32 | 20 | TBD21 | 218 | | | | | | 219 | LMS_SHAKE_M32_H25 | SHAKE256-256 | 32 | 25 | TBD22 | 220 | | | | | | 221 | LMS_SHAKE_M24_H5 | SHAKE256-192 | 24 | 5 | TBD23 | 222 | | | | | | 223 | LMS_SHAKE_M24_H10 | SHAKE256-192 | 24 | 10 | TBD24 | 224 | | | | | | 225 | LMS_SHAKE_M24_H15 | SHAKE256-192 | 24 | 15 | TBD25 | 226 | | | | | | 227 | LMS_SHAKE_M24_H20 | SHAKE256-192 | 24 | 20 | TBD26 | 228 | | | | | | 229 | LMS_SHAKE_M24_H25 | SHAKE256-192 | 24 | 25 | TBD27 | 230 +--------------------+--------------+----+----+-------+ 232 Table 2 234 The id is the IANA-defined identifier used to denote this specific 235 parameter set, and which appears in both public keys and signatures. 237 The SHA256_M24, SHAKE_M32, SHAKE_M24 in the parameter set name denote 238 the SHA256/192, SHAKE256-256 and SHAKE256-192 hash functions defined 239 in Section 3. 241 6. Comparisons of 192 bit and 256 bit parameter sets 243 Switching to a 192 bit hash affects the signature size, the 244 computation time, and the security strength. 246 The major reason for considering these truncated parameter sets is 247 that they cause the signatures to shrink considerably. 249 Here is a table that gives the space used by both the 256 bit 250 parameter sets and the 192 bit parameter sets, for a range of 251 plausible Winternitz parameters and tree heights 253 +---------+------------+--------------+--------------+ 254 | ParmSet | Winternitz | 256 bit hash | 192 bit hash | 255 +---------+------------+--------------+--------------+ 256 | 15 | 4 | 2672 | 1624 | 257 | | | | | 258 | 15 | 8 | 1616 | 1024 | 259 | | | | | 260 | 20 | 4 | 2832 | 1744 | 261 | | | | | 262 | 20 | 8 | 1776 | 1144 | 263 | | | | | 264 | 15/10 | 4 | 5236 | 3172 | 265 | | | | | 266 | 15/10 | 8 | 3124 | 1972 | 267 | | | | | 268 | 15/15 | 4 | 5396 | 3292 | 269 | | | | | 270 | 15/15 | 8 | 3284 | 2092 | 271 | | | | | 272 | 20/10 | 4 | 5396 | 3292 | 273 | | | | | 274 | 20/10 | 8 | 3284 | 2092 | 275 | | | | | 276 | 20/15 | 4 | 5556 | 3412 | 277 | | | | | 278 | 20/15 | 8 | 3444 | 2212 | 279 +---------+------------+--------------+--------------+ 281 Table 3 283 ParmSet: this is the height of the Merkle tree(s); parameter sets 284 listed as a single integer have L=1, and consist a single Merkle tree 285 of that height; parameter sets with L=2 are listed as x/y, with x 286 being the height of the top level Merkle tree, and y being the bottom 287 level. 289 Winternitz: this is the Winternitz parameter used (for the tests that 290 use multiple trees, this applies to all of them). 292 256 bit hash: the size in bytes of a signature, assuming that a 256 293 bit hash is used in the signature (either SHA256 or SHAKE256/256). 295 192 bit hash: the size in bytes of a signature, assuming that a 192 296 bit hash is used in the signature (either SHA256/192 or 297 SHAKE256/192). 299 An examination of the signature sizes show that the 192 bit 300 parameters consistently give a 35% - 40% reduction in the size of the 301 signature in comparison with the 256 bit parameters. 303 In addition, for SHA256-192, there is a smaller (circa 20%) reduction 304 in the amount of computation required for a signature operation with 305 a 192 bit hash. The SHAKE256-192 signatures may have either a faster 306 or slower computation, depending on the implementation speed of SHAKE 307 versus SHA-256 hashes. 309 The SHAKE256-256 based parameter sets give no space advantage (or 310 disadvantage) over the existing SHA256-based parameter sets; any 311 performance delta would depend solely on the implementation and 312 whether they can generate SHAKE hashes faster than SHA-256 ones. 314 7. IANA Considerations 316 [TO BE REMOVED: The entries from Section 4, namely 317 LMOTS_SHA256_N24_W1 through LMOTS_SHAKE_N24_W8 , should be inserted 318 into https://www.iana.org/assignments/leighton-micali-signatures/ 319 leighton-micali-signatures.xhtml#lm-ots-signatures ] 321 [TO BE REMOVED: The entries from Section 5, namely LMS_SHA256_M24_H5 322 through LMS_SHAKE_M24_H25 should be inserted into 323 https://www.iana.org/assignments/leighton-micali-signatures/leighton- 324 micali-signatures.xhtml#leighton-micali-signatures-1 ] 326 Until IANA assigns the codepoints, we will (for testing purposes 327 only) use the following private use code points to do any necessary 328 interoperability testing. Such an implementation must change to the 329 IANA-assigned code points when they become available. 331 +---------------------+---------------------+ 332 | Parameter Set Name | Temporary Codepoint | 333 +---------------------+---------------------+ 334 | LMOTS_SHA256_N24_W1 | 0xE0000001 | 335 | | | 336 | LMOTS_SHA256_N24_W2 | 0xE0000002 | 337 | | | 338 | LMOTS_SHA256_N24_W4 | 0xE0000003 | 339 | | | 340 | LMOTS_SHA256_N24_W8 | 0xE0000004 | 341 | | | 342 | LMOTS_SHAKE_N32_W1 | 0xE0000005 | 343 | | | 344 | LMOTS_SHAKE_N32_W2 | 0xE0000006 | 345 | | | 346 | LMOTS_SHAKE_N32_W4 | 0xE0000007 | 347 | | | 348 | LMOTS_SHAKE_N32_W8 | 0xE0000008 | 349 | | | 350 | LMOTS_SHAKE_N24_W1 | 0xE0000009 | 351 | | | 352 | LMOTS_SHAKE_N24_W2 | 0xE000000A | 353 | | | 354 | LMOTS_SHAKE_N24_W4 | 0xE000000B | 355 | | | 356 | LMOTS_SHAKE_N24_W8 | 0xE000000C | 357 | | | 358 | LMS_SHA256_M24_H5 | 0xE0000001 | 359 | | | 360 | LMS_SHA256_M24_H10 | 0xE0000002 | 361 | | | 362 | LMS_SHA256_M24_H15 | 0xE0000003 | 363 | | | 364 | LMS_SHA256_M24_H20 | 0xE0000004 | 365 | | | 366 | LMS_SHA256_M24_H25 | 0xE0000005 | 367 | | | 368 | LMS_SHAKE_M32_H5 | 0xE0000006 | 369 | | | 370 | LMS_SHAKE_M32_H10 | 0xE0000007 | 371 | | | 372 | LMS_SHAKE_M32_H15 | 0xE0000008 | 373 | | | 374 | LMS_SHAKE_M32_H20 | 0xE0000009 | 375 | | | 376 | LMS_SHAKE_M32_H25 | 0xE000000A | 377 | | | 378 | LMS_SHAKE_M24_H5 | 0xE000000B | 379 | | | 380 | LMS_SHAKE_M24_H10 | 0xE000000C | 381 | | | 382 | LMS_SHAKE_M24_H15 | 0xE000000D | 383 | | | 384 | LMS_SHAKE_M24_H20 | 0xE000000E | 385 | | | 386 | LMS_SHAKE_M24_H25 | 0xE000000F | 387 +---------------------+---------------------+ 389 Table 4 391 8. Security Considerations 393 The strength of a signature that uses the SHA256/192, SHAKE256-256 394 and SHAKE256-192 hash functions is based on the difficultly in 395 finding preimages or second preimages to those hash functions. 397 The case of SHAKE256-256 is essentially the same as the existing 398 SHA-256 based signatures; the difficultly of finding preimages is 399 essentially the same, and so they have (barring unexpected 400 cryptographical advances) essentially the same level of security. 402 The case of SHA256/192 and SHAKE256-192 requires closer analysis. 404 For a classical (nonquantum) computer, they have no known attack 405 better than performing hashes of a large number of distinct 406 preimages; as a successful attack has a high probability of requiring 407 nearly 2**192 hash computations (for either SHA256/192 or 408 SHAKE256-192). These can be taken as the expected work effort, and 409 would appear to be completely infeasible in practice. 411 For a Quantum Computer, they could in theory use a Grover's algorithm 412 to reduce the expected complexity required to circa 2**96 hash 413 computations (for N=24). On the other hand, to implement Grover's 414 algorithm with this number of hash computations would require 415 performing circa 2**96 hash computations in succession, which will 416 take more time than is likely to be acceptable to any attacker. To 417 speed this up, the attacker would need to run a number of instances 418 of Grover's algorithm in parallel. This would necessarily increase 419 the total work effort required, and to an extent that makes it likely 420 to be infeasible. 422 Hence, we expect that LMS based on these hash functions is secure 423 against both classical and quantum computers, even though, in both 424 cases, the expected work effort is less (for the N=24 case) than 425 against either SHA256 or SHAKE256-256. 427 8.1. Note on the version of SHAKE 429 FIPS 202 defines both SHAKE-128 and SHAKE-256. This specification 430 selects SHAKE-256, even though it is, for large messages, less 431 efficient. The reason is that SHAKE-128 has a low upper bound on the 432 difficulty of finding preimages (due to the invertibility of its 433 internal permutation), which would limit the strength of LMS (whose 434 strength is based on the difficulty of finding preimages). Hence, we 435 specify the use of SHAKE-256, which has a considerably stronger 436 preimage resistance. 438 9. References 440 9.1. Normative References 442 [FIPS180] National Institute of Standards and Technology, "Secure 443 Hash Standard (SHS)", FIPS 180-4, March 2012. 445 [FIPS202] National Institute of Standards and Technology, "SHA-3 446 Standard: Permutation-Based Hash and Extendable-Output 447 Functions", FIPS 202, August 2015. 449 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 450 Requirement Levels", BCP 14, RFC 2119, 451 DOI 10.17487/RFC2119, March 1997, 452 . 454 [RFC3979] Bradner, S., Ed., "Intellectual Property Rights in IETF 455 Technology", RFC 3979, DOI 10.17487/RFC3979, March 2005, 456 . 458 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 459 Procedure in RFC 3979", RFC 4879, DOI 10.17487/RFC4879, 460 April 2007, . 462 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 463 IANA Considerations Section in RFCs", RFC 5226, 464 DOI 10.17487/RFC5226, May 2008, 465 . 467 [RFC8554] McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali 468 Hash-Based Signatures", RFC 8554, DOI 10.17487/RFC8554, 469 April 2019, . 471 9.2. Informative References 473 [Grover96] 474 Grover, L., "A fast quantum mechanical algorithm for 475 database search", 28th ACM Symposium on the Theory of 476 Computing p. 212, 1996. 478 Appendix A. Test Cases 480 In the future, this section will include an example test vector that 481 uses the new hash functions 483 Authors' Addresses 485 Scott Fluhrer 486 Cisco Systems 487 170 West Tasman Drive 488 San Jose, CA 489 USA 491 Email: sfluhrer@cisco.com 493 Quynh Dang 494 NIST 495 100 Bureau Drive 496 Gaithersburg, MD 497 USA 499 Email: quynh.dang@nist.gov