idnits 2.17.1 draft-mcgrew-hash-sigs-04.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 are 2 instances 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 == Line 1047 has weird spacing: '...ey_info info...' -- The document date (March 21, 2016) is 2952 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 675 -- Looks like a reference, but probably isn't: '1' on line 1528 == Missing Reference: 'L' is mentioned on line 838, but not defined == Missing Reference: 'L-1' is mentioned on line 839, but not defined -- Looks like a reference, but probably isn't: '2' on line 1528 -- Looks like a reference, but probably isn't: '4' on line 875 -- Looks like a reference, but probably isn't: '16' on line 1001 -- Looks like a reference, but probably isn't: '32' on line 1007 -- Looks like a reference, but probably isn't: '265' on line 907 -- Looks like a reference, but probably isn't: '133' on line 913 -- Looks like a reference, but probably isn't: '67' on line 919 -- Looks like a reference, but probably isn't: '34' on line 925 -- Looks like a reference, but probably isn't: '20' on line 985 -- Looks like a reference, but probably isn't: '10' on line 987 -- Looks like a reference, but probably isn't: '5' on line 989 -- Looks like a reference, but probably isn't: '31' on line 1026 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) Summary: 2 errors (**), 0 flaws (~~), 4 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 Cisco Systems 5 Expires: September 22, 2016 March 21, 2016 7 Hash-Based Signatures 8 draft-mcgrew-hash-sigs-04 10 Abstract 12 This note describes a digital signature system based on cryptographic 13 hash functions, following the seminal work in this area of Lamport, 14 Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in 15 1995. It specifies a one-time signature scheme and a general 16 signature scheme. These systems provide asymmetric authentication 17 without using large integer mathematics and can achieve a high 18 security level. They are suitable for compact implementations, are 19 relatively simple to implement, and naturally resist side-channel 20 attacks. Unlike most other signature systems, hash-based signatures 21 would still be secure even if it proves feasible for an attacker to 22 build a quantum computer. 24 Status of this Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on September 22, 2016. 41 Copyright Notice 43 Copyright (c) 2016 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 1.1. Conventions Used In This Document . . . . . . . . . . . . 5 61 2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 6 63 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 64 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 7 65 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 7 66 3.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 8 67 3.2. Security string . . . . . . . . . . . . . . . . . . . . . 9 68 3.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 10 70 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . . 11 71 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . . 11 72 4.2. Hashing Functions . . . . . . . . . . . . . . . . . . . . 12 73 4.3. Signature Methods . . . . . . . . . . . . . . . . . . . . 12 74 4.4. Private Key . . . . . . . . . . . . . . . . . . . . . . . 12 75 4.5. Public Key . . . . . . . . . . . . . . . . . . . . . . . . 13 76 4.6. Checksum . . . . . . . . . . . . . . . . . . . . . . . . . 14 77 4.7. Signature Generation . . . . . . . . . . . . . . . . . . . 14 78 4.8. Signature Verification . . . . . . . . . . . . . . . . . . 15 80 5. Leighton Micali Signatures . . . . . . . . . . . . . . . . . . 17 81 5.1. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 17 82 5.2. LMS Public Key . . . . . . . . . . . . . . . . . . . . . . 17 83 5.3. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 18 84 5.3.1. LMS Signature Generation . . . . . . . . . . . . . . . 18 85 5.4. LMS Signature Verification . . . . . . . . . . . . . . . . 19 87 6. Hierarchical signatures . . . . . . . . . . . . . . . . . . . 21 88 6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . . 21 89 6.2. Signature Generation . . . . . . . . . . . . . . . . . . . 21 90 6.3. Signature Verification . . . . . . . . . . . . . . . . . . 22 92 7. Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 94 8. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 30 96 9. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 98 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32 100 11. Security Considerations . . . . . . . . . . . . . . . . . . . 34 101 11.1. Stateful signature algorithm . . . . . . . . . . . . . . . 34 102 11.2. Security of LM-OTS Checksum . . . . . . . . . . . . . . . 35 104 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 37 106 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 38 107 13.1. Normative References . . . . . . . . . . . . . . . . . . . 38 108 13.2. Informative References . . . . . . . . . . . . . . . . . . 38 110 Appendix A. LM-OTS Parameter Options . . . . . . . . . . . . . . 40 112 Appendix B. An iterative algorithm for computing an LMS 113 public key . . . . . . . . . . . . . . . . . . . . . 41 115 Appendix C. Example implementation . . . . . . . . . . . . . . . 42 117 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 43 119 1. Introduction 121 One-time signature systems, and general purpose signature systems 122 built out of one-time signature systems, have been known since 1979 123 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 124 benefited from renewed attention in the last decade. The 125 characteristics of these signature systems are small private and 126 public keys and fast signature generation and verification, but large 127 signatures and relatively slow key generation. In recent years there 128 has been interest in these systems because of their post-quantum 129 security and their suitability for compact implementations. 131 This note describes the Leighton and Micali adaptation [USPTO5432852] 132 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 133 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 134 signature system [Merkle79] with enough specificity to ensure 135 interoperability between implementations. An example implementation 136 is given in an appendix. 138 A signature system provides asymmetric message authentication. The 139 key generation algorithm produces a public/private key pair. A 140 message is signed by a private key, producing a signature, and a 141 message/signature pair can be verified by a public key. A One-Time 142 Signature (OTS) system can be used to sign exactly one message 143 securely, but cannot securely sign more than one. An N-time 144 signature system can be used to sign N or fewer messages securely. A 145 Merkle tree signature scheme is an N-time signature system that uses 146 an OTS system as a component. In this note we describe the Leighton- 147 Micali Signature (LMS) system, which is a variant of the Merkle 148 scheme. We denote the one-time signature scheme that it incorporates 149 as LM-OTS. 151 This note is structured as follows. Notation is introduced in 152 Section 3. The LM-OTS signature system is described in Section 4, 153 and the LMS N-time signature system is described in Section 5. 154 Sufficient detail is provided to ensure interoperability. The IANA 155 registry for these signature systems is described in Section 10. 156 Security considerations are presented in Section 11. 158 1.1. Conventions Used In This Document 160 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 161 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 162 document are to be interpreted as described in [RFC2119]. 164 2. Interface 166 The LMS signing algorithm is stateful; once a particular value of the 167 private key is used to sign one message, it MUST NOT be used to sign 168 another. 170 The key generation algorithm takes as input an indication of the 171 parameters for the signature system. If it is successful, it 172 returns both a private key and a public key. Otherwise, it 173 returns an indication of failure. 175 The signing algorithm takes as input the message to be signed and 176 the current value of the private key. If successful, it returns a 177 signature and the next value of the private key, if there is such 178 a value. After the private key of an N-time signature system has 179 signed N messages, the signing algorithm returns the signature and 180 an indication that there is no next value of the private key that 181 can be used for signing. If unsuccessful, it returns an 182 indication of failure. 184 The verification algorithm takes as input the public key, a 185 message, and a signature, and returns an indication of whether or 186 not the signature and message pair are valid. 188 A message/signature pair are valid if the signature was returned by 189 the signing algorithm upon input of the message and the private key 190 corresponding to the public key; otherwise, the signature and message 191 pair are not valid with probability very close to one. 193 3. Notation 195 3.1. Data Types 197 Bytes and byte strings are the fundamental data types. A single byte 198 is denoted as a pair of hexadecimal digits with a leading "0x". A 199 byte string is an ordered sequence of zero or more bytes and is 200 denoted as an ordered sequence of hexadecimal characters with a 201 leading "0x". For example, 0xe534f0 is a byte string with a length 202 of three. An array of byte strings is an ordered set, indexed 203 starting at zero, in which all strings have the same length. 205 Unsigned integers are converted into byte strings by representing 206 them in network byte order. To make the number of bytes in the 207 representation explicit, we define the functions u8str(X), u16str(X), 208 and u32str(X), which return one, two, and four byte values, 209 respectively. 211 3.1.1. Operators 213 When a and b are real numbers, mathematical operators are defined as 214 follows: 216 ^ : a ^ b denotes the result of a raised to the power of b 218 * : a * b denotes the product of a multiplied by b 220 / : a / b denotes the quotient of a divided by b 222 % : a % b denotes the remainder of the integer division of a by b 224 + : a + b denotes the sum of a and b 226 - : a - b denotes the difference of a and b 228 The standard order of operations is used when evaluating arithmetic 229 expressions. 231 If A and B are bytes, then A AND B denotes the bitwise logical and 232 operation. 234 When B is a byte and i is an integer, then B >> i denotes the logical 235 right-shift operation. Similarly, B << i denotes the logical left- 236 shift operation. 238 If S and T are byte strings, then S || T denotes the concatenation of 239 S and T. 241 The i^th byte string in an array A is denoted as A[i]. 243 3.1.2. Strings of w-bit elements 245 If S is a byte string, then byte(S, i) denotes its i^th byte, where 246 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 247 the range of bytes from the i^th to the j^th byte, inclusive. For 248 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 249 2) is 0x0406. 251 A byte string can be considered to be a string of w-bit unsigned 252 integers; the correspondence is defined by the function coef(S, i, w) 253 as follows: 255 If S is a string, i is a positive integer, and w is a member of the 256 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 257 is interpreted as a sequence of w-bit values. That is, 259 coef(S, i, w) = (2^w - 1) AND 260 ( byte(S, floor(i * w / 8)) >> 261 (8 - (w * (i % (8 / w)) + w)) ) 263 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 264 coef(S, 0, 4) is 1. 266 S (represented as bits) 267 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 268 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 269 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 270 ^ 271 | 272 coef(S, 7, 1) 274 S (represented as four-bit values) 275 +-----------+-----------+-----------+-----------+ 276 | 1 | 2 | 3 | 4 | 277 +-----------+-----------+-----------+-----------+ 278 ^ 279 | 280 coef(S, 0, 4) 282 The return value of coef is an unsigned integer. If i is larger than 283 the number of w-bit values in S, then coef(S, i, w) is undefined, and 284 an attempt to compute that value should raise an error. 286 3.2. Security string 288 To improve security against attacks that amortize their effort 289 against multiple invocations of the hash function H, Leighton and 290 Micali introduce a "security string" that is distinct for each 291 invocation of H. The following fields can appear in a security 292 string: 294 I - an identifier for the private key. This value is 31 bytes 295 long, and it MUST be distinct from all other such identifiers. It 296 SHOULD be chosen uniformly at random, or via a pseudorandom 297 process, at the time that a key pair is generated, in order to 298 ensure that it will be distinct with probability close to one, but 299 it MAY be a structured identifier. 301 D - a domain separation parameter, which is a single byte that 302 takes on different values in the different algorithms in which H 303 is invoked. D takes on the following values: 305 D_ITER = 0x00 in the iterations of the LM-OTS algorithms 307 D_PBLC = 0x01 when computing the hash of all of the iterates in 308 the LM-OTS algorithm 310 D_MESG = 0x02 when computing the hash of the message in the LM- 311 OTS algorithms 313 D_LEAF = 0x03 when computing the hash of the leaf of an LMS 314 tree 316 D_INTR = 0x04 when computing the hash of an interior node of an 317 LMS tree 319 C - an n-byte randomizer that is included with the message 320 whenever it is being hashed to improve security. C MUST be chosen 321 uniformly at random, or via a pseudorandom process with a 322 cryptographic strength that matches or exceeds that of the LM-OTS 323 algorithm itself. 325 i - in the LM-OTS one-time signature scheme, i is the index of the 326 private key element upon which H is being applied. It is 327 represented as a 16-bit (two byte) unsigned integer in network 328 byte order. 330 j - in the LM-OTS one-time signature scheme, j is the iteration 331 number used when the private key element is being iteratively 332 hashed. It is represented as an 8-bit (one byte) unsigned 333 integer. 335 q - in the LM-OTS one-time signature scheme, q is a 336 diversification string provided as input. In the LMS N-time 337 signature scheme, each LM-OTS signature is associated with the 338 leaf of a tree, and q is set to the leaf number (as described 339 below). This ensures that a distinct value of q is used for each 340 distinct LM-OTS public/private keypair. q is represented as a four 341 byte string. 343 r - in the LMS N-time signature scheme, the node number r 344 associated with a particular node of the hash tree is used as an 345 input to the hash used to compute that node. This value is 346 represented as a 32-bit (four byte) unsigned integer in network 347 byte order. 349 3.3. Functions 351 If r is a non-negative real number, then we define the following 352 functions: 354 ceil(r) : returns the smallest integer larger than r 356 floor(r) : returns the largest integer smaller than r 358 lg(r) : returns the base-2 logarithm of r 360 4. LM-OTS One-Time Signatures 362 This section defines LM-OTS signatures. The signature is used to 363 validate the authenticity of a message by associating a secret 364 private key with a shared public key. These are one-time signatures; 365 each private key MUST be used only one time to sign any given 366 message. 368 As part of the signing process, a digest of the original message is 369 computed using the cryptographic hash function H (see Section 4.2), 370 and the resulting digest is signed. 372 In order to facilitate its use in an N-time signature system, the LM- 373 OTS key generation, signing, and verification algorithms all take as 374 input a diversification parameter q. When the LM-OTS signature 375 system is used outside of an N-time signature system, this value 376 SHOULD be set to the all-zero value. 378 4.1. Parameters 380 The signature system uses the parameters n and w, which are both 381 positive integers. The algorithm description also makes use of the 382 internal parameters p and ls, which are dependent on n and w. These 383 parameters are summarized as follows: 385 n : the number of bytes of the output of the hash function 387 w : the Winternitz parameter; it is a member of the set 388 { 1, 2, 4, 8 } 390 p : the number of n-byte string elements that make up the LM-OTS 391 signature 393 ls : the number of left-shift bits used in the checksum function 394 Cksm (defined in Section 4.6). 396 The value of n is determined by the functions selected for use as 397 part of the LM-OTS algorithm; the choice of this value has a strong 398 effect on the security of the system. The parameter w can be chosen 399 to set the number of bytes in the signature; it has little effect on 400 security. Note however, that there is a larger computational cost to 401 generate and verify a shorter signature. The values of p and ls are 402 dependent on the choices of the parameters n and w, as described in 403 Appendix A. A table illustrating various combinations of n, w, p, 404 and ls is provided in Table 1. 406 4.2. Hashing Functions 408 The LM-OTS algorithm uses a hash function H that accepts byte strings 409 of any length, and returns an n-byte string. 411 4.3. Signature Methods 413 To fully describe a LM-OTS signature method, the parameters n and w, 414 as well as the function H, MUST be specified. This section defines 415 several LM-OTS signature systems, each of which is identified by a 416 name. Values for p and ls are provided as a convenience. 418 +---------------------+-----------+----+---+-----+----+ 419 | Name | H | n | w | p | ls | 420 +---------------------+-----------+----+---+-----+----+ 421 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 422 | | | | | | | 423 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 424 | | | | | | | 425 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 426 | | | | | | | 427 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 428 | | | | | | | 429 | LMOTS_SHA256_N16_W1 | SHA256-16 | 16 | 1 | 68 | 8 | 430 | | | | | | | 431 | LMOTS_SHA256_N16_W2 | SHA256-16 | 16 | 2 | 68 | 8 | 432 | | | | | | | 433 | LMOTS_SHA256_N16_W4 | SHA256-16 | 16 | 4 | 35 | 4 | 434 | | | | | | | 435 | LMOTS_SHA256_N16_W8 | SHA256-16 | 16 | 8 | 18 | 0 | 436 +---------------------+-----------+----+---+-----+----+ 438 Table 1 440 Here SHA256 denotes the NIST standard hash function [FIPS180]. 441 SHA256-16 denotes the SHA256 hash function with its final output 442 truncated to return the leftmost 16 bytes. 444 4.4. Private Key 446 The LM-OTS private key consists of an array of size p containing 447 n-byte strings. Let x denote the private key. This private key must 448 be used to sign one and only one message. It must therefore be 449 unique from all other private keys. The following algorithm shows 450 pseudocode for generating x. 452 Algorithm 0: Generating a Private Key 454 set type to the typecode of the algorithm 455 set n and p according to the typecode and Table 1 456 for ( i = 0; i < p; i = i + 1 ) { 457 set x[i] to a uniformly random n-byte string 458 } 459 return u32str(type) || x[0] || x[1] || ... || x[p-1] 461 An implementation MAY use a pseudorandom method to compute x[i], as 462 suggested in [Merkle79], page 46. The details of the pseudorandom 463 method do not affect interoperability, but the cryptographic strength 464 MUST match that of the LM-OTS algorithm. 466 4.5. Public Key 468 The LM-OTS public key is generated from the private key by 469 iteratively applying the function H to each individual element of x, 470 for 2^w - 1 iterations, then hashing all of the resulting values. 472 Each public/private key pair is associated with a single identifier 473 I. This string MUST be 31 bytes long, and be generated as described 474 in Section 3.2. It MUST be generated by a uniform random or 475 pseudorandom process during the LM-OTS key pair generation, unless a 476 structured identifier is provided as an input to the algorithm. 478 The diversification parameter q is an input to the algorithm, as 479 described in Section 3.2. (In the LMS scheme, this parameter is set 480 to the leaf number, as each LM-OTS key pair is associated with the 481 leaf of a tree.) 483 The following algorithm shows pseudocode for generating the public 484 key, where the array x is the private key. 486 Algorithm 1: Generating a Public Key From a Private Key 488 set type to the typecode of the algorithm 489 set n and p according to the typecode and Table 1 490 for ( i = 0; i < p; i = i + 1 ) { 491 tmp = x[i] 492 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 493 tmp = H(tmp || I || q || u16str(i) || u8str(j) || D_ITER) 494 } 495 y[i] = tmp 496 } 497 return H(I || q || y[0] || y[1] || ... || y[p-1] || D_PBLC) 499 The public key the value returned by Algorithm 1. 501 4.6. Checksum 503 A checksum is used to ensure that any forgery attempt that 504 manipulates the elements of an existing signature will be detected. 505 The security property that it provides is detailed in Section 11. 506 The checksum function Cksm is defined as follows, where S denotes the 507 byte string that is input to that function, and the value sum is a 508 16-bit unsigned integer: 510 Algorithm 2: Checksum Calculation 512 sum = 0 513 for ( i = 0; i < u; i = i + 1 ) { 514 sum = sum + (2^w - 1) - coef(S, i, w) 515 } 516 return (sum << ls) 518 Because of the left-shift operation, the rightmost bits of the result 519 of Cksm will often be zeros. Due to the value of p, these bits will 520 not be used during signature generation or verification. 522 4.7. Signature Generation 524 The LM-OTS signature of a message is generated by first appending the 525 randomizer C, the identifier string I, the diversification string q, 526 and D_MESG to the message, then using H to compute the hash of the 527 resulting string, concatenating the checksum of the hash to the hash 528 itself, then considering the resulting value as a sequence of w-bit 529 values, and using each of the the w-bit values to determine the 530 number of times to apply the function H to the corresponding element 531 of the private key. The outputs of the function H are concatenated 532 together and returned as the signature. The pseudocode for this 533 procedure is shown below. 535 The identifier string I and diversification string q are the same as 536 in Section 4.5. 538 Algorithm 3: Generating a Signature From a Private Key and a Message 540 set type to the typecode of the algorithm 541 set n and p according to the typecode and Table 1 542 set C to a uniformly random n-byte string 543 Q = H(C || I || q || D_MESG || message) 544 for ( i = 0; i < p; i = i + 1 ) { 545 a = coef(Q || Cksm(Q), i, w) 546 tmp = x[i] 547 for ( j = 0; j < a; j = j + 1 ) { 548 tmp = H(tmp || I || q || u16str(i) || u8str(j) || D_ITER) 549 } 550 y[i] = tmp 551 } 552 return u32str(type) || C || q || y[0] || y[1] || ... || y[p-1] 554 Note that this algorithm results in a signature whose elements are 555 intermediate values of the elements computed by the public key 556 algorithm in Section 4.5. 558 The signature is the string returned by Algorithm 3. Section 7 559 specifies the typecode and more formally defines the encoding and 560 decoding of the string. 562 4.8. Signature Verification 564 In order to verify a message with its signature (an array of n-byte 565 strings, denoted as y), the receiver must "complete" the series of 566 applications of H using the w-bit values of the message hash and its 567 checksum. This computation should result in a value that matches the 568 provided public key. 570 Algorithm 4: Verifying a Signature and Message Using a Public Key 572 if the signature is not at least four bytes long, return INVALID 574 set type by applying uint32str() to the first four bytes of the 575 signature 577 if the type computed from the signature is not equal to the 578 type of the public key, return INVALID 580 set n and p according to the type and Table 1 582 if the signature is not exactly 8 + n * (p+1) bytes long, return 583 INVALID 585 parse C, q, and y from the signature as follows: 586 type = first 4 bytes 587 C = next n bytes 588 q = next four bytes 589 y[0] = next n bytes 590 y[1] = next n bytes 591 ... 592 y[p-1] = next n bytes 593 Q = H(C || I || q || D_MESG || message) 594 for ( i = 0; i < p; i = i + 1 ) { 595 a = (2^w - 1) - coef(Q || Cksm(Q), i, w) 596 tmp = y[i] 597 for ( j = a+1; j < 2^w - 1; j = j + 1 ) { 598 tmp = H(tmp || I || q || u16str(i) || u8str(j) || D_ITER) 599 } 600 z[i] = tmp 601 } 602 candidate = H(I || q || z[0] || z[1] || ... || z[p-1] || D_PBLC) 603 if (candidate = public_key) 604 return VALID 605 else 606 return INVALID 608 5. Leighton Micali Signatures 610 The Leighton Micali Signature (LMS) method can sign a potentially 611 large but fixed number of messages. An LMS system uses two 612 cryptographic components: a one-time signature method and a hash 613 function. Each LMS public/private key pair is associated with a 614 perfect binary tree, each node of which contains an n-byte value. 615 Each leaf of the tree contains the value of the public key of an LM- 616 OTS public/private key pair. The value contained by the root of the 617 tree is the LMS public key. Each interior node is computed by 618 applying the hash function to the concatenation of the values of its 619 children nodes. 621 An LMS system has the following parameters: 623 h : the height (number of levels - 1) in the tree, and 625 n : the number of bytes associated with each node. 627 There are 2^h leaves in the tree. 629 5.1. LMS Private Key 631 An LMS private key consists of 2^h one-time signature private keys 632 and the leaf number of the next LM-OTS private key that has not yet 633 been used. The leaf number is initialized to zero when the LMS 634 private key is created. 636 An LMS private key MAY be generated pseudorandomly from a secret 637 value, in which case the secret value MUST be at least n bytes long, 638 be uniformly random, and MUST NOT be used for any other purpose than 639 the generation of the LMS private key. The details of how this 640 process is done do not affect interoperability; that is, the public 641 key verification operation is independent of these details. 643 5.2. LMS Public Key 645 An LMS public key is defined as follows, where we denote the public 646 key associated with the i^th LM-OTS private key as OTS_PUBKEY[i], 647 with i ranging from 0 to (2^h)-1. Each instance of an LMS public/ 648 private key pair is associated with a perfect binary tree, and the 649 nodes of that tree are indexed from 1 to 2^(h+1)-1. Each node is 650 associated with an n-byte string, and the string for the rth node is 651 denoted as T[r] and is defined as 653 T[r] = / H(OTS_PUBKEY[r-2^h] || I || u32str(r) || D_LEAF) if r >= 2^h 654 \ H(T[2*r] || T[2*r+1] || I || u32str(r) || D_INTR) otherwise. 656 The LMS public key is the string u32str(type) || I || T[1]. 657 Section 7 specifies the typecode and more formally defines the 658 format. The value T[1] can be computed via recursive application of 659 the above equation, or by any equivalent method. An iterative 660 procedure is outlined in Appendix B. 662 5.3. LMS Signature 664 An LMS signature consists of 666 a typecode indicating the particular LMS algorithm, 668 an LM-OTS signature, and 670 an array of values that is associated with the path through the 671 tree from the leaf associated with the LM-OTS signature to the 672 root. 674 Symbolically, the signature can be represented as u32str(type) || 675 lmots_signature || path[0] || path[1] || ... || path[p-1]. Section 7 676 specifies the typecode and more formally defines the format. The 677 array of values contains the siblings of the nodes on the path from 678 the leaf to the root but does not contain the nodes on the path 679 itself. The array for a tree with height h will have h values. The 680 first value is the sibling of the leaf, the next value is the sibling 681 of the parent of the leaf, and so on up the path to the root. 683 5.3.1. LMS Signature Generation 685 To compute the LMS signature of a message with an LMS private key, 686 the signer first computes the LM-OTS signature of the message using 687 the leaf number of the next unused LM-OTS private key. Before 688 releasing the signature, the leaf number in the LMS private key MUST 689 be incremented to prevent the LM-OTS private key from being used 690 again. The node number in the signature is set to the leaf number of 691 the LMS private key that was used in the signature. Then the 692 signature and the LMS private key are returned. 694 The array of node values in the signature MAY be computed in any way. 695 There are many potential time/storage tradeoffs that can be applied. 696 The fastest alternative is to store all of the nodes of the tree and 697 set the array in the signature by copying them. The least storage 698 intensive alternative is to recompute all of the nodes for each 699 signature. Note that the details of this procedure are not important 700 for interoperability; it is not necessary to know any of these 701 details in order to perform the signature verification operation. 702 The internal nodes of the tree need not be kept secret, and thus a 703 node-caching scheme that stores only internal nodes can sidestep the 704 need for strong protections. 706 One useful time/storage tradeoff is described in Column 19 of 707 [USPTO5432852]. 709 5.4. LMS Signature Verification 711 An LMS signature is verified by first using the LM-OTS signature 712 verification algorithm to compute the LM-OTS public key from the LM- 713 OTS signature and the message. The value of that public key is then 714 assigned to the associated leaf of the LMS tree, then the root of the 715 tree is computed from the leaf value and the node array (path[]) as 716 described below. If the root value matches the public key, then the 717 signature is valid; otherwise, the signature fails. 719 Algorithm 5: LMS Signature Verification 721 set pubtype by applying uint32str() to the first four bytes of the 722 public key 724 set sigtype by applying uint32str() to the first four bytes of the 725 signature 727 if pubtype is not equal to sigtype, return INVALID; otherwise, 728 continue 730 identify the height h of the tree from pubtype 732 parse q from the LM-OTS signature in the LMS signature 734 parse the path from the LMS signature 736 parse the LMS public key value from the lms_public_key 738 tmp = candidate public key computed from LM-OTS signature and message 739 tmp = H(tmp || I || u32str(node_num) || D_LEAF) 740 i = 0 741 n = node number = 2^h + q 742 while (node_num > 1) { 743 if (node_num is odd): 744 tmp = H(path[i] || tmp || I || u32str(node_num/2) || D_INTR) 745 else: 746 tmp = H(tmp || path[i] || I || u32str(node_num/2) || D_INTR) 747 node_num = node_num/2 748 i = i + 1 749 if (tmp == LMS public key vaule) 750 return 1 // message/signature pair is valid 751 else 752 return 0 // message/signature pair is invalid 754 Upon completion, v contains the value of the root of the LMS tree for 755 comparison. 757 The verifier MAY cache interior node values that have been computed 758 during a successful signature verification for use in subsequent 759 signature verifications. However, any implementation that does so 760 MUST make sure any nodes that are cached during a signature 761 verification process are deleted if that process does not result in a 762 successful match between the root of the tree and the LMS public key. 764 6. Hierarchical signatures 766 In scenarios where it is necessary to minimize the time taken by the 767 public key generation process, a hierarchical N-time signature scheme 768 can be used. Leighton and Micali describe a scheme in which an LMS 769 public key is used to sign a second LMS public key, which is then 770 distributed along with the signatures generated with the second 771 public key [USPTO5432852]. This hierarchical scheme, which we 772 describe in this section, uses an LMS scheme as a component. Each 773 level is associated with an LMS public key, private key, and 774 signature. The number of levels denoted L, and is between two and 775 eight, inclusive. The following notation is used, where i is an 776 integer between 1 and L inclusive: 778 prv[i] is the private key of the ith level, 780 pub[i] is the public key of the ith level, 782 sig[i] is the signature of the ith level, and 784 info[i] is lms_key_info, a structure containing information 785 describing the public key of the ith level, including the LMS 786 algorithm type, OTS algorithm type, and the Identifier I. 788 In this section, we say that an N-time private key is exhausted when 789 it has signed all N messages, and thus it can no longer be used for 790 signing. 792 6.1. Key Generation 794 To generate an HSS private and public key pair, new LMS private and 795 public keys are generated for prv[i] and pub[i] for i=1, ..., L. 796 These key pairs MUST be generated independently, and each key pair 797 MUST use a distinct Identity I. 799 The public key of the HSS scheme is pub[1], the public key of the 800 first level, followed by the lms_key_info structures for the 801 remaining levels. 803 The HSS private key consists of prv[1], ... , prv[L]. The values 804 pub[1] and prv[1] do not change, though the values of pub[i] and 805 prv[i] are dynamic for i > 1, and are changed by the signature 806 generation algorithm. 808 6.2. Signature Generation 810 To sign a message using the private key prv, the following steps are 811 performed: 813 The message is signed with prv[L], and the value sig[L] is set to 814 that result. 816 The value of the HSS signature is set to sig[1] || ... || sig[L]. 818 If prv[L] is exhausted, then the key pair associated with that 819 level is regenerated as follows. A new LMS public and private key 820 pair with the same algorithm parameters is generated, and pub[L] 821 and prv[L] are set to those values. pub[L] is signed with 822 prv[L-1], and sig[L-1] is set to the resulting value. If prv[L-1] 823 is exhausted, then the regeneration process is applied to that 824 key, and so on for L-1 up to 2. 826 6.3. Signature Verification 828 To verify a signature sig and message using the public key pub, the 829 following steps are performed: 831 The signature sig is parsed into its components sig[1] || ... || 832 sig[L]. 834 The signature sig[L] and message is verified using the public key 835 pub[L]. If verification fails, then an indication of failure is 836 returned. Otherwise, processing continues as follows. 838 The signature sig[L-1] of the "message" pub[L] is verified using 839 the public key pub[L-1]. If verification fails, then an 840 indication of failure is returned. Otherwise, this process is 841 repeated for all levels from L-1 down to 2. 843 The signature sig[1] of the "message" pub[2] is verified using the 844 value of the HSS public key. If verification fails, then an 845 indication of failure is returned. Otherwise, an indication of 846 success is returned. 848 7. Formats 850 The signature and public key formats are formally defined using the 851 External Data Representation (XDR) [RFC4506] in order to provide an 852 unambiguous, machine readable definition. For clarity, we also 853 include a private key format as well, though consistency is not 854 needed for interoperability and an implementation MAY use any private 855 key format. Though XDR is used, these formats are simple and easy to 856 parse without any special tools. An illustration of the layout of 857 data in these objects is provided below. The definitions are as 858 follows: 860 /* 861 * one-time signature primitives 862 */ 863 enum ots_algorithm_type { 864 ots_reserved = 0, 865 lmots_sha256_n16_w1 = 1, 866 lmots_sha256_n16_w2 = 2, 867 lmots_sha256_n16_w4 = 3, 868 lmots_sha256_n16_w8 = 4, 869 lmots_sha256_n32_w1 = 5, 870 lmots_sha256_n32_w2 = 6, 871 lmots_sha256_n32_w4 = 7, 872 lmots_sha256_n32_w8 = 8 873 }; 875 typedef opaque bytestring4[4]; 876 typedef opaque bytestring16[16]; 877 typedef opaque bytestring32[32]; 879 struct lmots_signature_n16_p265 { 880 bytestring16 C; 881 bytestring4 q; 882 bytestring16 y[265]; 883 }; 885 struct lmots_signature_n16_p133 { 886 bytestring16 C; 887 bytestring4 q; 888 bytestring16 y[133]; 889 }; 891 struct lmots_signature_n16_p67 { 892 bytestring16 C; 893 bytestring4 q; 894 bytestring16 y[67]; 896 }; 898 struct lmots_signature_n16_p34 { 899 bytestring16 C; 900 bytestring4 q; 901 bytestring16 y[34]; 902 }; 904 struct lmots_signature_n32_p265 { 905 bytestring32 C; 906 bytestring4 q; 907 bytestring32 y[265]; 908 }; 910 struct lmots_signature_n32_p133 { 911 bytestring32 C; 912 bytestring4 q; 913 bytestring32 y[133]; 914 }; 916 struct lmots_signature_n32_p67 { 917 bytestring32 C; 918 bytestring4 q; 919 bytestring32 y[67]; 920 }; 922 struct lmots_signature_n32_p34 { 923 bytestring32 C; 924 bytestring4 q; 925 bytestring32 y[34]; 926 }; 928 union ots_signature switch (ots_algorithm_type type) { 929 case lmots_sha256_n16_w1: 930 lmots_signature_n16_p256 sig_n16_p265; 931 case lmots_sha256_n16_w2: 932 lmots_signature_n16_p133 sig_n16_p133; 933 case lmots_sha256_n16_w4: 934 lmots_signature_n16_p67 sig_n16_p67; 935 case lmots_sha256_n16_w8: 936 lmots_signature_n16_p43 sig_n16_p34; 937 case lmots_sha256_n32_w1: 938 lmots_signature_n32_p256 sig_n32_p265; 939 case lmots_sha256_n32_w2: 940 lmots_signature_n32_p133 sig_n32_p133; 941 case lmots_sha256_n32_w4: 942 lmots_signature_n32_p67 sig_n32_p67; 943 case lmots_sha256_n32_w8: 945 lmots_signature_n32_p43 sig_n32_p34; 946 default: 947 void; /* error condition */ 948 }; 950 union ots_private_key switch (ots_algorithm_type type) { 951 case lmots_sha256_n16_w1: 952 case lmots_sha256_n16_w2: 953 case lmots_sha256_n16_w4: 954 case lmots_sha256_n16_w8: 955 bytestring16 x16; 956 case lmots_sha256_n32_w1: 957 case lmots_sha256_n32_w2: 958 case lmots_sha256_n32_w4: 959 case lmots_sha256_n32_w8: 960 bytestring32 x32; 961 default: 962 void; /* error condition */ 963 }; 965 /* leighton micali signature (lms) data types */ 967 enum lms_algorithm_type { 968 lms_reserved = 0, 969 lms_sha256_n32_h20 = 1, 970 lms_sha256_n32_h10 = 2, 971 lms_sha256_n32_h5 = 3, 972 lms_sha256_n16_h20 = 4, 973 lms_sha256_n16_h10 = 5, 974 lms_sha256_n16_h5 = 6 975 }; 977 union lms_path switch (lms_algorithm_type type) { 978 case lms_sha256_n32_h20: 979 bytestring32 path_n32_h20[20]; 980 case lms_sha256_n32_h10: 981 bytestring32 path_n32_h10[10]; 982 case lms_sha256_n32_h5: 983 bytestring32 path_n32_h5[5]; 984 case lms_sha256_n16_h20: 985 bytestring16 path_n16_h20[20]; 986 case lms_sha256_n16_h10: 987 bytestring16 path_n16_h10[10]; 988 case lms_sha256_n16_h5: 989 bytestring16 path_n16_h5[5]; 990 default: 991 void; /* error condition */ 992 }; 993 struct lms_signature { 994 ots_signature lmots_sig; 995 lms_path nodes; 996 }; 998 struct lms_key_n16 { 999 ots_algorithm_type ots_alg_type; 1000 opaque I[31]; 1001 opaque value[16]; 1002 }; 1004 struct lms_key_n32 { 1005 ots_algorithm_type ots_alg_type; 1006 opaque I[31]; 1007 opaque value[32]; 1008 }; 1010 union lms_public_key switch (lms_algorithm_type type) { 1011 case lms_sha256_n32_h20: 1012 case lms_sha256_n32_h10: 1013 case lms_sha256_n32_h5: 1014 lms_key_n32 z_n32; 1015 case lms_sha256_n16_h20: 1016 case lms_sha256_n16_h10: 1017 case lms_sha256_n16_h5: 1018 lms_key_n16 z_n16; 1019 default: 1020 void; /* error condition */ 1021 }; 1023 struct lms_key_info { 1024 lms_algorithm_type lms_alg_type; 1025 ots_algorithm_type ots_alg_type; 1026 opaque I[31]; 1027 }; 1029 union lms_private_key switch (lms_algorithm_type type) { 1030 case lms_sha256_n32_h20: 1031 case lms_sha256_n32_h10: 1032 case lms_sha256_n32_h5: 1033 lms_key_n32 z_n32; 1034 case lms_sha256_n16_h20: 1035 case lms_sha256_n16_h10: 1036 case lms_sha256_n16_h5: 1037 lms_key_n16 z_n16; 1038 default: 1039 void; /* error condition */ 1040 }; 1041 /* 1042 * hierarchical signature scheme (hss) 1043 */ 1045 struct hss_public_key { 1046 lms_public_key pub; 1047 lms_key_info info<7>; 1048 }; 1050 struct hss_private_key { 1051 lms_private_key pub<8>; 1052 }; 1054 struct hss_signature { 1055 lms_signature sig<8>; /* maximum of eight levels */ 1056 }; 1058 /* 1059 * hss_data_type and hss_data provide high level data types for all of 1060 * the objects that might need to be stored on a file system, as a 1061 * convenience to the implementer 1062 */ 1063 enum hss_data_type { 1064 reserved = 0, 1065 type_lms_public_key = 1, 1066 type_lms_private_key = 2, 1067 type_hss_public_key = 3, 1068 type_hss_private_key = 4, 1069 type_hss_signature = 5 1070 }; 1072 union hss_data switch (hss_data_type type) { 1073 case type_lms_public_key: 1074 lms_public_key lms_public_key_data; 1075 case type_lms_private_key: 1076 lms_private_key lms_private_key_data; 1077 case type_hss_public_key: 1078 hss_public_key hss_public_key_data; 1079 case type_hss_private_key: 1080 hss_private_key hss_private_key_data; 1081 case type_hss_signature: 1082 hss_signature hss_signature_data; 1083 default: 1084 void; 1085 }; 1087 Many of the objects start with a typecode. A verifier MUST check 1088 each of these typecodes, and a verification operation on a signature 1089 with an unknown type MUST return INVALID. The expected length of a 1090 variable-length object can be determined from its typecode, and if an 1091 object has a different length, then any signature computed from the 1092 object is INVALID. 1094 The layout of the data inside of public keys, signatures, and private 1095 keys is illustrated below, using the following notation. Each line 1096 describes a single object, and indentation is used to show that an 1097 object is contained in another object. Some of these objects do not 1098 appear explicitly in the data format, as they are merely logical 1099 groupings. Objects that do appear explicitly are indicated by an 1100 asterisk (*). The lengths of some objects is variable, and some 1101 object names are incomplete (because more than one name might 1102 appear), so this diagriam is meant as a conceptual aid only, and not 1103 a precise definition. 1105 hss_public_key 1106 * hss_algorithm_type 1107 lms_public_key 1108 * lms_algorithm_type 1109 lms_public_key_n 1110 * ots_algorithm_type 1111 * I 1112 * value 1113 lms_key_info 1114 * lms_algorithm_type 1115 * ots_algorithm_type 1116 * I 1118 hss_private_key 1119 * hss_algorithm_type 1120 lms_private_key 1121 * lms_algorithm_type 1122 lms_public_key_n 1123 * ots_algorithm_type 1124 * I 1125 * value 1126 lms_private_key 1127 * lms_algorithm_type 1128 lms_public_key_n 1129 * ots_algorithm_type 1130 * I 1131 * value 1133 hss_signature 1134 * hss_algorithm_type 1135 lms_public_key 1136 * lms_algorithm_type 1137 lms_key_n 1138 * ots_algorithm_type 1139 * I 1140 * value 1141 lms_signature 1142 ots_signature 1143 * ots_algorithm_type 1144 * C 1145 * q 1146 * y[p] 1147 lms_path 1148 * lms_algorithm_type 1149 * path[h] 1150 lms_signature 1151 ots_signature 1152 * ots_algorithm_type 1153 * C 1154 * q 1155 * y[p] 1156 lms_path 1157 * lms_algorithm_type 1158 * path[h] 1160 8. Rationale 1162 The goal of this note is to describe the LM-OTS and LMS algorithms 1163 following the original references and present the modern security 1164 analysis of those algorithms. Other signature methods are out of 1165 scope and may be interesting follow-on work. 1167 We adopt the techniques described by Leighton and Micali to mitigate 1168 attacks that amortize their work over multiple invocations of the 1169 hash function. 1171 The values taken by the identifier I across different LMS public/ 1172 private key pairs are required to be distinct in order to improve 1173 security. That distinctness ensures the uniqueness of the inputs to 1174 H across all of those public/private key pair instances, which is 1175 important for provable security in the random oracle model. The 1176 length of I is set at 31 bytes so that randomly chosen values of I 1177 will be distinct with probability at least 1 - 1/2^128 as long as 1178 there are 2^60 or fewer instances of LMS public/private key pairs. 1180 The sizes of the parameters in the security string are such that, for 1181 n=16, the LM-OTS iterates a 55-byte value (that is, the string that 1182 is input to H() during the iteration over j during signature 1183 generation and verification is 55 bytes long). Thus, when SHA-256 is 1184 used as the function H, only a single invocation of its compression 1185 function is needed. 1187 The signature and public key formats are designed so that they are 1188 easy to parse. Each format starts with a 32-bit enumeration value 1189 that indicates all of the details of the signature algorithm and 1190 hence defines all of the information that is needed in order to parse 1191 the format. 1193 The Checksum Section 4.6 is calculated using a non-negative integer 1194 "sum", whose width was chosen to be an integer number of w-bit fields 1195 such that it is capable of holding the difference of the total 1196 possible number of applications of the function H as defined in the 1197 signing algorithm of Section 4.7 and the total actual number. In the 1198 worst case (i.e. the actual number of times H is iteratively applied 1199 is 0), the sum is (2^w - 1) * ceil(8*n/w). Thus for the purposes of 1200 this document, which describes signature methods based on H = SHA256 1201 (n = 32 bytes) and w = { 1, 2, 4, 8 }, the sum variable is a 16-bit 1202 non-negative integer for all combinations of n and w. The 1203 calculation uses the parameter ls defined in Section 4.1 and 1204 calculated in Appendix A, which indicates the number of bits used in 1205 the left-shift operation. 1207 9. History 1209 This is the fourth version of this draft. It has the following 1210 changes from the previous version: 1212 In Algorithms 3 and 4, the message was moved from the initial 1213 position of the input to the function H to the final position, in 1214 the computation of the intermediate variable Q. This was done to 1215 improve security by preventing an an attacker that can find a 1216 collision in H from taking advantage of that fact via the forward 1217 chaining property of Merkle-Damgard. 1219 The Hierarchical Signature Scheme was generalized slightly so that 1220 it can use more than two levels. 1222 Several points of confusion were corrected; these had resulted 1223 from incomplete or inconsistent changes from the Merkle approach 1224 of the earlier draft to the Leighton-Micali approach. 1226 This section is to be removed by the RFC editor upon publication. 1228 10. IANA Considerations 1230 The Internet Assigned Numbers Authority (IANA) is requested to create 1231 two registries: one for OTS signatures, which includes all of the LM- 1232 OTS signatures as defined in Section 3, and one for Leighton-Micali 1233 Signatures, as defined in Section 4. Additions to these registries 1234 require that a specification be documented in an RFC or another 1235 permanent and readily available reference in sufficient detail that 1236 interoperability between independent implementations is possible. 1237 Each entry in the registry contains the following elements: 1239 a short name, such as "LMS_SHA256_n32_h10", 1241 a positive number, and 1243 a reference to a specification that completely defines the 1244 signature method test cases that can be used to verify the 1245 correctness of an implementation. 1247 Requests to add an entry to the registry MUST include the name and 1248 the reference. The number is assigned by IANA. These number 1249 assignments SHOULD use the smallest available palindromic number. 1250 Submitters SHOULD have their requests reviewed by the IRTF Crypto 1251 Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants 1252 that are unfamiliar with IANA processes should visit 1253 http://www.iana.org. 1255 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1256 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1257 are reserved for private use; no attempt will be made to prevent 1258 multiple sites from using the same value in different (and 1259 incompatible) ways [RFC2434]. 1261 The LM-OTS registry is as follows. 1263 +---------------------+-----------+--------------------+ 1264 | Name | Reference | Numeric Identifier | 1265 +---------------------+-----------+--------------------+ 1266 | LMOTS_SHA256_N16_W1 | Section 4 | 0x00000001 | 1267 | | | | 1268 | LMOTS_SHA256_N16_W2 | Section 4 | 0x00000002 | 1269 | | | | 1270 | LMOTS_SHA256_N16_W4 | Section 4 | 0x00000003 | 1271 | | | | 1272 | LMOTS_SHA256_N16_W8 | Section 4 | 0x00000004 | 1273 | | | | 1274 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000005 | 1275 | | | | 1276 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000006 | 1277 | | | | 1278 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000007 | 1279 | | | | 1280 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000008 | 1281 +---------------------+-----------+--------------------+ 1283 Table 2 1285 The LMS registry is as follows. 1287 +--------------------+-----------+--------------------+ 1288 | Name | Reference | Numeric Identifier | 1289 +--------------------+-----------+--------------------+ 1290 | LMS_SHA256_N32_H20 | Section 5 | 0x00000001 | 1291 | | | | 1292 | LMS_SHA256_N32_H10 | Section 5 | 0x00000002 | 1293 | | | | 1294 | LMS_SHA256_N32_H5 | Section 5 | 0x00000003 | 1295 | | | | 1296 | LMS_SHA256_N16_H20 | Section 5 | 0x00000004 | 1297 | | | | 1298 | LMS_SHA256_N16_H10 | Section 5 | 0x00000005 | 1299 | | | | 1300 | LMS_SHA256_N16_H5 | Section 5 | 0x00000006 | 1301 +--------------------+-----------+--------------------+ 1303 Table 3 1305 An IANA registration of a signature system does not constitute an 1306 endorsement of that system or its security. 1308 11. Security Considerations 1310 The security goal of a signature system is to prevent forgeries. A 1311 successful forgery occurs when an attacker who does not know the 1312 private key associated with a public key can find a message and 1313 signature that are valid with that public key (that is, the Signature 1314 Verification algorithm applied to that signature and message and 1315 public key will return "valid"). Such an attacker, in the strongest 1316 case, may have the ability to forge valid signatures for an arbitrary 1317 number of other messages. 1319 LM-OTS and LMS are provably secure in the random oracle model, as 1320 shown by Katz [Katz15]. From Theorem 8 of that reference: 1322 For any adversary attacking arbitrarily many instances of the one- 1323 time signature scheme, and making at most q hash queries, the 1324 probability with which the adversary is able to forge a signature 1325 with respect to any of the instances is at most q2^(1-8n). 1327 Here n is the number of bytes in the output of the hash function (as 1328 defined in Section 4.1). Thus, the security of the algorithms 1329 defined in this note can be roughly described as follows. For a 1330 security level of roughly 128 bits, assuming that there are no 1331 quantum computers, use n=16 by selecting an algorithm identifier with 1332 N16 in its name. For a security level of roughly 128 bits, assuming 1333 that there are quantum computers that can compute the input to an 1334 arbitrary function with computational cost equivalent to the square 1335 root of the size of the domain of that function [Grover96], use n=32 1336 by selecting an algorithm identifier with N32 in its name. 1338 11.1. Stateful signature algorithm 1340 The LMS signature system, like all N-time signature systems, requires 1341 that the signer maintain state across different invocations of the 1342 signing algorithm, to ensure that none of the component one-time 1343 signature systems are used more than once. This section calls out 1344 some important practical considerations around this statefulness. 1346 In a typical computing environment, a private key will be stored in 1347 non-volatile media such as on a hard drive. Before it is used to 1348 sign a message, it will be read into an application's Random Access 1349 Memory (RAM). After a signature is generated, the value of the 1350 private key will need to be updated by writing the new value of the 1351 private key into non-volatile storage. It is essential for security 1352 that the application ensure that this value is actually written into 1353 that storage, yet there may be one or more memory caches between it 1354 and the application. Memory caching is commonly done in the file 1355 system, and in a physical memory unit on the hard disk that is 1356 dedicated to that purpose. To ensure that the updated value is 1357 written to physical media, the application may need to take several 1358 special steps. In a POSIX environment, for instance,the O_SYNC flag 1359 (for the open() system call) will cause invocations of the write() 1360 system call to block the calling process until the data has been to 1361 the underlying hardware. However, if that hardware has its own 1362 memory cache, it must be separately dealt with using an operating 1363 system or device specific tool such as hdparm to flush the on-drive 1364 cache, or turn off write caching for that drive. Because these 1365 details vary across different operating systems and devices, this 1366 note does not attempt to provide complete guidance; instead, we call 1367 the implementer's attention to these issues. 1369 When hierarchical signatures are used, an easy way to minimize the 1370 private key synchronization issues is to have the private key for the 1371 second level resident in RAM only, and never write that value into 1372 non-volatile memory. A new second level public/private key pair will 1373 be generated whenever the application (re)starts; thus, failures such 1374 as a power outage or application crash are automatically 1375 accommodated. Implementations SHOULD use this approach wherever 1376 possible. 1378 11.2. Security of LM-OTS Checksum 1380 To show the security of LM-OTS checksum, we consider the signature y 1381 of a message with a private key x and let h = H(message) and 1382 c = Cksm(H(message)) (see Section 4.7). To attempt a forgery, an 1383 attacker may try to change the values of h and c. Let h' and c' 1384 denote the values used in the forgery attempt. If for some integer j 1385 in the range 0 to (u-1), inclusive, 1387 a' = coef(h', j, w), 1389 a = coef(h, j, w), and 1391 a' > a 1393 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1394 iteratively applying function F to the j^th term of the signature an 1395 additional (a' - a) times. However, as a result of the increased 1396 number of hashing iterations, the checksum value c' will decrease 1397 from its original value of c. Thus a valid signature's checksum will 1398 have, for some number k in the range u to (p-1), inclusive, 1400 b' = coef(c', k, w), 1402 b = coef(c, k, w), and 1403 b' < b 1405 Due to the one-way property of F, the attacker cannot easily compute 1406 F^b'(x[k]) from F^b(x[k]) = y[k]. 1408 12. Acknowledgements 1410 Thanks are due to Chirag Shroff, Andreas Hulsing, Burt Kaliski, Eric 1411 Osterweil, Ahmed Kosba, Russ Housley, and Scott Fluhrer for 1412 constructive suggestions and valuable detailed review. We esepcially 1413 acknowledge Jerry Solinas, Laurie Law, and Kevin Igoe, who pointed 1414 out the security benefits of the approach of Leighton and Micali 1415 [USPTO5432852] and Jonathan Katz, who gave us security guidance. 1417 13. References 1419 13.1. Normative References 1421 [FIPS180] National Institute of Standards and Technology, "Secure 1422 Hash Standard (SHS)", FIPS 180-4, March 2012. 1424 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1425 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 1426 RFC2119, March 1997, 1427 . 1429 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1430 IANA Considerations Section in RFCs", RFC 2434, 1431 DOI 10.17487/RFC2434, October 1998, 1432 . 1434 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1435 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, 1436 May 2006, . 1438 [USPTO5432852] 1439 Leighton, T. and S. Micali, "Large provably fast and 1440 secure digital signature schemes from secure hash 1441 functions", U.S. Patent 5,432,852, July 1995. 1443 13.2. Informative References 1445 [C:Merkle87] 1446 Merkle, R., "A Digital Signature Based on a Conventional 1447 Encryption Function", Lecture Notes in Computer 1448 Science crypto87vol, 1988. 1450 [C:Merkle89a] 1451 Merkle, R., "A Certified Digital Signature", Lecture Notes 1452 in Computer Science crypto89vol, 1990. 1454 [C:Merkle89b] 1455 Merkle, R., "One Way Hash Functions and DES", Lecture 1456 Notes in Computer Science crypto89vol, 1990. 1458 [Grover96] 1459 Grover, L., "A fast quantum mechanical algorithm for 1460 database search", 28th ACM Symposium on the Theory of 1461 Computing p. 212, 1996. 1463 [Katz15] Katz, J., "Analysis of a proposed hash-based signature 1464 standard", Contribution to 1465 IRTF http://www.cs.umd.edu/~jkatz/papers/ 1466 HashBasedSigs.pdf, 2015. 1468 [Merkle79] 1469 Merkle, R., "Secrecy, Authentication, and Public Key 1470 Systems", Stanford University Information Systems 1471 Laboratory Technical Report 1979-1, 1979. 1473 Appendix A. LM-OTS Parameter Options 1475 A table illustrating various combinations of n and w with the 1476 associated values of u, v, ls, and p is provided in Table 4. 1478 The parameters u, v, ls, and p are computed as follows: 1480 u = ceil(8*n/w) 1481 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1482 ls = (number of bits in sum) - (v * w) 1483 p = u + v 1485 Here u and v represent the number of w-bit fields required to contain 1486 the hash of the message and the checksum byte strings, respectively. 1487 The "number of bits in sum" is defined according to Section 4.6. And 1488 as the value of p is the number of w-bit elements of ( H(message) || 1489 Cksm(H(message)) ), it is also equivalently the number of byte 1490 strings that form the private key and the number of byte strings in 1491 the signature. 1493 +---------+------------+-----------+-----------+-------+------------+ 1494 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1495 | Length | Parameter | Elements | Elements | Shift | Number of | 1496 | in | (w) | in Hash | in | (ls) | w-bit | 1497 | Bytes | | (u) | Checksum | | Elements | 1498 | (n) | | | (v) | | (p) | 1499 +---------+------------+-----------+-----------+-------+------------+ 1500 | 16 | 1 | 128 | 8 | 8 | 137 | 1501 | | | | | | | 1502 | 16 | 2 | 64 | 4 | 8 | 68 | 1503 | | | | | | | 1504 | 16 | 4 | 32 | 3 | 4 | 35 | 1505 | | | | | | | 1506 | 16 | 8 | 16 | 2 | 0 | 18 | 1507 | | | | | | | 1508 | 32 | 1 | 256 | 9 | 7 | 265 | 1509 | | | | | | | 1510 | 32 | 2 | 128 | 5 | 6 | 133 | 1511 | | | | | | | 1512 | 32 | 4 | 64 | 3 | 4 | 67 | 1513 | | | | | | | 1514 | 32 | 8 | 32 | 2 | 0 | 34 | 1515 +---------+------------+-----------+-----------+-------+------------+ 1517 Table 4 1519 Appendix B. An iterative algorithm for computing an LMS public key 1521 The LMS public key can be computed using the following algorithm or 1522 any equivalent method. The algorithm uses a stack of hashes for data 1523 and a separate stack of integers to keep track of the level of the 1524 tree. It also makes use of a hash function with the typical init/ 1525 update/final interface to hash functions; the result of the 1526 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 1527 hash_update(N[n]), v = hash_final(), in that order, is identical to 1528 that of the invocation of H(N[1] || N[2] || ... || N[n]). 1530 Generating an LMS Public Key From an LMS Private Key 1532 for ( i = 0; i < num_lmots_keys; i = i + 2 ) { 1533 level = 0; 1534 for ( j = 0; j < 2; j = j + 1 ) { 1535 r = node number 1536 push H(OTS_PUBKEY[i+j] || I || u32str(r) || D_LEAF) onto data stack 1537 push level onto the integer stack 1538 } 1539 while ( height of the integer stack >= 2 ) { 1540 if level of the top 2 elements on the integer stack are equal { 1541 hash_init() 1542 siblings = "" 1543 repeat ( 2 ) { 1544 siblings = (pop(data stack) || siblings) 1545 level = pop(integer stack) 1546 } 1547 hash_update(siblings) 1548 r = node number 1549 hash_update(I || u32str(r) || D_INTR) 1550 push hash_final() onto the data stack 1551 push (level + 1) onto the integer stack 1552 } 1553 } 1554 } 1555 public_key = pop(data stack) 1557 Note that this pseudocode expects that all 2^h leaves of the tree 1558 have equal depth. Neither stack ever contains more than h+1 1559 elements. For typical parameters, these stacks will hold around 512 1560 bytes of data. 1562 Appendix C. Example implementation 1564 --- Pending Revision --- 1566 Authors' Addresses 1568 David McGrew 1569 Cisco Systems 1570 13600 Dulles Technology Drive 1571 Herndon, VA 20171 1572 USA 1574 Email: mcgrew@cisco.com 1576 Michael Curcio 1577 Cisco Systems 1578 7025-2 Kit Creek Road 1579 Research Triangle Park, NC 27709-4987 1580 USA 1582 Email: micurcio@cisco.com