idnits 2.17.1 draft-mcgrew-hash-sigs-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 : ---------------------------------------------------------------------------- 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 date (October 31, 2016) is 2705 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: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 1353 -- Looks like a reference, but probably isn't: '1' on line 1588 == Missing Reference: 'L-1' is mentioned on line 978, but not defined == Missing Reference: 'L-2' is mentioned on line 951, but not defined -- Looks like a reference, but probably isn't: '16' on line 1008 -- Looks like a reference, but probably isn't: '32' on line 1086 -- Looks like a reference, but probably isn't: '265' on line 1013 -- Looks like a reference, but probably isn't: '133' on line 1018 -- Looks like a reference, but probably isn't: '67' on line 1023 -- Looks like a reference, but probably isn't: '34' on line 1028 -- Looks like a reference, but probably isn't: '20' on line 1066 -- Looks like a reference, but probably isn't: '15' on line 1068 -- Looks like a reference, but probably isn't: '10' on line 1070 -- Looks like a reference, but probably isn't: '5' on line 1072 -- Looks like a reference, but probably isn't: '64' on line 1085 -- Looks like a reference, but probably isn't: '2' on line 1588 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 3979 (Obsoleted by RFC 8179) ** Obsolete normative reference: RFC 4879 (Obsoleted by RFC 8179) Summary: 3 errors (**), 0 flaws (~~), 3 warnings (==), 16 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group D. McGrew 3 Internet-Draft M. Curcio 4 Intended status: Informational S. Fluhrer 5 Expires: May 4, 2017 Cisco Systems 6 October 31, 2016 8 Hash-Based Signatures 9 draft-mcgrew-hash-sigs-05 11 Abstract 13 This note describes a digital signature system based on cryptographic 14 hash functions, following the seminal work in this area of Lamport, 15 Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in 16 1995. It specifies a one-time signature scheme and a general 17 signature scheme. These systems provide asymmetric authentication 18 without using large integer mathematics and can achieve a high 19 security level. They are suitable for compact implementations, are 20 relatively simple to implement, and naturally resist side-channel 21 attacks. Unlike most other signature systems, hash-based signatures 22 would still be secure even if it proves feasible for an attacker to 23 build a quantum computer. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on May 4, 2017. 42 Copyright Notice 44 Copyright (c) 2016 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 61 2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 63 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 4 64 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 5 65 3.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 6 66 3.2. Security string . . . . . . . . . . . . . . . . . . . . . 7 67 3.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 8 68 3.4. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 8 69 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 8 70 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 9 71 4.2. Hashing Functions . . . . . . . . . . . . . . . . . . . . 9 72 4.3. Signature Methods . . . . . . . . . . . . . . . . . . . . 9 73 4.4. Private Key . . . . . . . . . . . . . . . . . . . . . . . 10 74 4.5. Public Key . . . . . . . . . . . . . . . . . . . . . . . 11 75 4.6. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 11 76 4.7. Signature Generation . . . . . . . . . . . . . . . . . . 12 77 4.8. Signature Verification . . . . . . . . . . . . . . . . . 13 78 5. Leighton Micali Signatures . . . . . . . . . . . . . . . . . 15 79 5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 16 80 5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 16 81 5.3. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 17 82 5.4. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 17 83 5.4.1. LMS Signature Generation . . . . . . . . . . . . . . 18 84 5.5. LMS Signature Verification . . . . . . . . . . . . . . . 19 85 6. Hierarchical signatures . . . . . . . . . . . . . . . . . . . 21 86 6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 21 87 6.2. Signature Generation . . . . . . . . . . . . . . . . . . 22 88 6.3. Signature Verification . . . . . . . . . . . . . . . . . 22 89 7. Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 90 8. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 26 91 9. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 92 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 93 11. Intellectual Property . . . . . . . . . . . . . . . . . . . . 29 94 11.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 29 95 12. Security Considerations . . . . . . . . . . . . . . . . . . . 30 96 12.1. Stateful signature algorithm . . . . . . . . . . . . . . 31 97 12.2. Security of LM-OTS Checksum . . . . . . . . . . . . . . 32 98 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 32 99 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 33 100 14.1. Normative References . . . . . . . . . . . . . . . . . . 33 101 14.2. Informative References . . . . . . . . . . . . . . . . . 33 102 Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 34 103 Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 35 104 Appendix C. An iterative algorithm for computing an LMS public 105 key . . . . . . . . . . . . . . . . . . . . . . . . 36 106 Appendix D. Example implementation . . . . . . . . . . . . . . . 36 107 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 37 109 1. Introduction 111 One-time signature systems, and general purpose signature systems 112 built out of one-time signature systems, have been known since 1979 113 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 114 benefited from renewed attention in the last decade. The 115 characteristics of these signature systems are small private and 116 public keys and fast signature generation and verification, but large 117 signatures and relatively slow key generation. In recent years there 118 has been interest in these systems because of their post-quantum 119 security and their suitability for compact verifier implementations. 121 This note describes the Leighton and Micali adaptation [USPTO5432852] 122 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 123 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 124 signature system [Merkle79] with enough specificity to ensure 125 interoperability between implementations. An example implementation 126 is given in an appendix. 128 A signature system provides asymmetric message authentication. The 129 key generation algorithm produces a public/private key pair. A 130 message is signed by a private key, producing a signature, and a 131 message/signature pair can be verified by a public key. A One-Time 132 Signature (OTS) system can be used to sign exactly one message 133 securely, but cannot securely sign more than one. An N-time 134 signature system can be used to sign N or fewer messages securely. A 135 Merkle tree signature scheme is an N-time signature system that uses 136 an OTS system as a component. 138 In this note we describe the Leighton-Micali Signature (LMS) system, 139 which is a variant of the Merkle scheme, and a Hierarchical Signature 140 System (HSS) built on top of it that can efficiently scale to larger 141 numbers of signatures. We denote the one-time signature scheme 142 incorporate in LMS as LM-OTS. This note is structured as follows. 143 Notation is introduced in Section 3. The LM-OTS signature system is 144 described in Section 4, and the LMS and HSS N-time signature systems 145 are described in Section 5 and Section 6, respectively. Sufficient 146 detail is provided to ensure interoperability. The IANA registry for 147 these signature systems is described in Section 10. Security 148 considerations are presented in Section 12. 150 1.1. Conventions Used In This Document 152 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 153 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 154 document are to be interpreted as described in [RFC2119]. 156 2. Interface 158 The LMS signing algorithm is stateful; once a particular value of the 159 private key is used to sign one message, it MUST NOT be used to sign 160 another. 162 The key generation algorithm takes as input an indication of the 163 parameters for the signature system. If it is successful, it 164 returns both a private key and a public key. Otherwise, it 165 returns an indication of failure. 167 The signing algorithm takes as input the message to be signed and 168 the current value of the private key. If successful, it returns a 169 signature and the next value of the private key, if there is such 170 a value. After the private key of an N-time signature system has 171 signed N messages, the signing algorithm returns the signature and 172 an indication that there is no next value of the private key that 173 can be used for signing. If unsuccessful, it returns an 174 indication of failure. 176 The verification algorithm takes as input the public key, a 177 message, and a signature, and returns an indication of whether or 178 not the signature and message pair are valid. 180 A message/signature pair are valid if the signature was returned by 181 the signing algorithm upon input of the message and the private key 182 corresponding to the public key; otherwise, the signature and message 183 pair are not valid with probability very close to one. 185 3. Notation 187 3.1. Data Types 189 Bytes and byte strings are the fundamental data types. A single byte 190 is denoted as a pair of hexadecimal digits with a leading "0x". A 191 byte string is an ordered sequence of zero or more bytes and is 192 denoted as an ordered sequence of hexadecimal characters with a 193 leading "0x". For example, 0xe534f0 is a byte string with a length 194 of three. An array of byte strings is an ordered set, indexed 195 starting at zero, in which all strings have the same length. 197 Unsigned integers are converted into byte strings by representing 198 them in network byte order. To make the number of bytes in the 199 representation explicit, we define the functions u8str(X), u16str(X), 200 and u32str(X), which take a nonnegative integer X as input and return 201 one, two, and four byte strings, respectively. We also make use of 202 the functions strTou8(S), strTou16(S), and strTou32(S), which take a 203 one, two, or four byte string S as input and return a nonnegative 204 integer; these functions are such that u8str(strTou8(S)) = S, 205 u16str(strTou16(S)) = S, and u32str(strTou326(S)) for all values of S 206 that are in the appropriate range. 208 3.1.1. Operators 210 When a and b are real numbers, mathematical operators are defined as 211 follows: 213 ^ : a ^ b denotes the result of a raised to the power of b 215 * : a * b denotes the product of a multiplied by b 217 / : a / b denotes the quotient of a divided by b 219 % : a % b denotes the remainder of the integer division of a by b 221 + : a + b denotes the sum of a and b 223 - : a - b denotes the difference of a and b 225 The standard order of operations is used when evaluating arithmetic 226 expressions. 228 If A and B are bytes, then A AND B denotes the bitwise logical and 229 operation. 231 When B is a byte and i is an integer, then B >> i denotes the logical 232 right-shift operation. Similarly, B << i denotes the logical left- 233 shift operation. 235 If S and T are byte strings, then S || T denotes the concatenation of 236 S and T. 238 The i^th byte string in an array A is denoted as A[i]. 240 3.1.2. Strings of w-bit elements 242 If S is a byte string, then byte(S, i) denotes its i^th byte, where 243 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 244 the range of bytes from the i^th to the j^th byte, inclusive. For 245 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 246 2) is 0x0406. 248 A byte string can be considered to be a string of w-bit unsigned 249 integers; the correspondence is defined by the function coef(S, i, w) 250 as follows: 252 If S is a string, i is a positive integer, and w is a member of the 253 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 254 is interpreted as a sequence of w-bit values. That is, 256 coef(S, i, w) = (2^w - 1) AND 257 ( byte(S, floor(i * w / 8)) >> 258 (8 - (w * (i % (8 / w)) + w)) ) 260 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 261 coef(S, 0, 4) is 1. 263 S (represented as bits) 264 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 265 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 266 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 267 ^ 268 | 269 coef(S, 7, 1) 271 S (represented as four-bit values) 272 +-----------+-----------+-----------+-----------+ 273 | 1 | 2 | 3 | 4 | 274 +-----------+-----------+-----------+-----------+ 275 ^ 276 | 277 coef(S, 0, 4) 279 The return value of coef is an unsigned integer. If i is larger than 280 the number of w-bit values in S, then coef(S, i, w) is undefined, and 281 an attempt to compute that value should raise an error. 283 3.2. Security string 285 To improve security against attacks that amortize their effort 286 against multiple invocations of the hash function H, Leighton and 287 Micali introduce a "security string" that is distinct for each 288 invocation of H. The following fields can appear in a security 289 string: 291 I - an identifier for the LMS public/private keypair. The length 292 of this value varies based on the LMS parameter set and it MUST be 293 chosen uniformly at random, or via a pseudorandom process, at the 294 time that a key pair is generated, in order to ensure that it will 295 be distinct from the identifier of any other LMS private key with 296 probability close to one. 298 D - a domain separation parameter, which is a single byte that 299 takes on different values in the different algorithms in which H 300 is invoked. D takes on the following values: 302 D_ITER = 0x00 in the iterations of the LM-OTS algorithms 304 D_PBLC = 0x01 when computing the hash of all of the iterates in 305 the LM-OTS algorithm 307 D_MESG = 0x02 when computing the hash of the message in the LM- 308 OTS algorithms 310 D_LEAF = 0x03 when computing the hash of the leaf of an LMS 311 tree 313 D_INTR = 0x04 when computing the hash of an interior node of an 314 LMS tree 316 D_I = 0x05 when computing the I value for a nonroot LM tree in 317 the HSS system 319 D_PRG = 0x06 in the recommended pseudorandom process for 320 generating LMS private keys 322 C - an n-byte randomizer that is included with the message 323 whenever it is being hashed to improve security. C MUST be chosen 324 uniformly at random, or via a pseudorandom process. 326 r - in the LMS N-time signature scheme, the node number r 327 associated with a particular node of a hash tree is used as an 328 input to the hash used to compute that node. This value is 329 represented as a 32-bit (four byte) unsigned integer in network 330 byte order. 332 q - in the LMS N-time signature scheme, each LM-OTS signature is 333 associated with the leaf of a hash tree, and q is set to the leaf 334 number. This ensures that a distinct value of q is used for each 335 distinct LM-OTS public/private keypair. This value is represented 336 as a 32-bit (four byte) unsigned integer in network byte order. 338 i - in the LM-OTS one-time signature scheme, i is the index of the 339 private key element upon which H is being applied. It is 340 represented as a 16-bit (two byte) unsigned integer in network 341 byte order. 343 j - in the LM-OTS one-time signature scheme, j is the iteration 344 number used when the private key element is being iteratively 345 hashed. It is represented as an 8-bit (one byte) unsigned 346 integer. 348 3.3. Functions 350 If r is a non-negative real number, then we define the following 351 functions: 353 ceil(r) : returns the smallest integer larger than r 355 floor(r) : returns the largest integer smaller than r 357 lg(r) : returns the base-2 logarithm of r 359 3.4. Typecodes 361 A typecode is an unsigned integer that is associated with a 362 particular data format. The format of the LM-OTS, LMS, and HSS 363 signatures and public keys all begin with a typecode that indicates 364 the precise details used in that format. These typecodes are 365 represented as four-byte unsigned integers in network byte order; 366 equivalently, they are XDR enumerations (see Section 7). 368 4. LM-OTS One-Time Signatures 370 This section defines LM-OTS signatures. The signature is used to 371 validate the authenticity of a message by associating a secret 372 private key with a shared public key. These are one-time signatures; 373 each private key MUST be used only one time to sign any given 374 message. 376 As part of the signing process, a digest of the original message is 377 computed using the cryptographic hash function H (see Section 4.2), 378 and the resulting digest is signed. 380 In order to facilitate its use in an N-time signature system, the LM- 381 OTS key generation, signing, and verification algorithms all take as 382 input a diversification parameter q. When the LM-OTS signature 383 system is used outside of an N-time signature system, this value 384 SHOULD be set to the all-zero value. 386 4.1. Parameters 388 The signature system uses the parameters n and w, which are both 389 positive integers. The algorithm description also makes use of the 390 internal parameters p and ls, which are dependent on n and w. These 391 parameters are summarized as follows: 393 n : the number of bytes of the output of the hash function 395 w : the width (number of bits) of the Winternitz coefficients; it 396 is a member of the set { 1, 2, 4, 8 } 398 p : the number of n-byte string elements that make up the LM-OTS 399 signature 401 ls : the number of left-shift bits used in the checksum function 402 Cksm (defined in Section 4.6). 404 The value of n is determined by the functions selected for use as 405 part of the LM-OTS algorithm; the choice of this value has a strong 406 effect on the security of the system. The parameter w determines the 407 length of the Winternitz chains computed as a part of the OTS 408 signature (which involve 2^w-1 invocations of the hash function); it 409 has little effect on security. Increasing w will shorten the 410 signature, but at a cost of a larger computation to generate and 411 verify a signature. The values of p and ls are dependent on the 412 choices of the parameters n and w, as described in Appendix B. A 413 table illustrating various combinations of n, w, p, and ls is 414 provided in Table 1. 416 4.2. Hashing Functions 418 The LM-OTS algorithm uses a hash function H that accepts byte strings 419 of any length, and returns an n-byte string. 421 4.3. Signature Methods 423 To fully describe a LM-OTS signature method, the parameters n and w, 424 the length LenS of the security string S, as well as the function H, 425 MUST be specified. This section defines several LM-OTS signature 426 systems, each of which is identified by a name. Values for p and ls 427 are provided as a convenience. 429 +---------------------+--------+----+---+------+-----+----+ 430 | Name | H | n | w | LenS | p | ls | 431 +---------------------+--------+----+---+------+-----+----+ 432 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 68 | 265 | 7 | 433 | | | | | | | | 434 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 68 | 133 | 6 | 435 | | | | | | | | 436 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 68 | 67 | 4 | 437 | | | | | | | | 438 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 68 | 34 | 0 | 439 +---------------------+--------+----+---+------+-----+----+ 441 Table 1 443 Here SHA256 denotes the NIST standard hash function [FIPS180]. 444 SHA256-16 denotes the SHA256 hash function with its final output 445 truncated to return the leftmost 16 bytes; that is, immediately after 446 computing the SHA256 hash, the 32 bit hash output is truncated to be 447 the leftmost 16 bytes. 449 4.4. Private Key 451 The LM-OTS private key consists of a typecode indicating the 452 particular LM-OTS algorithm, an array x[] containing p n-byte 453 strings, and a LenS-bygte security string S. This private key MUST 454 be used to sign (at most) one message. The following algorithm shows 455 pseudocode for generating a private key. 457 Algorithm 0: Generating a Private Key 459 1. set type to the typecode of the algorithm 461 2. if no security string S has been provided as input, then set S to 462 a LenS-byte string generated uniformly at random 464 3. set n and p according to the typecode and Table 1 466 4. compute the array x as follows: 467 for ( i = 0; i < p; i = i + 1 ) { 468 set x[i] to a uniformly random n-byte string 469 } 471 5. return u32str(type) || S || x[0] || x[1] || ... || x[p-1] 473 An implementation MAY use a pseudorandom method to compute x[i], as 474 suggested in [Merkle79], page 46. The details of the pseudorandom 475 method do not affect interoperability, but the cryptographic strength 476 MUST match that of the LM-OTS algorithm. Appendix A provides an 477 example of a pseudorandom method for computing LM-OTS private key. 479 4.5. Public Key 481 The LM-OTS public key is generated from the private key by 482 iteratively applying the function H to each individual element of x, 483 for 2^w - 1 iterations, then hashing all of the resulting values. 485 The public key is generated from the private key using the following 486 algorithm, or any equivalent process. 488 Algorithm 1: Generating a One Time Signature Public Key From a 489 Private Key 491 1. set type to the typecode of the algorithm 493 2. set the integers n, p, and w according to the typecode and Table 1 495 3. determine x and S from the private key 497 3. compute the string K as follows: 498 for ( i = 0; i < p; i = i + 1 ) { 499 tmp = x[i] 500 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 501 tmp = H(S || tmp || u16str(i) || u8str(j) || D_ITER) 502 } 503 y[i] = tmp 504 } 505 K = H(S || y[0] || ... || y[p-1] || D_PBLC) 507 4. return u32str(type) || S || K 509 The public key is the value returned by Algorithm 1. 511 4.6. Checksum 513 A checksum is used to ensure that any forgery attempt that 514 manipulates the elements of an existing signature will be detected. 515 The security property that it provides is detailed in Section 12. 516 The checksum function Cksm is defined as follows, where S denotes the 517 n-byte string that is input to that function, and the value sum is a 518 16-bit unsigned integer: 520 Algorithm 2: Checksum Calculation 522 sum = 0 523 for ( i = 0; i < (n*8/w); i = i + 1 ) { 524 sum = sum + (2^w - 1) - coef(S, i, w) 525 } 526 return (sum << ls) 528 Because of the left-shift operation, the rightmost bits of the result 529 of Cksm will often be zeros. Due to the value of p, these bits will 530 not be used during signature generation or verification. 532 4.7. Signature Generation 534 The LM-OTS signature of a message is generated by first prepending 535 the randomizer C and the security string S to the message, then 536 appending D_MESG to the resulting string then computing its hash, 537 concatenating the checksum of the hash to the hash itself, then 538 considering the resulting value as a sequence of w-bit values, and 539 using each of the w-bit values to determine the number of times to 540 apply the function H to the corresponding element of the private key. 541 The outputs of the function H are concatenated together and returned 542 as the signature. The pseudocode for this procedure is shown below. 544 The identifier string I and diversification string q are the same as 545 in Section 4.5. 547 Algorithm 3: Generating a One Time Signature From a Private Key and a 548 Message 550 1. set type to the typecode of the algorithm 552 2. set n, p, and w according to the typecode and Table 1 554 3. determine x and S from the private key 556 3. set C to a uniformly random n-byte string 558 4. compute the array y as follows: 559 Q = H(S || C || message || D_MESG ) 560 for ( i = 0; i < p; i = i + 1 ) { 561 a = coef(Q || Cksm(Q), i, w) 562 tmp = x[i] 563 for ( j = 0; j < a; j = j + 1 ) { 564 tmp = H(S || tmp || u16str(i) || u8str(j) || D_ITER) 565 } 566 y[i] = tmp 567 } 569 5. return u32str(type) || C || y[0] || ... || y[p-1] 571 Note that this algorithm results in a signature whose elements are 572 intermediate values of the elements computed by the public key 573 algorithm in Section 4.5. 575 The signature is the string returned by Algorithm 3. Section 7 576 specifies the typecode and more formally defines the encoding and 577 decoding of the string. 579 4.8. Signature Verification 581 In order to verify a message with its signature (an array of n-byte 582 strings, denoted as y), the receiver must "complete" the chain of 583 iterations of H using the w-bit coefficients of the string resulting 584 from the concatenation of the message hash and its checksum. This 585 computation should result in a value that matches the provided public 586 key. 588 Algorithm 4a: Verifying a Signature and Message Using a Public Key 590 1. if the public key is not at least four bytes long, return INVALID 592 2. parse pubtype, S, and K from the public key as follows: 593 a. pubtype = strTou32(first 4 bytes of public key) 595 b. if pubtype is not equal to sigtype, return INVALID 597 c. if the public key is not exactly 4 + LenS + n bytes long, 598 return INVALID 600 c. S = next LenS bytes of public key 602 d. K = next n bytes of public key 604 3. compute the public key candidate Kc from the signature, 605 message, and the security string S obtained from the 606 public key, using Algorithm 4b. 608 4. if Kc is equal to K, return VALID; otherwise, return INVALID 610 Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, 611 Message, Signature Typecode Type , and a Security String S 613 1. if the signature is not at least four bytes long, return INVALID 615 2. parse sigtype, C, and y from the signature as follows: 616 a. sigtype = strTou32(first 4 bytes of signature) 618 b. if sigtype is not equal to Type, return INVALID 620 c. set n and p according to the sigtype and Table 1; if the 621 signature is not exactly 8 + n * (p+1) bytes long, return INVALID 623 d. C = next n bytes of signature 625 e. y[0] = next n bytes of signature 626 y[1] = next n bytes of signature 627 ... 628 y[p-1] = next n bytes of signature 630 3. compute the string Kc as follows 631 Q = H(S || C || message || D_MESG) 632 for ( i = 0; i < p; i = i + 1 ) { 633 a = coef(Q || Cksm(Q), i, w) 634 tmp = y[i] 635 for ( j = a; j < 2^w - 1; j = j + 1 ) { 636 tmp = H(S || tmp || u16str(i) || u8str(j) || D_ITER) 637 } 638 z[i] = tmp 639 } 640 Kc = H(S || z[0] || z[1] || ... || z[p-1] || D_PBLC) 642 4. return Kc 644 5. Leighton Micali Signatures 646 The Leighton Micali Signature (LMS) method can sign a potentially 647 large but fixed number of messages. An LMS system uses two 648 cryptographic components: a one-time signature method and a hash 649 function. Each LMS public/private key pair is associated with a 650 perfect binary tree, each node of which contains an n-byte value. 651 Each leaf of the tree contains the value of the public key of an LM- 652 OTS public/private key pair. The value contained by the root of the 653 tree is the LMS public key. Each interior node is computed by 654 applying the hash function to the concatenation of the values of its 655 children nodes. 657 Each node of the tree is associated with a node number, an unsigned 658 integer that is denoted as node_num in the algorithms below, which is 659 computed as follows. The root node has node number 1; for each node 660 with node number N, its left child has node number 2*N, while its 661 right child has node number 2*N+1. The result of this is that each 662 node within the tree will have a unique node number, and the leaves 663 will have node numbers 2^h, (2^h)+1, (2^h)+2, ..., (2^h)+(2^h)-1. In 664 general, the jth node at level L has node number 2^L + j. The node 665 number can conveniently be computed when it is needed in the LMS 666 algorithms, as described in those algorithms. 668 5.1. Parameters 670 An LMS system has the following parameters: 672 h : the height (number of levels - 1) in the tree, and 674 m : the number of bytes associated with each node. 676 There are 2^h leaves in the tree. The parameter m MAY have any value 677 in principle, but it SHOULD be equal to the parameter n from 678 Section 4.1 so that the security level of LMS is comparable to that 679 of LM-OTS. 681 +--------------------+--------+----+----+ 682 | Name | H | m | h | 683 +--------------------+--------+----+----+ 684 | LMS_SHA256_M32_H5 | SHA256 | 32 | 5 | 685 | | | | | 686 | LMS_SHA256_M32_H10 | SHA256 | 32 | 10 | 687 | | | | | 688 | LMS_SHA256_M32_H15 | SHA256 | 32 | 15 | 689 | | | | | 690 | LMS_SHA256_M32_H20 | SHA256 | 32 | 20 | 691 +--------------------+--------+----+----+ 693 Table 2 695 5.2. LMS Private Key 697 An LMS private key consists of an array OTS_PRIV[] of 2^h LM-OTS 698 private keys, and the leaf number q of the next LM-OTS private key 699 that has not yet been used. The qth element of OTS_PRIV[] is 700 generated using Algorithm 0 with the security string S = I || q. The 701 leaf number q is initialized to zero when the LMS private key is 702 created. The process is as follows: 704 Algorithm 5: Computing an LMS Private Key. 706 1. determine h and m from the typecode and Table 2. 708 2. compute the array OTS_PRIV[] as follows: 709 for ( q = 0; q < 2^h; q = q + 1) { 710 S = I || q 711 OTS_PRIV[q] = LM-OTS private key with security string S 712 } 714 3. q = 0 716 An LMS private key MAY be generated pseudorandomly from a secret 717 value, in which case the secret value MUST be at least m bytes long, 718 be uniformly random, and MUST NOT be used for any other purpose than 719 the generation of the LMS private key. The details of how this 720 process is done do not affect interoperability; that is, the public 721 key verification operation is independent of these details. 722 Appendix A provides an example of a pseudorandom method for computing 723 an LMS private key. 725 5.3. LMS Public Key 727 An LMS public key is defined as follows, where we denote the public 728 key associated with the i^th LM-OTS private key as OTS_PUB[i], with i 729 ranging from 0 to (2^h)-1. Each instance of an LMS public/private 730 key pair is associated with a perfect binary tree, and the nodes of 731 that tree are indexed from 1 to 2^(h+1)-1. Each node is associated 732 with an m-byte string, and the string for the rth node is denoted as 733 T[r] and is defined as 735 T[r] = / H(I || OTS_PUB[r-2^h] || u32str(r) || D_LEAF) if r >= 2^h, 736 \ H(I || T[2*r] || T[2*r+1] || u32str(r) || D_INTR) otherwise. 738 The LMS public key is the string u32str(type) || I || T[1]. 739 Section 7 specifies the format of the type variable. The value I is 740 the private key identifier (whose length is denoted by the parameter 741 set), and is the value used for all computations for the same LMS 742 tree. The value T[1] can be computed via recursive application of 743 the above equation, or by any equivalent method. An iterative 744 procedure is outlined in Appendix C. 746 5.4. LMS Signature 748 An LMS signature consists of 750 a typecode indicating the particular LMS algorithm, 751 the number q of the leaf associated with the LM-OTS signature, as 752 a four-byte unsigned integer in network byte order, 754 an LM-OTS signature, and 756 an array of h m-byte values that is associated with the path 757 through the tree from the leaf associated with the LM-OTS 758 signature to the root. 760 Symbolically, the signature can be represented as u32str(type) || 761 u32str(q) || ots_signature || path[0] || path[1] || ... || path[h-1]. 762 Section 7 specifies the typecode and more formally defines the 763 format. The array of values contains the siblings of the nodes on 764 the path from the leaf to the root but does not contain the nodes on 765 the path themselves. The array for a tree with height h will have h 766 values. The first value is the sibling of the leaf, the next value 767 is the sibling of the parent of the leaf, and so on up the path to 768 the root. 770 5.4.1. LMS Signature Generation 772 To compute the LMS signature of a message with an LMS private key, 773 the signer first computes the LM-OTS signature of the message using 774 the leaf number of the next unused LM-OTS private key. The leaf 775 number q in the signature is set to the leaf number of the LMS 776 private key that was used in the signature. Before releasing the 777 signature, the leaf number q in the LMS private key MUST be 778 incremented, to prevent the LM-OTS private key from being used again. 779 If the LMS private key is maintained in nonvolatile memory, then the 780 implementation MUST ensure that the incremented value has been stored 781 before releasing the signature. 783 The array of node values in the signature MAY be computed in any way. 784 There are many potential time/storage tradeoffs that can be applied. 785 The fastest alternative is to store all of the nodes of the tree and 786 set the array in the signature by copying them. The least storage 787 intensive alternative is to recompute all of the nodes for each 788 signature. Note that the details of this procedure are not important 789 for interoperability; it is not necessary to know any of these 790 details in order to perform the signature verification operation. 791 The internal nodes of the tree need not be kept secret, and thus a 792 node-caching scheme that stores only internal nodes can sidestep the 793 need for strong protections. 795 Several useful time/storage tradeoffs are described in the 'Small- 796 Memory LM Schemes' section of [USPTO5432852]. 798 5.5. LMS Signature Verification 800 An LMS signature is verified by first using the LM-OTS signature 801 verification algorithm to compute the LM-OTS public key from the LM- 802 OTS signature and the message. The value of that public key is then 803 assigned to the associated leaf of the LMS tree, then the root of the 804 tree is computed from the leaf value and the array path[] as 805 described in Algorithm 6 below. If the root value matches the public 806 key, then the signature is valid; otherwise, the signature fails. 808 Algorithm 6: LMS Signature Verification 810 1. if the public key is not at least four bytes long, return 811 INVALID 813 2. parse pubtype, I, and T[1] from the public key as follows: 814 a. pubtype = strTou32(first 4 bytes of public key) 816 b. if the public key is not exactly 4 + LenI + m bytes 817 long, return INVALID 819 c. I = next LenI bytes of the public key 821 d. T[1] = next m bytes of the public key 823 6. compute the candidate LMS root value Tc from the signature, 824 message, identifier and pubtype using Algorithm 6b. 826 7. if Tc is equal to T[1], return VALID; otherwise, return INVALID 828 Algorithm 6b: Computing an LMS Public Key Candidate from a Signature, 829 Message, Identifier, and algorithm typecode 831 1. if the signature is not at least eight bytes long, return INVALID 833 2. parse sigtype, q, ots_signature, and path from the signature as 834 follows: 835 a. sigtype = strTou32(first 4 bytes of signature) 837 b. if pubtype is not equal to sigtype, return INVALID 839 c. set m, h, and LenI according to sigtype and Table 2; 841 d. q = strTou32(next 4 bytes of signature) 843 e. otssigtype = strTou32(next 4 bytes of signature) 845 f. set n and p according to otssigtype and Table 1; if the 846 signature does string is not at least 12 + n * (p + 1) + m * h 847 bytes long, return INVALID 849 g. ots_signature = bytes 8 through 8 + n * (p + 1) of signature 851 h. set path as follows: 852 path[0] = next m bytes of signature 853 path[1] = next m bytes of signature 854 ... 855 path[h-1] = next m bytes of signature 857 5. Kc = candidate public key computed by applying Algorithm 4b 858 to the signature ots_signature, the message, and the 859 security string S = I || q 861 6. compute the candidate LMS root value Tc as follows: 862 tmp = H(I || Kc || u32str(node_num) || D_LEAF) 863 i = 0 864 node_num = 2^h + q 865 while (node_num > 1) { 866 if (node_num is odd): 867 tmp = H(I || path[i] || tmp || u32str(node_num/2) || D_INTR) 868 else: 869 tmp = H(I || tmp || path[i] || u32str(node_num/2) || D_INTR) 870 node_num = node_num/2 871 i = i + 1 873 7. return Tc 875 6. Hierarchical signatures 877 In scenarios where it is necessary to minimize the time taken by the 878 public key generation process, a Hierarchical N-time Signature System 879 (HSS) can be used. Leighton and Micali describe a scheme in which an 880 LMS public key is used to sign a second LMS public key, which is then 881 distributed along with the signatures generated with the second 882 public key [USPTO5432852]. This hierarchical scheme, which we 883 describe in this section, uses an LMS scheme as a component. It also 884 makes use of an hbs_key_info structure, which contains the typecode 885 of the LMS algorithm and the typecode of the LM-OTS algorithm. 887 Each level of the hierarchy is associated with a distinct LMS public 888 key, private key, signature, and identifier. The number of levels is 889 denoted L, and is between two and eight, inclusive. The following 890 notation is used, where i is an integer between 0 and L-1 inclusive, 891 and the root of the hierarchy is level 0: 893 prv[i] is the LMS private key of the ith level, 895 pub[i] is the LMS public key of the ith level (which includes the 896 identifier I as well as the key value K), 898 sig[i] is the LMS signature of the ith level, 900 In this section, we say that an N-time private key is exhausted when 901 it has generated N signatures, and thus it can no longer be used for 902 signing. 904 6.1. Key Generation 906 When an HSS keypair is generated, the keypair for each level has its 907 own identifier. 909 To generate an HSS private and public key pair, new LMS private and 910 public keys are generated for prv[i] and pub[i] for i=0, ..., L-1. 911 These key pairs, and their identifiers, MUST be generated 912 independently. All of the information of the leaf level L-1, 913 including the private key, MUST NOT be stored in nonvolatile memory. 914 Letting nv denote the lowest level for which prv[nv] is stored in 915 nonvolatile memory, there are nv nonvolatile levels, and L-nv 916 volatile levels. For security, nv should be as close to zero as 917 possible (see Section 12.1). 919 The public key of the HSS scheme is pub[1], the public key of the 920 first level, followed by an array info[] containing the hbs_key_info 921 structures for the remaining levels 1, ..., L-1. 923 The HSS private key consists of prv[0], ... , prv[L-1]. The values 924 pub[0] and prv[0] do not change, though the values of pub[i] and 925 prv[i] are dynamic for i > 1, and are changed by the signature 926 generation algorithm. 928 6.2. Signature Generation 930 To sign a message using the private key prv, the following steps are 931 performed: 933 If prv[L-1] is exhausted, then determine the smallest integer d 934 such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] 935 are exhausted. If d is equal to one, then the HSS keypair is 936 exhausted, and it MUST NOT generate any more signatures. 937 Otherwise, the keypairs for levels d through L-1 must be 938 regenerated during the signature generation process, as follows. 939 For i from d to L-1, a new LMS public and private key pair with a 940 new identifier is generated, pub[i] and prv[i] are set to those 941 values, then the public key pub[i] is signed with prv[i-1], and 942 sig[i-1] is set to the resulting value. 944 The message is signed with prv[L-1], and the value sig[L-1] is set 945 to that result. 947 The value of the HSS signature is set as follows. We let 948 signed_pub_key denote an array of strings, where signed_pub_key[i] 949 = sig[i] || pub[i+1], for i between 0 and L-2, inclusive. Then 950 the HSS signature is u32str(L-1) || signed_pub_key[0] || ... || 951 signed_pub_key[L-2] || sig[L-1]. 953 Note that the number of signed_pub_key elements in the signature 954 is indicated by the value L-1 that appears in the initial four 955 bytes of the signature. 957 6.3. Signature Verification 959 To verify a signature sig and message using the public key pub, the 960 following steps are performed: 962 The signature S is parsed into its components as follows: 964 L' = strToU32(first four bytes of S) 965 for (i = 0; i < L'; i = i + 1) { 966 siglist[0] = next LMS signature parsed from S 967 publist[1] = next LMS public key parsed from S 968 } 969 siglist[L-1] = next LMS signature parsed from S 971 key = pub 972 for (i =0; i < L'; i = i + 1) { 973 sig = siglist[i] 974 msg = publist[i] 975 if (lms_verify(msg, key, sig) != VALID): 976 return INVALID 977 key = msg 978 return lms_verify(message, key, siglist[L-1]) 980 Since the length of an LMS signature cannot be known without parsing 981 it, the HSS signature verification algorithm makes use of an LMS 982 signature parsing routine that takes as input a string consisting of 983 an LMS signature with an arbitrary string appended to it, and returns 984 both the LMS signature and the appended string. The latter is passed 985 on for futher processing. 987 7. Formats 989 The signature and public key formats are formally defined using the 990 External Data Representation (XDR) [RFC4506] in order to provide an 991 unambiguous, machine readable definition. For clarity, we also 992 include a private key format as well, though consistency is not 993 needed for interoperability and an implementation MAY use any private 994 key format. Though XDR is used, these formats are simple and easy to 995 parse without any special tools. An illustration of the layout of 996 data in these objects is provided below. The definitions are as 997 follows: 999 /* one-time signatures */ 1001 enum ots_algorithm_type { 1002 ots_reserved = 0, 1003 lmots_sha256_n32_w1 = 1, 1004 lmots_sha256_n32_w2 = 2, 1005 lmots_sha256_n32_w4 = 3, 1006 lmots_sha256_n32_w8 = 4 1007 }; 1008 typedef opaque bytestring16[16]; 1009 typedef opaque bytestring32[32]; 1011 struct lmots_signature_n32_p265 { 1012 bytestring32 C; 1013 bytestring32 y[265]; 1014 }; 1016 struct lmots_signature_n32_p133 { 1017 bytestring32 C; 1018 bytestring32 y[133]; 1019 }; 1021 struct lmots_signature_n32_p67 { 1022 bytestring32 C; 1023 bytestring32 y[67]; 1024 }; 1026 struct lmots_signature_n32_p34 { 1027 bytestring32 C; 1028 bytestring32 y[34]; 1029 }; 1031 union ots_signature switch (ots_algorithm_type type) { 1032 case lmots_sha256_n32_w1: 1033 lmots_signature_n32_p265 sig_n32_p265; 1034 case lmots_sha256_n32_w2: 1035 lmots_signature_n32_p133 sig_n32_p133; 1036 case lmots_sha256_n32_w4: 1037 lmots_signature_n32_p67 sig_n32_p67; 1038 case lmots_sha256_n32_w8: 1039 lmots_signature_n32_p34 sig_n32_p34; 1040 default: 1041 void; /* error condition */ 1042 }; 1044 union ots_private_key switch (ots_algorithm_type type) { 1045 case lmots_sha256_n32_w1: 1046 case lmots_sha256_n32_w2: 1047 case lmots_sha256_n32_w4: 1048 case lmots_sha256_n32_w8: 1049 bytestring32 x32; 1050 default: 1051 void; /* error condition */ 1052 }; 1054 /* hash based signatures (hbs) */ 1055 enum hbs_algorithm_type { 1056 hbs_reserved = 0, 1057 lms_sha256_n32_h20 = 1, 1058 lms_sha256_n32_h10 = 2, 1059 lms_sha256_n32_h5 = 3, 1060 }; 1062 /* leighton mical signatures (lms) */ 1064 union lms_path switch (hbs_algorithm_type type) { 1065 case lms_sha256_n32_h20: 1066 bytestring32 path_n32_h20[20]; 1067 case lms_sha256_n32_h15: 1068 bytestring32 path_n32_h15[15]; 1069 case lms_sha256_n32_h10: 1070 bytestring32 path_n32_h10[10]; 1071 case lms_sha256_n32_h5: 1072 bytestring32 path_n32_h5[5]; 1073 default: 1074 void; /* error condition */ 1075 }; 1077 struct lms_signature { 1078 unsigned int q; 1079 ots_signature lmots_sig; 1080 lms_path nodes; 1081 }; 1083 struct lms_key_n32 { 1084 ots_algorithm_type ots_alg_type; 1085 opaque I[64]; 1086 opaque K[32]; 1087 }; 1089 union hbs_public_key switch (hbs_algorithm_type type) { 1090 case lms_sha256_n32_h20: 1091 case lms_sha256_n32_h10: 1092 case lms_sha256_n32_h5: 1093 lms_key_n32 z_n32; 1094 default: 1095 void; /* error condition */ 1096 }; 1098 /* hierarchical signature system (hss) */ 1100 struct hss_public_key { 1101 unsigned int levels; 1102 hbs_public_key pub; 1104 }; 1106 struct signed_public_key { 1107 hbs_signature sig; 1108 hbs_public_key pub; 1109 } 1111 struct hss_signature { 1112 signed_public_key signed_keys; 1113 hbs_signature sig_of_message; 1114 }; 1116 Many of the objects start with a typecode. A verifier MUST check 1117 each of these typecodes, and a verification operation on a signature 1118 with an unknown type, or a type that does not correspond to the type 1119 within the public key MUST return INVALID. The expected length of a 1120 variable-length object can be determined from its typecode, and if an 1121 object has a different length, then any signature computed from the 1122 object is INVALID. 1124 8. Rationale 1126 The goal of this note is to describe the LM-OTS and LMS algorithms 1127 following the original references and present the modern security 1128 analysis of those algorithms. Other signature methods are out of 1129 scope and may be interesting follow-on work. 1131 We adopt the techniques described by Leighton and Micali to mitigate 1132 attacks that amortize their work over multiple invocations of the 1133 hash function. 1135 The values taken by the identifier I across different LMS public/ 1136 private key pairs are required to be distinct in order to improve 1137 security. That distinctness ensures the uniqueness of the inputs to 1138 H across all of those public/private key pair instances, which is 1139 important for provable security in the random oracle model. The 1140 length of I is set at 31 or 64 bytes so that randomly chosen values 1141 of I will be distinct with probability at least 1 - 1/2^128 as long 1142 as there are 2^60 or fewer instances of LMS public/private key pairs. 1144 The sizes of the parameters in the security string are such that, for 1145 n=16, the LM-OTS iterates a 55-byte value (that is, the string that 1146 is input to H() during the iteration over j during signature 1147 generation and verification is 55 bytes long). Thus, when SHA-256 is 1148 used as the function H, only a single invocation of its compression 1149 function is needed. 1151 The signature and public key formats are designed so that they are 1152 relatively easy to parse. Each format starts with a 32-bit 1153 enumeration value that indicates the details of the signature 1154 algorithm and provides all of the information that is needed in order 1155 to parse the format. 1157 The Checksum Section 4.6 is calculated using a non-negative integer 1158 "sum", whose width was chosen to be an integer number of w-bit fields 1159 such that it is capable of holding the difference of the total 1160 possible number of applications of the function H as defined in the 1161 signing algorithm of Section 4.7 and the total actual number. In the 1162 case that the number of times H is applied is 0, the sum is (2^w - 1) 1163 * (8*n/w). Thus for the purposes of this document, which describes 1164 signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 1165 4, 8 }, the sum variable is a 16-bit non-negative integer for all 1166 combinations of n and w. The calculation uses the parameter ls 1167 defined in Section 4.1 and calculated in Appendix B, which indicates 1168 the number of bits used in the left-shift operation. 1170 A future version of this specification may support hash functions 1171 other than SHA-256. 1173 9. History 1175 This is the fifth version of this draft. It has the following 1176 changes from previous versions: 1178 Version 04 1180 Specified that, in the HSS method, the I value was computed from 1181 the I value of the parent LM tree. Previous versions had the I 1182 value extracted from the public key (which meant that all LM trees 1183 of a particular level and public key used the same I value) 1185 Changed the length of the I field based on the parameter set. As 1186 noted in the Rationale section, this allows an implemetation to 1187 compute N=32 based parameter sets significantly faster. 1189 Modified the XDR of an HSS signature not to use an array of LM 1190 signatures; LM signatures are variable length, and XDR doesn't 1191 support arrays of variable length structures. 1193 Changed the LMS registry to be in a consistent order with the LM- 1194 OTS paramter sets. Also, added LMS parameter sets with height 15 1195 trees 1197 Previous versions 1198 In Algorithms 3 and 4, the message was moved from the initial 1199 position of the input to the function H to the final position, in 1200 the computation of the intermediate variable Q. This was done to 1201 improve security by preventing an attacker that can find a 1202 collision in H from taking advantage of that fact via the forward 1203 chaining property of Merkle-Damgard. 1205 The Hierarchical Signature Scheme was generalized slightly so that 1206 it can use more than two levels. 1208 Several points of confusion were corrected; these had resulted 1209 from incomplete or inconsistent changes from the Merkle approach 1210 of the earlier draft to the Leighton-Micali approach. 1212 This section is to be removed by the RFC editor upon publication. 1214 10. IANA Considerations 1216 The Internet Assigned Numbers Authority (IANA) is requested to create 1217 two registries: one for OTS signatures, which includes all of the LM- 1218 OTS signatures as defined in Section 3, and one for Leighton-Micali 1219 Signatures, as defined in Section 4. Additions to these registries 1220 require that a specification be documented in an RFC or another 1221 permanent and readily available reference in sufficient detail that 1222 interoperability between independent implementations is possible. 1223 Each entry in the registry contains the following elements: 1225 a short name, such as "LMS_SHA256_N32_H10", 1227 a positive number, and 1229 a reference to a specification that completely defines the 1230 signature method test cases that can be used to verify the 1231 correctness of an implementation. 1233 Requests to add an entry to the registry MUST include the name and 1234 the reference. The number is assigned by IANA. Submitters SHOULD 1235 have their requests reviewed by the IRTF Crypto Forum Research Group 1236 (CFRG) at cfrg@ietf.org. Interested applicants that are unfamiliar 1237 with IANA processes should visit http://www.iana.org. 1239 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1240 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1241 are reserved for private use; no attempt will be made to prevent 1242 multiple sites from using the same value in different (and 1243 incompatible) ways [RFC2434]. 1245 The LM-OTS registry is as follows. 1247 +----------------------+-----------+--------------------+ 1248 | Name | Reference | Numeric Identifier | 1249 +----------------------+-----------+--------------------+ 1250 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 | 1251 | | | | 1252 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 | 1253 | | | | 1254 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 | 1255 | | | | 1256 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 | 1257 +----------------------+-----------+--------------------+ 1259 Table 3 1261 The LMS registry is as follows. 1263 +--------------------+-----------+--------------------+ 1264 | Name | Reference | Numeric Identifier | 1265 +--------------------+-----------+--------------------+ 1266 | LMS_SHA256_M32_H5 | Section 5 | 0x00000005 | 1267 | | | | 1268 | LMS_SHA256_M32_H10 | Section 5 | 0x00000006 | 1269 | | | | 1270 | LMS_SHA256_M32_H15 | Section 5 | 0x00000007 | 1271 | | | | 1272 | LMS_SHA256_M32_H20 | Section 5 | 0x00000008 | 1273 +--------------------+-----------+--------------------+ 1275 Table 4 1277 An IANA registration of a signature system does not constitute an 1278 endorsement of that system or its security. 1280 11. Intellectual Property 1282 This draft is based on U.S. patent 5,432,852, which issued over 1283 twenty years ago and is thus expired. 1285 11.1. Disclaimer 1287 This document is not intended as legal advice. Readers are advised 1288 to consult with their own legal advisers if they would like a legal 1289 interpretation of their rights. 1291 The IETF policies and processes regarding intellectual property and 1292 patents are outlined in [RFC3979] and [RFC4879] and at 1293 https://datatracker.ietf.org/ipr/about. 1295 12. Security Considerations 1297 The security goal of a signature system is to prevent forgeries. A 1298 successful forgery occurs when an attacker who does not know the 1299 private key associated with a public key can find a message and 1300 signature that are valid with that public key (that is, the Signature 1301 Verification algorithm applied to that signature and message and 1302 public key will return VALID). Such an attacker, in the strongest 1303 case, may have the ability to forge valid signatures for an arbitrary 1304 number of other messages. 1306 LM-OTS is provably secure in the random oracle model, as shown by 1307 Katz [Katz15]. From Theorem 8 of that reference: 1309 For any adversary attacking arbitrarily many instances of the one- 1310 time signature scheme, and making at most q hash queries, the 1311 probability with which the adversary is able to forge a signature 1312 with respect to any of the instances is at most q2^(1-8n). 1314 Here n is the number of bytes in the output of the hash function (as 1315 defined in Section 4.1). Thus, the security of the algorithms 1316 defined in this note can be roughly described as follows. For a 1317 security level of roughly 128 bits, even assuming that there are 1318 quantum computers that can compute the input to an arbitrary function 1319 with computational cost equivalent to the square root of the size of 1320 the domain of that function [Grover96], use n=32 by selecting an 1321 algorithm identifier with N32 in its name. 1323 The format of the inputs to H() have the property that each 1324 invocation of that function has an input that is distinct from all 1325 others, with high probability. This property is important for a 1326 proof of security in the random oracle model. The formats used 1327 during key generation and signing are 1329 S || tmp || u16str(i) || u8str(j) || D_ITER 1330 S || y[0] || ... || y[p-1] || D_PBLC 1331 S || C || message || D_MESG 1332 I || OTS_PUB[r-2^h] || u32str(r) || D_LEAF 1333 I || T[2*r] || T[2*r+1] || u32str(r) || D_INTR 1334 I || u32str(q) || x_q[j-1] || u16str(j) || D_PRG 1336 Because the suffixes D_ITER, D_PBLC, D_LEAF, D_INTR, and D_PRG are 1337 distinct, the input formats ending with different suffixes are all 1338 distinct. It remains to show the distinctness of the inputs for each 1339 suffix. 1341 The values of I and C are chosen uniformly at random from the set of 1342 all n*8 bit strings. For n=32, it is highly likely that each value 1343 of I and C will be distinct, even when 2^96 such values are chosen. 1345 For D_ITER, D_PBLC, and D_MESG, the value of S = I || u32str(q) is 1346 distinct for each LMS leaf (or equivalently, for each q value). For 1347 D_ITER, the value of u16str(i) || u8str(j) is distinct for each 1348 invocation of H for a given leaf. For D_PBLC and D_MESG, the input 1349 format is used only once for each value of S, and thus distinctness 1350 is assured. The formats for D_INTR and D_LEAF are used exactly once 1351 for each value of r, which ensures their distinctness. For D_PRG, 1352 for a given value of I, q and j are distinct for each invocation of H 1353 (note that x_q[0] = SEED when j=0). 1355 12.1. Stateful signature algorithm 1357 The LMS signature system, like all N-time signature systems, requires 1358 that the signer maintain state across different invocations of the 1359 signing algorithm, to ensure that none of the component one-time 1360 signature systems are used more than once. This section calls out 1361 some important practical considerations around this statefulness. 1363 In a typical computing environment, a private key will be stored in 1364 non-volatile media such as on a hard drive. Before it is used to 1365 sign a message, it will be read into an application's Random Access 1366 Memory (RAM). After a signature is generated, the value of the 1367 private key will need to be updated by writing the new value of the 1368 private key into non-volatile storage. It is essential for security 1369 that the application ensure that this value is actually written into 1370 that storage, yet there may be one or more memory caches between it 1371 and the application. Memory caching is commonly done in the file 1372 system, and in a physical memory unit on the hard disk that is 1373 dedicated to that purpose. To ensure that the updated value is 1374 written to physical media, the application may need to take several 1375 special steps. In a POSIX environment, for instance, the O_SYNC flag 1376 (for the open() system call) will cause invocations of the write() 1377 system call to block the calling process until the data has been to 1378 the underlying hardware. However, if that hardware has its own 1379 memory cache, it must be separately dealt with using an operating 1380 system or device specific tool such as hdparm to flush the on-drive 1381 cache, or turn off write caching for that drive. Because these 1382 details vary across different operating systems and devices, this 1383 note does not attempt to provide complete guidance; instead, we call 1384 the implementer's attention to these issues. 1386 When hierarchical signatures are used, an easy way to minimize the 1387 private key synchronization issues is to have the private key for the 1388 second level resident in RAM only, and never write that value into 1389 non-volatile memory. A new second level public/private key pair will 1390 be generated whenever the application (re)starts; thus, failures such 1391 as a power outage or application crash are automatically 1392 accommodated. Implementations SHOULD use this approach wherever 1393 possible. 1395 12.2. Security of LM-OTS Checksum 1397 To show the security of LM-OTS checksum, we consider the signature y 1398 of a message with a private key x and let h = H(message) and 1399 c = Cksm(H(message)) (see Section 4.7). To attempt a forgery, an 1400 attacker may try to change the values of h and c. Let h' and c' 1401 denote the values used in the forgery attempt. If for some integer j 1402 in the range 0 to u, where u = ceil(8*n/w) is the size of the range 1403 that the checksum value can over), inclusive, 1405 a' = coef(h', j, w), 1407 a = coef(h, j, w), and 1409 a' > a 1411 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1412 iteratively applying function F to the j^th term of the signature an 1413 additional (a' - a) times. However, as a result of the increased 1414 number of hashing iterations, the checksum value c' will decrease 1415 from its original value of c. Thus a valid signature's checksum will 1416 have, for some number k in the range u to (p-1), inclusive, 1418 b' = coef(c', k, w), 1420 b = coef(c, k, w), and 1422 b' < b 1424 Due to the one-way property of F, the attacker cannot easily compute 1425 F^b'(x[k]) from F^b(x[k]) = y[k]. 1427 13. Acknowledgements 1429 Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric 1430 Osterweil, Ahmed Kosba, and Russ Housley for constructive suggestions 1431 and valuable detailed review. We especially acknowledge Jerry 1432 Solinas, Laurie Law, and Kevin Igoe, who pointed out the security 1433 benefits of the approach of Leighton and Micali [USPTO5432852] and 1434 Jonathan Katz, who gave us security guidance. 1436 14. References 1438 14.1. Normative References 1440 [FIPS180] National Institute of Standards and Technology, "Secure 1441 Hash Standard (SHS)", FIPS 180-4, March 2012. 1443 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1444 Requirement Levels", BCP 14, RFC 2119, 1445 DOI 10.17487/RFC2119, March 1997, 1446 . 1448 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1449 IANA Considerations Section in RFCs", RFC 2434, 1450 DOI 10.17487/RFC2434, October 1998, 1451 . 1453 [RFC3979] Bradner, S., Ed., "Intellectual Property Rights in IETF 1454 Technology", BCP 79, RFC 3979, DOI 10.17487/RFC3979, March 1455 2005, . 1457 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1458 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1459 2006, . 1461 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1462 Procedure in RFC 3979", BCP 79, RFC 4879, 1463 DOI 10.17487/RFC4879, April 2007, 1464 . 1466 [USPTO5432852] 1467 Leighton, T. and S. Micali, "Large provably fast and 1468 secure digital signature schemes from secure hash 1469 functions", U.S. Patent 5,432,852, July 1995. 1471 14.2. Informative References 1473 [C:Merkle87] 1474 Merkle, R., "A Digital Signature Based on a Conventional 1475 Encryption Function", Lecture Notes in Computer 1476 Science crypto87vol, 1988. 1478 [C:Merkle89a] 1479 Merkle, R., "A Certified Digital Signature", Lecture Notes 1480 in Computer Science crypto89vol, 1990. 1482 [C:Merkle89b] 1483 Merkle, R., "One Way Hash Functions and DES", Lecture 1484 Notes in Computer Science crypto89vol, 1990. 1486 [Grover96] 1487 Grover, L., "A fast quantum mechanical algorithm for 1488 database search", 28th ACM Symposium on the Theory of 1489 Computing p. 212, 1996. 1491 [Katz15] Katz, J., "Analysis of a proposed hash-based signature 1492 standard", Contribution to IRTF 1493 http://www.cs.umd.edu/~jkatz/papers/HashBasedSigs.pdf, 1494 2015. 1496 [Merkle79] 1497 Merkle, R., "Secrecy, Authentication, and Public Key 1498 Systems", Stanford University Information Systems 1499 Laboratory Technical Report 1979-1, 1979. 1501 Appendix A. Pseudorandom Key Generation 1503 An implementation MAY use the following pseudorandom process for 1504 generating an LMS private key. 1506 SEED is an m-byte value that is generated uniformly at random at 1507 the start of the process, 1509 I is LMS keypair identifier, 1511 q denotes the LMS leaf number of an LM-OTS private key, 1513 x_q denotes the x array of private elements in the LM-OTS private 1514 key with leaf number q, 1516 j is an index of the private key element, 1518 D_PRG is a diversification constant, and 1520 H is the hash function used in LM-OTS. 1522 The elements of the LM-OTS private keys are computed as follows: 1524 x_q[j] = / H(I || u32str(q) || SEED || u16str(j) || D_PRG) if j = 0, 1525 \ H(I || u32str(q) || x_q[j-1] || u16str(j) || D_PRG) otherwise 1527 This process stretches the m-byte random value SEED into a (much 1528 larger) set of pseudorandom values, using both output feedback and a 1529 unique counter in each invocation of H. The format of the inputs to 1530 H are chosen so that they are distinct from all other uses of H in 1531 LMS and LM-OTS. 1533 Appendix B. LM-OTS Parameter Options 1535 A table illustrating various combinations of n and w with the 1536 associated values of u, v, ls, and p is provided in Table 5. 1538 The parameters u, v, ls, and p are computed as follows: 1540 u = ceil(8*n/w) 1541 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1542 ls = (number of bits in sum) - (v * w) 1543 p = u + v 1545 Here u and v represent the number of w-bit fields required to contain 1546 the hash of the message and the checksum byte strings, respectively. 1547 The "number of bits in sum" is defined according to Section 4.6. And 1548 as the value of p is the number of w-bit elements of 1549 ( H(message) || Cksm(H(message)) ), it is also equivalently the 1550 number of byte strings that form the private key and the number of 1551 byte strings in the signature. 1553 +---------+------------+-----------+-----------+-------+------------+ 1554 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1555 | Length | Parameter | Elements | Elements | Shift | Number of | 1556 | in | (w) | in Hash | in | (ls) | w-bit | 1557 | Bytes | | (u) | Checksum | | Elements | 1558 | (n) | | | (v) | | (p) | 1559 +---------+------------+-----------+-----------+-------+------------+ 1560 | 16 | 1 | 128 | 8 | 8 | 137 | 1561 | | | | | | | 1562 | 16 | 2 | 64 | 4 | 8 | 68 | 1563 | | | | | | | 1564 | 16 | 4 | 32 | 3 | 4 | 35 | 1565 | | | | | | | 1566 | 16 | 8 | 16 | 2 | 0 | 18 | 1567 | | | | | | | 1568 | 32 | 1 | 256 | 9 | 7 | 265 | 1569 | | | | | | | 1570 | 32 | 2 | 128 | 5 | 6 | 133 | 1571 | | | | | | | 1572 | 32 | 4 | 64 | 3 | 4 | 67 | 1573 | | | | | | | 1574 | 32 | 8 | 32 | 2 | 0 | 34 | 1575 +---------+------------+-----------+-----------+-------+------------+ 1577 Table 5 1579 Appendix C. An iterative algorithm for computing an LMS public key 1581 The LMS public key can be computed using the following algorithm or 1582 any equivalent method. The algorithm uses a stack of hashes for data 1583 and a separate stack of integers to keep track of the level of the 1584 tree. It also makes use of a hash function with the typical 1585 init/update/final interface to hash functions; the result of the 1586 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 1587 hash_update(N[n]), v = hash_final(), in that order, is identical to 1588 that of the invocation of H(N[1] || N[2] || ... || N[n]). 1590 Generating an LMS Public Key From an LMS Private Key 1592 for ( i = 0; i < num_lmots_keys; i = i + 2 ) { 1593 level = 0; 1594 for ( j = 0; j < 2; j = j + 1 ) { 1595 r = node_num 1596 push H(I || OTS_PUBKEY[i+j] || u32str(r) || D_LEAF) on data stack 1597 push level onto the integer stack 1598 } 1599 while ( height of the integer stack >= 2 ) { 1600 if level of the top 2 elements on the integer stack are equal { 1601 hash_init() 1602 siblings = "" 1603 repeat ( 2 ) { 1604 siblings = (pop(data stack) || siblings) 1605 level = pop(integer stack) 1606 } 1607 hash_update(siblings) 1608 r = node_num 1609 hash_update(I || u32str(r) || D_INTR) 1610 push hash_final() onto the data stack 1611 push (level + 1) onto the integer stack 1612 } 1613 } 1614 } 1615 public_key = pop(data stack) 1617 Note that this pseudocode expects that all 2^h leaves of the tree 1618 have equal depth. Neither stack ever contains more than h+1 1619 elements. For typical parameters, these stacks will hold around 512 1620 bytes of data. 1622 Appendix D. Example implementation 1623 --- Pending Revision --- 1625 Authors' Addresses 1627 David McGrew 1628 Cisco Systems 1629 13600 Dulles Technology Drive 1630 Herndon, VA 20171 1631 USA 1633 Email: mcgrew@cisco.com 1635 Michael Curcio 1636 Cisco Systems 1637 7025-2 Kit Creek Road 1638 Research Triangle Park, NC 27709-4987 1639 USA 1641 Email: micurcio@cisco.com 1643 Scott Fluhrer 1644 Cisco Systems 1645 170 West Tasman Drive 1646 San Jose, CA 1647 USA 1649 Email: sfluhrer@cisco.com