idnits 2.17.1 draft-mcgrew-hash-sigs-03.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 31 instances of too long lines in the document, the longest one being 272 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 19, 2015) is 3112 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 689 -- Looks like a reference, but probably isn't: '1' on line 1345 -- Looks like a reference, but probably isn't: '16' on line 884 -- Looks like a reference, but probably isn't: '32' on line 614 -- Looks like a reference, but probably isn't: '265' on line 626 -- Looks like a reference, but probably isn't: '133' on line 628 -- Looks like a reference, but probably isn't: '67' on line 630 -- Looks like a reference, but probably isn't: '34' on line 632 -- Looks like a reference, but probably isn't: '264' on line 701 -- Looks like a reference, but probably isn't: '20' on line 868 -- Looks like a reference, but probably isn't: '10' on line 870 -- Looks like a reference, but probably isn't: '5' on line 872 -- Looks like a reference, but probably isn't: '64' on line 889 -- Looks like a reference, but probably isn't: '31' on line 890 -- Looks like a reference, but probably isn't: '2' on line 1345 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 17 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: April 21, 2016 October 19, 2015 7 Hash-Based Signatures 8 draft-mcgrew-hash-sigs-03 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 April 21, 2016. 41 Copyright Notice 43 Copyright (c) 2015 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 . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 60 2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 4 61 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 4 63 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 5 64 3.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 5 65 3.2. Security string . . . . . . . . . . . . . . . . . . . . . 6 66 3.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 8 67 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 8 68 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 8 69 4.2. Hashing Functions . . . . . . . . . . . . . . . . . . . . 9 70 4.3. Signature Methods . . . . . . . . . . . . . . . . . . . . 9 71 4.4. Private Key . . . . . . . . . . . . . . . . . . . . . . . 10 72 4.5. Public Key . . . . . . . . . . . . . . . . . . . . . . . 10 73 4.6. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 11 74 4.7. Signature Generation . . . . . . . . . . . . . . . . . . 11 75 4.8. Signature Verification . . . . . . . . . . . . . . . . . 12 76 4.9. Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 13 77 4.10. Formats . . . . . . . . . . . . . . . . . . . . . . . . . 13 78 5. Leighton Micali Signatures . . . . . . . . . . . . . . . . . 16 79 5.1. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 16 80 5.2. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 17 81 5.3. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 17 82 5.3.1. LMS Signature Generation . . . . . . . . . . . . . . 18 83 5.4. LMS Signature Verification . . . . . . . . . . . . . . . 18 84 5.5. LMS Formats . . . . . . . . . . . . . . . . . . . . . . . 19 85 6. Hierarchical signatures . . . . . . . . . . . . . . . . . . . 21 86 6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 21 87 6.2. Signature Generation . . . . . . . . . . . . . . . . . . 21 88 6.3. Signature Verification . . . . . . . . . . . . . . . . . 22 89 7. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 22 90 8. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 91 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 92 10. Security Considerations . . . . . . . . . . . . . . . . . . . 26 93 10.1. Stateful signature algorithm . . . . . . . . . . . . . . 26 94 10.2. Security of LM-OTS Checksum . . . . . . . . . . . . . . 27 95 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 96 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 28 97 12.1. Normative References . . . . . . . . . . . . . . . . . . 28 98 12.2. Informative References . . . . . . . . . . . . . . . . . 28 99 Appendix A. LM-OTS Parameter Options . . . . . . . . . . . . . . 29 100 Appendix B. An iterative algorithm for computing an LMS public 101 key . . . . . . . . . . . . . . . . . . . . . . . . 30 102 Appendix C. Example implementation . . . . . . . . . . . . . . . 31 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 42 105 1. Introduction 107 One-time signature systems, and general purpose signature systems 108 built out of one-time signature systems, have been known since 1979 109 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 110 benefited from renewed attention in the last decade. The 111 characteristics of these signature systems are small private and 112 public keys and fast signature generation and verification, but large 113 signatures and relatively slow key generation. In recent years there 114 has been interest in these systems because of their post-quantum 115 security and their suitability for compact implementations. 117 This note describes the Leighton and Micali adaptation [USPTO5432852] 118 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 119 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 120 signature system [Merkle79] with enough specificity to ensure 121 interoperability between implementations. An example implementation 122 is given in an appendix. 124 A signature system provides asymmetric message authentication. The 125 key generation algorithm produces a public/private key pair. A 126 message is signed by a private key, producing a signature, and a 127 message/signature pair can be verified by a public key. A One-Time 128 Signature (OTS) system can be used to sign exactly one message 129 securely, but cannot securely sign more than one. An N-time 130 signature system can be used to sign N or fewer messages securely. A 131 Merkle tree signature scheme is an N-time signature system that uses 132 an OTS system as a component. In this note we describe the Leighton- 133 Micali Signature (LMS) system, which is a variant of the Merkle 134 scheme. We denote the one-time signature scheme that it incorporates 135 as LM-OTS. 137 This note is structured as follows. Notation is introduced in 138 Section 3. The LM-OTS signature system is described in Section 4, 139 and the LMS N-time signature system is described in Section 5. 140 Sufficient detail is provided to ensure interoperability. The IANA 141 registry for these signature systems is described in Section 9. 142 Security considerations are presented in Section 10. 144 1.1. Conventions Used In This Document 146 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 147 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 148 document are to be interpreted as described in [RFC2119]. 150 2. Interface 152 The LMS signing algorithm is stateful; once a particular value of the 153 private key is used to sign one message, it MUST NOT be used to sign 154 another. To make this fact explicit in the interface, we use a 155 functional programming approach, in which the key generation, 156 signing, and verification algorithms do not have any side effects. 157 The signing algorithm returns both a signature and a different 158 private key value, which can be used to sign additional messages. 160 The key generation algorithm takes as input an indication of the 161 parameters for the signature system. If it is successful, it 162 returns both a private key and a public key. Otherwise, it 163 returns an indication of failure. 165 The signing algorithm takes as input the message to be signed and 166 the current value of the private key. If successful, it returns a 167 signature and the next value of the private key, if there is such 168 a value. After the private key of an N-time signature system has 169 signed N messages, the signing algorithm returns the signature and 170 an indication that there is no next value of the private key that 171 can be used for signing. If unsuccessful, it returns an 172 indication of failure. 174 The verification algorithm takes as input the public key, a 175 message, and a signature, and returns an indication of whether or 176 not the signature and message pair are valid. 178 A message/signature pair are valid if the signature was returned by 179 the signing algorithm upon input of the message and the private key 180 corresponding to the public key; otherwise, the signature and message 181 pair are not valid with probability very close to one. 183 3. Notation 185 3.1. Data Types 187 Bytes and byte strings are the fundamental data types. A single byte 188 is denoted as a pair of hexadecimal digits with a leading "0x". A 189 byte string is an ordered sequence of zero or more bytes and is 190 denoted as an ordered sequence of hexadecimal characters with a 191 leading "0x". For example, 0xe534f0 is a byte string with a length 192 of three. An array of byte strings is an ordered set, indexed 193 starting at zero, in which all strings have the same length. 195 Unsigned integers are converted into byte strings by representing 196 them in network byte order. To make the number of bytes in the 197 representation explicit, we define the functions uint8str(X), 198 uint16str(X), and uint32str(X), which return one, two, and four byte 199 values, respectively. 201 3.1.1. Operators 203 When a and b are real numbers, mathematical operators are defined as 204 follows: 206 ^ : a ^ b denotes the result of a raised to the power of b 208 * : a * b denotes the product of a multiplied by b 210 / : a / b denotes the quotient of a divided by b 212 % : a % b denotes the remainder of the integer division of a by b 214 + : a + b denotes the sum of a and b 216 - : a - b denotes the difference of a and b 218 The standard order of operations is used when evaluating arithmetic 219 expressions. 221 If A and B are bytes, then A AND B denotes the bitwise logical and 222 operation. 224 When B is a byte and i is an integer, then B >> i denotes the logical 225 right-shift operation. Similarly, B << i denotes the logical left- 226 shift operation. 228 If S and T are byte strings, then S || T denotes the concatenation of 229 S and T. 231 The i^th byte string in an array A is denoted as A[i]. 233 3.1.2. Strings of w-bit elements 235 If S is a byte string, then byte(S, i) denotes its i^th byte, where 236 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 237 the range of bytes from the i^th to the j^th byte, inclusive. For 238 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 239 2) is 0x0406. 241 A byte string can be considered to be a string of w-bit unsigned 242 integers; the correspondence is defined by the function coef(S, i, w) 243 as follows: 245 If S is a string, i is a positive integer, and w is a member of the 246 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 247 is interpreted as a sequence of w-bit values. That is, 249 coef(S, i, w) = (2^w - 1) AND 250 ( byte(S, floor(i * w / 8)) >> 251 (8 - (w * (i % (8 / w)) + w)) ) 253 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 254 coef(S, 0, 4) is 1. 256 S (represented as bits) 257 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 258 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 259 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 260 ^ 261 | 262 coef(S, 7, 1) 264 S (represented as four-bit values) 265 +-----------+-----------+-----------+-----------+ 266 | 1 | 2 | 3 | 4 | 267 +-----------+-----------+-----------+-----------+ 268 ^ 269 | 270 coef(S, 0, 4) 272 The return value of coef is an unsigned integer. If i is larger than 273 the number of w-bit values in S, then coef(S, i, w) is undefined, and 274 an attempt to compute that value should raise an error. 276 3.2. Security string 278 To improve security against attacks that amortize their effort 279 against multiple invocations of the hash function H, Leighton and 280 Micali introduce a "security string" that is distinct for each 281 invocation of H. The following fields can appear in a security 282 string: 284 I - an identifier for the private key. This value is 31 bytes 285 long, and it MUST be distinct from all other such identifiers. It 286 SHOULD be chosen uniformly at random, or via a pseudorandom 287 process, in order to ensure that it will be distinct with 288 probability close to one, but it MAY be a structured identifier. 290 D - a domain separation parameter, which is a single byte that 291 takes on different values in the different algorithms in which H 292 is invoked. D takes on the following values: 294 D_ITER = 0x00 in the iterations of the LM-OTS algorithms 296 D_PBLC = 0x01 when computing the hash of all of the iterates in 297 the LM-OTS algorithm 299 D_MESG = 0x02 when computing the hash of the message in the LM- 300 OTS algorithms 302 D_LEAF = 0x03 when computing the hash of the leaf of an LMS 303 tree 305 D_INTR = 0x04 when computing the hash of an interior node of an 306 LMS tree 308 C - an n-byte randomizer that is included with the message 309 whenever it is being hashed to improve security. C MUST be chosen 310 uniformly at random, or via a pseudorandom process. 312 i - in the LM-OTS one-time signature scheme, i is the index of the 313 private key element upon which H is being applied. It is 314 represented as a 16-bit (two byte) unsigned integer in network 315 byte order. 317 j - in the LM-OTS one-time signature scheme, j is the iteration 318 number used when the private key element is being iteratively 319 hashed. It is represented as an 8-bit (one byte) unsigned 320 integer. 322 q - in the LM-OTS one-time signature scheme, q is a 323 diversification string provided as input. In the LMS N-time 324 signature scheme, a distinct value of q is provided for each 325 distinct LM-OTS public/private keypair. It is represented as a 326 four byte string. 328 r - in the LMS N-time signature scheme, the node number r 329 associated with a particular node of the hash tree is used as an 330 input to the hash used to compute that node. This value is 331 represented as a 32-bit (four byte) unsigned integer in network 332 byte order. 334 3.3. Functions 336 If r is a non-negative real number, then we define the following 337 functions: 339 ceil(r) : returns the smallest integer larger than r 341 floor(r) : returns the largest integer smaller than r 343 lg(r) : returns the base-2 logarithm of r 345 4. LM-OTS One-Time Signatures 347 This section defines LM-OTS signatures. The signature is used to 348 validate the authenticity of a message by associating a secret 349 private key with a shared public key. These are one-time signatures; 350 each private key MUST be used only one time to sign any given 351 message. 353 As part of the signing process, a digest of the original message is 354 computed using the cryptographic hash function H (see Section 4.2), 355 and the resulting digest is signed. 357 In order to facilitate its use in an N-time signature system, the LM- 358 OTS key generation, signing, and verification algorithms all take as 359 input a diversification parameter q. When the LM-OTS signature 360 system is used outside of an N-time signature system, this value 361 SHOULD be set to the all-zero value. 363 4.1. Parameters 365 The signature system uses the parameters n and w, which are both 366 positive integers. The algorithm description also makes use of the 367 internal parameters p and ls, which are dependent on n and w. These 368 parameters are summarized as follows: 370 n : the number of bytes of the output of the hash function 372 w : the Winternitz parameter; it is a member of the set 373 { 1, 2, 4, 8 } 375 p : the number of n-byte string elements that make up the LM-OTS 376 signature 378 ls : the number of left-shift bits used in the checksum function 379 Cksm (defined in Section 4.6). 381 The value of n is determined by the functions selected for use as 382 part of the LM-OTS algorithm; the choice of this value has a strong 383 effect on the security of the system. The parameter w can be chosen 384 to set the number of bytes in the signature; it has little effect on 385 security. Note however, that there is a larger computational cost to 386 generate and verify a shorter signature. The values of p and ls are 387 dependent on the choices of the parameters n and w, as described in 388 Appendix A. A table illustrating various combinations of n, w, p, 389 and ls is provided in Table 1. 391 4.2. Hashing Functions 393 The LM-OTS algorithm uses a hash function H that accepts byte strings 394 of any length, and returns an n-byte string. 396 4.3. Signature Methods 398 To fully describe a LM-OTS signature method, the parameters n and w, 399 as well as the function H, MUST be specified. This section defines 400 several LM-OTS signature systems, each of which is identified by a 401 name. Values for p and ls are provided as a convenience. 403 +---------------------+-----------+----+---+-----+----+ 404 | Name | H | n | w | p | ls | 405 +---------------------+-----------+----+---+-----+----+ 406 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 407 | | | | | | | 408 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 409 | | | | | | | 410 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 411 | | | | | | | 412 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 413 | | | | | | | 414 | LMOTS_SHA256_N16_W1 | SHA256-16 | 16 | 1 | 68 | 8 | 415 | | | | | | | 416 | LMOTS_SHA256_N16_W2 | SHA256-16 | 16 | 2 | 68 | 8 | 417 | | | | | | | 418 | LMOTS_SHA256_N16_W4 | SHA256-16 | 16 | 4 | 35 | 4 | 419 | | | | | | | 420 | LMOTS_SHA256_N16_W8 | SHA256-16 | 16 | 8 | 18 | 0 | 421 +---------------------+-----------+----+---+-----+----+ 423 Table 1 425 Here SHA256 denotes the NIST standard hash function [FIPS180]. 426 SHA256-16 denotes the SHA256 hash function with its final output 427 truncated to return the leftmost 16 bytes. 429 4.4. Private Key 431 The LM-OTS private key consists of an array of size p containing 432 n-byte strings. Let x denote the private key. This private key must 433 be used to sign one and only one message. It must therefore be 434 unique from all other private keys. The following algorithm shows 435 pseudocode for generating x. 437 Algorithm 0: Generating a Private Key 439 for ( i = 0; i < p; i = i + 1 ) { 440 set x[i] to a uniformly random n-byte string 441 } 442 return x 444 An implementation MAY use a pseudorandom method to compute x[i], as 445 suggested in [Merkle79], page 46. The details of the pseudorandom 446 method do not affect interoperability, but the cryptographic strength 447 MUST match that of the LM-OTS algorithm. 449 4.5. Public Key 451 The LM-OTS public key is generated from the private key by 452 iteratively applying the function H to each individual element of x, 453 for 2^w - 1 iterations, then hashing all of the resulting values. 455 Each public/private key pair is associated with a single identifier 456 I. This string MUST be 31 bytes long, and be generated as described 457 in Section 3.2. 459 The diversification parameter q is an input to the algorithm, as 460 described in Section 3.2. 462 The following algorithm shows pseudocode for generating the public 463 key, where the array x is the private key. 465 Algorithm 1: Generating a Public Key From a Private Key 467 for ( i = 0; i < p; i = i + 1 ) { 468 tmp = x[i] 469 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 470 tmp = H(tmp || I || q || uint16str(i) || uint8str(j) || D_ITER) 471 } 472 y[i] = tmp 473 } 474 return H(I || q || y[0] || y[1] || ... || y[p-1] || D_PBLC) 476 The public key is the string consisting of a four-byte enumeration 477 that identifies the parameters in use, followed by the value returned 478 by Algorithm 1. Section 4.10 specifies the enumeration and more 479 formally defines the format. 481 4.6. Checksum 483 A checksum is used to ensure that any forgery attempt that 484 manipulates the elements of an existing signature will be detected. 485 The security property that it provides is detailed in Section 10. 486 The checksum function Cksm is defined as follows, where S denotes the 487 byte string that is input to that function, and the value sum is a 488 16-bit unsigned integer: 490 Algorithm 2: Checksum Calculation 492 sum = 0 493 for ( i = 0; i < u; i = i + 1 ) { 494 sum = sum + (2^w - 1) - coef(S, i, w) 495 } 496 return (sum << ls) 498 Because of the left-shift operation, the rightmost bits of the result 499 of Cksm will often be zeros. Due to the value of p, these bits will 500 not be used during signature generation or verification. 502 4.7. Signature Generation 504 The LM-OTS signature of a message is generated by first appending the 505 randomizer C, the identifier string I, and the diversification string 506 q to the message, then using H to compute the hash of the resulting 507 string, concatenating the checksum of the hash to the hash itself, 508 then considering the resulting value as a sequence of w-bit values, 509 and using each of the the w-bit values to determine the number of 510 times to apply the function H to the corresponding element of the 511 private key. The outputs of the function H are concatenated together 512 and returned as the signature. The pseudocode for this procedure is 513 shown below. 515 The identifier string I and diversification string q are the same as 516 in Section 4.5. 518 Algorithm 3: Generating a Signature From a Private Key and a Message 520 set C to a uniformly random n-byte string 521 set type to the appropriate ots_algorithm_type 522 Q = H(message || C || I || q || D_MESG) 523 for ( i = 0; i < p; i = i + 1 ) { 524 a = coef(Q || Cksm(Q), i, w) 525 tmp = x[i] 526 for ( j = 0; j < a; j = j + 1 ) { 527 tmp = H(tmp || I || q || uint16str(i) || uint8str(j) || D_ITER) 528 } 529 y[i] = tmp 530 } 531 return type || C || I || 0x00 || q || (y[0] || y[1] || ... || y[p-1]) 533 Note that this algorithm results in a signature whose elements are 534 intermediate values of the elements computed by the public key 535 algorithm in Section 4.5. 537 The signature is the string consisting of a four-byte enumeration 538 that identifies the parameters in use, followed by the value returned 539 by Algorithm 3. Section 4.10 specifies the enumeration and more 540 formally defines the format. 542 4.8. Signature Verification 544 In order to verify a message with its signature (an array of n-byte 545 strings, denoted as y), the receiver must "complete" the series of 546 applications of H using the w-bit values of the message hash and its 547 checksum. This computation should result in a value that matches the 548 provided public key. 550 Algorithm 4: Verifying a Signature and Message Using a Public Key 552 parse C, I, q, and y from the signature as follows: 553 type = first 4 bytes 554 C = next n bytes 555 I = next 31 bytes 556 NULL = next byte; this padding value is discarded 557 q = next four bytes 558 y[0] = next n bytes 559 y[1] = next n bytes 560 ... 561 y[p-1] = next n bytes 562 Q = H(message || C || I || q || D_MESG) 563 for ( i = 0; i < p; i = i + 1 ) { 564 a = (2^w - 1) - coef(Q || Cksm(Q), i, w) 565 tmp = y[i] 566 for ( j = a+1; j < 2^w - 1; j = j + 1 ) { 567 tmp = H(tmp || I || q || uint16str(i) || uint8str(j) || D_ITER) 568 } 569 z[i] = tmp 570 } 571 candidate = H(z[0] || z[1] || ... || z[p-1] || I || q || D_PBLC) 572 if (candidate = public_key) 573 return 1 // message/signature pair is valid 574 else 575 return 0 // message/signature pair is invalid 577 4.9. Notes 579 A future version of this specification may define a method for 580 computing the signature of a very short message in which the hash is 581 not applied to the message during the signature computation. That 582 would allow the signatures to have reduced size. 584 4.10. Formats 586 The signature and public key formats are formally defined using the 587 External Data Representation (XDR) [RFC4506] in order to provide an 588 unambiguous, machine readable definition. For clarity, we also 589 include a private key format as well, though consistency is not 590 needed for interoperability and an implementation MAY use any private 591 key format. Though XDR is used, these formats are simple and easy to 592 parse without any special tools. The definitions are as follows: 594 /* 595 * ots_algorithm_type identifies a particular signature algorithm 596 */ 598 enum ots_algorithm_type { 599 ots_reserved = 0, 600 lmots_sha256_m16_w1 = 0x00000001, 601 lmots_sha256_m16_w2 = 0x00000002, 602 lmots_sha256_m16_w4 = 0x00000003, 603 lmots_sha256_m16_w8 = 0x00000004, 604 lmots_sha256_n32_w1 = 0x00000005, 605 lmots_sha256_n32_w2 = 0x00000006, 606 lmots_sha256_n32_w4 = 0x00000007, 607 lmots_sha256_n32_w8 = 0x00000008 608 }; 610 /* 611 * byte strings (for n=16 and n=32) 612 */ 613 typedef opaque bytestring16[16]; 614 typedef opaque bytestring32[32]; 616 union ots_signature switch (ots_algorithm_type type) { 617 case lmots_sha256_n16_w1: 618 bytestring16 y_n16_p265[265]; 619 case lmots_sha256_n16_w2: 620 bytestring16 y_n16_p133[133]; 621 case lmots_sha256_n16_w4: 622 bytestring16 y_n16_p67[67]; 623 case lmots_sha256_n16_w8: 624 bytestring16 y_n16_p34[34]; 625 case lmots_sha256_n32_w1: 626 bytestring32 y_n32_p265[265]; 627 case lmots_sha256_n32_w2: 628 bytestring32 y_m3_p133[133]; 629 case lmots_sha256_n32_w4: 630 bytestring32 y_n32_y_p67[67]; 631 case lmots_sha256_n32_w8: 632 bytestring32 y_n32_p34[34]; 633 default: 634 void; /* error condition */ 635 }; 637 union ots_public_key switch (ots_algorithm_type type) { 638 case lmots_sha256_n16_w1: 639 case lmots_sha256_n16_w2: 640 case lmots_sha256_n16_w4: 641 case lmots_sha256_n16_w8: 642 case lmots_sha256_n32_w1: 643 case lmots_sha256_n32_w2: 644 case lmots_sha256_n32_w4: 645 case lmots_sha256_n32_w8: 647 bytestring32 y32; 648 default: 649 void; /* error condition */ 650 }; 652 union ots_private_key switch (ots_algorithm_type type) { 653 case lmots_sha256_m16_w1: 654 case lmots_sha256_m16_w2: 655 case lmots_sha256_m16_w4: 656 case lmots_sha256_m16_w8: 657 bytestring20 x20; 658 case lmots_sha256_n32_w1: 659 case lmots_sha256_n32_w2: 660 case lmots_sha256_n32_w4: 661 case lmots_sha256_n32_w8: 662 bytestring32 x32; 663 default: 664 void; /* error condition */ 665 }; 667 Though the data formats are formally defined by XDR, we include 668 diagrams as well as a convenience to the reader. An example of the 669 format of an lmots_signature is illustrated below, for 670 lmots_sha256_n32_w1. An ots_signature consists of a 32-bit unsigned 671 integer that indicates the ots_algorithm_type, followed by other 672 data, whose format depends only on the ots_algorithm_type. For LM- 673 OTS, that data is an array of equal-length byte strings. The number 674 of bytes in each byte string, and the number of elements in the 675 array, are determined by the ots_algorithm_type field. In the case 676 of lmots_sha256_n32_w1, the array has 265 elements, each of which is 677 a 32-byte string. The XDR array y_n32_p265 denotes the array y as 678 used in the algorithm descriptions above, using the parameters of 679 n=32 and p=265 for lmots_sha256_n32_w1. 681 A verifier MUST check the ots_algorithm_type field, and a 682 verification operation on a signature with an unknown 683 lmots_algorithm_type MUST return FAIL. 685 +---------------------------------+ 686 | ots_algorithm_type | 687 +---------------------------------+ 688 | | 689 | y_n32_p265[0] | 690 | | 691 +---------------------------------+ 692 | | 693 | y_n32_p265[1] | 694 | | 695 +---------------------------------+ 696 | | 697 ~ .... ~ 698 | | 699 +---------------------------------+ 700 | | 701 | y_n32_p265[264] | 702 | | 703 +---------------------------------+ 705 5. Leighton Micali Signatures 707 The Leighton Micali Signature (LMS) method can sign a potentially 708 large but fixed number of messages. An LMS system uses two 709 cryptographic components: a one-time signature method and a hash 710 function. Each LMS public/private key pair is associated with a 711 perfect binary tree, each node of which contains an n-byte value. 712 Each leaf of the tree contains the value of the public key of an LM- 713 OTS public/private key pair. The value contained by the root of the 714 tree is the LMS public key. Each interior node is computed by 715 applying the hash function to the concatenation of the values of its 716 children nodes. 718 An LMS system has the following parameters: 720 h : the height (number of levels - 1) in the tree, and 722 n : the number of bytes associated with each node. 724 There are 2^h leaves in the tree. 726 5.1. LMS Private Key 728 An LMS private key consists of 2^h one-time signature private keys 729 and the leaf number of the next LM-OTS private key that has not yet 730 been used. The leaf number is initialized to zero when the LMS 731 private key is created. 733 An LMS private key MAY be generated pseudorandomly from a secret 734 value, in which case the secret value MUST be at least n bytes long, 735 be uniformly random, and MUST NOT be used for any other purpose than 736 the generation of the LMS private key. The details of how this 737 process is done do not affect interoperability; that is, the public 738 key verification operation is independent of these details. 740 5.2. LMS Public Key 742 An LMS public key is defined as follows, where we denote the public 743 key associated with the i^th LM-OTS private key as OTS_PUBKEY[i], 744 with i ranging from 0 to (2^h)-1. Each instance of an LMS public/ 745 private key pair is associated with a perfect binary tree, and the 746 nodes of that tree are indexed from 1 to 2^(h+1)-1. Each node is 747 associated with an n-byte string, and the string for the rth node is 748 denoted as T[r] and is defined as 750 T[r] = / H(OTS_PUBKEY[r-2^h] || I || uint32str(r) || D_LEAF) if r >= 2^h 751 \ H(T[2*r] || T[2*r+1] || I || uint32str(r) || D_INTR) otherwise. 753 The LMS public key is the string consisting of a four-byte 754 enumeration that identifies the parameters in use, followed by the 755 string T[1]. Section 5.5 specifies the enumeration and more formally 756 defines the format. The value T[1] can be computed via recursive 757 application of the above equation, or by any equivalent method. An 758 iterative procedure is outlined in Appendix B. 760 5.3. LMS Signature 762 An LMS signature consists of 764 a typecode indicating the particular LMS algorithm, 766 an LM-OTS signature, and 768 an array of values that is associated with the path through the 769 tree from the leaf associated with the LM-OTS signature to the 770 root. 772 The array of values contains the siblings of the nodes on the path 773 from the leaf to the root but does not contain the nodes on the path 774 itself. The array for a tree with height h will have h values. The 775 first value is the sibling of the leaf, the next value is the sibling 776 of the parent of the leaf, and so on up the path to the root. 778 5.3.1. LMS Signature Generation 780 To compute the LMS signature of a message with an LMS private key, 781 the signer first computes the LM-OTS signature of the message using 782 the leaf number of the next unused LM-OTS private key. Before 783 releasing the signature, the leaf number in the LMS private key MUST 784 be incremented to prevent the LM-OTS private key from being used 785 again. The node number in the signature is set to the leaf number of 786 the LMS private key that was used in the signature. Then the 787 signature and the LMS private key are returned. 789 The array of node values in the signature MAY be computed in any way. 790 There are many potential time/storage tradeoffs that can be applied. 791 The fastest alternative is to store all of the nodes of the tree and 792 set the array in the signature by copying them. The least storage 793 intensive alternative is to recompute all of the nodes for each 794 signature. Note that the details of this procedure are not important 795 for interoperability; it is not necessary to know any of these 796 details in order to perform the signature verification operation. 797 The internal nodes of the tree need not be kept secret, and thus a 798 node-caching scheme that stores only internal nodes can sidestep the 799 need for strong protections. 801 One useful time/storage tradeoff is described in Column 19 of 802 [USPTO5432852]. 804 5.4. LMS Signature Verification 806 An LMS signature is verified by first using the LM-OTS signature 807 verification algorithm to compute the LM-OTS public key from the LM- 808 OTS signature and the message. The value of that public key is then 809 assigned to the associated leaf of the LMS tree, then the root of the 810 tree is computed from the leaf value and the node array (path[]) as 811 described below. If the root value matches the public key, then the 812 signature is valid; otherwise, the signature fails. 814 Algorithm 6: LMS Signature Verification 816 identify the height h of the tree from the algorithm type 817 determine the leaf number the LM-OTS q value to an integer 818 n = node number = 2^h + leaf_number 819 tmp = candidate public key computed from LM-OTS signature and message 820 tmp = H(tmp || I || uint32str(node_num) || D_LEAF) 821 i = 0 822 while (node_num > 1) { 823 if (node_num is odd): 824 tmp = H(path[i] || tmp || I || uint32str(node_num/2) || D_INTR) 825 else: 826 tmp = H(tmp || path[i] || I || uint32str(node_num/2) || D_INTR) 827 node_num = node_num/2 828 i = i + 1 829 if (tmp == lms_public_key) 830 return 1 // message/signature pair is valid 831 else 832 return 0 // message/signature pair is invalid 834 Upon completion, v contains the value of the root of the LMS tree for 835 comparison. 837 The verifier MAY cache interior node values that have been computed 838 during a successful signature verification for use in subsequent 839 signature verifications. However, any implementation that does so 840 MUST make sure any nodes that are cached during a signature 841 verification process are deleted if that process does not result in a 842 successful match between the root of the tree and the LMS public key. 844 5.5. LMS Formats 846 LMS signatures and public keys are defined using XDR syntax as 847 follows: 849 enum lms_algorithm_type { 850 lms_reserved = 0x00000000, 851 lms_sha256_n32_h20 = 0x00000001, 852 lms_sha256_n32_h10 = 0x00000002, 853 lms_sha256_n32_h5 = 0x00000003 854 lms_sha256_n16_h20 = 0x00000004, 855 lms_sha256_n16_h10 = 0x00000005, 856 lms_sha256_n16_h5 = 0x00000006 857 }; 859 union lms_path switch (lms_algorithm_type type) { 860 case lms_sha256_n32_h20: 861 bytestring32 path_n32_h20[20]; 863 case lms_sha256_n32_h10: 864 bytestring32 path_n32_h10[10]; 865 case lms_sha256_n32_h5: 866 bytestring32 path_n32_h5[5]; 867 case lms_sha256_n16_h20: 868 bytestring32 path_n16_h20[20]; 869 case lms_sha256_n16_h10: 870 bytestring32 path_n16_h10[10]; 871 case lms_sha256_n16_h5: 872 bytestring32 path_n16_h5[5]; 873 default: 874 void; /* error condition */ 875 }; 877 struct lms_signature { 878 ots_signature ots_sig; 879 lms_path nodes; 880 }; 882 struct lms_public_key_n16 { 883 ots_algorithm_type ots_alg_type; 884 opaque value[16]; /* public key */ 885 }; 887 struct lms_public_key_n64 { 888 ots_algorithm_type ots_alg_type; 889 opaque value[64]; /* public key */ 890 opaque I[31]; /* identity */ 891 }; 893 union lms_public_key switch (lms_algorithm_type type) { 894 case lms_sha256_n32_h20: 895 case lms_sha256_n32_h10: 896 case lms_sha256_n32_h5: 897 lms_public_key_n32 z_n32; 898 case lms_sha256_n16_h20: 899 case lms_sha256_n16_h10: 900 case lms_sha256_n16_h5: 901 lms_public_key_n16 z_n16; 902 default: 903 void; /* error condition */ 904 }; 906 6. Hierarchical signatures 908 In scenarios where it is necessary to minimize the time taken by the 909 public key generation process, a hierarchical N-time signature scheme 910 can be used. Leighton and Micali describe a scheme in which an LMS 911 public key is used to sign a second LMS public key, which is then 912 distributed along with the signatures generated with the second 913 public key [USPTO5432852]. This hierarchical scheme, which we 914 describe in this section, uses an LMS scheme as a component, and it 915 has two levels. Each level is associated with an LMS public key, 916 private key, and signature. The following notation is used, where i 917 is an integer between 1 and 2 inclusive: 919 prv[i] is the private key of the ith level, 921 pub[i] is the public key of the ith level, and 923 sig[i] is the signature of the ith level. 925 In this section, we say that an N-time private key is exhausted when 926 it has signed all N messages, and thus it can no longer be used for 927 signing. 929 6.1. Key Generation 931 To generate an HLMS private and public key pair, new LMS private and 932 public keys are generated for prv[i] and pub[i] for i=1,2. These key 933 pairs MUST be generated independently. 935 The public key of the HLMS scheme is pub[1], the public key of the 936 first level. The HLMS private key consists of prv[1] and prv[2]. 937 The values pub[1] and prv[1] do not change, though the values of 938 pub[2] and prv[2] are dynamic, and are changed by the signature 939 generation algorithm. 941 6.2. Signature Generation 943 To sign a message using the private key prv, the following steps are 944 performed: 946 The message is signed with prv[2], and the value sig[2] is set to 947 that result. 949 The value of the HLMS signature is set to type || pub[2] || 950 sig[1] || sig[2], where type is the typecode for the particular 951 HLMS algorithm. 953 If prv[2] is exhausted, then a new LMS public and private key pair 954 is generated, and pub[2] and prv[2] are set to those values. 955 pub[2] is signed with prv[1], and sig[1] is set to the resulting 956 value. 958 6.3. Signature Verification 960 To verify a signature sig and message using the public key pub, the 961 following steps are performed: 963 The signature sig is parsed into its components type, pub[2], 964 sig[1] and sig[2]. 966 The signature sig[2] and message is verified using the public key 967 pub[2]. If verification fails, then an indication of failure is 968 returned. Otherwise, processing continues as follows. 970 The signature sig[1] of the "message" pub[2] is verified using the 971 public key pub. If verification fails, then an indication of 972 failure is returned. Otherwise, an indication of success is 973 returned. 975 7. Rationale 977 The goal of this note is to describe the LM-OTS and LMS algorithms 978 following the original references and present the modern security 979 analysis of those algorithms. Other signature methods are out of 980 scope and may be interesting follow-on work. 982 We adopt the techniques described by Leighton and Micali to mitigate 983 attacks that amortize their work over multiple invocations of the 984 hash function. 986 The values taken by the identifier I across different LMS public/ 987 private key pairs are required to be distinct in order to improve 988 security. That distinctness ensures the uniqueness of the inputs to 989 H across all of those public/private key pair instances, which is 990 important for provable security in the random oracle model. The 991 length of I is set at 31 bytes so that randomly chosen values of I 992 will be distinct with probability at least 1 - 1/2^128 as long as 993 there are 2^60 or fewer instances of LMS public/private key pairs. 995 The sizes of the parameters in the security string are such that, for 996 n=16, the LM-OTS iterates a 55-byte value (that is, the string that 997 is input to H() during the iteration over j during signature 998 generation and verification is 55 bytes long). Thus, when SHA-256 is 999 used as the function H, only a single invocation of its compression 1000 function is needed. 1002 The signature and public key formats are designed so that they are 1003 easy to parse. Each format starts with a 32-bit enumeration value 1004 that indicates all of the details of the signature algorithm and 1005 hence defines all of the information that is needed in order to parse 1006 the format. 1008 The Checksum Section 4.6 is calculated using a non-negative integer 1009 "sum", whose width was chosen to be an integer number of w-bit fields 1010 such that it is capable of holding the difference of the total 1011 possible number of applications of the function H as defined in the 1012 signing algorithm of Section 4.7 and the total actual number. In the 1013 worst case (i.e. the actual number of times H is iteratively applied 1014 is 0), the sum is (2^w - 1) * ceil(8*n/w). Thus for the purposes of 1015 this document, which describes signature methods based on H = SHA256 1016 (n = 32 bytes) and w = { 1, 2, 4, 8 }, the sum variable is a 16-bit 1017 non-negative integer for all combinations of n and w. The 1018 calculation uses the parameter ls defined in Section 4.1 and 1019 calculated in Appendix A, which indicates the number of bits used in 1020 the left-shift operation. 1022 8. History 1024 This is the third version version of this draft. It has the 1025 following changes: 1027 It adopts the "security string" approach of Leighton and Micali 1028 [USPTO5432852] in order to improve security. 1030 It adopts Leighton and Micali's idea of hashing a randomizer 1031 string (C, as defined in Section 3.2) with the message, so that 1032 finding an arbitrary collision in H will not lead to a forgery. 1034 It defines a multi-level signature scheme, again following that 1035 described by Leighton and Micali. 1037 It eliminates the function F and its iterates; the function H is 1038 used in its stead. The adoption of the security string makes this 1039 simplification possible. 1041 It fixes the branching number at two for simplicity. 1043 This section is to be removed by the RFC editor upon publication. 1045 9. IANA Considerations 1047 The Internet Assigned Numbers Authority (IANA) is requested to create 1048 two registries: one for OTS signatures, which includes all of the LM- 1049 OTS signatures as defined in Section 3, and one for Leighton-Micali 1050 Signatures, as defined in Section 4. Additions to these registries 1051 require that a specification be documented in an RFC or another 1052 permanent and readily available reference in sufficient detail that 1053 interoperability between independent implementations is possible. 1054 Each entry in the registry contains the following elements: 1056 a short name, such as "LMS_SHA256_n32_h10", 1058 a positive number, and 1060 a reference to a specification that completely defines the 1061 signature method test cases that can be used to verify the 1062 correctness of an implementation. 1064 Requests to add an entry to the registry MUST include the name and 1065 the reference. The number is assigned by IANA. These number 1066 assignments SHOULD use the smallest available palindromic number. 1067 Submitters SHOULD have their requests reviewed by the IRTF Crypto 1068 Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants 1069 that are unfamiliar with IANA processes should visit 1070 http://www.iana.org. 1072 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1073 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1074 are reserved for private use; no attempt will be made to prevent 1075 multiple sites from using the same value in different (and 1076 incompatible) ways [RFC2434]. 1078 The LM-OTS registry is as follows. 1080 +----------------------+-----------+--------------------+ 1081 | Name | Reference | Numeric Identifier | 1082 +----------------------+-----------+--------------------+ 1083 | LMOTS_SHA256_N16_W1 | Section 4 | 0x00000001 | 1084 | | | | 1085 | LMOTS_SHA256_N16_W2 | Section 4 | 0x00000002 | 1086 | | | | 1087 | LMOTS_SHA256_N16_W4 | Section 4 | 0x00000003 | 1088 | | | | 1089 | LMOTS_SHA256_N16_W8 | Section 4 | 0x00000004 | 1090 | | | | 1091 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000005 | 1092 | | | | 1093 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000006 | 1094 | | | | 1095 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000007 | 1096 | | | | 1097 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000008 | 1098 +----------------------+-----------+--------------------+ 1100 Table 2 1102 The LMS registry is as follows. 1104 +--------------------+-----------+--------------------+ 1105 | Name | Reference | Numeric Identifier | 1106 +--------------------+-----------+--------------------+ 1107 | LMS_SHA256_N32_H20 | Section 5 | 0x00000001 | 1108 | | | | 1109 | LMS_SHA256_N32_H10 | Section 5 | 0x00000002 | 1110 | | | | 1111 | LMS_SHA256_N32_H5 | Section 5 | 0x00000003 | 1112 | | | | 1113 | LMS_SHA256_N16_H20 | Section 5 | 0x00000004 | 1114 | | | | 1115 | LMS_SHA256_N16_H10 | Section 5 | 0x00000005 | 1116 | | | | 1117 | LMS_SHA256_N16_H5 | Section 5 | 0x00000006 | 1118 +--------------------+-----------+--------------------+ 1120 Table 3 1122 An IANA registration of a signature system does not constitute an 1123 endorsement of that system or its security. 1125 10. Security Considerations 1127 The security goal of a signature system is to prevent forgeries. A 1128 successful forgery occurs when an attacker who does not know the 1129 private key associated with a public key can find a message and 1130 signature that are valid with that public key (that is, the Signature 1131 Verification algorithm applied to that signature and message and 1132 public key will return "valid"). Such an attacker, in the strongest 1133 case, may have the ability to forge valid signatures for an arbitrary 1134 number of other messages. 1136 LM-OTS and LMS are provably secure in the random oracle model, as 1137 shown by Katz [Katz15]. From Theorem 8 of that reference: 1139 For any adversary attacking arbitrarily many instances of the one- 1140 time signature scheme, and making at most q hash queries, the 1141 probability with which the adversary is able to forge a signature 1142 with respect to any of the instances is at most q2^(1-8n). 1144 Here n is the number of bytes in the output of the hash function (as 1145 defined in Section 4.1). Thus, the security of the algorithms 1146 defined in this note can be roughly described as follows. For a 1147 security level of roughly 128 bits, assuming that there are no 1148 quantum computers, use n=16 by selecting an algorithm identifier with 1149 N16 in its name. For a security level of roughly 128 bits, assuming 1150 that there are quantum computers that can compute the input to an 1151 arbitrary function with computational cost equivalent to the square 1152 root of the size of the domain of that function [Grover96], use n=32 1153 by selecting an algorithm identifier with N32 in its name. 1155 10.1. Stateful signature algorithm 1157 The LMS signature system, like all N-time signature systems, requires 1158 that the signer maintain state across different invocations of the 1159 signing algorithm, to ensure that none of the component one-time 1160 signature systems are used more than once. This section calls out 1161 some important practical considerations around this statefulness. 1163 In a typical computing environment, a private key will be stored in 1164 non-volatile media such as on a hard drive. Before it is used to 1165 sign a message, it will be read into an application's Random Access 1166 Memory (RAM). After a signature is generated, the value of the 1167 private key will need to be updated by writing the new value of the 1168 private key into non-volatile storage. It is essential for security 1169 that the application ensure that this value is actually written into 1170 that storage, yet there may be one or more memory caches between it 1171 and the application. Memory caching is commonly done in the file 1172 system, and in a physical memory unit on the hard disk that is 1173 dedicated to that purpose. To ensure that the updated value is 1174 written to physical media, the application may need to take several 1175 special steps. In a POSIX environment, for instance,the O_SYNC flag 1176 (for the open() system call) will cause invocations of the write() 1177 system call to block the calling process until the data has been to 1178 the underlying hardware. However, if that hardware has its own 1179 memory cache, it must be separately dealt with using an operating 1180 system or device specific tool such as hdparm to flush the on-drive 1181 cache, or turn off write caching for that drive. Because these 1182 details vary across different operating systems and devices, this 1183 note does not attempt to provide complete guidance; instead, we call 1184 the implementer's attention to these issues. 1186 When hierarchical signatures are used, an easy way to minimize the 1187 private key synchronization issues is to have the private key for the 1188 second level resident in RAM only, and never write that value into 1189 non-volatile memory. A new second level public/private key pair will 1190 be generated whenever the application (re)starts; thus, failures such 1191 as a power outage or application crash are automatically 1192 accommodated. Implementations SHOULD use this approach wherever 1193 possible. 1195 10.2. Security of LM-OTS Checksum 1197 To show the security of LM-OTS checksum, we consider the signature y 1198 of a message with a private key x and let h = H(message) and 1199 c = Cksm(H(message)) (see Section 4.7). To attempt a forgery, an 1200 attacker may try to change the values of h and c. Let h' and c' 1201 denote the values used in the forgery attempt. If for some integer j 1202 in the range 0 to (u-1), inclusive, 1204 a' = coef(h', j, w), 1206 a = coef(h, j, w), and 1208 a' > a 1210 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1211 iteratively applying function F to the j^th term of the signature an 1212 additional (a' - a) times. However, as a result of the increased 1213 number of hashing iterations, the checksum value c' will decrease 1214 from its original value of c. Thus a valid signature's checksum will 1215 have, for some number k in the range u to (p-1), inclusive, 1217 b' = coef(c', k, w), 1219 b = coef(c, k, w), and 1220 b' < b 1222 Due to the one-way property of F, the attacker cannot easily compute 1223 F^b'(x[k]) from F^b(x[k]) = y[k]. 1225 11. Acknowledgements 1227 Thanks are due to Chirag Shroff, Andreas Hulsing, Burt Kaliski, Eric 1228 Osterweil, Ahmed Kosba, Russ Housley, and Scott Fluhrer for 1229 constructive suggestions and valuable detailed review. We esepcially 1230 acknowledge Jerry Solinas, Laurie Law, and Kevin Igoe, who pointed 1231 out the security benefits of the approach of Leighton and Micali 1232 [USPTO5432852] and Jonathan Katz, who gave us security guidance. 1234 12. References 1236 12.1. Normative References 1238 [FIPS180] National Institute of Standards and Technology, "Secure 1239 Hash Standard (SHS)", FIPS 180-4, March 2012. 1241 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1242 Requirement Levels", BCP 14, RFC 2119, 1243 DOI 10.17487/RFC2119, March 1997, 1244 . 1246 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1247 IANA Considerations Section in RFCs", RFC 2434, 1248 DOI 10.17487/RFC2434, October 1998, 1249 . 1251 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1252 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1253 2006, . 1255 [USPTO5432852] 1256 Leighton, T. and S. Micali, "Large provably fast and 1257 secure digital signature schemes from secure hash 1258 functions", U.S. Patent 5,432,852, July 1995. 1260 12.2. Informative References 1262 [C:Merkle87] 1263 Merkle, R., "A Digital Signature Based on a Conventional 1264 Encryption Function", Lecture Notes in Computer 1265 Science crypto87vol, 1988. 1267 [C:Merkle89a] 1268 Merkle, R., "A Certified Digital Signature", Lecture Notes 1269 in Computer Science crypto89vol, 1990. 1271 [C:Merkle89b] 1272 Merkle, R., "One Way Hash Functions and DES", Lecture 1273 Notes in Computer Science crypto89vol, 1990. 1275 [Grover96] 1276 Grover, L., "A fast quantum mechanical algorithm for 1277 database search", 28th ACM Symposium on the Theory of 1278 Computing p. 212, 1996. 1280 [Katz15] Katz, J., "Analysis of a proposed hash-based signature 1281 standard", Contribution to IRTF 1282 http://www.cs.umd.edu/~jkatz/papers/HashBasedSigs.pdf, 1283 2015. 1285 [Merkle79] 1286 Merkle, R., "Secrecy, Authentication, and Public Key 1287 Systems", Stanford University Information Systems 1288 Laboratory Technical Report 1979-1, 1979. 1290 Appendix A. LM-OTS Parameter Options 1292 A table illustrating various combinations of n and w with the 1293 associated values of u, v, ls, and p is provided in Table 4. 1295 The parameters u, v, ls, and p are computed as follows: 1297 u = ceil(8*n/w) 1298 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1299 ls = (number of bits in sum) - (v * w) 1300 p = u + v 1302 Here u and v represent the number of w-bit fields required to contain 1303 the hash of the message and the checksum byte strings, respectively. 1304 The "number of bits in sum" is defined according to Section 4.6. And 1305 as the value of p is the number of w-bit elements of 1306 ( H(message) || Cksm(H(message)) ), it is also equivalently the 1307 number of byte strings that form the private key and the number of 1308 byte strings in the signature. 1310 +---------+------------+-----------+-----------+-------+------------+ 1311 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1312 | Length | Parameter | Elements | Elements | Shift | Number of | 1313 | in | (w) | in Hash | in | (ls) | w-bit | 1314 | Bytes | | (u) | Checksum | | Elements | 1315 | (n) | | | (v) | | (p) | 1316 +---------+------------+-----------+-----------+-------+------------+ 1317 | 16 | 1 | 128 | 8 | 8 | 137 | 1318 | | | | | | | 1319 | 16 | 2 | 64 | 4 | 8 | 68 | 1320 | | | | | | | 1321 | 16 | 4 | 32 | 3 | 4 | 35 | 1322 | | | | | | | 1323 | 16 | 8 | 16 | 2 | 0 | 18 | 1324 | | | | | | | 1325 | 32 | 1 | 256 | 9 | 7 | 265 | 1326 | | | | | | | 1327 | 32 | 2 | 128 | 5 | 6 | 133 | 1328 | | | | | | | 1329 | 32 | 4 | 64 | 3 | 4 | 67 | 1330 | | | | | | | 1331 | 32 | 8 | 32 | 2 | 0 | 34 | 1332 +---------+------------+-----------+-----------+-------+------------+ 1334 Table 4 1336 Appendix B. An iterative algorithm for computing an LMS public key 1338 The LMS public key can be computed using the following algorithm or 1339 any equivalent method. The algorithm uses a stack of hashes for data 1340 and a separate stack of integers to keep track of the level of the 1341 tree. It also makes use of a hash function with the typical 1342 init/update/final interface to hash functions; the result of the 1343 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 1344 hash_update(N[n]), v = hash_final(), in that order, is identical to 1345 that of the invocation of H(N[1] || N[2] || ... || N[n]). 1347 Generating an LMS Public Key From an LMS Private Key 1349 for ( i = 0; i < num_lmots_keys; i = i + 2 ) { 1350 level = 0; 1351 for ( j = 0; j < 2; j = j + 1 ) { 1352 r = node number 1353 push H(OTS_PUBKEY[i+j] || I || uint32str(r) || D_LEAF) onto data stack 1354 push level onto the integer stack 1355 } 1356 while ( height of the integer stack >= 2 ) { 1357 if level of the top 2 elements on the integer stack are equal { 1358 hash_init() 1359 siblings = "" 1360 repeat ( 2 ) { 1361 siblings = (pop(data stack) || siblings) 1362 level = pop(integer stack) 1363 } 1364 hash_update(siblings) 1365 r = node number 1366 hash_update(I || uint32str(r) || D_INTR) 1367 push hash_final() onto the data stack 1368 push (level + 1) onto the integer stack 1369 } 1370 } 1371 } 1372 public_key = pop(data stack) 1374 Note that this pseudocode expects that all 2^h leaves of the tree 1375 have equal depth. Neither stack ever contains more than h+1 1376 elements. For typical parameters, these stacks will hold around 512 1377 bytes of data. 1379 Appendix C. Example implementation 1381 # example implementation for Leighton-Micali hash based signatures 1382 # Internet draft 1383 # 1384 # Notes: 1385 # 1386 # * only a limted set of parameters are supported; in particular, 1387 # * w=8 and n=32 1388 # 1389 # * HLMS, LMS, and LM-OTS are all implemented 1390 # 1391 # * uncommenting print statements may be useful for debugging, or 1392 # for understanding the mechanics of 1393 # 1394 # 1395 # LMOTS constants 1396 # 1397 D_ITER = chr(0x00) # in the iterations of the LM-OTS algorithms 1398 D_PBLC = chr(0x01) # when computing the hash of all of the iterates in the LM-OTS algorithm 1399 D_MESG = chr(0x02) # when computing the hash of the message in the LMOTS algorithms 1400 D_LEAF = chr(0x03) # when computing the hash of the leaf of an LMS tree 1401 D_INTR = chr(0x04) # when computing the hash of an interior node of an LMS tree 1403 NULL = chr(0) # used as padding for encoding 1405 lmots_sha256_n32_w8 = 0x08000008 # typecode for LM-OTS with n=32, w=8 1406 lms_sha256_n32_h10 = 0x02000002 # typecode for LMS with n=32, h=10 1407 hlms_sha256_n32_l2 = 0x01000001 # typecode for two-level HLMS with n=32 1409 # LMOTS parameters 1410 # 1411 n = 32; p = 34; w = 8; ls = 0 1413 def bytes_in_lmots_sig(): 1414 return n*(p+1)+40 # 4 + n + 31 + 1 + 4 + n*p 1416 from Crypto.Hash import SHA256 1417 from Crypto import Random 1419 # SHA256 hash function 1420 # 1421 def H(x): 1422 # print "hash input: " + stringToHex(x) 1423 h = SHA256.new() 1424 h.update(x) 1425 return h.digest()[0:n] 1427 def sha256_iter(x, num): 1428 tmp = x 1429 for j in range(0, num): 1430 tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER) 1432 # entropy source 1433 # 1434 entropySource = Random.new() 1436 # integer to string conversion 1437 # 1438 def uint32ToString(x): 1439 c4 = chr(x & 0xff) 1440 x = x >> 8 1441 c3 = chr(x & 0xff) 1442 x = x >> 8 1443 c2 = chr(x & 0xff) 1444 x = x >> 8 1445 c1 = chr(x & 0xff) 1446 return c1 + c2 + c3 + c4 1448 def uint16ToString(x): 1449 c2 = chr(x & 0xff) 1450 x = x >> 8 1451 c1 = chr(x & 0xff) 1452 return c1 + c2 1454 def uint8ToString(x): 1455 return chr(x) 1457 def stringToUint(x): 1458 sum = 0 1459 for c in x: 1460 sum = sum * 256 + ord(c) 1461 return sum 1463 # string-to-hex function needed for debugging 1464 # 1465 def stringToHex(x): 1466 return "".join("{:02x}".format(ord(c)) for c in x) 1468 # LM-OTS functions 1469 # 1470 def encode_lmots_sig(C, I, q, y): 1471 result = uint32ToString(lmots_sha256_n32_w8) + C + I + NULL + q 1472 for i, e in enumerate(y): 1473 result = result + y[i] 1474 return result 1476 def decode_lmots_sig(sig): 1477 if (len(sig) != bytes_in_lmots_sig()): 1478 print "error decoding signature; incorrect length (" + str(len(sig)) + " bytes)" 1479 typecode = sig[0:4] 1480 if (typecode != uint32ToString(lmots_sha256_n32_w8)): 1481 print "error decoding signature; got typecode " + stringToHex(typecode) + ", expected: " + stringToHex(uint32ToString(lmots_sha256_n32_w8)) 1482 return "" 1483 C = sig[4:n+4] 1484 I = sig[n+4:n+35] 1485 q = sig[n+36:n+40] # note: skip over NULL 1486 y = list() 1487 pos = n+40 1488 for i in range(0, p): 1489 y.append(sig[pos:pos+n]) 1490 pos = pos + n 1491 return C, I, q, y 1493 def print_lmots_sig(sig): 1494 C, I, q, y = decode_lmots_sig(sig) 1495 print "C:\t" + stringToHex(C) 1496 print "I:\t" + stringToHex(I) 1497 print "q:\t" + stringToHex(q) 1498 for i, e in enumerate(y): 1499 print "y[" + str(i) + "]:\t" + stringToHex(e) 1501 # Algorithm 0: Generating a Private Key 1502 # 1503 def lmots_gen_priv(): 1504 priv = list() 1505 for i in range(0, p): 1506 priv.append(entropySource.read(n)) 1507 return priv 1509 # Algorithm 1: Generating a Public Key From a Private Key 1510 # 1511 def lmots_gen_pub(private_key, I, q): 1512 hash = SHA256.new() 1513 hash.update(I + q) 1514 for i, x in enumerate(private_key): 1515 tmp = x 1516 # print "i:" + str(i) + " range: " + str(range(0, 256)) 1517 for j in range(0, 256): 1518 tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER) 1519 hash.update(tmp) 1520 hash.update(D_PBLC) 1521 return hash.digest() 1523 # Algorithm 2: Merkle Checksum Calculation 1524 # 1525 def checksum(x): 1526 sum = 0 1527 for c in x: 1528 sum = sum + ord(c) 1529 # print format(sum, '04x') 1530 c1 = chr(sum >> 8) 1531 c2 = chr(sum & 0xff) 1532 return c1 + c2 1534 # Algorithm 3: Generating a Signature From a Private Key and a Message 1535 # 1536 def lmots_gen_sig(private_key, I, q, message): 1537 C = entropySource.read(n) 1538 hashQ = H(message + C + I + q + D_MESG) 1539 V = hashQ + checksum(hashQ) 1540 # print "V: " + stringToHex(V) 1541 y = list() 1542 for i, x in enumerate(private_key): 1543 tmp = x 1544 # print "i:" + str(i) + " range: " + str(range(0, ord(V[i]))) 1545 for j in range(0, ord(V[i])): 1546 tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER) 1547 y.append(tmp) 1548 return encode_lmots_sig(C, I, q, y) 1550 def lmots_sig_to_pub(sig, message): 1551 C, I, q, y = decode_lmots_sig(sig) 1552 hashQ = H(message + C + I + q + D_MESG) 1553 V = hashQ + checksum(hashQ) 1554 # print "V: " + stringToHex(V) 1555 hash = SHA256.new() 1556 hash.update(I + q) 1557 for i, y in enumerate(y): 1558 tmp = y 1559 # print "i:" + str(i) + " range: " + str(range(ord(V[i]), 256)) 1560 for j in range(ord(V[i]), 256): 1561 tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER) 1562 hash.update(tmp) 1563 hash.update(D_PBLC) 1564 return hash.digest() 1566 # Algorithm 4: Verifying a Signature and Message Using a Public Key 1567 # 1568 def lmots_verify_sig(public_key, sig, message): 1569 z = lmots_sig_to_pub(sig, message) 1570 # print "z: " + stringToHex(z) 1571 if z == public_key: 1572 return 1 1573 else: 1574 return 0 1576 # LM-OTS test functions 1577 # 1578 I = entropySource.read(31) 1579 q = uint32ToString(0) 1580 private_key = lmots_gen_priv() 1582 print "LMOTS private key: " 1583 for i, x in enumerate(private_key): 1584 print "x[" + str(i) + "]:\t" + stringToHex(x) 1586 public_key = lmots_gen_pub(private_key, I, q) 1588 print "LMOTS public key: " 1589 print stringToHex(public_key) 1591 message = "The right of the people to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures, shall not be violated, and no warrants shall issue, but upon probable cause, supported by oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized." 1593 print "message: " + message 1595 sig = lmots_gen_sig(private_key, I, q, message) 1597 print "LMOTS signature byte length: " + str(len(sig)) 1599 print "LMOTS signature: " 1600 print_lmots_sig(sig) 1602 print "verification: " 1603 print "true positive test: " 1604 if (lmots_verify_sig(public_key, sig, message) == 1): 1605 print "passed: message/signature pair is valid as expected" 1606 else: 1607 print "failed: message/signature pair is invalid" 1609 print "false positive test: " 1610 if (lmots_verify_sig(public_key, sig, "some other message") == 1): 1611 print "failed: message/signature pair is valid (expected failure)" 1612 else: 1613 print "passed: message/signature pair is invalid as expected" 1615 # LMS N-time signatures functions 1616 # 1617 h = 10 # height (number of levels -1) of tree 1619 def encode_lms_sig(lmots_sig, path): 1620 result = uint32ToString(lms_sha256_n32_h10) + lmots_sig 1621 for i, e in enumerate(path): 1622 result = result + path[i] 1623 return result 1625 def decode_lms_sig(sig): 1626 typecode = sig[0:4] 1627 if (typecode != uint32ToString(lms_sha256_n32_h10)): 1628 print "error decoding signature; got typecode " + stringToHex(typecode) + ", expected: " + stringToHex(uint32ToString(lms_sha256_h10)) 1629 return "" 1630 pos = 4 + bytes_in_lmots_sig() 1631 lmots_sig = sig[4:pos] 1632 path = list() 1633 for i in range(0,h): 1634 # print "sig[" + str(i) + "]:\t" + stringToHex(sig[pos:pos+n]) 1635 path.append(sig[pos:pos+n]) 1636 pos = pos + n 1637 return lmots_sig, path 1639 def print_lms_sig(sig): 1640 lmots_sig, path = decode_lms_sig(sig) 1641 print_lmots_sig(lmots_sig) 1642 for i, e in enumerate(path): 1643 print "path[" + str(i) + "]:\t" + str(stringToHex(e)) 1645 def bytes_in_lms_sig(): 1646 return bytes_in_lmots_sig() + h*n + 4 1648 class lms_private_key(object): 1650 # Algorithm for computing root and other nodes (alternative to Algorithm 6) 1651 # 1652 def T(self, j): 1653 # print "T(" + str(j) + ")" 1654 if (j >= 2**h): 1655 self.nodes[j] = H(self.pub[j - 2**h] + self.I + uint32ToString(j) + D_LEAF) 1656 return self.nodes[j] 1657 else: 1658 self.nodes[j] = H(self.T(2*j) + self.T(2*j+1) + self.I + uint32ToString(j) + D_INTR) 1659 return self.nodes[j] 1661 def __init__(self): 1662 self.I = entropySource.read(31) 1663 self.priv = list() 1664 self.pub = list() 1665 for q in range(0, 2**h): 1666 # print "generating " + str(q) + "th OTS key" 1667 ots_priv = lmots_gen_priv() 1668 ots_pub = lmots_gen_pub(ots_priv, self.I, uint32ToString(q)) 1669 self.priv.append(ots_priv) 1670 self.pub.append(ots_pub) 1671 self.leaf_num = 0 1672 self.nodes = {} 1673 self.lms_public_key = self.T(1) 1675 def num_sigs_remaining(): 1676 return 2**h - self.leaf_num 1678 def printHex(self): 1679 for i, p in enumerate(self.priv): 1681 print "priv[" + str(i) + "]:" 1682 for j, x in enumerate(p): 1683 print "x[" + str(j) + "]:\t" + stringToHex(x) 1684 print "pub[" + str(i) + "]:\t" + stringToHex(self.pub[i]) 1685 for t, T in self.nodes.items(): 1686 print "T(" + str(t) + "):\t" + stringToHex(T) 1687 print "pub: \t" + stringToHex(self.lms_public_key) 1689 def get_public_key(self): 1690 return self.lms_public_key 1692 def get_path(self, leaf_num): 1693 node_num = leaf_num + 2**h 1694 # print "signing node " + str(node_num) 1695 path = list() 1696 while node_num > 1: 1697 if (node_num % 2): 1698 # print "path" + str(node_num - 1) + ": " + stringToHex(self.nodes[node_num - 1]) 1699 path.append(self.nodes[node_num - 1]) 1700 else: 1701 # print "path " + str(node_num + 1) + ": " + stringToHex(self.nodes[node_num + 1]) 1702 path.append(self.nodes[node_num + 1]) 1703 node_num = node_num/2 1704 return path 1706 def sign(self, message): 1707 if (self.leaf_num >= 2**h): 1708 return "" 1709 sig = lmots_gen_sig(self.priv[self.leaf_num], self.I, uint32ToString(self.leaf_num), message) 1710 # C, I, q, y = decode_lmots_sig(sig) 1711 path = self.get_path(self.leaf_num) 1712 leaf_num = self.leaf_num 1713 self.leaf_num = self.leaf_num + 1 1714 return encode_lms_sig(sig, path) 1716 class lms_public_key(object): 1718 def __init__(self, value): 1719 self.value = value 1721 def verify(self, message, sig): 1722 lmots_sig, path = decode_lms_sig(sig) 1723 C, I, q, y = decode_lmots_sig(lmots_sig) # note: only q is actually needed here 1724 node_num = stringToUint(q) + 2**h 1725 # print "verifying node " + str(node_num) 1726 pathvalue = iter(path) 1727 tmp = lmots_sig_to_pub(lmots_sig, message) 1728 tmp = H(tmp + I + uint32ToString(node_num) + D_LEAF) 1729 while node_num > 1: 1730 # print "S(" + str(node_num) + "):\t" + stringToHex(tmp) 1731 if (node_num % 2): 1732 # print "adding node " + str(node_num - 1) 1733 tmp = H(pathvalue.next() + tmp + I + uint32ToString(node_num/2) + D_INTR) 1734 else: 1735 # print "adding node " + str(node_num + 1) 1736 tmp = H(tmp + pathvalue.next() + I + uint32ToString(node_num/2) + D_INTR) 1737 node_num = node_num/2 1738 # print "pubkey: " + stringToHex(tmp) 1739 if (tmp == self.value): 1740 return 1 1741 else: 1742 return 0 1744 # test LMS signatures 1745 # 1747 print "LMS test" 1749 lms_priv = lms_private_key() 1750 lms_pub = lms_public_key(lms_priv.get_public_key()) 1752 # lms_priv.printHex() 1754 for i in range(0, 2**h): 1755 sig = lms_priv.sign(message) 1757 print "LMS signature byte length: " + str(len(sig)) 1759 # print_lms_sig(sig) 1761 print "true positive test" 1762 if (lms_pub.verify(message, sig) == 1): 1763 print "passed: LMS message/signature pair is valid" 1764 else: 1765 print "failed: LMS message/signature pair is invalid" 1767 print "false positive test" 1768 if (lms_pub.verify("other message", sig) == 1): 1769 print "failed: LMS message/signature pair is valid (expected failure)" 1770 else: 1771 print "passed: LMS message/signature pair is invalid as expected" 1773 # Hierarchical LMS signatures (HLMS) 1775 def encode_hlms_sig(pub2, sig1, lms_sig): 1776 result = uint32ToString(hlms_sha256_n32_l2) 1777 result = result + pub2 1778 result = result + sig1 1779 result = result + lms_sig 1780 return result 1782 def decode_hlms_sig(sig): 1783 typecode = sig[0:4] 1784 if (typecode != uint32ToString(hlms_sha256_n32_l2)): 1785 print "error decoding signature; got typecode " + stringToHex(typecode) + ", expected: " + stringToHex(uint32ToString(hlms_sha256_n32_l2)) 1786 return "" 1787 pub2 = sig[4:36] 1788 lms_sig_len = bytes_in_lms_sig() 1789 sig1 = sig[36:36+lms_sig_len] 1790 lms_sig = sig[36+lms_sig_len:36+2*lms_sig_len] 1791 return pub2, sig1, lms_sig 1793 def print_hlms_sig(sig): 1794 pub2, sig1, lms_sig = decode_hlms_sig(sig) 1795 print "pub2:\t" + stringToHex(pub2) 1796 print "sig1: " 1797 print_lms_sig(sig1) 1798 print "sig2: " 1799 print_lms_sig(lms_sig) 1801 class hlms_private_key(object): 1802 def __init__(self): 1803 self.prv1 = lms_private_key() 1804 self.init_level_2() 1806 def init_level_2(self): 1807 self.prv2 = lms_private_key() 1808 self.sig1 = self.prv1.sign(self.prv2.get_public_key()) 1810 def get_public_key(self): 1811 return self.prv1.get_public_key() 1813 def sign(self, message): 1814 lms_sig = self.prv2.sign(message) 1815 if (lms_sig == ""): 1816 print "refreshing level 2 public/private key pair" 1817 self.init_level_2() 1818 lms_sig = self.prv2.sign(message) 1819 return encode_hlms_sig(self.prv2.get_public_key(), self.sig1, lms_sig) 1821 class hlms_public_key(object): 1822 def __init__(self, value): 1823 self.pub1 = lms_public_key(value) 1825 def verify(self, message, sig): 1826 pub2, sig1, lms_sig = decode_hlms_sig(sig) 1827 if (self.pub1.verify(pub2, sig1) == 1): 1828 if (lms_public_key(pub2).verify(message, lms_sig) == 1): 1829 return 1 1830 else: 1831 print "pub2 verification of lms_sig did not pass" 1832 else: 1833 print "pub1 verification of sig1 did not pass" 1834 return 0 1836 print "HLMS testing" 1838 hlms_prv = hlms_private_key() 1840 hlms_pub = hlms_public_key(hlms_prv.get_public_key()) 1842 for i in range(0, 4096): 1844 sig = hlms_prv.sign(message) 1846 # print_hlms_sig(sig) 1848 print "HLMS signature byte length: " + str(len(sig)) 1850 print "testing verification (" + str(i) + "th iteration)" 1851 print "true positive test" 1852 if (hlms_pub.verify(message, sig) == 1): 1853 print "passed; HLMS message/signature pair is valid" 1854 else: 1855 print "failed; HLMS message/signature pair is invalid" 1857 print "false positive test" 1858 if (hlms_pub.verify("other message", sig) == 1): 1859 print "failed; HLMS message/signature pair is valid (expected failure)" 1860 else: 1861 print "passed; HLMS message/signature pair is invalid as expected" 1863 Authors' Addresses 1865 David McGrew 1866 Cisco Systems 1867 13600 Dulles Technology Drive 1868 Herndon, VA 20171 1869 USA 1871 Email: mcgrew@cisco.com 1873 Michael Curcio 1874 Cisco Systems 1875 7025-2 Kit Creek Road 1876 Research Triangle Park, NC 27709-4987 1877 USA 1879 Email: micurcio@cisco.com