idnits 2.17.1 draft-mcgrew-hash-sigs-06.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 7 instances of too long lines in the document, the longest one being 30 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 (March 5, 2017) is 2608 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 1939 -- Looks like a reference, but probably isn't: '1' on line 1941 == Missing Reference: 'Nnv' is mentioned on line 928, but not defined == Missing Reference: 'L-1' is mentioned on line 1006, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 981, but not defined == Missing Reference: 'Nspk' is mentioned on line 981, but not defined -- Looks like a reference, but probably isn't: '32' on line 1933 -- Looks like a reference, but probably isn't: '265' on line 1041 -- Looks like a reference, but probably isn't: '133' on line 1046 -- Looks like a reference, but probably isn't: '67' on line 1051 -- Looks like a reference, but probably isn't: '34' on line 1056 -- Looks like a reference, but probably isn't: '5' on line 1879 -- Looks like a reference, but probably isn't: '10' on line 1889 -- Looks like a reference, but probably isn't: '15' on line 1899 -- Looks like a reference, but probably isn't: '20' on line 1909 -- Looks like a reference, but probably isn't: '25' on line 1919 -- Looks like a reference, but probably isn't: '64' on line 1109 -- Looks like a reference, but probably isn't: '2' on line 1943 -- Looks like a reference, but probably isn't: '3' on line 1945 -- Looks like a reference, but probably isn't: '4' on line 1947 -- Looks like a reference, but probably isn't: '6' on line 1881 -- Looks like a reference, but probably isn't: '7' on line 1883 -- Looks like a reference, but probably isn't: '8' on line 1885 -- Looks like a reference, but probably isn't: '9' on line 1887 -- Looks like a reference, but probably isn't: '11' on line 1891 -- Looks like a reference, but probably isn't: '12' on line 1893 -- Looks like a reference, but probably isn't: '13' on line 1895 -- Looks like a reference, but probably isn't: '14' on line 1897 -- Looks like a reference, but probably isn't: '16' on line 1901 -- Looks like a reference, but probably isn't: '17' on line 1903 -- Looks like a reference, but probably isn't: '18' on line 1905 -- Looks like a reference, but probably isn't: '19' on line 1907 -- Looks like a reference, but probably isn't: '21' on line 1911 -- Looks like a reference, but probably isn't: '22' on line 1913 -- Looks like a reference, but probably isn't: '23' on line 1915 -- Looks like a reference, but probably isn't: '24' on line 1917 -- Looks like a reference, but probably isn't: '26' on line 1921 -- Looks like a reference, but probably isn't: '27' on line 1923 -- Looks like a reference, but probably isn't: '28' on line 1925 -- Looks like a reference, but probably isn't: '29' on line 1927 -- Looks like a reference, but probably isn't: '30' on line 1929 -- Looks like a reference, but probably isn't: '31' on line 1931 -- Looks like a reference, but probably isn't: '33' on line 1935 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 3979 (Obsoleted by RFC 8179) ** Obsolete normative reference: RFC 4879 (Obsoleted by RFC 8179) Summary: 4 errors (**), 0 flaws (~~), 5 warnings (==), 41 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group D. McGrew 3 Internet-Draft M. Curcio 4 Intended status: Informational S. Fluhrer 5 Expires: September 6, 2017 Cisco Systems 6 March 5, 2017 8 Hash-Based Signatures 9 draft-mcgrew-hash-sigs-06 11 Abstract 13 This note describes a digital signature system based on cryptographic 14 hash functions, following the seminal work in this area of Lamport, 15 Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in 16 1995. It specifies a one-time signature scheme and a general 17 signature scheme. These systems provide asymmetric authentication 18 without using large integer mathematics and can achieve a high 19 security level. They are suitable for compact implementations, are 20 relatively simple to implement, and naturally resist side-channel 21 attacks. Unlike most other signature systems, hash-based signatures 22 would still be secure even if it proves feasible for an attacker to 23 build a quantum computer. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on September 6, 2017. 42 Copyright Notice 44 Copyright (c) 2017 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 61 2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 63 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 4 64 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 5 65 3.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 6 66 3.2. Security string . . . . . . . . . . . . . . . . . . . . . 7 67 3.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 8 68 3.4. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 8 69 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 8 70 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 9 71 4.2. Parameter Sets . . . . . . . . . . . . . . . . . . . . . 9 72 4.3. Private Key . . . . . . . . . . . . . . . . . . . . . . . 10 73 4.4. Public Key . . . . . . . . . . . . . . . . . . . . . . . 11 74 4.5. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 11 75 4.6. Signature Generation . . . . . . . . . . . . . . . . . . 12 76 4.7. Signature Verification . . . . . . . . . . . . . . . . . 13 77 5. Leighton Micali Signatures . . . . . . . . . . . . . . . . . 15 78 5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 16 79 5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 17 80 5.3. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 17 81 5.4. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 18 82 5.4.1. LMS Signature Generation . . . . . . . . . . . . . . 18 83 5.5. LMS Signature Verification . . . . . . . . . . . . . . . 19 84 6. Hierarchical signatures . . . . . . . . . . . . . . . . . . . 21 85 6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 21 86 6.2. Signature Generation . . . . . . . . . . . . . . . . . . 22 87 6.3. Signature Verification . . . . . . . . . . . . . . . . . 23 88 7. Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 89 8. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 26 90 9. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 91 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 92 11. Intellectual Property . . . . . . . . . . . . . . . . . . . . 30 93 11.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 30 94 12. Security Considerations . . . . . . . . . . . . . . . . . . . 30 95 12.1. Stateful signature algorithm . . . . . . . . . . . . . . 32 96 12.2. Security of LM-OTS Checksum . . . . . . . . . . . . . . 32 98 13. Comparison with other work . . . . . . . . . . . . . . . . . 33 99 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 34 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 34 101 15.1. Normative References . . . . . . . . . . . . . . . . . . 34 102 15.2. Informative References . . . . . . . . . . . . . . . . . 35 103 Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 36 104 Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 36 105 Appendix C. An iterative algorithm for computing an LMS public 106 key . . . . . . . . . . . . . . . . . . . . . . . . 37 107 Appendix D. Example Implementation . . . . . . . . . . . . . . . 38 108 Appendix E. Test Cases . . . . . . . . . . . . . . . . . . . . . 38 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 43 111 1. Introduction 113 One-time signature systems, and general purpose signature systems 114 built out of one-time signature systems, have been known since 1979 115 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 116 benefited from renewed attention in the last decade. The 117 characteristics of these signature systems are small private and 118 public keys and fast signature generation and verification, but large 119 signatures and relatively slow key generation. In recent years there 120 has been interest in these systems because of their post-quantum 121 security and their suitability for compact verifier implementations. 123 This note describes the Leighton and Micali adaptation [USPTO5432852] 124 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 125 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 126 signature system [Merkle79] with enough specificity to ensure 127 interoperability between implementations. 129 A signature system provides asymmetric message authentication. The 130 key generation algorithm produces a public/private key pair. A 131 message is signed by a private key, producing a signature, and a 132 message/signature pair can be verified by a public key. A One-Time 133 Signature (OTS) system can be used to sign at most one message 134 securely, but cannot securely sign more than one. An N-time 135 signature system can be used to sign N or fewer messages securely. A 136 Merkle tree signature scheme is an N-time signature system that uses 137 an OTS system as a component. 139 In this note we describe the Leighton-Micali Signature (LMS) system, 140 which is a variant of the Merkle scheme, and a Hierarchical Signature 141 System (HSS) built on top of it that can efficiently scale to larger 142 numbers of signatures. We denote the one-time signature scheme 143 incorporate in LMS as LM-OTS. This note is structured as follows. 144 Notation is introduced in Section 3. The LM-OTS signature system is 145 described in Section 4, and the LMS and HSS N-time signature systems 146 are described in Section 5 and Section 6, respectively. Sufficient 147 detail is provided to ensure interoperability. The IANA registry for 148 these signature systems is described in Section 10. Security 149 considerations are presented in Section 12. 151 1.1. Conventions Used In This Document 153 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 154 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 155 document are to be interpreted as described in [RFC2119]. 157 2. Interface 159 The LMS signing algorithm is stateful; it modifies and updates the 160 private key as a side effect of generating a signature. Once a 161 particular value of the private key is used to sign one message, it 162 MUST NOT be used to sign another. 164 The key generation algorithm takes as input an indication of the 165 parameters for the signature system. If it is successful, it 166 returns both a private key and a public key. Otherwise, it 167 returns an indication of failure. 169 The signing algorithm takes as input the message to be signed and 170 the current value of the private key. If successful, it returns a 171 signature and the next value of the private key, if there is such 172 a value. After the private key of an N-time signature system has 173 signed N messages, the signing algorithm returns the signature and 174 an indication that there is no next value of the private key that 175 can be used for signing. If unsuccessful, it returns an 176 indication of failure. 178 The verification algorithm takes as input the public key, a 179 message, and a signature, and returns an indication of whether or 180 not the signature and message pair are valid. 182 A message/signature pair are valid if the signature was returned by 183 the signing algorithm upon input of the message and the private key 184 corresponding to the public key; otherwise, the signature and message 185 pair are not valid with probability very close to one. 187 3. Notation 189 3.1. Data Types 191 Bytes and byte strings are the fundamental data types. A single byte 192 is denoted as a pair of hexadecimal digits with a leading "0x". A 193 byte string is an ordered sequence of zero or more bytes and is 194 denoted as an ordered sequence of hexadecimal characters with a 195 leading "0x". For example, 0xe534f0 is a byte string with a length 196 of three. An array of byte strings is an ordered set, indexed 197 starting at zero, in which all strings have the same length. 199 Unsigned integers are converted into byte strings by representing 200 them in network byte order. To make the number of bytes in the 201 representation explicit, we define the functions u8str(X), u16str(X), 202 and u32str(X), which take a non-negative integer X as input and 203 return one, two, and four byte strings, respectively. We also make 204 use of the function strTou32(S), which takes a four byte string S as 205 input and returns a non-negative integer; the identity 206 u32str(strTou32(S)) = S holds for any four-byte string S. 208 3.1.1. Operators 210 When a and b are real numbers, mathematical operators are defined as 211 follows: 213 ^ : a ^ b denotes the result of a raised to the power of b 215 * : a * b denotes the product of a multiplied by b 217 / : a / b denotes the quotient of a divided by b 219 % : a % b denotes the remainder of the integer division of a by b 221 + : a + b denotes the sum of a and b 223 - : a - b denotes the difference of a and b 225 The standard order of operations is used when evaluating arithmetic 226 expressions. 228 When B is a byte and i is an integer, then B >> i denotes the logical 229 right-shift operation. Similarly, B << i denotes the logical left- 230 shift operation. 232 If S and T are byte strings, then S || T denotes the concatenation of 233 S and T. If S and T are equal length byte strings, then S AND T 234 denotes the bitwise logical and operation. 236 The i^th element in an array A is denoted as A[i]. 238 3.1.2. Strings of w-bit elements 240 If S is a byte string, then byte(S, i) denotes its i^th byte, where 241 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 242 the range of bytes from the i^th to the j^th byte, inclusive. For 243 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 244 2) is 0x0406. 246 A byte string can be considered to be a string of w-bit unsigned 247 integers; the correspondence is defined by the function coef(S, i, w) 248 as follows: 250 If S is a string, i is a positive integer, and w is a member of the 251 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 252 is interpreted as a sequence of w-bit values. That is, 254 coef(S, i, w) = (2^w - 1) AND 255 ( byte(S, floor(i * w / 8)) >> 256 (8 - (w * (i % (8 / w)) + w)) ) 258 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 259 coef(S, 0, 4) is 1. 261 S (represented as bits) 262 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 263 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 264 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 265 ^ 266 | 267 coef(S, 7, 1) 269 S (represented as four-bit values) 270 +-----------+-----------+-----------+-----------+ 271 | 1 | 2 | 3 | 4 | 272 +-----------+-----------+-----------+-----------+ 273 ^ 274 | 275 coef(S, 0, 4) 277 The return value of coef is an unsigned integer. If i is larger than 278 the number of w-bit values in S, then coef(S, i, w) is undefined, and 279 an attempt to compute that value should raise an error. 281 3.2. Security string 283 To improve security against attacks that amortize their effort 284 against multiple invocations of the hash function, Leighton and 285 Micali introduce a "security string" that is distinct for each 286 invocation of that function. The following fields can appear in a 287 security string: 289 I - an identifier for the LMS public/private key pair. The length 290 of this value varies based on the LMS parameter set and it MUST be 291 chosen uniformly at random, or via a pseudorandom process, at the 292 time that a key pair is generated, in order to ensure that it will 293 be distinct from the identifier of any other LMS private key with 294 probability close to one. 296 D - a domain separation parameter, which is a single byte that 297 takes on different values in the different algorithms in which H 298 is invoked. D takes on the following values: 300 D_ITER = 0x00 in the iterations of the LM-OTS algorithms 302 D_PBLC = 0x01 when computing the hash of all of the iterates in 303 the LM-OTS algorithm 305 D_MESG = 0x02 when computing the hash of the message in the LM- 306 OTS algorithms 308 D_LEAF = 0x03 when computing the hash of the leaf of an LMS 309 tree 311 D_INTR = 0x04 when computing the hash of an interior node of an 312 LMS tree 314 D_PRG = 0x05 in the recommended pseudorandom process for 315 generating LMS private keys 317 C - an n-byte randomizer that is included with the message 318 whenever it is being hashed to improve security. C MUST be chosen 319 uniformly at random, or via a pseudorandom process. 321 r - in the LMS N-time signature scheme, the node number r 322 associated with a particular node of a hash tree is used as an 323 input to the hash used to compute that node. This value is 324 represented as a 32-bit (four byte) unsigned integer in network 325 byte order. 327 q - in the LMS N-time signature scheme, each LM-OTS signature is 328 associated with the leaf of a hash tree, and q is set to the leaf 329 number. This ensures that a distinct value of q is used for each 330 distinct LM-OTS public/private key pair. This value is 331 represented as a 32-bit (four byte) unsigned integer in network 332 byte order. 334 i - in the LM-OTS scheme, i is the index of the private key 335 element upon which H is being applied. It is represented as a 336 16-bit (two byte) unsigned integer in network byte order. 338 j - in the LM-OTS scheme, j is the iteration number used when the 339 private key element is being iteratively hashed. It is 340 represented as an 8-bit (one byte) unsigned integer. 342 3.3. Functions 344 If r is a non-negative real number, then we define the following 345 functions: 347 ceil(r) : returns the smallest integer larger than r 349 floor(r) : returns the largest integer smaller than r 351 lg(r) : returns the base-2 logarithm of r 353 3.4. Typecodes 355 A typecode is an unsigned integer that is associated with a 356 particular data format. The format of the LM-OTS, LMS, and HSS 357 signatures and public keys all begin with a typecode that indicates 358 the precise details used in that format. These typecodes are 359 represented as four-byte unsigned integers in network byte order; 360 equivalently, they are XDR enumerations (see Section 7). 362 4. LM-OTS One-Time Signatures 364 This section defines LM-OTS signatures. The signature is used to 365 validate the authenticity of a message by associating a secret 366 private key with a shared public key. These are one-time signatures; 367 each private key MUST be used at most one time to sign any given 368 message. 370 As part of the signing process, a digest of the original message is 371 computed using the cryptographic hash function H (see Section 4.1), 372 and the resulting digest is signed. 374 In order to facilitate its use in an N-time signature system, the LM- 375 OTS key generation, signing, and verification algorithms all take as 376 input a diversification parameter q. When the LM-OTS signature 377 system is used outside of an N-time signature system, this value 378 SHOULD be set to the all-zero value. 380 4.1. Parameters 382 The signature system uses the parameters n and w, which are both 383 positive integers. The algorithm description also makes use of the 384 internal parameters p and ls, which are dependent on n and w. These 385 parameters are summarized as follows: 387 n : the number of bytes of the output of the hash function 389 w : the width (number of bits) of the Winternitz coefficients; it 390 is a member of the set { 1, 2, 4, 8 } 392 p : the number of n-byte string elements that make up the LM-OTS 393 signature 395 ls : the number of left-shift bits used in the checksum function 396 Cksm (defined in Section 4.5). 398 H : a second-preimage-resistant cryptographic hash function that 399 accepts byte strings of any length, and returns an n-byte string. 401 For more background on the cryptographic security requirements on H, 402 see the Section 12. 404 The value of n is determined by the functions selected for use as 405 part of the LM-OTS algorithm; the choice of this value has a strong 406 effect on the security of the system. The parameter w determines the 407 length of the Winternitz chains computed as a part of the OTS 408 signature (which involve 2^w-1 invocations of the hash function); it 409 has little effect on security. Increasing w will shorten the 410 signature, but at a cost of a larger computation to generate and 411 verify a signature. The values of p and ls are dependent on the 412 choices of the parameters n and w, as described in Appendix B. A 413 table illustrating various combinations of n, w, p, and ls is 414 provided in Table 1. 416 4.2. Parameter Sets 418 To fully describe a LM-OTS signature method, the parameters n and w, 419 the length LenS of the security string S, as well as the function H, 420 MUST be specified. This section defines several LM-OTS methods, each 421 of which is identified by a name. The values for p and ls are 422 provided as a convenience. 424 +---------------------+--------+----+---+------+-----+----+ 425 | Name | H | n | w | LenS | p | ls | 426 +---------------------+--------+----+---+------+-----+----+ 427 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 68 | 265 | 7 | 428 | | | | | | | | 429 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 68 | 133 | 6 | 430 | | | | | | | | 431 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 68 | 67 | 4 | 432 | | | | | | | | 433 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 68 | 34 | 0 | 434 +---------------------+--------+----+---+------+-----+----+ 436 Table 1 438 Here SHA256 denotes the NIST standard hash function [FIPS180]. 440 4.3. Private Key 442 The LM-OTS private key consists of a typecode indicating the 443 particular LM-OTS algorithm, an array x[] containing p n-byte 444 strings, and a LenS-byte security string S. This private key MUST be 445 used to sign (at most) one message. The following algorithm shows 446 pseudocode for generating a private key. 448 Algorithm 0: Generating a Private Key 450 1. set type to the typecode of the algorithm 452 2. if no security string S has been provided as input, then set S to 453 a LenS-byte string generated uniformly at random 455 3. set n and p according to the typecode and Table 1 457 4. compute the array x as follows: 458 for ( i = 0; i < p; i = i + 1 ) { 459 set x[i] to a uniformly random n-byte string 460 } 462 5. return u32str(type) || S || x[0] || x[1] || ... || x[p-1] 464 An implementation MAY use a pseudorandom method to compute x[i], as 465 suggested in [Merkle79], page 46. The details of the pseudorandom 466 method do not affect interoperability, but the cryptographic strength 467 MUST match that of the LM-OTS algorithm. Appendix A provides an 468 example of a pseudorandom method for computing LM-OTS private key. 470 4.4. Public Key 472 The LM-OTS public key is generated from the private key by 473 iteratively applying the function H to each individual element of x, 474 for 2^w - 1 iterations, then hashing all of the resulting values. 476 The public key is generated from the private key using the following 477 algorithm, or any equivalent process. 479 Algorithm 1: Generating a One Time Signature Public Key From a 480 Private Key 482 1. set type to the typecode of the algorithm 484 2. set the integers n, p, and w according to the typecode and Table 1 486 3. determine x and S from the private key 488 4. compute the string K as follows: 489 for ( i = 0; i < p; i = i + 1 ) { 490 tmp = x[i] 491 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 492 tmp = H(S || tmp || u16str(i) || u8str(j) || D_ITER) 493 } 494 y[i] = tmp 495 } 496 K = H(S || y[0] || ... || y[p-1] || D_PBLC) 498 5. return u32str(type) || S || K 500 The public key is the value returned by Algorithm 1. 502 4.5. Checksum 504 A checksum is used to ensure that any forgery attempt that 505 manipulates the elements of an existing signature will be detected. 506 The security property that it provides is detailed in Section 12. 507 The checksum function Cksm is defined as follows, where S denotes the 508 n-byte string that is input to that function, and the value sum is a 509 16-bit unsigned integer: 511 Algorithm 2: Checksum Calculation 513 sum = 0 514 for ( i = 0; i < (n*8/w); i = i + 1 ) { 515 sum = sum + (2^w - 1) - coef(S, i, w) 516 } 517 return (sum << ls) 519 Because of the left-shift operation, the rightmost bits of the result 520 of Cksm will often be zeros. Due to the value of p, these bits will 521 not be used during signature generation or verification. 523 4.6. Signature Generation 525 The LM-OTS signature of a message is generated by first prepending 526 the randomizer C and the security string S to the message, then 527 appending D_MESG to the resulting string then computing its hash, 528 concatenating the checksum of the hash to the hash itself, then 529 considering the resulting value as a sequence of w-bit values, and 530 using each of the w-bit values to determine the number of times to 531 apply the function H to the corresponding element of the private key. 532 The outputs of the function H are concatenated together and returned 533 as the signature. The pseudocode for this procedure is shown below. 535 Algorithm 3: Generating a One Time Signature From a Private Key and a 536 Message 538 1. set type to the typecode of the algorithm 540 2. set n, p, and w according to the typecode and Table 1 542 3. determine x and S from the private key 544 4. set C to a uniformly random n-byte string 546 5. compute the array y as follows: 547 Q = H(S || C || message || D_MESG ) 548 for ( i = 0; i < p; i = i + 1 ) { 549 a = coef(Q || Cksm(Q), i, w) 550 tmp = x[i] 551 for ( j = 0; j < a; j = j + 1 ) { 552 tmp = H(S || tmp || u16str(i) || u8str(j) || D_ITER) 553 } 554 y[i] = tmp 555 } 557 6. return u32str(type) || C || y[0] || ... || y[p-1] 559 Note that this algorithm results in a signature whose elements are 560 intermediate values of the elements computed by the public key 561 algorithm in Section 4.4. 563 The signature is the string returned by Algorithm 3. Section 7 564 specifies the typecode and more formally defines the encoding and 565 decoding of the string. 567 4.7. Signature Verification 569 In order to verify a message with its signature (an array of n-byte 570 strings, denoted as y), the receiver must "complete" the chain of 571 iterations of H using the w-bit coefficients of the string resulting 572 from the concatenation of the message hash and its checksum. This 573 computation should result in a value that matches the provided public 574 key. 576 Algorithm 4a: Verifying a Signature and Message Using a Public Key 578 1. if the public key is not at least four bytes long, return INVALID 580 2. parse pubtype, S, and K from the public key as follows: 581 a. pubtype = strTou32(first 4 bytes of public key) 583 b. if pubtype is not equal to sigtype, return INVALID 585 c. if the public key is not exactly 4 + LenS + n bytes long, 586 return INVALID 588 c. S = next LenS bytes of public key 590 d. K = next n bytes of public key 592 3. compute the public key candidate Kc from the signature, 593 message, and the security string S obtained from the 594 public key, using Algorithm 4b. If Algorithm 4b returns 595 INVALID, then return INVALID. 597 4. if Kc is equal to K, return VALID; otherwise, return INVALID 599 Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, 600 Message, Signature Typecode Type , and a Security String S 602 1. if the signature is not at least four bytes long, return INVALID 604 2. parse sigtype, C, and y from the signature as follows: 605 a. sigtype = strTou32(first 4 bytes of signature) 607 b. if sigtype is not equal to Type, return INVALID 609 c. set n and p according to the sigtype and Table 1; if the 610 signature is not exactly 4 + n * (p+1) bytes long, return INVALID 612 d. C = next n bytes of signature 614 e. y[0] = next n bytes of signature 615 y[1] = next n bytes of signature 616 ... 617 y[p-1] = next n bytes of signature 619 3. compute the string Kc as follows 620 Q = H(S || C || message || D_MESG) 621 for ( i = 0; i < p; i = i + 1 ) { 622 a = coef(Q || Cksm(Q), i, w) 623 tmp = y[i] 624 for ( j = a; j < 2^w - 1; j = j + 1 ) { 625 tmp = H(S || tmp || u16str(i) || u8str(j) || D_ITER) 626 } 627 z[i] = tmp 628 } 629 Kc = H(S || z[0] || z[1] || ... || z[p-1] || D_PBLC) 631 4. return Kc 633 5. Leighton Micali Signatures 635 The Leighton Micali Signature (LMS) method can sign a potentially 636 large but fixed number of messages. An LMS system uses two 637 cryptographic components: a one-time signature method and a hash 638 function. Each LMS public/private key pair is associated with a 639 perfect binary tree, each node of which contains an m-byte value. 640 Each leaf of the tree contains the value of the public key of an LM- 641 OTS public/private key pair. The value contained by the root of the 642 tree is the LMS public key. Each interior node is computed by 643 applying the hash function to the concatenation of the values of its 644 children nodes. 646 Each node of the tree is associated with a node number, an unsigned 647 integer that is denoted as node_num in the algorithms below, which is 648 computed as follows. The root node has node number 1; for each node 649 with node number N < 2^h, its left child has node number 2*N, while 650 its right child has node number 2*N+1. The result of this is that 651 each node within the tree will have a unique node number, and the 652 leaves will have node numbers 2^h, (2^h)+1, (2^h)+2, ..., 653 (2^h)+(2^h)-1. In general, the j^th node at level L has node number 654 2^L + j. The node number can conveniently be computed when it is 655 needed in the LMS algorithms, as described in those algorithms. 657 5.1. Parameters 659 An LMS system has the following parameters: 661 h : the height (number of levels - 1) in the tree, and 663 m : the number of bytes associated with each node. 665 H : a second-preimage-resistant cryptographic hash function that 666 accepts byte strings of any length, and returns an m-byte string. 667 H SHOULD be the same as in Section 4.1, but MAY be different. 669 There are 2^h leaves in the tree. The hash function used within the 670 LMS system MUST be the same as the hash function used within the LM- 671 OTS system used to generate the leaves. This is required because 672 both use the same I value, and hence must have the same length of I 673 value (and the length of the I value is dependent on the hash 674 function). 676 +--------------------+--------+----+----+ 677 | Name | H | m | h | 678 +--------------------+--------+----+----+ 679 | LMS_SHA256_M32_H5 | SHA256 | 32 | 5 | 680 | | | | | 681 | LMS_SHA256_M32_H10 | SHA256 | 32 | 10 | 682 | | | | | 683 | LMS_SHA256_M32_H15 | SHA256 | 32 | 15 | 684 | | | | | 685 | LMS_SHA256_M32_H20 | SHA256 | 32 | 20 | 686 | | | | | 687 | LMS_SHA256_M32_H24 | SHA256 | 32 | 25 | 688 +--------------------+--------+----+----+ 690 Table 2 692 5.2. LMS Private Key 694 An LMS private key consists of an array OTS_PRIV[] of 2^h LM-OTS 695 private keys, and the leaf number q of the next LM-OTS private key 696 that has not yet been used. The q^th element of OTS_PRIV[] is 697 generated using Algorithm 0 with the security string S = I || q. The 698 leaf number q is initialized to zero when the LMS private key is 699 created. The process is as follows: 701 Algorithm 5: Computing an LMS Private Key. 703 1. determine h and m from the typecode and Table 2. 705 2. compute the array OTS_PRIV[] as follows: 706 for ( q = 0; q < 2^h; q = q + 1) { 707 S = I || q 708 OTS_PRIV[q] = LM-OTS private key with security string S 709 } 711 3. q = 0 713 An LMS private key MAY be generated pseudorandomly from a secret 714 value, in which case the secret value MUST be at least m bytes long, 715 be uniformly random, and MUST NOT be used for any other purpose than 716 the generation of the LMS private key. The details of how this 717 process is done do not affect interoperability; that is, the public 718 key verification operation is independent of these details. 719 Appendix A provides an example of a pseudorandom method for computing 720 an LMS private key. 722 5.3. LMS Public Key 724 An LMS public key is defined as follows, where we denote the public 725 key associated with the i^th LM-OTS private key as OTS_PUB[i], with i 726 ranging from 0 to (2^h)-1. Each instance of an LMS public/private 727 key pair is associated with a perfect binary tree, and the nodes of 728 that tree are indexed from 1 to 2^(h+1)-1. Each node is associated 729 with an m-byte string, and the string for the r^th node is denoted as 730 T[r] and is defined as 732 T[r] = / H(I || OTS_PUB[r-2^h] || u32str(r) || D_LEAF) if r >= 2^h, 733 \ H(I || T[2*r] || T[2*r+1] || u32str(r) || D_INTR) otherwise. 735 The LMS public key is the string u32str(type) || I || T[1]. 736 Section 7 specifies the format of the type variable. The value I is 737 the private key identifier (whose length is denoted by the parameter 738 set), and is the value used for all computations for the same LMS 739 tree. The value T[1] can be computed via recursive application of 740 the above equation, or by any equivalent method. An iterative 741 procedure is outlined in Appendix C. 743 5.4. LMS Signature 745 An LMS signature consists of 747 a typecode indicating the particular LMS algorithm, 749 the number q of the leaf associated with the LM-OTS signature, as 750 a four-byte unsigned integer in network byte order, 752 an LM-OTS signature, and 754 an array of h m-byte values that is associated with the path 755 through the tree from the leaf associated with the LM-OTS 756 signature to the root. 758 Symbolically, the signature can be represented as u32str(q) || 759 ots_signature || u32str(type) || path[0] || path[1] || ... || 760 path[h-1]. Section 7 specifies the typecode and more formally 761 defines the format. The array of values contains the siblings of the 762 nodes on the path from the leaf to the root but does not contain the 763 nodes on the path themselves. The array for a tree with height h 764 will have h values. The first value is the sibling of the leaf, the 765 next value is the sibling of the parent of the leaf, and so on up the 766 path to the root. 768 5.4.1. LMS Signature Generation 770 To compute the LMS signature of a message with an LMS private key, 771 the signer first computes the LM-OTS signature of the message using 772 the leaf number of the next unused LM-OTS private key. The leaf 773 number q in the signature is set to the leaf number of the LMS 774 private key that was used in the signature. Before releasing the 775 signature, the leaf number q in the LMS private key MUST be 776 incremented, to prevent the LM-OTS private key from being used again. 777 If the LMS private key is maintained in nonvolatile memory, then the 778 implementation MUST ensure that the incremented value has been stored 779 before releasing the signature. 781 The array of node values in the signature MAY be computed in any way. 782 There are many potential time/storage tradeoffs that can be applied. 783 The fastest alternative is to store all of the nodes of the tree and 784 set the array in the signature by copying them. The least storage 785 intensive alternative is to recompute all of the nodes for each 786 signature. Note that the details of this procedure are not important 787 for interoperability; it is not necessary to know any of these 788 details in order to perform the signature verification operation. 789 The internal nodes of the tree need not be kept secret, and thus a 790 node-caching scheme that stores only internal nodes can sidestep the 791 need for strong protections. 793 Several useful time/storage tradeoffs are described in the 'Small- 794 Memory LM Schemes' section of [USPTO5432852]. 796 5.5. LMS Signature Verification 798 An LMS signature is verified by first using the LM-OTS signature 799 verification algorithm (Algorithm 4b) to compute the LM-OTS public 800 key from the LM-OTS signature and the message. The value of that 801 public key is then assigned to the associated leaf of the LMS tree, 802 then the root of the tree is computed from the leaf value and the 803 array path[] as described in Algorithm 6 below. If the root value 804 matches the public key, then the signature is valid; otherwise, the 805 signature fails. 807 Algorithm 6: LMS Signature Verification 809 1. if the public key is not at least four bytes long, return 810 INVALID 812 2. parse pubtype, I, and T[1] from the public key as follows: 813 a. pubtype = strTou32(first 4 bytes of public key) 815 b. if the public key is not exactly 4 + LenI + m bytes 816 long, return INVALID 818 c. I = next LenI bytes of the public key 820 d. T[1] = next m bytes of the public key 822 6. compute the candidate LMS root value Tc from the signature, 823 message, identifier and pubtype using Algorithm 6b. 825 7. if Tc is equal to T[1], return VALID; otherwise, return INVALID 827 Algorithm 6b: Computing an LMS Public Key Candidate from a Signature, 828 Message, Identifier, and algorithm typecode 830 1. if the signature is not at least eight bytes long, return INVALID 832 2. parse sigtype, q, ots_signature, and path from the signature as 833 follows: 834 a. q = strTou32(first 4 bytes of signature) 836 b. otssigtype = strTou32(next 4 bytes of signature) 838 c. if otssigtype is not the OTS typecode from the public key, return INVALID 840 d. set n, p according to otssigtype and Table 1; if the 841 signature is not at least 12 + n * (p + 1) bytes long, return INVALID 843 e. ots_signature = bytes 8 through 8 + n * (p + 1) of signature 845 f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1)) 847 f. if sigtype is not the LM typecode from the public key, return INVALID 849 g. set m, h according to sigtype and Table 2 851 h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID 853 i. set path as follows: 854 path[0] = next m bytes of signature 855 path[1] = next m bytes of signature 856 ... 857 path[h-1] = next m bytes of signature 859 5. Kc = candidate public key computed by applying Algorithm 4b 860 to the signature ots_signature, the message, and the 861 security string S = I || q 863 6. compute the candidate LMS root value Tc as follows: 864 node_num = 2^h + q 865 tmp = H(I || Kc || u32str(node_num) || D_LEAF) 866 i = 0 867 while (node_num > 1) { 868 if (node_num is odd): 869 tmp = H(I || path[i] || tmp || u32str(node_num/2) || D_INTR) 870 else: 871 tmp = H(I || tmp || path[i] || u32str(node_num/2) || D_INTR) 872 node_num = node_num/2 873 i = i + 1 874 } 875 Tc = tmp 877 7. return Tc 879 6. Hierarchical signatures 881 In scenarios where it is necessary to minimize the time taken by the 882 public key generation process, a Hierarchical N-time Signature System 883 (HSS) can be used. Leighton and Micali describe a scheme in which an 884 LMS public key is used to sign a second LMS public key, which is then 885 distributed along with the signatures generated with the second 886 public key [USPTO5432852]. This hierarchical scheme, which we 887 describe in this section, uses an LMS scheme as a component. HSS, in 888 essence, utilizes a tree of LMS trees, in which the HSS public key 889 contains the public key of the LMS tree at the root, and an HSS 890 signature is associated with a path from the root of the HSS tree to 891 one of its leaves. Compared to LMS, HSS has a much reduced public 892 key generation time, as only the root tree needs to be generated 893 prior to the distribution of the HSS public key. 895 Each level of the hierarchy is associated with a distinct LMS public 896 key, private key, signature, and identifier. The number of levels is 897 denoted L, and is between one and eight, inclusive. The following 898 notation is used, where i is an integer between 0 and L-1 inclusive, 899 and the root of the hierarchy is level 0: 901 prv[i] is the LMS private key of the i^th level, 903 pub[i] is the LMS public key of the i^th level (which includes the 904 identifier I as well as the key value K), 906 sig[i] is the LMS signature of the i^th level, 908 In this section, we say that an N-time private key is exhausted when 909 it has generated N signatures, and thus it can no longer be used for 910 signing. 912 HSS allows L=1, in which case the HSS public key and signature 913 formats are essentially the LMS public key and signature formats, 914 prepended by a fixed field. Since HSS with L=1 has very little 915 overhead compared to LMS, all implementations MUST support HSS in 916 order to maximize interoperability. 918 6.1. Key Generation 920 When an HSS key pair is generated, the key pair for each level MUST 921 have its own identifier. 923 To generate an HSS private and public key pair, new LMS private and 924 public keys are generated for prv[i] and pub[i] for i=0, ... , L-1. 925 These key pairs, and their identifiers, MUST be generated 926 independently. All of the information of the leaf level L-1, 927 including the private key, MUST NOT be stored in nonvolatile memory. 928 Letting Nnv denote the lowest level for which prv[Nnv] is stored in 929 nonvolatile memory, there are Nnv nonvolatile levels, and L-Nnv 930 volatile levels. For security, Nnv should be as close to one as 931 possible (see Section 12.1). 933 The public key of the HSS scheme is consists of the number of levels 934 L, followed by pub[0], the public key of the top level. 936 The HSS private key consists of prv[0], ... , prv[L-1]. The values 937 pub[0] and prv[0] do not change, though the values of pub[i] and 938 prv[i] are dynamic for i > 0, 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 If prv[L-1] is exhausted, then determine the smallest integer d 947 such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] 948 are exhausted. If d is equal to zero, then the HSS key pair is 949 exhausted, and it MUST NOT generate any more signatures. 950 Otherwise, the key pairs for levels d through L-1 must be 951 regenerated during the signature generation process, as follows. 952 For i from d to L-1, a new LMS public and private key pair with a 953 new identifier is generated, pub[i] and prv[i] are set to those 954 values, then the public key pub[i] is signed with prv[i-1], and 955 sig[i-1] is set to the resulting value. 957 The message is signed with prv[L-1], and the value sig[L-1] is set 958 to that result. 960 The value of the HSS signature is set as follows. We let 961 signed_pub_key denote an array of octet strings, where 962 signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk- 963 1, inclusive, where Nspk = L-1 denotes the number of signed public 964 keys. Then the HSS signature is u32str(Nspk) || 965 signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]. 967 Note that the number of signed_pub_key elements in the signature 968 is indicated by the value Nspk that appears in the initial four 969 bytes of the signature. 971 In the specific case of L=1, the format of an HSS signature is 973 u32str(0) || sig[0] 975 In the general case, the format of an HSS signature is 977 u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk] 979 which is equivalent to 981 u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk]. 983 6.3. Signature Verification 985 To verify a signature sig and message using the public key pub, the 986 following steps are performed: 988 The signature S is parsed into its components as follows: 990 L' = strTou32(first four bytes of S) 991 if L' is not equal to the number of levels L in pub: 992 return INVALID 993 for (i = 0; i < L; i = i + 1) { 994 siglist[i] = next LMS signature parsed from S 995 publist[i] = next LMS public key parsed from S 996 } 997 siglist[L-1] = next LMS signature parsed from S 999 key = pub 1000 for (i =0; i < L; i = i + 1) { 1001 sig = siglist[i] 1002 msg = publist[i] 1003 if (lms_verify(msg, key, sig) != VALID): 1004 return INVALID 1005 key = msg 1006 return lms_verify(message, key, siglist[L-1]) 1008 Since the length of an LMS signature cannot be known without parsing 1009 it, the HSS signature verification algorithm makes use of an LMS 1010 signature parsing routine that takes as input a string consisting of 1011 an LMS signature with an arbitrary string appended to it, and returns 1012 both the LMS signature and the appended string. The latter is passed 1013 on for further processing. 1015 7. Formats 1017 The signature and public key formats are formally defined using the 1018 External Data Representation (XDR) [RFC4506] in order to provide an 1019 unambiguous, machine readable definition. For clarity, we also 1020 include a private key format as well, though consistency is not 1021 needed for interoperability and an implementation MAY use any private 1022 key format. Though XDR is used, these formats are simple and easy to 1023 parse without any special tools. An illustration of the layout of 1024 data in these objects is provided below. The definitions are as 1025 follows: 1027 /* one-time signatures */ 1029 enum ots_algorithm_type { 1030 lmots_reserved = 0, 1031 lmots_sha256_n32_w1 = 1, 1032 lmots_sha256_n32_w2 = 2, 1033 lmots_sha256_n32_w4 = 3, 1034 lmots_sha256_n32_w8 = 4 1035 }; 1037 typedef opaque bytestring32[32]; 1039 struct lmots_signature_n32_p265 { 1040 bytestring32 C; 1041 bytestring32 y[265]; 1042 }; 1044 struct lmots_signature_n32_p133 { 1045 bytestring32 C; 1046 bytestring32 y[133]; 1047 }; 1049 struct lmots_signature_n32_p67 { 1050 bytestring32 C; 1051 bytestring32 y[67]; 1052 }; 1054 struct lmots_signature_n32_p34 { 1055 bytestring32 C; 1056 bytestring32 y[34]; 1057 }; 1059 union ots_signature switch (ots_algorithm_type type) { 1060 case lmots_sha256_n32_w1: 1061 lmots_signature_n32_p265 sig_n32_p265; 1062 case lmots_sha256_n32_w2: 1063 lmots_signature_n32_p133 sig_n32_p133; 1064 case lmots_sha256_n32_w4: 1065 lmots_signature_n32_p67 sig_n32_p67; 1066 case lmots_sha256_n32_w8: 1067 lmots_signature_n32_p34 sig_n32_p34; 1069 default: 1070 void; /* error condition */ 1071 }; 1073 /* hash based signatures (hbs) */ 1075 enum hbs_algorithm_type { 1076 hbs_reserved = 0, 1077 lms_sha256_n32_h5 = 5, 1078 lms_sha256_n32_h10 = 6, 1079 lms_sha256_n32_h15 = 7, 1080 lms_sha256_n32_h20 = 8, 1081 lms_sha256_n32_h25 = 9, 1082 }; 1084 /* leighton micali signatures (lms) */ 1086 union lms_path switch (hbs_algorithm_type type) { 1087 case lms_sha256_n32_h5: 1088 bytestring32 path_n32_h5[5]; 1089 case lms_sha256_n32_h10: 1090 bytestring32 path_n32_h10[10]; 1091 case lms_sha256_n32_h15: 1092 bytestring32 path_n32_h15[15]; 1093 case lms_sha256_n32_h20: 1094 bytestring32 path_n32_h20[20]; 1095 case lms_sha256_n32_h25: 1096 bytestring32 path_n32_h25[25]; 1097 default: 1098 void; /* error condition */ 1099 }; 1101 struct lms_signature { 1102 unsigned int q; 1103 ots_signature lmots_sig; 1104 lms_path nodes; 1105 }; 1107 struct lms_key_n32 { 1108 ots_algorithm_type ots_alg_type; 1109 opaque I[64]; 1110 opaque K[32]; 1111 }; 1113 union hbs_public_key switch (hbs_algorithm_type type) { 1114 case lms_sha256_n32_h5: 1115 case lms_sha256_n32_h10: 1117 case lms_sha256_n32_h15: 1118 case lms_sha256_n32_h20: 1119 case lms_sha256_n32_h25: 1120 lms_key_n32 z_n32; 1121 default: 1122 void; /* error condition */ 1123 }; 1125 /* hierarchical signature system (hss) */ 1127 struct hss_public_key { 1128 unsigned int L; 1129 hbs_public_key pub; 1130 }; 1132 struct signed_public_key { 1133 hbs_signature sig; 1134 hbs_public_key pub; 1135 } 1137 struct hss_signature { 1138 signed_public_key signed_keys<7>; 1139 hbs_signature sig_of_message; 1140 }; 1142 Many of the objects start with a typecode. A verifier MUST check 1143 each of these typecodes, and a verification operation on a signature 1144 with an unknown type, or a type that does not correspond to the type 1145 within the public key MUST return INVALID. The expected length of a 1146 variable-length object can be determined from its typecode, and if an 1147 object has a different length, then any signature computed from the 1148 object is INVALID. 1150 8. Rationale 1152 The goal of this note is to describe the LM-OTS and LMS algorithms 1153 following the original references and present the modern security 1154 analysis of those algorithms. Other signature methods are out of 1155 scope and may be interesting follow-on work. 1157 We adopt the techniques described by Leighton and Micali to mitigate 1158 attacks that amortize their work over multiple invocations of the 1159 hash function. 1161 The values taken by the identifier I across different LMS public/ 1162 private key pairs are required to be distinct in order to improve 1163 security. That distinctness ensures the uniqueness of the inputs to 1164 H across all of those public/private key pair instances, which is 1165 important for provable security in the random oracle model. The 1166 length of I is set at 31 or 64 bytes so that randomly chosen values 1167 of I will be distinct with probability at least 1 - 1/2^128 as long 1168 as there are 2^60 or fewer instances of LMS public/private key pairs. 1170 The sizes of the parameters in the security string are such that the 1171 hashes computed by both LM and LM-OTS start with a fixed 64-byte I 1172 value. The reason this size was selected was to allow an 1173 implementation to compute the intermediate hash state after 1174 processing I once (similar to the well-known optimization for HMAC), 1175 and hence the majority of hashes computed during LM-OTS processing 1176 can be performed using a single hash compression operation when using 1177 SHA-256. Other hash functions, which may be used in future 1178 specifications, can use a similar strategy, as long as I is long 1179 enough that it is very unlikely to repeat if chosen uniformly at 1180 random. 1182 The signature and public key formats are designed so that they are 1183 relatively easy to parse. Each format starts with a 32-bit 1184 enumeration value that indicates the details of the signature 1185 algorithm and provides all of the information that is needed in order 1186 to parse the format. 1188 The Checksum Section 4.5 is calculated using a non-negative integer 1189 "sum", whose width was chosen to be an integer number of w-bit fields 1190 such that it is capable of holding the difference of the total 1191 possible number of applications of the function H as defined in the 1192 signing algorithm of Section 4.6 and the total actual number. In the 1193 case that the number of times H is applied is 0, the sum is (2^w - 1) 1194 * (8*n/w). Thus for the purposes of this document, which describes 1195 signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 1196 4, 8 }, the sum variable is a 16-bit non-negative integer for all 1197 combinations of n and w. The calculation uses the parameter ls 1198 defined in Section 4.1 and calculated in Appendix B, which indicates 1199 the number of bits used in the left-shift operation. 1201 9. History 1203 This is the fifth version of this draft. It has the following 1204 changes from previous versions: 1206 Version 05 1208 Clarified the L=1 specific case. 1210 Extended the parameter sets to include an H=25 option 1212 A large number of corrections and clarifications 1213 Added a comparison to XMSS and SPHINCS, and citations to those 1214 algorithms and to the recent Security Standardization Research 1215 2016 publications on the security of LMS and on the state 1216 management in hash-based signatures. 1218 Version 04 1220 Specified that, in the HSS method, the I value was computed from 1221 the I value of the parent LM tree. Previous versions had the I 1222 value extracted from the public key (which meant that all LM trees 1223 of a particular level and public key used the same I value) 1225 Changed the length of the I field based on the parameter set. As 1226 noted in the Rationale section, this allows an implementation to 1227 compute SHA256 n=32 based parameter sets significantly faster. 1229 Modified the XDR of an HSS signature not to use an array of LM 1230 signatures; LM signatures are variable length, and XDR doesn't 1231 support arrays of variable length structures. 1233 Changed the LMS registry to be in a consistent order with the LM- 1234 OTS parameter sets. Also, added LMS parameter sets with height 15 1235 trees 1237 Previous versions 1239 In Algorithms 3 and 4, the message was moved from the initial 1240 position of the input to the function H to the final position, in 1241 the computation of the intermediate variable Q. This was done to 1242 improve security by preventing an attacker that can find a 1243 collision in H from taking advantage of that fact via the forward 1244 chaining property of Merkle-Damgard. 1246 The Hierarchical Signature Scheme was generalized slightly so that 1247 it can use more than two levels. 1249 Several points of confusion were corrected; these had resulted 1250 from incomplete or inconsistent changes from the Merkle approach 1251 of the earlier draft to the Leighton-Micali approach. 1253 This section is to be removed by the RFC editor upon publication. 1255 10. IANA Considerations 1257 The Internet Assigned Numbers Authority (IANA) is requested to create 1258 two registries: one for OTS signatures, which includes all of the LM- 1259 OTS signatures as defined in Section 3, and one for Leighton-Micali 1260 Signatures, as defined in Section 4. Additions to these registries 1261 require that a specification be documented in an RFC or another 1262 permanent and readily available reference in sufficient detail that 1263 interoperability between independent implementations is possible. 1264 Each entry in the registry contains the following elements: 1266 a short name, such as "LMS_SHA256_M32_H10", 1268 a positive number, and 1270 a reference to a specification that completely defines the 1271 signature method test cases that can be used to verify the 1272 correctness of an implementation. 1274 Requests to add an entry to the registry MUST include the name and 1275 the reference. The number is assigned by IANA. Submitters SHOULD 1276 have their requests reviewed by the IRTF Crypto Forum Research Group 1277 (CFRG) at cfrg@ietf.org. Interested applicants that are unfamiliar 1278 with IANA processes should visit http://www.iana.org. 1280 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1281 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1282 are reserved for private use; no attempt will be made to prevent 1283 multiple sites from using the same value in different (and 1284 incompatible) ways [RFC2434]. 1286 The LM-OTS registry is as follows. 1288 +----------------------+-----------+--------------------+ 1289 | Name | Reference | Numeric Identifier | 1290 +----------------------+-----------+--------------------+ 1291 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 | 1292 | | | | 1293 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 | 1294 | | | | 1295 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 | 1296 | | | | 1297 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 | 1298 +----------------------+-----------+--------------------+ 1300 Table 3 1302 The LMS registry is as follows. 1304 +--------------------+-----------+--------------------+ 1305 | Name | Reference | Numeric Identifier | 1306 +--------------------+-----------+--------------------+ 1307 | LMS_SHA256_M32_H5 | Section 5 | 0x00000005 | 1308 | | | | 1309 | LMS_SHA256_M32_H10 | Section 5 | 0x00000006 | 1310 | | | | 1311 | LMS_SHA256_M32_H15 | Section 5 | 0x00000007 | 1312 | | | | 1313 | LMS_SHA256_M32_H20 | Section 5 | 0x00000008 | 1314 | | | | 1315 | LMS_SHA256_M32_H25 | Section 5 | 0x00000009 | 1316 +--------------------+-----------+--------------------+ 1318 Table 4 1320 An IANA registration of a signature system does not constitute an 1321 endorsement of that system or its security. 1323 11. Intellectual Property 1325 This draft is based on U.S. patent 5,432,852, which issued over 1326 twenty years ago and is thus expired. 1328 11.1. Disclaimer 1330 This document is not intended as legal advice. Readers are advised 1331 to consult with their own legal advisers if they would like a legal 1332 interpretation of their rights. 1334 The IETF policies and processes regarding intellectual property and 1335 patents are outlined in [RFC3979] and [RFC4879] and at 1336 https://datatracker.ietf.org/ipr/about. 1338 12. Security Considerations 1340 The hash function H MUST have second preimage resistance: it must be 1341 computationally infeasible for an attacker that is given one message 1342 M to be able to find a second message M' such that H(M) = H(M'). 1344 The security goal of a signature system is to prevent forgeries. A 1345 successful forgery occurs when an attacker who does not know the 1346 private key associated with a public key can find a message and 1347 signature that are valid with that public key (that is, the Signature 1348 Verification algorithm applied to that signature and message and 1349 public key will return VALID). Such an attacker, in the strongest 1350 case, may have the ability to forge valid signatures for an arbitrary 1351 number of other messages. 1353 LMS is provably secure in the random oracle model, as shown by Katz 1354 [Katz16]. From Theorem 2 of that reference: 1356 For any adversary attacking the LMS scheme and making at most q 1357 hash queries, the probability the adversary forges a signature is 1358 at most 3*q/2^(8*n). 1360 Here n is the number of bytes in the output of the hash function (as 1361 defined in Section 4.1). The security of all of the the algorithms 1362 and parameter sets defined in this note is roughly 128 bits, even 1363 assuming that there are quantum computers that can compute the input 1364 to an arbitrary function with computational cost equivalent to the 1365 square root of the size of the domain of that function [Grover96]. 1367 The format of the inputs to the hash function H have the property 1368 that each invocation of that function has an input that is distinct 1369 from all others, with very high probability. This property is 1370 important for a proof of security in the random oracle model. The 1371 formats used during key generation and signing are 1373 S || tmp || u16str(i) || u8str(j) || D_ITER 1374 S || y[0] || ... || y[p-1] || D_PBLC 1375 S || C || message || D_MESG 1376 I || OTS_PUB[r-2^h] || u32str(r) || D_LEAF 1377 I || T[2*r] || T[2*r+1] || u32str(r) || D_INTR 1378 I || u32str(q) || x_q[j-1] || u16str(j) || D_PRG 1380 Because the suffixes D_ITER, D_PBLC, D_LEAF, D_INTR, and D_PRG are 1381 distinct, the input formats ending with different suffixes are all 1382 distinct. It remains to show the distinctness of the inputs for each 1383 suffix. 1385 The values of I and C are chosen uniformly at random from the set of 1386 all n*8 bit strings. For n=32, it is highly likely that each value 1387 of I and C will be distinct, even when 2^96 such values are chosen. 1389 For D_ITER, D_PBLC, and D_MESG, the value of S = I || u32str(q) is 1390 distinct for each LMS leaf (or equivalently, for each q value). For 1391 D_ITER, the value of u16str(i) || u8str(j) is distinct for each 1392 invocation of H for a given leaf. For D_PBLC and D_MESG, the input 1393 format is used only once for each value of S, and thus distinctness 1394 is assured. The formats for D_INTR and D_LEAF are used exactly once 1395 for each value of r, which ensures their distinctness. For D_PRG, 1396 for a given value of I, q and j are distinct for each invocation of H 1397 (note that x_q[0] = SEED when j=0). 1399 12.1. Stateful signature algorithm 1401 The LMS signature system, like all N-time signature systems, requires 1402 that the signer maintain state across different invocations of the 1403 signing algorithm, to ensure that none of the component one-time 1404 signature systems are used more than once. This section calls out 1405 some important practical considerations around this statefulness. 1407 In a typical computing environment, a private key will be stored in 1408 non-volatile media such as on a hard drive. Before it is used to 1409 sign a message, it will be read into an application's Random Access 1410 Memory (RAM). After a signature is generated, the value of the 1411 private key will need to be updated by writing the new value of the 1412 private key into non-volatile storage. It is essential for security 1413 that the application ensure that this value is actually written into 1414 that storage, yet there may be one or more memory caches between it 1415 and the application. Memory caching is commonly done in the file 1416 system, and in a physical memory unit on the hard disk that is 1417 dedicated to that purpose. To ensure that the updated value is 1418 written to physical media, the application may need to take several 1419 special steps. In a POSIX environment, for instance, the O_SYNC flag 1420 (for the open() system call) will cause invocations of the write() 1421 system call to block the calling process until the data has been to 1422 the underlying hardware. However, if that hardware has its own 1423 memory cache, it must be separately dealt with using an operating 1424 system or device specific tool such as hdparm to flush the on-drive 1425 cache, or turn off write caching for that drive. Because these 1426 details vary across different operating systems and devices, this 1427 note does not attempt to provide complete guidance; instead, we call 1428 the implementer's attention to these issues. 1430 When hierarchical signatures are used, an easy way to minimize the 1431 private key synchronization issues is to have the private key for the 1432 second level resident in RAM only, and never write that value into 1433 non-volatile memory. A new second level public/private key pair will 1434 be generated whenever the application (re)starts; thus, failures such 1435 as a power outage or application crash are automatically 1436 accommodated. Implementations SHOULD use this approach wherever 1437 possible. 1439 12.2. Security of LM-OTS Checksum 1441 To show the security of LM-OTS checksum, we consider the signature y 1442 of a message with a private key x and let h = H(message) and 1443 c = Cksm(H(message)) (see Section 4.6). To attempt a forgery, an 1444 attacker may try to change the values of h and c. Let h' and c' 1445 denote the values used in the forgery attempt. If for some integer j 1446 in the range 0 to u, where u = ceil(8*n/w) is the size of the range 1447 that the checksum value can over), inclusive, 1449 a' = coef(h', j, w), 1451 a = coef(h, j, w), and 1453 a' > a 1455 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1456 iteratively applying function F to the j^th term of the signature an 1457 additional (a' - a) times. However, as a result of the increased 1458 number of hashing iterations, the checksum value c' will decrease 1459 from its original value of c. Thus a valid signature's checksum will 1460 have, for some number k in the range u to (p-1), inclusive, 1462 b' = coef(c', k, w), 1464 b = coef(c, k, w), and 1466 b' < b 1468 Due to the one-way property of F, the attacker cannot easily compute 1469 F^b'(x[k]) from F^b(x[k]) = y[k]. 1471 13. Comparison with other work 1473 The eXtended Merkle Signature Scheme (XMSS) [XMSS] is similar to HSS 1474 in several ways. Both are stateful hash based signature schemes, and 1475 both use a hierarchical approach, with a Merkle tree at each level of 1476 the hierarchy. XMSS signatures are slightly shorter than HSS 1477 signatures, for equivalent security and an equal number of 1478 signatures. 1480 HSS has several advantages over XMSS. HSS operations are roughly 1481 four times faster than the comparable XMSS ones, when SHA256 is used 1482 as the underlying hash, because the hash operation dominates any 1483 measure of performance, and XMSS performs four compression function 1484 invocations (two for the PRF, two for the F function) where HSS need 1485 only perform one. Additionally, HSS is somewhat simpler, and it 1486 admits a single-level tree in a simple way (as described in 1487 Section 6.2). 1489 Another advantage of HSS is the fact that it can use a stateless 1490 hash-based signature scheme in its non-volatile levels, while 1491 continuing to use LMS in its volatile levels, and thus realize a 1492 hybrid stateless/stateful scheme as described in [STMGMT]. While we 1493 conjecture that hybrid schemes will offer lower computation times and 1494 signature sizes than purely stateless schemes, the details are 1495 outside the scope of this note. HSS is therefore amenable to future 1496 extensions that will enable it to be used in environments in which a 1497 purely stateful scheme would be too brittle. 1499 SPHINCS [SPHINCS] is a purely stateless hash based signature scheme. 1500 While that property benefits security, its signature sizes and 1501 generation times are an order of magnitude (or more) larger than 1502 those of HSS, making it more difficult to adopt in some practical 1503 scenarios. 1505 14. Acknowledgements 1507 Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric 1508 Osterweil, Ahmed Kosba, Russ Housley and Philip Lafrance for 1509 constructive suggestions and valuable detailed review. We especially 1510 acknowledge Jerry Solinas, Laurie Law, and Kevin Igoe, who pointed 1511 out the security benefits of the approach of Leighton and Micali 1512 [USPTO5432852] and Jonathan Katz, who gave us security guidance. 1514 15. References 1516 15.1. Normative References 1518 [FIPS180] National Institute of Standards and Technology, "Secure 1519 Hash Standard (SHS)", FIPS 180-4, March 2012. 1521 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1522 Requirement Levels", BCP 14, RFC 2119, 1523 DOI 10.17487/RFC2119, March 1997, 1524 . 1526 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1527 IANA Considerations Section in RFCs", RFC 2434, 1528 DOI 10.17487/RFC2434, October 1998, 1529 . 1531 [RFC3979] Bradner, S., Ed., "Intellectual Property Rights in IETF 1532 Technology", BCP 79, RFC 3979, DOI 10.17487/RFC3979, March 1533 2005, . 1535 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1536 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1537 2006, . 1539 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1540 Procedure in RFC 3979", BCP 79, RFC 4879, 1541 DOI 10.17487/RFC4879, April 2007, 1542 . 1544 [USPTO5432852] 1545 Leighton, T. and S. Micali, "Large provably fast and 1546 secure digital signature schemes from secure hash 1547 functions", U.S. Patent 5,432,852, July 1995. 1549 15.2. Informative References 1551 [C:Merkle87] 1552 Merkle, R., "A Digital Signature Based on a Conventional 1553 Encryption Function", Lecture Notes in Computer 1554 Science crypto87vol, 1988. 1556 [C:Merkle89a] 1557 Merkle, R., "A Certified Digital Signature", Lecture Notes 1558 in Computer Science crypto89vol, 1990. 1560 [C:Merkle89b] 1561 Merkle, R., "One Way Hash Functions and DES", Lecture 1562 Notes in Computer Science crypto89vol, 1990. 1564 [Grover96] 1565 Grover, L., "A fast quantum mechanical algorithm for 1566 database search", 28th ACM Symposium on the Theory of 1567 Computing p. 212, 1996. 1569 [Katz16] Katz, J., "Analysis of a proposed hash-based signature 1570 standard", Security Standardization Research (SSR) 1571 Conference http://www.cs.umd.edu/~jkatz/papers/ 1572 HashBasedSigs-SSR16.pdf, 2016. 1574 [Merkle79] 1575 Merkle, R., "Secrecy, Authentication, and Public Key 1576 Systems", Stanford University Information Systems 1577 Laboratory Technical Report 1979-1, 1979. 1579 [SPHINCS] Bernstein, D., Hopwood, D., Hulsing, A., Lange, T., 1580 Niederhagen, R., Papachristadoulou, L., Schneider, M., 1581 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical 1582 Stateless Hash-Based Signatures.", Annual International 1583 Conference on the Theory and Applications of Cryptographic 1584 Techniques Springer., 2015. 1586 [STMGMT] McGrew, D., Fluhrer, S., Kampanakis, P., Gazdag, S., 1587 Butin, D., and J. Buchmann, "State Management for Hash- 1588 based Signatures.", Security Standardization Resarch (SSR) 1589 Conference 224., 2016. 1591 [XMSS] Buchmann, J., Dahmen, E., and . Andreas Hulsing, "XMSS-a 1592 practical forward secure signature scheme based on minimal 1593 security assumptions.", International Workshop on Post- 1594 Quantum Cryptography Springer Berlin., 2011. 1596 Appendix A. Pseudorandom Key Generation 1598 An implementation MAY use the following pseudorandom process for 1599 generating an LMS private key. 1601 SEED is an m-byte value that is generated uniformly at random at 1602 the start of the process, 1604 I is LMS key pair identifier, 1606 q denotes the LMS leaf number of an LM-OTS private key, 1608 x_q denotes the x array of private elements in the LM-OTS private 1609 key with leaf number q, 1611 j is an index of the private key element, 1613 D_PRG is a diversification constant, and 1615 H is the hash function used in LM-OTS. 1617 The elements of the LM-OTS private keys are computed as: 1619 x_q[j] = H(I || u32str(q) || SEED || u16str(j) || D_PRG). 1621 This process stretches the m-byte random value SEED into a (much 1622 larger) set of pseudorandom values, using a unique counter in each 1623 invocation of H. The format of the inputs to H are chosen so that 1624 they are distinct from all other uses of H in LMS and LM-OTS. 1626 Appendix B. LM-OTS Parameter Options 1628 A table illustrating various combinations of n and w with the 1629 associated values of u, v, ls, and p is provided in Table 5. 1631 The parameters u, v, ls, and p are computed as follows: 1633 u = ceil(8*n/w) 1634 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1635 ls = (number of bits in sum) - (v * w) 1636 p = u + v 1638 Here u and v represent the number of w-bit fields required to contain 1639 the hash of the message and the checksum byte strings, respectively. 1640 The "number of bits in sum" is defined according to Section 4.5. And 1641 as the value of p is the number of w-bit elements of 1642 ( H(message) || Cksm(H(message)) ), it is also equivalently the 1643 number of byte strings that form the private key and the number of 1644 byte strings in the signature. 1646 +---------+------------+-----------+-----------+-------+------------+ 1647 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1648 | Length | Parameter | Elements | Elements | Shift | Number of | 1649 | in | (w) | in Hash | in | (ls) | w-bit | 1650 | Bytes | | (u) | Checksum | | Elements | 1651 | (n) | | | (v) | | (p) | 1652 +---------+------------+-----------+-----------+-------+------------+ 1653 | 16 | 1 | 128 | 8 | 8 | 137 | 1654 | | | | | | | 1655 | 16 | 2 | 64 | 4 | 8 | 68 | 1656 | | | | | | | 1657 | 16 | 4 | 32 | 3 | 4 | 35 | 1658 | | | | | | | 1659 | 16 | 8 | 16 | 2 | 0 | 18 | 1660 | | | | | | | 1661 | 32 | 1 | 256 | 9 | 7 | 265 | 1662 | | | | | | | 1663 | 32 | 2 | 128 | 5 | 6 | 133 | 1664 | | | | | | | 1665 | 32 | 4 | 64 | 3 | 4 | 67 | 1666 | | | | | | | 1667 | 32 | 8 | 32 | 2 | 0 | 34 | 1668 +---------+------------+-----------+-----------+-------+------------+ 1670 Table 5 1672 Appendix C. An iterative algorithm for computing an LMS public key 1674 The LMS public key can be computed using the following algorithm or 1675 any equivalent method. The algorithm uses a stack of hashes for 1676 data. It also makes use of a hash function with the typical 1677 init/update/final interface to hash functions; the result of the 1678 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 1679 hash_update(N[n]), v = hash_final(), in that order, is identical to 1680 that of the invocation of H(N[1] || N[2] || ... || N[n]). 1682 Generating an LMS Public Key From an LMS Private Key 1684 for ( i = 0; i < num_lmots_keys; i = i + 1 ) { 1685 r = i + num_lmots_keys; 1686 temp = H(I || OTS_PUBKEY[i] || u32str(r) || D_LEAF) 1687 j = i; 1688 while (j % 2 == 1) { 1689 r = (r - 1)/2; j = (j-1) / 2; 1690 left_size = pop(data stack); 1691 temp = H(I || left_side || temp || u32str(r) || D_INTR) 1692 } 1693 push temp onto the data stack 1694 } 1695 public_key = pop(data stack) 1697 Note that this pseudocode expects that all 2^h leaves of the tree 1698 have equal depth; that is, num_lmots_keys to be a power of 2. The 1699 maximum depth of the stack will be h-1 elements, that is, a total of 1700 (h-1)*n bytes; for the currently defined parameter sets, this will 1701 never be more than 768 bytes of data. 1703 Appendix D. Example Implementation 1705 An example implementation can be found online at 1706 http://github.com/davidmcgrew/hash-sigs/. 1708 Appendix E. Test Cases 1710 This section provides test cases that can be used to verify or debug 1711 an implementation. This data is formatted with the name of the 1712 elements on the left, and the value of the elements on the right, in 1713 hexadecimal. The concatenation of all of the values within a public 1714 key or signature produces that public key or signature, and values 1715 that do not fit within a single line are listed across successive 1716 lines. 1718 Test Case 1 Public Key 1720 -------------------------------------------- 1721 HSS public key 1722 levels 00000002 1723 -------------------------------------------- 1724 LMS public key 1725 LMS type 00000005 # LMS_SHA256_M32_H5 1726 LMOTS_type 00000004 # LMOTS_SHA256_N32_W8 1727 I a5f1da931d9acad25800936e78400a9f 1728 35e42c3026a95f52c3380dcec2cedc86 1729 67c3d6060c407aea9101c37298e38c31 1730 b54d8bb61a2c9668d01216814cc3788c 1731 K 348ed79a731eabe47a3cd7ab603ef8de 1732 6db2e83eaa08fe742cdeb36e635590e2 1733 -------------------------------------------- 1734 -------------------------------------------- 1736 Test Case 1 Message 1738 -------------------------------------------- 1739 Message 54686520706f77657273206e6f742064 |The powers not d| 1740 656c65676174656420746f2074686520 |elegated to the | 1741 556e6974656420537461746573206279 |United States by| 1742 2074686520436f6e737469747574696f | the Constitutio| 1743 6e2c206e6f722070726f686962697465 |n, nor prohibite| 1744 6420627920697420746f207468652053 |d by it to the S| 1745 74617465732c20617265207265736572 |tates, are reser| 1746 76656420746f20746865205374617465 |ved to the State| 1747 7320726573706563746976656c792c20 |s respectively, | 1748 6f7220746f207468652070656f706c65 |or to the people| 1749 2e0a |..| 1750 -------------------------------------------- 1752 Test Case 1 Signature 1754 -------------------------------------------- 1755 HSS signature 1756 Nspk 00000001 1757 sig[0]: 1758 -------------------------------------------- 1759 LMS signature 1760 q 00000001 1761 -------------------------------------------- 1762 LMOTS signature 1763 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1764 C c638b5aa5d3ebec1648986cff65a1b2e 1765 7213487c25c6fe15b1c859603f741e16 1767 y[0] b11e8ec40acfc44e74248c312cc8b027 1768 7fb992afb099f43cd69675b7bd6c22aa 1769 y[1] 84ddb5ceade53f2097dae9b124be8773 1770 b275d470efa1038437378d8756092b17 1771 y[2] 1bd8bac797db1a3e977f28e73aff1c3b 1772 94bd3dacca4af4384b6271742e25c841 1773 y[3] 9a9d179629c2b966c0eb25a998243094 1774 d5f1a7185c0fdf0d9bf9dfa707cbae82 1775 y[4] 545c4e5e2d86db1fad025f41e13276d0 1776 d28559d5ab81bd81fc97b63f914e1606 1777 y[5] ddd89cd611fe2a766f4e98d5932c1a27 1778 1d879592794f84e7decfcef6e9f00d0d 1779 y[6] 2e20b82d50149fc5a5fe2a4c42e1dd10 1780 85e9a151c9bc11417b388a2b7018ec1a 1781 y[7] 731c1077e54f8b8eba828d3a3462ed6c 1782 f340c7e8a93364df9174127a57463ea1 1783 y[8] ad3c122d9eb92e29dd97b1a0f9165a09 1784 c1f1f5eb4d0315d287fdcbff30a4fe15 1785 y[9] 59eb238bb17c0583df83c5aac1cf5a85 1786 d72c12e2522090b5a130c4e580687b97 1787 y[10] 62d897571b95c3c61d7dac8168a60a1e 1788 c1c38879129d30c99ecccf51edd0699e 1789 y[11] 170b88ba98253729134e00e81e523f82 1790 ef5eaba611a10c3955eb0548918cd103 1791 y[12] fc40ee27c672af4fbc42f314cb1fc0c1 1792 5d42a6372bbe83b22f9334629b4af452 1793 y[13] 00b60c768eb1cb888220ee2c4f08ba59 1794 bbb4b7793a5651e3dd10ef4b0bb5ed24 1795 y[14] 9740e05d35f8670ff6271c5503a6be87 1796 7561f9e6f4c81e1b903e5048b20b5fb2 1797 y[15] dad7f51142c23faa4ecd2774b2e25fee 1798 73a93f02466c3fb9d80b10e4becf7d81 1799 y[16] 1b6a0f4590231de56e0275466790feb0 1800 26f15e65c26dc45beb908afdba13e560 1801 y[17] 46cac18acb86b10f96a5fcb59b07999c 1802 04f6febe461220c544dcc8328767c5a0 1803 y[18] 01e434d65bc787ffd952f1404496f3f1 1804 dd91260e929c60c2725bde980438e591 1805 y[19] c0eb0788c2d40a867028f1109b80f6a3 1806 32c4c54ef39078df71a89dda43053c36 1807 y[20] c13d2ffb54c5b236d32eb07ea08ea3eb 1808 147fca0367512330736781d028756e53 1809 y[21] 2b4e109b812789d44079e8f3c7833362 1810 4c0b5255b14057404168710a802cedd1 1811 y[22] b39be11a52cfbb522b17e796004ae6a7 1812 0c17aee15eb0d8f8239c5c95d3143633 1813 y[23] 92d30c6c2268f27eeb0f64ff46312e47 1814 8ca388c37d895d1850f8abb5ac4f4d62 1816 y[24] 39eac305ec8fd13a4a1f537b46e71d26 1817 3ee4ff2066256b8f1facf42d90e439a2 1818 y[25] 2511733d1c27a3a76fd6d34b8c2d6c98 1819 419756af39148825a60c0bab0dc5e44d 1820 y[26] eb282478ecde2460b045e0b4f1649b23 1821 24eb21570d2804ebb331fef94b6a09d4 1822 y[27] f6139d54e2ec15b5c770ae0dda018748 1823 82f0a04e8d61d7f7985668fad9295aa8 1824 y[28] b851fa7a223c9bd8b7badb46ba7a6474 1825 e269f0261693af2589f2ba948616946d 1826 y[29] 7d9e09f8c2d2311884469b0910990cc1 1827 952eba6dcf6ffbd7fe348c79698b9e74 1828 y[30] 01f370a89c4de025393ccdd6ea4278e3 1829 07dd69025a77ad13f91d55dd8b11d320 1830 y[31] 9b10acf760ca29f58866836dfbc00e1c 1831 790d63bac8cdea86408df23a7c780259 1832 y[32] db23d2482b65f2f4f5613660ef7a27e1 1833 a4cc4cd695fe7cd52be2c5f1a7140a38 1834 y[33] 59f431952579592822aa15389fffb05d 1835 3528f92b91a8f376a5af2cb61fd8d2c5 1836 -------------------------------------------- 1837 LMS type 00000005 # LMS_SHA256_M32_H5 1838 path[0] 76b85fb075704d6cd66c6d9c48c512ad 1839 5a41e84ef199ff2d07300400357a032d 1840 path[1] ef12462838a0fe139bb8b429eeb4e76e 1841 09b704611bdbb30c107db13076e52ee6 1842 path[2] 055b20ae2af30d52b9e0d1194b979b5f 1843 897f23437a33c0f3099a4fe0f79662b8 1844 path[3] 1fbd4cbf61a92e5eb45fa68358410cb7 1845 812540c560ed7bd2256cc912a80f5260 1846 path[4] 6b60e09d773b729d806ace549227b376 1847 2fa7a55942b07a77b165e0d729899617 1848 pub[0]: 1849 -------------------------------------------- 1850 LMS public key 1851 LMS type 00000005 # LMS_SHA256_M32_H5 1852 LMOTS_type 00000004 # LMOTS_SHA256_N32_W8 1853 I 9fc3084bbea5e6d31af8586bc14d8154 1854 f5532b14745e196dcadd820aa11ea137 1855 f06a326778eeb875c6035934ee6470ae 1856 8bfa18f1a1d36e1553f28aa87b878006 1857 K 2d7920997295fc74ad49ea4c5ad6735e 1858 1e967c966766924b799e734ae922989a 1859 -------------------------------------------- 1860 final_signature: 1861 -------------------------------------------- 1862 LMS signature 1863 q 00000009 1864 -------------------------------------------- 1865 LMOTS signature 1866 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1867 C 8c721faaa063d1c0a5acef3cc83b4f3a 1868 a3c3863586030c2fb1abdbbff08baf34 1869 y[0] 36a7fc7f0287f1fc10ca471502bae902 1870 bed6be97b576ef330e119bc93f043811 1871 y[1] d5de1e0a4431f850d1d264bf880628aa 1872 9f53c66a23b3f87075651dfc4a05de3e 1873 y[2] bc8a1addc634dc1f38f27dbfee708169 1874 78007e9400618586b715c15ca153a1fa 1875 y[3] 1d3a4711354893db705500d8d2b4ae98 1876 3fc358de7817ba6da1baaee64e670f43 1877 y[4] 7fe3675543c548d8e3b23430b86dfb16 1878 27164c4b953086bc544ebcbef54c9437 1879 y[5] f79837dcc32e158f7858c5ad3c09628c 1880 b1715ae69c3489cf617527956385f7c9 1881 y[6] bf1a7365629691b10499e39405b07edc 1882 3464fd71170af8e50e06f644778b337e 1883 y[7] 42b3a15affcd482de83dc1d408cfdf4a 1884 2b0e4566a09eaaae8269a0695c00b1a7 1885 y[8] 3e482cf25b44d65474276cfc34f7991d 1886 15cb1defb2236fa7b697362cd9e6d1e0 1887 y[9] 5dd1342b137d7d3a54374dba7ba5741e 1888 1aaa2831ff62dfdf52b8aee2559fb27c 1889 y[10] aebe546a5006b857692c32f0f6a8386d 1890 96646631e953942126d7793715245caa 1891 y[11] 1704d819e50f2a2ec6c1271ed47db819 1892 b8ea3529a343818ec58c14206bbb5eea 1893 y[12] 681897efa723779ffd970ee4d8841bee 1894 c87cf9cc14a5369d3196a3331e057be4 1895 y[13] e7b4c26fa6e74c916cd73be77406812d 1896 7dd1258e14dcf4ebb2b137d5f9a1d628 1897 y[14] e4d661b240c0c6f75e954e1872c2d135 1898 cb0b758c270b42193ab9838c360c8dc5 1899 y[15] 43b7dfd7e6d49778f3eeb328ddb57078 1900 f24610b710ba20a01fccdec1f3f02763 1901 y[16] 776ddbd8c82e25f6ab0f46cd1f776ffc 1902 00c1c55ef5f2429ad12501a8ad876901 1903 y[17] 1d51dee1851abc129fa99aae096d1da1 1904 8acb95f7f78b5adeaaa4d4ea53984b1a 1905 y[18] a562394d39c479b93fea1db213e3685a 1906 8a9368b16fd4b3086729f61ec3d65ff8 1907 y[19] f4f634d430522606761ee1ad522f5a86 1908 573c5e7b0f6aeb90d1bdfb0cdec61272 1909 y[20] 52b4b07683a59441377899e9558f5181 1910 56318c83fb6a9c1c0a49b43d3ae08dec 1911 y[21] 221d0f3bc0230d9c080e06bddfce2f12 1912 3b0bc012644aed82f4d565564461d814 1913 y[22] 62c401a74d41959720dd05dc717d3bcd 1914 2790ddd2af0e4d6214990b0fee5fdaed 1915 y[23] 8af103391e6edceb8d08554249092ebe 1916 949f8b1671ceabb7f6a991163da95372 1917 y[24] 0b384b59c8589030165bb90917b9a9a7 1918 9462eecf5f6196280d23129011ddbd5e 1919 y[25] 4c99f50a7ae2cf8debc7d0034c39eb3f 1920 33b67889073c62b7fbcccadc4921763c 1921 y[26] 512a485d8cc78f80a783a84348e17411 1922 7a4e3716319316a2eb42c014a54616e8 1923 y[27] 40156b0d511f8762c3d2a0a3946e0b6f 1924 993320206c930980cd6a9751e57c62dc 1925 y[28] aa1cf6303ca775d71a91629bd904ac20 1926 35226dc9d5b653dcd30673738374829f 1927 y[29] f57d72293c0f1b3666004667248881bd 1928 9338b59b049f4e0091f5d39879fca9b6 1929 y[30] 6c0d4b4eb19d9e63fef18f5657974ff4 1930 d36bf23055dcb6ed4f7e5ce1ad04bfac 1931 y[31] e91630344345eea1470efb49e4854411 1932 8a09561d498e90a50c8d68c3e726d15b 1933 y[32] f20871eaa508b929a5210bc027c92038 1934 07a94c1cae545a97baf6dd961eddb72f 1935 y[33] 5fd33572aae2da10093c3600e26ead7e 1936 eaa9e1dce4f253985f4f922b77057535 1937 -------------------------------------------- 1938 LMS type 00000005 # LMS_SHA256_M32_H5 1939 path[0] e89d230cd37998a27929b8ac966a76c6 1940 73ae712267ab51ee82c754dc583efb34 1941 path[1] a6f3e4f96984891c7bbc80468a88aedd 1942 e5e6661e32d84c106f5353d660092428 1943 path[2] affef3d925d9f0da2b7a5bbafc5099e2 1944 169b29695c69a425bab93ece3fcfa376 1945 path[3] 75c32f006ef4599340508179caa9da3c 1946 574b16721535ce74b1e287e507aab414 1947 path[4] 0ea5e46102296e0bb564d99520b5593f 1948 25c07a581408d453ce99d615f565ebc2 1950 Authors' Addresses 1952 David McGrew 1953 Cisco Systems 1954 13600 Dulles Technology Drive 1955 Herndon, VA 20171 1956 USA 1958 Email: mcgrew@cisco.com 1959 Michael Curcio 1960 Cisco Systems 1961 7025-2 Kit Creek Road 1962 Research Triangle Park, NC 27709-4987 1963 USA 1965 Email: micurcio@cisco.com 1967 Scott Fluhrer 1968 Cisco Systems 1969 170 West Tasman Drive 1970 San Jose, CA 1971 USA 1973 Email: sfluhrer@cisco.com