idnits 2.17.1 draft-mcgrew-hash-sigs-09.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 11 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 (February 23, 2018) is 2254 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 2398 -- Looks like a reference, but probably isn't: '1' on line 2400 == Missing Reference: 'L-1' is mentioned on line 998, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 1022, but not defined == Missing Reference: 'Nspk' is mentioned on line 1047, but not defined -- Looks like a reference, but probably isn't: '32' on line 2392 -- Looks like a reference, but probably isn't: '265' on line 1082 -- Looks like a reference, but probably isn't: '133' on line 1087 -- Looks like a reference, but probably isn't: '67' on line 1092 -- Looks like a reference, but probably isn't: '34' on line 2222 -- Looks like a reference, but probably isn't: '5' on line 2338 -- Looks like a reference, but probably isn't: '10' on line 2348 -- Looks like a reference, but probably isn't: '15' on line 2358 -- Looks like a reference, but probably isn't: '20' on line 2368 -- Looks like a reference, but probably isn't: '25' on line 2378 -- Looks like a reference, but probably isn't: '16' on line 2360 -- Looks like a reference, but probably isn't: '2' on line 2402 -- Looks like a reference, but probably isn't: '3' on line 2404 -- Looks like a reference, but probably isn't: '4' on line 2406 -- Looks like a reference, but probably isn't: '6' on line 2340 -- Looks like a reference, but probably isn't: '7' on line 2342 -- Looks like a reference, but probably isn't: '8' on line 2344 -- Looks like a reference, but probably isn't: '9' on line 2346 -- Looks like a reference, but probably isn't: '11' on line 2350 -- Looks like a reference, but probably isn't: '12' on line 2352 -- Looks like a reference, but probably isn't: '13' on line 2354 -- Looks like a reference, but probably isn't: '14' on line 2356 -- Looks like a reference, but probably isn't: '17' on line 2362 -- Looks like a reference, but probably isn't: '18' on line 2364 -- Looks like a reference, but probably isn't: '19' on line 2366 -- Looks like a reference, but probably isn't: '21' on line 2370 -- Looks like a reference, but probably isn't: '22' on line 2372 -- Looks like a reference, but probably isn't: '23' on line 2374 -- Looks like a reference, but probably isn't: '24' on line 2376 -- Looks like a reference, but probably isn't: '26' on line 2380 -- Looks like a reference, but probably isn't: '27' on line 2382 -- Looks like a reference, but probably isn't: '28' on line 2384 -- Looks like a reference, but probably isn't: '29' on line 2386 -- Looks like a reference, but probably isn't: '30' on line 2388 -- Looks like a reference, but probably isn't: '31' on line 2390 -- Looks like a reference, but probably isn't: '33' on line 2394 -- Looks like a reference, but probably isn't: '35' on line 2224 -- Looks like a reference, but probably isn't: '36' on line 2226 -- Looks like a reference, but probably isn't: '37' on line 2228 -- Looks like a reference, but probably isn't: '38' on line 2230 -- Looks like a reference, but probably isn't: '39' on line 2232 -- Looks like a reference, but probably isn't: '40' on line 2234 -- Looks like a reference, but probably isn't: '41' on line 2236 -- Looks like a reference, but probably isn't: '42' on line 2238 -- Looks like a reference, but probably isn't: '43' on line 2240 -- Looks like a reference, but probably isn't: '44' on line 2242 -- Looks like a reference, but probably isn't: '45' on line 2244 -- Looks like a reference, but probably isn't: '46' on line 2246 -- Looks like a reference, but probably isn't: '47' on line 2248 -- Looks like a reference, but probably isn't: '48' on line 2250 -- Looks like a reference, but probably isn't: '49' on line 2252 -- Looks like a reference, but probably isn't: '50' on line 2254 -- Looks like a reference, but probably isn't: '51' on line 2256 -- Looks like a reference, but probably isn't: '52' on line 2258 -- Looks like a reference, but probably isn't: '53' on line 2260 -- Looks like a reference, but probably isn't: '54' on line 2262 -- Looks like a reference, but probably isn't: '55' on line 2264 -- Looks like a reference, but probably isn't: '56' on line 2266 -- Looks like a reference, but probably isn't: '57' on line 2268 -- Looks like a reference, but probably isn't: '58' on line 2271 -- Looks like a reference, but probably isn't: '59' on line 2273 -- Looks like a reference, but probably isn't: '60' on line 2275 -- Looks like a reference, but probably isn't: '61' on line 2277 -- Looks like a reference, but probably isn't: '62' on line 2279 -- Looks like a reference, but probably isn't: '63' on line 2281 -- Looks like a reference, but probably isn't: '64' on line 2283 -- Looks like a reference, but probably isn't: '65' on line 2285 -- Looks like a reference, but probably isn't: '66' on line 2287 == Unused Reference: 'Grover96' is defined on line 1631, but no explicit reference was found in the text == Unused Reference: 'Katz16' is defined on line 1636, but no explicit reference was found in the text == Unused Reference: 'SPHINCS' is defined on line 1647, but no explicit reference was found in the text == Unused Reference: 'STMGMT' is defined on line 1654, but no explicit reference was found in the text ** 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 (~~), 8 warnings (==), 72 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: August 27, 2018 Cisco Systems 6 February 23, 2018 8 Hash-Based Signatures 9 draft-mcgrew-hash-sigs-09 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 https://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 August 27, 2018. 42 Copyright Notice 44 Copyright (c) 2018 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 (https://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 . . . . . . . . . . . . . . . . . . . . . . . . . . 5 63 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 5 64 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 5 65 3.1.2. Functions . . . . . . . . . . . . . . . . . . . . . . 6 66 3.1.3. Strings of w-bit elements . . . . . . . . . . . . . . 6 67 3.2. Security string . . . . . . . . . . . . . . . . . . . . . 7 68 3.3. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 9 69 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 9 70 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 9 71 4.2. Parameter Sets . . . . . . . . . . . . . . . . . . . . . 10 72 4.3. Private Key . . . . . . . . . . . . . . . . . . . . . . . 11 73 4.4. Public Key . . . . . . . . . . . . . . . . . . . . . . . 11 74 4.5. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 12 75 4.6. Signature Generation . . . . . . . . . . . . . . . . . . 13 76 4.7. Signature Verification . . . . . . . . . . . . . . . . . 14 77 5. Leighton Micali Signatures . . . . . . . . . . . . . . . . . 15 78 5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 16 79 5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 16 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 . . . . . . . . . . . . . . . . . . . . . 22 86 6.2. Signature Generation . . . . . . . . . . . . . . . . . . 22 87 6.3. Signature Verification . . . . . . . . . . . . . . . . . 23 88 7. Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 89 8. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 27 90 9. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 91 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 92 11. Intellectual Property . . . . . . . . . . . . . . . . . . . . 31 93 11.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 31 94 12. Security Considerations . . . . . . . . . . . . . . . . . . . 31 95 12.1. Stateful signature algorithm . . . . . . . . . . . . . . 33 96 12.2. Security of LM-OTS Checksum . . . . . . . . . . . . . . 34 98 13. Comparison with other work . . . . . . . . . . . . . . . . . 34 99 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 35 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 35 101 15.1. Normative References . . . . . . . . . . . . . . . . . . 35 102 15.2. Informative References . . . . . . . . . . . . . . . . . 36 103 Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 37 104 Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 38 105 Appendix C. An iterative algorithm for computing an LMS public 106 key . . . . . . . . . . . . . . . . . . . . . . . . 39 107 Appendix D. Method for deriving authentication path for a 108 signature . . . . . . . . . . . . . . . . . . . . . 40 109 Appendix E. Example Implementation . . . . . . . . . . . . . . . 40 110 Appendix F. Parameter Set Recommendations . . . . . . . . . . . 41 111 Appendix G. Test Cases . . . . . . . . . . . . . . . . . . . . . 42 112 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 53 114 1. Introduction 116 One-time signature systems, and general purpose signature systems 117 built out of one-time signature systems, have been known since 1979 118 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 119 benefited from renewed attention in the last decade. The 120 characteristics of these signature systems are small private and 121 public keys and fast signature generation and verification, but large 122 signatures and moderately slow key generation (in comparison with RSA 123 and ECDSA). Private keys can be made very small by appropriate key 124 generation, for example, as described in Appendix A. In recent years 125 there has been interest in these systems because of their post- 126 quantum security and their suitability for compact verifier 127 implementations. 129 This note describes the Leighton and Micali adaptation [USPTO5432852] 130 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 131 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 132 signature system [Merkle79] with enough specificity to ensure 133 interoperability between implementations. 135 A signature system provides asymmetric message authentication. The 136 key generation algorithm produces a public/private key pair. A 137 message is signed by a private key, producing a signature, and a 138 message/signature pair can be verified by a public key. A One-Time 139 Signature (OTS) system can be used to sign one message securely, but 140 will become insecure if more than one is signed with the same public/ 141 private key pair. An N-time signature system can be used to sign N 142 or fewer messages securely. A Merkle tree signature scheme is an 143 N-time signature system that uses an OTS system as a component. 145 In this note we describe the Leighton-Micali Signature (LMS) system, 146 which is a variant of the Merkle scheme, and a Hierarchical Signature 147 System (HSS) built on top of it that can efficiently scale to larger 148 numbers of signatures. We denote the one-time signature scheme 149 incorporated in LMS as LM-OTS. This note is structured as follows. 150 Notation is introduced in Section 3. The LM-OTS signature system is 151 described in Section 4, and the LMS and HSS N-time signature systems 152 are described in Section 5 and Section 6, respectively. Sufficient 153 detail is provided to ensure interoperability. The public formats 154 are described in Section 7. The rationale for design decisions are 155 given in Section 8. The changes made to this document over previous 156 versions is listed in Section 9. The IANA registry for these 157 signature systems is described in Section 10. Intellectual Property 158 issues are discussed in Section 11. Security considerations are 159 presented in Section 12. 161 1.1. Conventions Used In This Document 163 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 164 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 165 document are to be interpreted as described in [RFC2119]. 167 2. Interface 169 The LMS signing algorithm is stateful; it modifies and updates the 170 private key as a side effect of generating a signature. Once a 171 particular value of the private key is used to sign one message, it 172 MUST NOT be used to sign another. 174 The key generation algorithm takes as input an indication of the 175 parameters for the signature system. If it is successful, it 176 returns both a private key and a public key. Otherwise, it 177 returns an indication of failure. 179 The signing algorithm takes as input the message to be signed and 180 the current value of the private key. If successful, it returns a 181 signature and the next value of the private key, if there is such 182 a value. After the private key of an N-time signature system has 183 signed N messages, the signing algorithm returns the signature and 184 an indication that there is no next value of the private key that 185 can be used for signing. If unsuccessful, it returns an 186 indication of failure. 188 The verification algorithm takes as input the public key, a 189 message, and a signature, and returns an indication of whether or 190 not the signature and message pair are valid. 192 A message/signature pair are valid if the signature was returned by 193 the signing algorithm upon input of the message and the private key 194 corresponding to the public key; otherwise, the signature and message 195 pair are not valid with probability very close to one. 197 3. Notation 199 3.1. Data Types 201 Bytes and byte strings are the fundamental data types. A single byte 202 is denoted as a pair of hexadecimal digits with a leading "0x". A 203 byte string is an ordered sequence of zero or more bytes and is 204 denoted as an ordered sequence of hexadecimal characters with a 205 leading "0x". For example, 0xe534f0 is a byte string with a length 206 of three. An array of byte strings is an ordered set, indexed 207 starting at zero, in which all strings have the same length. 209 Unsigned integers are converted into byte strings by representing 210 them in network byte order. To make the number of bytes in the 211 representation explicit, we define the functions u8str(X), u16str(X), 212 and u32str(X), which take a non-negative integer X as input and 213 return one, two, and four byte strings, respectively. We also make 214 use of the function strTou32(S), which takes a four byte string S as 215 input and returns a non-negative integer; the identity 216 u32str(strTou32(S)) = S holds for any four-byte string S. 218 3.1.1. Operators 220 When a and b are real numbers, mathematical operators are defined as 221 follows: 223 ^ : a ^ b denotes the result of a raised to the power of b 225 * : a * b denotes the product of a multiplied by b 227 / : a / b denotes the quotient of a divided by b 229 % : a % b denotes the remainder of the integer division of a by b 231 + : a + b denotes the sum of a and b 233 - : a - b denotes the difference of a and b 235 The standard order of operations is used when evaluating arithmetic 236 expressions. 238 When B is a byte and i is an integer, then B >> i denotes the logical 239 right-shift operation by i positions. Similarly, B << i denotes the 240 logical left-shift operation. 242 If S and T are byte strings, then S || T denotes the concatenation of 243 S and T. If S and T are equal length byte strings, then S AND T 244 denotes the bitwise logical and operation. 246 The i^th element in an array A is denoted as A[i]. 248 3.1.2. Functions 250 If r is a non-negative real number, then we define the following 251 functions: 253 ceil(r) : returns the smallest integer larger than r 255 floor(r) : returns the largest integer smaller than r 257 lg(r) : returns the base-2 logarithm of r 259 3.1.3. Strings of w-bit elements 261 If S is a byte string, then byte(S, i) denotes its i^th byte, where 262 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 263 the range of bytes from the i^th to the j^th byte, inclusive. For 264 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 265 2) is 0x0406. 267 A byte string can be considered to be a string of w-bit unsigned 268 integers; the correspondence is defined by the function coef(S, i, w) 269 as follows: 271 If S is a string, i is a positive integer, and w is a member of the 272 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 273 is interpreted as a sequence of w-bit values. That is, 275 coef(S, i, w) = (2^w - 1) AND 276 ( byte(S, floor(i * w / 8)) >> 277 (8 - (w * (i % (8 / w)) + w)) ) 279 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 280 coef(S, 0, 4) is 1. 282 S (represented as bits) 283 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 284 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 285 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 286 ^ 287 | 288 coef(S, 7, 1) 290 S (represented as four-bit values) 291 +-----------+-----------+-----------+-----------+ 292 | 1 | 2 | 3 | 4 | 293 +-----------+-----------+-----------+-----------+ 294 ^ 295 | 296 coef(S, 0, 4) 298 The return value of coef is an unsigned integer. If i is larger than 299 the number of w-bit values in S, then coef(S, i, w) is undefined, and 300 an attempt to compute that value should raise an error. 302 3.2. Security string 304 To improve security against attacks that amortize their effort 305 against multiple invocations of the hash function, Leighton and 306 Micali introduce a "security string" that is distinct for each 307 invocation of that function. Whenever this process computes a hash, 308 the string being hashed will start with a string formed from the 309 below fields. These fields will appear in fixed locations in the 310 value we compute the hash of, and so we list where in the hash these 311 fields would be present. These fields are: 313 I - a 16 byte identifier for the LMS public/private key pair. It 314 MUST be chosen uniformly at random, or via a pseudorandom process, 315 at the time that a key pair is generated, in order to minimize the 316 probability that any specific value of I be used for a large 317 number of different LMS private keys. This is always bytes 0-15 318 of the hash. 320 r - in the LMS N-time signature scheme, the node number r 321 associated with a particular node of a hash tree is used as an 322 input to the hash used to compute that node. This value is 323 represented as a 32-bit (four byte) unsigned integer in network 324 byte order. Either r or q (depending on the domain separation 325 parameter) will be bytes 16-19 of the hash. 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. Either r or q (depending on the domain separation 333 parameter) will be bytes 16-19 of the hash. 335 D - a domain separation parameter, which is a two byte identifier 336 that takes on different values in the different contexts in which 337 the hash function is invoked. D occurs in bytes 20, 21 of the 338 hash, and takes on the following values: 340 D_PBLC = 0x8080 when computing the hash of all of the iterates 341 in the LM-OTS algorithm 343 D_MESG = 0x8181 when computing the hash of the message in the 344 LM-OTS algorithms 346 D_LEAF = 0x8282 when computing the hash of the leaf of an LMS 347 tree 349 D_INTR = 0x8383 when computing the hash of an interior node of 350 an LMS tree 352 i = a value between 0 and 264; this is used in the LM-OTS 353 scheme, when either computing the iterations of the Winternitz 354 chain, or when using the suggested LM-OTS private key 355 generation process. The value is also the index of the LM-OTS 356 private key element upon which H is being applied. It is 357 represented as a 16-bit (two byte) unsigned integer in network 358 byte order. 360 j - in the LM-OTS scheme, j is the iteration number used when the 361 private key element is being iteratively hashed. It is 362 represented as an 8-bit (one byte) unsigned integer and is present 363 if D is a value between 0 and 264. If present, it occurs at byte 364 22 of the hash. 366 C - an n-byte randomizer that is included with the message 367 whenever it is being hashed to improve security. C MUST be chosen 368 uniformly at random, or via a pseudorandom process. It is present 369 if D=D_MESG, and it occurs at bytes 22 to 21+n of the hash. 371 3.3. Typecodes 373 A typecode is an unsigned integer that is associated with a 374 particular data format. The format of the LM-OTS, LMS, and HSS 375 signatures and public keys all begin with a typecode that indicates 376 the precise details used in that format. These typecodes are 377 represented as four-byte unsigned integers in network byte order; 378 equivalently, they are XDR enumerations (see Section 7). 380 4. LM-OTS One-Time Signatures 382 This section defines LM-OTS signatures. The signature is used to 383 validate the authenticity of a message by associating a secret 384 private key with a shared public key. These are one-time signatures; 385 each private key MUST be used at most one time to sign any given 386 message. 388 As part of the signing process, a digest of the original message is 389 computed using the cryptographic hash function H (see Section 4.1), 390 and the resulting digest is signed. 392 In order to facilitate its use in an N-time signature system, the LM- 393 OTS key generation, signing, and verification algorithms all take as 394 input a diversification parameter q (which is used as part of the 395 security string, as listed in Section 3.2. When the LM-OTS signature 396 system is used outside of an N-time signature system, this value 397 SHOULD be set to the all-zero value. 399 4.1. Parameters 401 The signature system uses the parameters n and w, which are both 402 positive integers. The algorithm description also makes use of the 403 internal parameters p and ls, which are dependent on n and w. These 404 parameters are summarized as follows: 406 n : the number of bytes of the output of the hash function 408 w : the width (in bits) of the Winternitz coefficients; it is a 409 member of the set { 1, 2, 4, 8 } 411 p : the number of n-byte string elements that make up the LM-OTS 412 signature 414 ls : the number of left-shift bits used in the checksum function 415 Cksm (defined in Section 4.5). 417 H : a second-preimage-resistant cryptographic hash function that 418 accepts byte strings of any length, and returns an n-byte string. 420 For more background on the cryptographic security requirements on H, 421 see the Section 12. 423 The value of n is determined by the hash function selected for use as 424 part of the LM-OTS algorithm; the choice of this value has a strong 425 effect on the security of the system. The parameter w determines the 426 length of the Winternitz chains computed as a part of the OTS 427 signature (which involve 2^w-1 invocations of the hash function); it 428 has little effect on security. Increasing w will shorten the 429 signature, but at a cost of a larger computation to generate and 430 verify a signature. The values of p and ls are dependent on the 431 choices of the parameters n and w, as described in Appendix B. A 432 table illustrating various combinations of n, w, p, and ls is 433 provided in Table 1. 435 4.2. Parameter Sets 437 To fully describe a LM-OTS signature method, the parameters n and w, 438 as well as the function H, MUST be specified. This section defines 439 several LM-OTS methods, each of which is identified by a name. The 440 values for p and ls are provided as a convenience; the formal method 441 of computing them is given in Appendix B. 443 The value of w describes a space/time trade-off; increasing the value 444 of w will cause the signature to shrink (by decreasing the value of 445 p) while increasing the amount of time needed to perform operations 446 with it (generate the public key, generate and verify the signature); 447 in general, the LM-OTS signature is n*p bytes long, and public key 448 generation will take p*(2^w-1)+1 hash computations (and signature 449 generation and verification will take about half that on average). 451 +---------------------+--------+----+---+-----+----+ 452 | Name | H | n | w | p | ls | 453 +---------------------+--------+----+---+-----+----+ 454 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 455 | | | | | | | 456 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 457 | | | | | | | 458 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 459 | | | | | | | 460 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 461 +---------------------+--------+----+---+-----+----+ 463 Table 1 465 Here SHA256 denotes the NIST standard hash function [FIPS180]. 467 4.3. Private Key 469 The format of the LM-OTS private key is an internal matter to the 470 implementation, and this document does not attempt to define it. One 471 possibility is that the private key may consist of a typecode 472 indicating the particular LM-OTS algorithm, an array x[] containing p 473 n-byte strings, and the 16 byte string I and the 4 byte string q. 474 This private key MUST be used to sign (at most) one message. The 475 following algorithm shows pseudocode for generating a private key. 477 Algorithm 0: Generating a Private Key 479 1. retrieve the value q from the type, and the value I the 16 byte 480 identifier of the LMS public/private keypair that this LM-OTS private 481 key will be used with 483 2. set type to the typecode of the algorithm 485 3. set n and p according to the typecode and Table 1 487 4. compute the array x as follows: 488 for ( i = 0; i < p; i = i + 1 ) { 489 set x[i] to a uniformly random n-byte string 490 } 492 5. return u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] 494 An implementation MAY use a pseudorandom method to compute x[i], as 495 suggested in [Merkle79], page 46. The details of the pseudorandom 496 method do not affect interoperability, but the cryptographic strength 497 MUST match that of the LM-OTS algorithm. Appendix A provides an 498 example of a pseudorandom method for computing the LM-OTS private 499 key. 501 4.4. Public Key 503 The LM-OTS public key is generated from the private key by 504 iteratively applying the function H to each individual element of x, 505 for 2^w - 1 iterations, then hashing all of the resulting values. 507 The public key is generated from the private key using the following 508 algorithm, or any equivalent process. 510 Algorithm 1: Generating a One Time Signature Public Key From a 511 Private Key 513 1. set type to the typecode of the algorithm 515 2. set the integers n, p, and w according to the typecode and Table 1 517 3. determine x, I and q from the private key 519 4. compute the string K as follows: 520 for ( i = 0; i < p; i = i + 1 ) { 521 tmp = x[i] 522 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 523 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 524 } 525 y[i] = tmp 526 } 527 K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) 529 5. return u32str(type) || I || u32str(q) || K 531 The public key is the value returned by Algorithm 1. 533 4.5. Checksum 535 A checksum is used to ensure that any forgery attempt that 536 manipulates the elements of an existing signature will be detected. 537 The security property that it provides is detailed in Section 12. 538 The checksum function Cksm is defined as follows, where S denotes the 539 n-byte string that is input to that function, and the value sum is a 540 16-bit unsigned integer: 542 Algorithm 2: Checksum Calculation 544 sum = 0 545 for ( i = 0; i < (n*8/w); i = i + 1 ) { 546 sum = sum + (2^w - 1) - coef(S, i, w) 547 } 548 return (sum << ls) 550 Because of the left-shift operation, the rightmost bits of the result 551 of Cksm will often be zeros. Due to the value of p, these bits will 552 not be used during signature generation or verification. 554 4.6. Signature Generation 556 The LM-OTS signature of a message is generated by first prepending 557 the LM key identifier I, the LM leaf identifier q, the value D_MESG 558 and the randomizer C to the message, then computing the hash, and 559 then concatenating the checksum of the hash to the hash itself, then 560 considering the resulting value as a sequence of w-bit values, and 561 using each of the w-bit values to determine the number of times to 562 apply the function H to the corresponding element of the private key. 563 The outputs of the function H are concatenated together and returned 564 as the signature. The pseudocode for this procedure is shown below. 566 Algorithm 3: Generating a One Time Signature From a Private Key and a 567 Message 569 1. set type to the typecode of the algorithm 571 2. set n, p, and w according to the typecode and Table 1 573 3. determine x, I and q from the private key 575 4. set C to a uniformly random n-byte string 577 5. compute the array y as follows: 578 Q = H(I || u32str(q) || u16str(D_MESG) || C || message) 579 for ( i = 0; i < p; i = i + 1 ) { 580 a = coef(Q || Cksm(Q), i, w) 581 tmp = x[i] 582 for ( j = 0; j < a; j = j + 1 ) { 583 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 584 } 585 y[i] = tmp 586 } 588 6. return u32str(type) || C || y[0] || ... || y[p-1] 590 Note that this algorithm results in a signature whose elements are 591 intermediate values of the elements computed by the public key 592 algorithm in Section 4.4. 594 The signature is the string returned by Algorithm 3. Section 7 595 specifies the typecode and more formally defines the encoding and 596 decoding of the string. 598 4.7. Signature Verification 600 In order to verify a message with its signature (an array of n-byte 601 strings, denoted as y), the receiver must "complete" the chain of 602 iterations of H using the w-bit coefficients of the string resulting 603 from the concatenation of the message hash and its checksum. This 604 computation should result in a value that matches the provided public 605 key. 607 Algorithm 4a: Verifying a Signature and Message Using a Public Key 609 1. if the public key is not at least four bytes long, return INVALID 611 2. parse pubtype, I, q, and K from the public key as follows: 612 a. pubtype = strTou32(first 4 bytes of public key) 614 b. if the public key is not exactly 24 + n bytes long, 615 return INVALID 617 c. I = next 16 bytes of public key 619 d. q = strTou32(next 4 bytes of public key) 621 e. K = next n bytes of public key 623 3. compute the public key candidate Kc from the signature, 624 message, and the identifiers I and q obtained from the 625 public key, using Algorithm 4b. If Algorithm 4b returns 626 INVALID, then return INVALID. 628 4. if Kc is equal to K, return VALID; otherwise, return INVALID 630 Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, 631 Message, Signature Typecode Type , and identifiers I, q 633 1. if the signature is not at least four bytes long, return INVALID 635 2. parse sigtype, C, and y from the signature as follows: 636 a. sigtype = strTou32(first 4 bytes of signature) 638 b. if sigtype is not equal to pubtype, return INVALID 640 c. set n and p according to the pubtype and Table 1; if the 641 signature is not exactly 4 + n * (p+1) bytes long, return INVALID 643 d. C = next n bytes of signature 645 e. y[0] = next n bytes of signature 646 y[1] = next n bytes of signature 647 ... 648 y[p-1] = next n bytes of signature 650 3. compute the string Kc as follows 651 Q = H(I || u32str(q) || u16str(D_MESG) || C || message) 652 for ( i = 0; i < p; i = i + 1 ) { 653 a = coef(Q || Cksm(Q), i, w) 654 tmp = y[i] 655 for ( j = a; j < 2^w - 1; j = j + 1 ) { 656 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 657 } 658 z[i] = tmp 659 } 660 Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1]) 662 4. return Kc 664 5. Leighton Micali Signatures 666 The Leighton Micali Signature (LMS) method can sign a potentially 667 large but fixed number of messages. An LMS system uses two 668 cryptographic components: a one-time signature method and a hash 669 function. Each LMS public/private key pair is associated with a 670 perfect binary tree, each node of which contains an m-byte value, 671 where m is the output length of the hash function. Each leaf of the 672 tree contains the value of the public key of an LM-OTS public/private 673 key pair. The value contained by the root of the tree is the LMS 674 public key. Each interior node is computed by applying the hash 675 function to the concatenation of the values of its children nodes. 677 Each node of the tree is associated with a node number, an unsigned 678 integer that is denoted as node_num in the algorithms below, which is 679 computed as follows. The root node has node number 1; for each node 680 with node number N < 2^h, its left child has node number 2*N, while 681 its right child has node number 2*N+1. The result of this is that 682 each node within the tree will have a unique node number, and the 683 leaves will have node numbers 2^h, (2^h)+1, (2^h)+2, ..., 684 (2^h)+(2^h)-1. In general, the j^th node at level L has node number 685 2^L + j. The node number can conveniently be computed when it is 686 needed in the LMS algorithms, as described in those algorithms. 688 5.1. Parameters 690 An LMS system has the following parameters: 692 h : the height (number of levels - 1) in the tree, and 694 m : the number of bytes associated with each node. 696 H : a second-preimage-resistant cryptographic hash function that 697 accepts byte strings of any length, and returns an m-byte string. 698 H SHOULD be the same as in Section 4.1, but MAY be different. 700 There are 2^h leaves in the tree. The hash function used within the 701 LMS system SHOULD be the same as the hash function used within the 702 LM-OTS system used to generate the leaves. 704 +--------------------+--------+----+----+ 705 | Name | H | m | h | 706 +--------------------+--------+----+----+ 707 | LMS_SHA256_M32_H5 | SHA256 | 32 | 5 | 708 | | | | | 709 | LMS_SHA256_M32_H10 | SHA256 | 32 | 10 | 710 | | | | | 711 | LMS_SHA256_M32_H15 | SHA256 | 32 | 15 | 712 | | | | | 713 | LMS_SHA256_M32_H20 | SHA256 | 32 | 20 | 714 | | | | | 715 | LMS_SHA256_M32_H25 | SHA256 | 32 | 25 | 716 +--------------------+--------+----+----+ 718 Table 2 720 5.2. LMS Private Key 722 The format of the LMS private key is an internal matter to the 723 implementation, and this document does not attempt to define it. One 724 possibility is that it may consist of an array OTS_PRIV[] of 2^h LM- 725 OTS private keys, and the leaf number q of the next LM-OTS private 726 key that has not yet been used. The q^th element of OTS_PRIV[] is 727 generated using Algorithm 0 with the identifiers I, q. The leaf 728 number q is initialized to zero when the LMS private key is created. 729 The process is as follows: 731 Algorithm 5: Computing an LMS Private Key. 733 1. determine h and m from the typecode and Table 2. 735 2. compute the array OTS_PRIV[] as follows: 736 for ( q = 0; q < 2^h; q = q + 1) { 737 OTS_PRIV[q] = LM-OTS private key with identifiers I, q 738 } 740 3. q = 0 742 An LMS private key MAY be generated pseudorandomly from a secret 743 value, in which case the secret value MUST be at least m bytes long, 744 be uniformly random, and MUST NOT be used for any other purpose than 745 the generation of the LMS private key. The details of how this 746 process is done do not affect interoperability; that is, the public 747 key verification operation is independent of these details. 748 Appendix A provides an example of a pseudorandom method for computing 749 an LMS private key. 751 The signature generation logic uses q as the next leaf to use, hence 752 step 3 starts it off at the left-most one. 754 5.3. LMS Public Key 756 An LMS public key is defined as follows, where we denote the public 757 key final hash value (namely, the K value computed in algorithm 1) 758 associated with the i^th LM-OTS private key as OTS_PUB_HASH[i], with 759 i ranging from 0 to (2^h)-1. Each instance of an LMS public/private 760 key pair is associated with a balanced binary tree, and the nodes of 761 that tree are indexed from 1 to 2^(h+1)-1. Each node is associated 762 with an m-byte string, and the string for the r^th node is denoted as 763 T[r] and is defined as 765 T[r]=/ H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h]) if r >= 2^h, 766 \ H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1]) otherwise. 768 The LMS public key is the string u32str(type) || u32str(otstype) || 769 I || T[1]. Section 7 specifies the format of the type variable. The 770 value otstype is the parameter set for the LM-OTS public/private 771 keypairs used. The value I is the private key identifier, and is the 772 value used for all computations for the same LMS tree. The value 773 T[1] can be computed via recursive application of the above equation, 774 or by any equivalent method. An iterative procedure is outlined in 775 Appendix C. 777 5.4. LMS Signature 779 An LMS signature consists of 781 the number q of the leaf associated with the LM-OTS signature, as 782 a four-byte unsigned integer in network byte order, 784 an LM-OTS signature, and 786 a typecode indicating the particular LMS algorithm, 788 an array of h m-byte values that is associated with the path 789 through the tree from the leaf associated with the LM-OTS 790 signature to the root. 792 Symbolically, the signature can be represented as u32str(q) || 793 ots_signature || u32str(type) || path[0] || path[1] || ... || 794 path[h-1]. Section 7 specifies the typecode and more formally 795 defines the format. The array of values contains the siblings of the 796 nodes on the path from the leaf to the root but does not contain the 797 nodes on the path themselves. The array for a tree with height h 798 will have h values. The first value is the sibling of the leaf, the 799 next value is the sibling of the parent of the leaf, and so on up the 800 path to the root. 802 5.4.1. LMS Signature Generation 804 To compute the LMS signature of a message with an LMS private key, 805 the signer first computes the LM-OTS signature of the message using 806 the leaf number of the next unused LM-OTS private key. The leaf 807 number q in the signature is set to the leaf number of the LMS 808 private key that was used in the signature. Before releasing the 809 signature, the leaf number q in the LMS private key MUST be 810 incremented, to prevent the LM-OTS private key from being used again. 811 If the LMS private key is maintained in nonvolatile memory, then the 812 implementation MUST ensure that the incremented value has been stored 813 before releasing the signature. The issue this tries to prevent is a 814 scenario where a) we generate a signature, using one LM-OTS private 815 key, and release it to the application, b) before we update the 816 nonvolatile memory, we crash, and c) we reboot, and generate a second 817 signature using the same LM-OTS private key; with two different 818 signatures using the same LM-OTS private key, someone could 819 potentially generate a forged signature of a third message. 821 The array of node values in the signature MAY be computed in any way. 822 There are many potential time/storage tradeoffs that can be applied. 823 The fastest alternative is to store all of the nodes of the tree and 824 set the array in the signature by copying them; pseudocode to do so 825 appears in Appendix D. The least storage intensive alternative is to 826 recompute all of the nodes for each signature. Note that the details 827 of this procedure are not important for interoperability; it is not 828 necessary to know any of these details in order to perform the 829 signature verification operation. The internal nodes of the tree 830 need not be kept secret, and thus a node-caching scheme that stores 831 only internal nodes can sidestep the need for strong protections. 833 Several useful time/storage tradeoffs are described in the 'Small- 834 Memory LM Schemes' section of [USPTO5432852]. 836 5.5. LMS Signature Verification 838 An LMS signature is verified by first using the LM-OTS signature 839 verification algorithm (Algorithm 4b) to compute the LM-OTS public 840 key from the LM-OTS signature and the message. The value of that 841 public key is then assigned to the associated leaf of the LMS tree, 842 then the root of the tree is computed from the leaf value and the 843 array path[] as described in Algorithm 6 below. If the root value 844 matches the public key, then the signature is valid; otherwise, the 845 signature fails. 847 Algorithm 6: LMS Signature Verification 849 1. if the public key is not at least eight bytes long, return 850 INVALID 852 2. parse pubtype, I, and T[1] from the public key as follows: 854 a. pubtype = strTou32(first 4 bytes of public key) 856 b. ots_typecode = strTou32(next 4 bytes of public key) 858 c. set m according to pubtype, based on Table 2 860 d. if the public key is not exactly 24 + m bytes 861 long, return INVALID 863 e. I = next 16 bytes of the public key 865 f. T[1] = next m bytes of the public key 867 3. compute the LMS Public Key Candidate Tc from the signature, 868 message, identifier, pubtype and ots_typecode using Algorithm 6b. 870 4. if Tc is equal to T[1], return VALID; otherwise, return INVALID 872 Algorithm 6b: Computing an LMS Public Key Candidate from a Signature, 873 Message, Identifier, and algorithm typecode 875 1. if the signature is not at least eight bytes long, return INVALID 877 2. parse sigtype, q, ots_signature, and path from the signature as 878 follows: 880 a. q = strTou32(first 4 bytes of signature) 882 b. otssigtype = strTou32(next 4 bytes of signature) 884 c. if otssigtype is not the OTS typecode from the public key, return INVALID 886 d. set n, p according to otssigtype and Table 1; if the 887 signature is not at least 12 + n * (p + 1) bytes long, return INVALID 889 e. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature 891 f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1)) 893 f. if sigtype is not the LM typecode from the public key, return INVALID 894 g. set m, h according to sigtype and Table 2 896 h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID 898 i. set path as follows: 899 path[0] = next m bytes of signature 900 path[1] = next m bytes of signature 901 ... 902 path[h-1] = next m bytes of signature 904 3. Kc = candidate public key computed by applying Algorithm 4b 905 to the signature ots_signature, the message, and the 906 identifiers I, q 908 4. compute the candidate LMS root value Tc as follows: 909 node_num = 2^h + q 910 tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) 911 i = 0 912 while (node_num > 1) { 913 if (node_num is odd): 914 tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) 915 else: 916 tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i]) 917 node_num = node_num/2 918 i = i + 1 919 } 920 Tc = tmp 922 5. return Tc 924 6. Hierarchical signatures 926 In scenarios where it is necessary to minimize the time taken by the 927 public key generation process, a Hierarchical N-time Signature System 928 (HSS) can be used. Leighton and Micali describe a scheme in which an 929 LMS public key is used to sign a second LMS public key, which is then 930 distributed along with the signatures generated with the second 931 public key [USPTO5432852]. This hierarchical scheme, which we 932 describe in this section, uses an LMS scheme as a component. HSS, in 933 essence, utilizes a tree of LMS trees, in which the HSS public key 934 contains the public key of the LMS tree at the root, and an HSS 935 signature is associated with a path from the root of the HSS tree to 936 one of its leaves. Compared to LMS, HSS has a much reduced public 937 key generation time, as only the root tree needs to be generated 938 prior to the distribution of the HSS public key. 940 Each level of the hierarchy is associated with a distinct LMS public 941 key, private key, signature, and identifier. The number of levels is 942 denoted L, and is between one and eight, inclusive. The following 943 notation is used, where i is an integer between 0 and L-1 inclusive, 944 and the root of the hierarchy is level 0: 946 prv[i] is the LMS private key of the i^th level, 948 pub[i] is the LMS public key of the i^th level (which includes the 949 identifier I as well as the key value K), 951 sig[i] is the LMS signature of the i^th level, 953 In this section, we say that an N-time private key is exhausted when 954 it has generated N signatures, and thus it can no longer be used for 955 signing. 957 HSS allows L=1, in which case the HSS public key and signature 958 formats are essentially the LMS public key and signature formats, 959 prepended by a fixed field. Since HSS with L=1 has very little 960 overhead compared to LMS, all implementations MUST support HSS in 961 order to maximize interoperability. 963 6.1. Key Generation 965 When an HSS key pair is generated, the key pair for each level MUST 966 have its own identifier I. 968 To generate an HSS private and public key pair, new LMS private and 969 public keys are generated for prv[i] and pub[i] for i=0, ... , L-1. 970 These key pairs, and their identifiers, MUST be generated 971 independently. 973 The public key of the HSS scheme consists of the number of levels L, 974 followed by pub[0], the public key of the top level. 976 The HSS private key consists of prv[0], ... , prv[L-1]. The values 977 pub[0] and prv[0] do not change, though the values of pub[i] and 978 prv[i] are dynamic for i > 0, and are changed by the signature 979 generation algorithm. 981 6.2. Signature Generation 983 To sign a message using the private key prv, the following steps are 984 performed: 986 If prv[L-1] is exhausted, then determine the smallest integer d 987 such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] 988 are exhausted. If d is equal to zero, then the HSS key pair is 989 exhausted, and it MUST NOT generate any more signatures. 991 Otherwise, the key pairs for levels d through L-1 must be 992 regenerated during the signature generation process, as follows. 993 For i from d to L-1, a new LMS public and private key pair with a 994 new identifier is generated, pub[i] and prv[i] are set to those 995 values, then the public key pub[i] is signed with prv[i-1], and 996 sig[i-1] is set to the resulting value. 998 The message is signed with prv[L-1], and the value sig[L-1] is set 999 to that result. 1001 The value of the HSS signature is set as follows. We let 1002 signed_pub_key denote an array of octet strings, where 1003 signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk- 1004 1, inclusive, where Nspk = L-1 denotes the number of signed public 1005 keys. Then the HSS signature is u32str(Nspk) || 1006 signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]. 1008 Note that the number of signed_pub_key elements in the signature 1009 is indicated by the value Nspk that appears in the initial four 1010 bytes of the signature. 1012 In the specific case of L=1, the format of an HSS signature is 1014 u32str(0) || sig[0] 1016 In the general case, the format of an HSS signature is 1018 u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk] 1020 which is equivalent to 1022 u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk] 1024 6.3. Signature Verification 1026 To verify a signature sig and message using the public key pub, the 1027 following steps are performed: 1029 The signature S is parsed into its components as follows: 1031 Nspk = strTou32(first four bytes of S) 1032 if Nspk+1 is not equal to the number of levels L in pub: 1033 return INVALID 1034 for (i = 0; i < Nspk; i = i + 1) { 1035 siglist[i] = next LMS signature parsed from S 1036 publist[i] = next LMS public key parsed from S 1037 } 1038 siglist[Nspk] = next LMS signature parsed from S 1040 key = pub 1041 for (i = 0; i < Nspk; i = i + 1) { 1042 sig = siglist[i] 1043 msg = publist[i] 1044 if (lms_verify(msg, key, sig) != VALID): 1045 return INVALID 1046 key = msg 1047 return lms_verify(message, key, siglist[Nspk]) 1049 Since the length of an LMS signature cannot be known without parsing 1050 it, the HSS signature verification algorithm makes use of an LMS 1051 signature parsing routine that takes as input a string consisting of 1052 an LMS signature with an arbitrary string appended to it, and returns 1053 both the LMS signature and the appended string. The latter is passed 1054 on for further processing. 1056 7. Formats 1058 The signature and public key formats are formally defined using the 1059 External Data Representation (XDR) [RFC4506] in order to provide an 1060 unambiguous, machine readable definition. For clarity, we also 1061 include a private key format as well, though consistency is not 1062 needed for interoperability and an implementation MAY use any private 1063 key format. Though XDR is used, these formats are simple and easy to 1064 parse without any special tools. An illustration of the layout of 1065 data in these objects is provided below. The definitions are as 1066 follows: 1068 /* one-time signatures */ 1070 enum ots_algorithm_type { 1071 lmots_reserved = 0, 1072 lmots_sha256_n32_w1 = 1, 1073 lmots_sha256_n32_w2 = 2, 1074 lmots_sha256_n32_w4 = 3, 1075 lmots_sha256_n32_w8 = 4 1076 }; 1078 typedef opaque bytestring32[32]; 1080 struct lmots_signature_n32_p265 { 1081 bytestring32 C; 1082 bytestring32 y[265]; 1083 }; 1085 struct lmots_signature_n32_p133 { 1086 bytestring32 C; 1087 bytestring32 y[133]; 1088 }; 1090 struct lmots_signature_n32_p67 { 1091 bytestring32 C; 1092 bytestring32 y[67]; 1093 }; 1095 struct lmots_signature_n32_p34 { 1096 bytestring32 C; 1097 bytestring32 y[34]; 1098 }; 1100 union ots_signature switch (ots_algorithm_type type) { 1101 case lmots_sha256_n32_w1: 1102 lmots_signature_n32_p265 sig_n32_p265; 1103 case lmots_sha256_n32_w2: 1104 lmots_signature_n32_p133 sig_n32_p133; 1105 case lmots_sha256_n32_w4: 1106 lmots_signature_n32_p67 sig_n32_p67; 1107 case lmots_sha256_n32_w8: 1108 lmots_signature_n32_p34 sig_n32_p34; 1109 default: 1110 void; /* error condition */ 1111 }; 1113 /* hash based signatures (hbs) */ 1115 enum hbs_algorithm_type { 1116 hbs_reserved = 0, 1117 lms_sha256_n32_h5 = 5, 1118 lms_sha256_n32_h10 = 6, 1119 lms_sha256_n32_h15 = 7, 1120 lms_sha256_n32_h20 = 8, 1121 lms_sha256_n32_h25 = 9, 1123 }; 1125 /* leighton micali signatures (lms) */ 1127 union lms_path switch (hbs_algorithm_type type) { 1128 case lms_sha256_n32_h5: 1129 bytestring32 path_n32_h5[5]; 1130 case lms_sha256_n32_h10: 1131 bytestring32 path_n32_h10[10]; 1132 case lms_sha256_n32_h15: 1133 bytestring32 path_n32_h15[15]; 1134 case lms_sha256_n32_h20: 1135 bytestring32 path_n32_h20[20]; 1136 case lms_sha256_n32_h25: 1137 bytestring32 path_n32_h25[25]; 1138 default: 1139 void; /* error condition */ 1140 }; 1142 struct lms_signature { 1143 unsigned int q; 1144 ots_signature lmots_sig; 1145 lms_path nodes; 1146 }; 1148 struct lms_key_n32 { 1149 ots_algorithm_type ots_alg_type; 1150 opaque I[16]; 1151 opaque K[32]; 1152 }; 1154 union hbs_public_key switch (hbs_algorithm_type type) { 1155 case lms_sha256_n32_h5: 1156 case lms_sha256_n32_h10: 1157 case lms_sha256_n32_h15: 1158 case lms_sha256_n32_h20: 1159 case lms_sha256_n32_h25: 1160 lms_key_n32 z_n32; 1161 default: 1162 void; /* error condition */ 1163 }; 1165 /* hierarchical signature system (hss) */ 1167 struct hss_public_key { 1168 unsigned int L; 1169 hbs_public_key pub; 1170 }; 1171 struct signed_public_key { 1172 hbs_signature sig; 1173 hbs_public_key pub; 1174 } 1176 struct hss_signature { 1177 signed_public_key signed_keys<7>; 1178 hbs_signature sig_of_message; 1179 }; 1181 Many of the objects start with a typecode. A verifier MUST check 1182 each of these typecodes, and a verification operation on a signature 1183 with an unknown type, or a type that does not correspond to the type 1184 within the public key MUST return INVALID. The expected length of a 1185 variable-length object can be determined from its typecode, and if an 1186 object has a different length, then any signature computed from the 1187 object is INVALID. 1189 8. Rationale 1191 The goal of this note is to describe the LM-OTS, LMS and HSS 1192 algorithms following the original references and present the modern 1193 security analysis of those algorithms. Other signature methods are 1194 out of scope and may be interesting follow-on work. 1196 We adopt the techniques described by Leighton and Micali to mitigate 1197 attacks that amortize their work over multiple invocations of the 1198 hash function. 1200 The values taken by the identifier I across different LMS public/ 1201 private key pairs are chosen randomly in order to improve security. 1202 The analysis of this method in [Fluhrer17] shows that we do not need 1203 uniqueness to ensure security; we do need to ensure that we don't 1204 have a large number of private keys that use the same I value. By 1205 randomly selecting 16 byte I values, the chance that, out of 2^64 1206 private keys, 4 or more of them will use the same I value is 1207 negligible (that is, has probability less than 2^-128). 1209 The reason this size was selected was to optimize the Winternitz hash 1210 chain operation. With the current settings, the value being hashed 1211 is exactly 55 bytes long (for a 32 byte hash function), which SHA-256 1212 can hash in a single hash compression operation. Other hash 1213 functions may be used in future specifications; all the ones that we 1214 will be likely to support (SHA-512/256 and the various SHA-3 hashes) 1215 would work well with a 16 byte I value. 1217 The signature and public key formats are designed so that they are 1218 relatively easy to parse. Each format starts with a 32-bit 1219 enumeration value that indicates the details of the signature 1220 algorithm and provides all of the information that is needed in order 1221 to parse the format. 1223 The Checksum Section 4.5 is calculated using a non-negative integer 1224 "sum", whose width was chosen to be an integer number of w-bit fields 1225 such that it is capable of holding the difference of the total 1226 possible number of applications of the function H as defined in the 1227 signing algorithm of Section 4.6 and the total actual number. In the 1228 case that the number of times H is applied is 0, the sum is (2^w - 1) 1229 * (8*n/w). Thus for the purposes of this document, which describes 1230 signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 1231 4, 8 }, the sum variable is a 16-bit non-negative integer for all 1232 combinations of n and w. The calculation uses the parameter ls 1233 defined in Section 4.1 and calculated in Appendix B, which indicates 1234 the number of bits used in the left-shift operation. 1236 9. History 1238 This is the eigth version of this draft. It has the following 1239 changes from previous versions: 1241 Version 08 1243 Added additional test vector with private key 1245 Added appendix with discussion of parameter set trade-offs 1247 Miscellaneous clarifications and typo corrections. 1249 Version 07 1251 Corrected the LMS public key format specification in section 5.3; 1252 the format listed in section 7 was correct. 1254 Corrected the LMS public key generation algorithm in appendix C. 1255 The hashes listed in section 5.3 were correct. 1257 Corrected the HSS signature verification algorithm in section 6.3. 1259 Miscellaneous clarifications and typo corrections. 1261 Version 06 1263 Modified the order of the values that were hashed to make it 1264 easier to prove security. 1266 Decreased the size of the I LMS public key identifier to 16 bytes. 1268 Version 05 1270 Clarified the L=1 specific case. 1272 Extended the parameter sets to include an H=25 option 1274 A large number of corrections and clarifications 1276 Added a comparison to XMSS and SPHINCS, and citations to those 1277 algorithms and to the recent Security Standardization Research 1278 2016 publications on the security of LMS and on the state 1279 management in hash-based signatures. 1281 Version 04 1283 Specified that, in the HSS method, the I value was computed from 1284 the I value of the parent LM tree. Previous versions had the I 1285 value extracted from the public key (which meant that all LM trees 1286 of a particular level and public key used the same I value) 1288 Changed the length of the I field based on the parameter set. As 1289 noted in the Rationale section, this allows an implementation to 1290 compute SHA256 n=32 based parameter sets significantly faster. 1292 Modified the XDR of an HSS signature not to use an array of LM 1293 signatures; LM signatures are variable length, and XDR doesn't 1294 support arrays of variable length structures. 1296 Changed the LMS registry to be in a consistent order with the LM- 1297 OTS parameter sets. Also, added LMS parameter sets with height 15 1298 trees 1300 Previous versions 1302 In Algorithms 3 and 4, the message was moved from the initial 1303 position of the input to the function H to the final position, in 1304 the computation of the intermediate variable Q. This was done to 1305 improve security by preventing an attacker that can find a 1306 collision in H from taking advantage of that fact via the forward 1307 chaining property of Merkle-Damgard. 1309 The Hierarchical Signature Scheme was generalized slightly so that 1310 it can use more than two levels. 1312 Several points of confusion were corrected; these had resulted 1313 from incomplete or inconsistent changes from the Merkle approach 1314 of the earlier draft to the Leighton-Micali approach. 1316 This section is to be removed by the RFC editor upon publication. 1318 10. IANA Considerations 1320 The Internet Assigned Numbers Authority (IANA) is requested to create 1321 two registries: one for OTS signatures, which includes all of the LM- 1322 OTS signatures as defined in Section 3, and one for Leighton-Micali 1323 Signatures, as defined in Section 4. Additions to these registries 1324 require that a specification be documented in an RFC or another 1325 permanent and readily available reference in sufficient detail that 1326 interoperability between independent implementations is possible. 1327 Each entry in the registry contains the following elements: 1329 a short name, such as "LMS_SHA256_M32_H10", 1331 a positive number, and 1333 a reference to a specification that completely defines the 1334 signature method test cases that can be used to verify the 1335 correctness of an implementation. 1337 Requests to add an entry to the registry MUST include the name and 1338 the reference. The number is assigned by IANA. Submitters SHOULD 1339 have their requests reviewed by the IRTF Crypto Forum Research Group 1340 (CFRG) at cfrg@ietf.org. Interested applicants that are unfamiliar 1341 with IANA processes should visit http://www.iana.org. 1343 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1344 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1345 are reserved for private use; no attempt will be made to prevent 1346 multiple sites from using the same value in different (and 1347 incompatible) ways [RFC2434]. 1349 The LM-OTS registry is as follows. 1351 +----------------------+-----------+--------------------+ 1352 | Name | Reference | Numeric Identifier | 1353 +----------------------+-----------+--------------------+ 1354 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 | 1355 | | | | 1356 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 | 1357 | | | | 1358 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 | 1359 | | | | 1360 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 | 1361 +----------------------+-----------+--------------------+ 1363 Table 3 1365 The LMS registry is as follows. 1367 +--------------------+-----------+--------------------+ 1368 | Name | Reference | Numeric Identifier | 1369 +--------------------+-----------+--------------------+ 1370 | LMS_SHA256_M32_H5 | Section 5 | 0x00000005 | 1371 | | | | 1372 | LMS_SHA256_M32_H10 | Section 5 | 0x00000006 | 1373 | | | | 1374 | LMS_SHA256_M32_H15 | Section 5 | 0x00000007 | 1375 | | | | 1376 | LMS_SHA256_M32_H20 | Section 5 | 0x00000008 | 1377 | | | | 1378 | LMS_SHA256_M32_H25 | Section 5 | 0x00000009 | 1379 +--------------------+-----------+--------------------+ 1381 Table 4 1383 An IANA registration of a signature system does not constitute an 1384 endorsement of that system or its security. 1386 11. Intellectual Property 1388 This draft is based on U.S. patent 5,432,852, which issued over 1389 twenty years ago and is thus expired. 1391 11.1. Disclaimer 1393 This document is not intended as legal advice. Readers are advised 1394 to consult with their own legal advisers if they would like a legal 1395 interpretation of their rights. 1397 The IETF policies and processes regarding intellectual property and 1398 patents are outlined in [RFC3979] and [RFC4879] and at 1399 https://datatracker.ietf.org/ipr/about. 1401 12. Security Considerations 1403 The hash function H MUST have second preimage resistance: it must be 1404 computationally infeasible for an attacker that is given one message 1405 M to be able to find a second message M' such that H(M) = H(M'). 1407 The security goal of a signature system is to prevent forgeries. A 1408 successful forgery occurs when an attacker who does not know the 1409 private key associated with a public key can find a message and 1410 signature that are valid with that public key (that is, the Signature 1411 Verification algorithm applied to that signature and message and 1412 public key will return VALID). Such an attacker, in the strongest 1413 case, may have the ability to forge valid signatures for an arbitrary 1414 number of other messages. 1416 LMS is provably secure in the random oracle model, where the hash 1417 compression function is considered the random oracle, as shown by 1418 [Fluhrer17]. Corollary 1 of that paper states: 1420 If we have no more than 2^64 randomly chosen LMS private keys, 1421 allow the attacker access to a signing oracle and a SHA-256 hash 1422 compression oracle, and allow a maximum of 2^120 hash compression 1423 computations, then the probability of an attacker being able to 1424 generate a single forgery against any of those LMS keys is less 1425 than 2^-129. 1427 The format of the inputs to the hash function H have the property 1428 that each invocation of that function has an input that is repeated 1429 by a small bounded number of other inputs (due to potential repeats 1430 of the I value), and in particular, will vary somewhere in the first 1431 23 bytes of the value being hashed. This property is important for a 1432 proof of security in the random oracle model. The formats used 1433 during key generation and signing are 1435 I || u32str(q) || u16str(i) || u8str(j) || tmp 1436 I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1] 1437 I || u32str(q) || u16str(D_MESG) || C || message 1438 I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h] 1439 I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1] 1440 I || u32str(q) || u16str(j) || u8str(0xff) || SEED 1442 Each hash type listed is distinct; at locations 20, 21 of each hash, 1443 there exists either a fixed value D_PBLC, D_MESG, D_LEAF, D_INTR, or 1444 a 16 bit value (i or j). These fixed values are distinct from each 1445 other, and large (over 32768), while the 16 bit values are small 1446 (currently no more than 265; possibly being slightly larger if larger 1447 hash functions are supported; hence the hash invocations with i/j 1448 will not collide any of the D_PBLC, D_MESG, D_LEAF, D_INTR hashes. 1449 The only other collision possibility is the Winternitz chain hash 1450 colliding with the recommended pseudorandom key generation process; 1451 here, at location 22, the Winternitz chain function has the value 1452 u8str(j), where j is a value between 0 and 254, while location 22 of 1453 the recommended pseudorandom key generation process has value 255. 1455 For the Winternitz chaining function, D_PBLC, and D_MESG, the value 1456 of I || u32str(q) is distinct for each LMS leaf (or equivalently, for 1457 each q value). For the Winternitz chaining function, the value of 1458 u16str(i) || u8str(j) is distinct for each invocation of H for a 1459 given leaf. For D_PBLC and D_MESG, the input format is used only 1460 once for each value of q, and thus distinctness is assured. The 1461 formats for D_INTR and D_LEAF are used exactly once for each value of 1462 r, which ensures their distinctness. For the recommended 1463 pseuddorandom key generation process, for a given value of I, q and j 1464 are distinct for each invocation of H. 1466 The value of I is chosen uniformly at random from the set of all 128 1467 bit strings. If 2^64 public keys are generated (and hence 2^64 1468 random I values), there is a nontrivial probability of a duplicate 1469 (which would imply duplicate prefixes. However, there will be an 1470 extremely high probability there will not be a four-way collision 1471 (that is, any I value used for four distinct LMS keys; probability < 1472 2^-132), and hence the number of repeats for any specific prefix will 1473 be limited to 3. This can be shown (in [Fluhrer17]) to have only a 1474 limited effect on the security of the system. 1476 12.1. Stateful signature algorithm 1478 The LMS signature system, like all N-time signature systems, requires 1479 that the signer maintain state across different invocations of the 1480 signing algorithm, to ensure that none of the component one-time 1481 signature systems are used more than once. This section calls out 1482 some important practical considerations around this statefulness. 1484 In a typical computing environment, a private key will be stored in 1485 non-volatile media such as on a hard drive. Before it is used to 1486 sign a message, it will be read into an application's Random Access 1487 Memory (RAM). After a signature is generated, the value of the 1488 private key will need to be updated by writing the new value of the 1489 private key into non-volatile storage. It is essential for security 1490 that the application ensure that this value is actually written into 1491 that storage, yet there may be one or more memory caches between it 1492 and the application. Memory caching is commonly done in the file 1493 system, and in a physical memory unit on the hard disk that is 1494 dedicated to that purpose. To ensure that the updated value is 1495 written to physical media, the application may need to take several 1496 special steps. In a POSIX environment, for instance, the O_SYNC flag 1497 (for the open() system call) will cause invocations of the write() 1498 system call to block the calling process until the data has been to 1499 the underlying hardware. However, if that hardware has its own 1500 memory cache, it must be separately dealt with using an operating 1501 system or device specific tool such as hdparm to flush the on-drive 1502 cache, or turn off write caching for that drive. Because these 1503 details vary across different operating systems and devices, this 1504 note does not attempt to provide complete guidance; instead, we call 1505 the implementer's attention to these issues. 1507 When hierarchical signatures are used, an easy way to minimize the 1508 private key synchronization issues is to have the private key for the 1509 second level resident in RAM only, and never write that value into 1510 non-volatile memory. A new second level public/private key pair will 1511 be generated whenever the application (re)starts; thus, failures such 1512 as a power outage or application crash are automatically 1513 accommodated. Implementations SHOULD use this approach wherever 1514 possible. 1516 12.2. Security of LM-OTS Checksum 1518 To show the security of LM-OTS checksum, we consider the signature y 1519 of a message with a private key x and let h = H(message) and 1520 c = Cksm(H(message)) (see Section 4.6). To attempt a forgery, an 1521 attacker may try to change the values of h and c. Let h' and c' 1522 denote the values used in the forgery attempt. If for some integer j 1523 in the range 0 to u, where u = ceil(8*n/w) is the size of the range 1524 that the checksum value can cover), inclusive, 1526 a' = coef(h', j, w), 1528 a = coef(h, j, w), and 1530 a' > a 1532 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1533 iteratively applying function F to the j^th term of the signature an 1534 additional (a' - a) times. However, as a result of the increased 1535 number of hashing iterations, the checksum value c' will decrease 1536 from its original value of c. Thus a valid signature's checksum will 1537 have, for some number k in the range u to (p-1), inclusive, 1539 b' = coef(c', k, w), 1541 b = coef(c, k, w), and 1543 b' < b 1545 Due to the one-way property of F, the attacker cannot easily compute 1546 F^b'(x[k]) from F^b(x[k]) = y[k]. 1548 13. Comparison with other work 1550 The eXtended Merkle Signature Scheme (XMSS) [XMSS] is similar to HSS 1551 in several ways. Both are stateful hash based signature schemes, and 1552 both use a hierarchical approach, with a Merkle tree at each level of 1553 the hierarchy. XMSS signatures are slightly shorter than HSS 1554 signatures, for equivalent security and an equal number of 1555 signatures. 1557 HSS has several advantages over XMSS. HSS operations are roughly 1558 four times faster than the comparable XMSS ones, when SHA256 is used 1559 as the underlying hash. This occurs because the hash operation done 1560 as a part of the Winternitz iterations dominates performance, and 1561 XMSS performs four compression function invocations (two for the PRF, 1562 two for the F function) where HSS need only perform one. 1563 Additionally, HSS is somewhat simpler, and it allows a single-level 1564 tree in a simple way (as described in Section 6.2). 1566 14. Acknowledgements 1568 Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric 1569 Osterweil, Ahmed Kosba, Russ Housley, Philip Lafrance, Alexander 1570 Truskovsky, Mark Peruzel for constructive suggestions and valuable 1571 detailed review. We especially acknowledge Jerry Solinas, Laurie 1572 Law, and Kevin Igoe, who pointed out the security benefits of the 1573 approach of Leighton and Micali [USPTO5432852] and Jonathan Katz, who 1574 gave us security guidance, and Bruno Couillard and Jim Goodman for an 1575 especially thorough review. 1577 15. References 1579 15.1. Normative References 1581 [FIPS180] National Institute of Standards and Technology, "Secure 1582 Hash Standard (SHS)", FIPS 180-4, March 2012. 1584 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1585 Requirement Levels", BCP 14, RFC 2119, 1586 DOI 10.17487/RFC2119, March 1997, 1587 . 1589 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1590 IANA Considerations Section in RFCs", RFC 2434, 1591 DOI 10.17487/RFC2434, October 1998, 1592 . 1594 [RFC3979] Bradner, S., Ed., "Intellectual Property Rights in IETF 1595 Technology", RFC 3979, DOI 10.17487/RFC3979, March 2005, 1596 . 1598 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1599 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1600 2006, . 1602 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1603 Procedure in RFC 3979", RFC 4879, DOI 10.17487/RFC4879, 1604 April 2007, . 1606 [USPTO5432852] 1607 Leighton, T. and S. Micali, "Large provably fast and 1608 secure digital signature schemes from secure hash 1609 functions", U.S. Patent 5,432,852, July 1995. 1611 15.2. Informative References 1613 [C:Merkle87] 1614 Merkle, R., "A Digital Signature Based on a Conventional 1615 Encryption Function", Lecture Notes in Computer 1616 Science crypto87vol, 1988. 1618 [C:Merkle89a] 1619 Merkle, R., "A Certified Digital Signature", Lecture Notes 1620 in Computer Science crypto89vol, 1990. 1622 [C:Merkle89b] 1623 Merkle, R., "One Way Hash Functions and DES", Lecture 1624 Notes in Computer Science crypto89vol, 1990. 1626 [Fluhrer17] 1627 Fluhrer, S., "Further analysis of a proposed hash-based 1628 signature standard", 1629 EPrint http://eprint.iacr.org/2017/553.pdf, 2017. 1631 [Grover96] 1632 Grover, L., "A fast quantum mechanical algorithm for 1633 database search", 28th ACM Symposium on the Theory of 1634 Computing p. 212, 1996. 1636 [Katz16] Katz, J., "Analysis of a proposed hash-based signature 1637 standard", Security Standardization Research (SSR) 1638 Conference 1639 http://www.cs.umd.edu/~jkatz/papers/HashBasedSigs- 1640 SSR16.pdf, 2016. 1642 [Merkle79] 1643 Merkle, R., "Secrecy, Authentication, and Public Key 1644 Systems", Stanford University Information Systems 1645 Laboratory Technical Report 1979-1, 1979. 1647 [SPHINCS] Bernstein, D., Hopwood, D., Hulsing, A., Lange, T., 1648 Niederhagen, R., Papachristadoulou, L., Schneider, M., 1649 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical 1650 Stateless Hash-Based Signatures.", Annual International 1651 Conference on the Theory and Applications of Cryptographic 1652 Techniques Springer., 2015. 1654 [STMGMT] McGrew, D., Fluhrer, S., Kampanakis, P., Gazdag, S., 1655 Butin, D., and J. Buchmann, "State Management for Hash- 1656 based Signatures.", Security Standardization Resarch (SSR) 1657 Conference 224., 2016. 1659 [XMSS] Buchmann, J., Dahmen, E., and . Andreas Hulsing, "XMSS-a 1660 practical forward secure signature scheme based on minimal 1661 security assumptions.", International Workshop on Post- 1662 Quantum Cryptography Springer Berlin., 2011. 1664 Appendix A. Pseudorandom Key Generation 1666 An implementation MAY use the following pseudorandom process for 1667 generating an LMS private key. 1669 SEED is an m-byte value that is generated uniformly at random at 1670 the start of the process, 1672 I is LMS key pair identifier, 1674 q denotes the LMS leaf number of an LM-OTS private key, 1676 x_q denotes the x array of private elements in the LM-OTS private 1677 key with leaf number q, 1679 j is an index of the private key element, and 1681 H is the hash function used in LM-OTS. 1683 The elements of the LM-OTS private keys are computed as: 1685 x_q[j] = H(I || u32str(q) || u16str(j) || u8str(0xff) || SEED). 1687 This process stretches the m-byte random value SEED into a (much 1688 larger) set of pseudorandom values, using a unique counter in each 1689 invocation of H. The format of the inputs to H are chosen so that 1690 they are distinct from all other uses of H in LMS and LM-OTS. A 1691 careful reader will note that this is similar to the hash we perform 1692 when iterating through the Winternitz chain; however in that chain, 1693 the iteration index will vary between 0 and 254 maximum (for W=8), 1694 while the corresponding value in this formula is 255. This algorithm 1695 is included in the proof of security in [Fluhrer17] and hence this 1696 method is safe when used within the LMS system; however any other 1697 cryptographical secure method of generating private keys would also 1698 be safe. 1700 Appendix B. LM-OTS Parameter Options 1702 The LM-OTS one time signature method uses several internal 1703 parameters, which are a function of the selected parameter set. 1704 These internal parameters set: 1706 p - This is the number of independent Winternitz chains used in 1707 the signature; it will be the number of w-bit digits needed to 1708 hold the n-bit hash (u in the below equations), along with the 1709 number of digits needed to hold the checksum (v in the below 1710 equations) 1712 ls - This is the size of the shift needed to move the checksum so 1713 that it appears in the checksum digits 1715 The parameters ls, and p are computed as follows: 1717 u = ceil(8*n/w) 1718 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1719 ls = 16 - (v * w) 1720 p = u + v 1722 Here u and v represent the number of w-bit fields required to contain 1723 the hash of the message and the checksum byte strings, respectively. 1724 And as the value of p is the number of w-bit elements of 1725 ( H(message) || Cksm(H(message)) ), it is also equivalently the 1726 number of byte strings that form the private key and the number of 1727 byte strings in the signature. The value 16 in the ls computation of 1728 ls corresponds to the 16 bits value used for the sum variable in 1729 Algorithm 2 in Section 4.5 1731 A table illustrating various combinations of n and w with the 1732 associated values of u, v, ls, and p is provided in Table 5. 1734 +---------+------------+-----------+-----------+-------+------------+ 1735 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1736 | Length | Parameter | Elements | Elements | Shift | Number of | 1737 | in | (w) | in Hash | in | (ls) | w-bit | 1738 | Bytes | | (u) | Checksum | | Elements | 1739 | (n) | | | (v) | | (p) | 1740 +---------+------------+-----------+-----------+-------+------------+ 1741 | 32 | 1 | 256 | 9 | 7 | 265 | 1742 | | | | | | | 1743 | 32 | 2 | 128 | 5 | 6 | 133 | 1744 | | | | | | | 1745 | 32 | 4 | 64 | 3 | 4 | 67 | 1746 | | | | | | | 1747 | 32 | 8 | 32 | 2 | 0 | 34 | 1748 +---------+------------+-----------+-----------+-------+------------+ 1750 Table 5 1752 Appendix C. An iterative algorithm for computing an LMS public key 1754 The LMS public key can be computed using the following algorithm or 1755 any equivalent method. The algorithm uses a stack of hashes for 1756 data. It also makes use of a hash function with the typical 1757 init/update/final interface to hash functions; the result of the 1758 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 1759 hash_update(N[n]), v = hash_final(), in that order, is identical to 1760 that of the invocation of H(N[1] || N[2] || ... || N[n]). 1762 Generating an LMS Public Key from an LMS Private Key 1764 for ( i = 0; i < 2^h; i = i + 1 ) { 1765 r = i + num_lmots_keys; 1766 temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i]) 1767 j = i; 1768 while (j % 2 == 1) { 1769 r = (r - 1)/2; 1770 j = (j-1) / 2; 1771 left_side = pop(data stack); 1772 temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp) 1773 } 1774 push temp onto the data stack 1775 } 1776 public_key = pop(data stack) 1778 Note that this pseudocode expects that all 2^h leaves of the tree 1779 have equal depth; that is, num_lmots_keys to be a power of 2. The 1780 maximum depth of the stack will be h-1 elements, that is, a total of 1781 (h-1)*n bytes; for the currently defined parameter sets, this will 1782 never be more than 768 bytes of data. 1784 Appendix D. Method for deriving authentication path for a signature 1786 The LMS signature consists of u32str(q) || ots_signature || 1787 u32str(type) || path[0] || path[1] || ... || path[h-1]. This 1788 appendix shows one method of constructing the path[i] values, 1789 assuming that the implementation has stored the T[] array that was 1790 used to construct the public key. Note that this is not the only 1791 possible method; other methods exist which don't assume that you have 1792 the entire T[] array in memory. To compute path[i], you perform the 1793 following computations: 1795 Generating an LMS Path Value 1797 r = 2^h + q 1798 temp = (r / 2^i) xor 1 1799 return path[i] = T[temp] 1801 where 'xor' is the bitwise exclusive-or operation. 1803 Appendix E. Example Implementation 1805 Two example implementations can be found online at 1806 http://github.com/davidmcgrew/hash-sigs/ and at 1807 http://github.com/cisco/hash-sigs. 1809 Appendix F. Parameter Set Recommendations 1811 As for guidance as to the number of LMS level, and the size of each, 1812 any discussion of performance is implementation specific. In 1813 general, the sole drawback for a single LMS tree is the time it takes 1814 to generate the public key; as every LM-OTS public key needs to be 1815 generated, the time this takes can be substantial. For a two level 1816 tree, only the top level LMS tree and the initial bottom level LMS 1817 tree needs to be generated initially (before the first signature is 1818 generated); this will in general be significantly quicker. 1820 To give a general idea on the trade-offs available, we include some 1821 measurements taken with the github.com/cisco/hash-sigs LMS 1822 implementation, taken on a 3.3 GHz Xeon processor, with threading 1823 enabled. We tried various parameter sets, all with W=8 (which 1824 minimizes signature size, while increasing time). These are here to 1825 give a guideline as to what's possible; for the computational time, 1826 your mileage may vary, depending on the computing resources you have. 1827 The machine I have does not have the SHA-256 extensions; you could 1828 possibly do significantly better. 1830 ParmSet KeyGenTime SigSize KeyLifetime 1831 15 6 sec 1616 30 seconds 1832 20 3 min 1776 16 minutes 1833 25 1.5 hour 1936 9 hours 1834 15/10 6 sec 3172 9 hours 1835 15/15 6 sec 3332 12 days 1836 20/10 3 min 3332 12 days 1837 20/15 3 min 3492 1 year 1838 25/10 1.5 hour 3492 1 year 1839 25/15 1.5 hour 3652 34 years 1841 ParmSet: this is the height of the Merkle tree(s); parameter sets 1842 listed as a single integer consists of a single Merkle tree of that 1843 height; parameter sets that consist of two trees are listed as x/y, 1844 with x being the height of the top level Merkle tree, and y being the 1845 bottom level. 1847 KeyGenTime: the measured key generation time; that is, the time 1848 needed to generate the public private key pair. 1850 SigSize: the size of a signature (in bytes) 1852 KeyLifetime: the lifetime of a key, assuming we generated 1000 1853 signatures per second. In practice, we're not likely to get anywhere 1854 close to 1000 signatures per second sustained; if you have a more 1855 appropriate figure for your scenario, this column is pretty easy to 1856 recompute. 1858 As for signature generation or verification times, those are 1859 moderately insensitive to the above parameter settings (except for 1860 the Winternitz setting, and the number of Merkle trees for 1861 verification). Tests on the same machine (without multithreading) 1862 gave approximately 4msec to sign a short message, 2.6msec to verify; 1863 these tests used a two level ParmSet; a single level would 1864 approximately halve the verification time. All times can be 1865 significantly improved (by maybe a factor of 8) by using a parameter 1866 set with W=4; however that also about doubles the signature size. 1868 Appendix G. Test Cases 1870 This section provides test cases that can be used to verify or debug 1871 an implementation. This data is formatted with the name of the 1872 elements on the left, and the value of the elements on the right, in 1873 hexadecimal. The concatenation of all of the values within a public 1874 key or signature produces that public key or signature, and values 1875 that do not fit within a single line are listed across successive 1876 lines. 1878 Test Case 1 Public Key 1880 -------------------------------------------- 1881 HSS public key 1882 levels 00000002 1883 -------------------------------------------- 1884 LMS type 00000005 # LM_SHA256_M32_H5 1885 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1886 I 61a5d57d37f5e46bfb7520806b07a1b8 1887 K 50650e3b31fe4a773ea29a07f09cf2ea 1888 30e579f0df58ef8e298da0434cb2b878 1889 -------------------------------------------- 1890 -------------------------------------------- 1891 Test Case 1 Message 1893 -------------------------------------------- 1894 Message 54686520706f77657273206e6f742064 |The powers not d| 1895 656c65676174656420746f2074686520 |elegated to the | 1896 556e6974656420537461746573206279 |United States by| 1897 2074686520436f6e737469747574696f | the Constitutio| 1898 6e2c206e6f722070726f686962697465 |n, nor prohibite| 1899 6420627920697420746f207468652053 |d by it to the S| 1900 74617465732c20617265207265736572 |tates, are reser| 1901 76656420746f20746865205374617465 |ved to the State| 1902 7320726573706563746976656c792c20 |s respectively, | 1903 6f7220746f207468652070656f706c65 |or to the people| 1904 2e0a |..| 1905 -------------------------------------------- 1907 Test Case 1 Signature 1909 -------------------------------------------- 1910 HSS signature 1911 Nspk 00000001 1912 sig[0]: 1913 -------------------------------------------- 1914 LMS signature 1915 q 00000005 1916 -------------------------------------------- 1917 LMOTS signature 1918 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1919 C d32b56671d7eb98833c49b433c272586 1920 bc4a1c8a8970528ffa04b966f9426eb9 1921 y[0] 965a25bfd37f196b9073f3d4a232feb6 1922 9128ec45146f86292f9dff9610a7bf95 1923 y[1] a64c7f60f6261a62043f86c70324b770 1924 7f5b4a8a6e19c114c7be866d488778a0 1925 y[2] e05fd5c6509a6e61d559cf1a77a970de 1926 927d60c70d3de31a7fa0100994e162a2 1927 y[3] 582e8ff1b10cd99d4e8e413ef469559f 1928 7d7ed12c838342f9b9c96b83a4943d16 1929 y[4] 81d84b15357ff48ca579f19f5e71f184 1930 66f2bbef4bf660c2518eb20de2f66e3b 1931 y[5] 14784269d7d876f5d35d3fbfc7039a46 1932 2c716bb9f6891a7f41ad133e9e1f6d95 1933 y[6] 60b960e7777c52f060492f2d7c660e14 1934 71e07e72655562035abc9a701b473ecb 1935 y[7] c3943c6b9c4f2405a3cb8bf8a691ca51 1936 d3f6ad2f428bab6f3a30f55dd9625563 1937 y[8] f0a75ee390e385e3ae0b906961ecf41a 1938 e073a0590c2eb6204f44831c26dd768c 1940 y[9] 35b167b28ce8dc988a3748255230cef9 1941 9ebf14e730632f27414489808afab1d1 1942 y[10] e783ed04516de012498682212b078105 1943 79b250365941bcc98142da13609e9768 1944 y[11] aaf65de7620dabec29eb82a17fde35af 1945 15ad238c73f81bdb8dec2fc0e7f93270 1946 y[12] 1099762b37f43c4a3c20010a3d72e2f6 1947 06be108d310e639f09ce7286800d9ef8 1948 y[13] a1a40281cc5a7ea98d2adc7c7400c2fe 1949 5a101552df4e3cccfd0cbf2ddf5dc677 1950 y[14] 9cbbc68fee0c3efe4ec22b83a2caa3e4 1951 8e0809a0a750b73ccdcf3c79e6580c15 1952 y[15] 4f8a58f7f24335eec5c5eb5e0cf01dcf 1953 4439424095fceb077f66ded5bec73b27 1954 y[16] c5b9f64a2a9af2f07c05e99e5cf80f00 1955 252e39db32f6c19674f190c9fbc506d8 1956 y[17] 26857713afd2ca6bb85cd8c107347552 1957 f30575a5417816ab4db3f603f2df56fb 1958 y[18] c413e7d0acd8bdd81352b2471fc1bc4f 1959 1ef296fea1220403466b1afe78b94f7e 1960 y[19] cf7cc62fb92be14f18c2192384ebceaf 1961 8801afdf947f698ce9c6ceb696ed70e9 1962 y[20] e87b0144417e8d7baf25eb5f70f09f01 1963 6fc925b4db048ab8d8cb2a661ce3b57a 1964 y[21] da67571f5dd546fc22cb1f97e0ebd1a6 1965 5926b1234fd04f171cf469c76b884cf3 1966 y[22] 115cce6f792cc84e36da58960c5f1d76 1967 0f32c12faef477e94c92eb75625b6a37 1968 y[23] 1efc72d60ca5e908b3a7dd69fef02491 1969 50e3eebdfed39cbdc3ce9704882a2072 1970 y[24] c75e13527b7a581a556168783dc1e975 1971 45e31865ddc46b3c957835da252bb732 1972 y[25] 8d3ee2062445dfb85ef8c35f8e1f3371 1973 af34023cef626e0af1e0bc017351aae2 1974 y[26] ab8f5c612ead0b729a1d059d02bfe18e 1975 fa971b7300e882360a93b025ff97e9e0 1976 y[27] eec0f3f3f13039a17f88b0cf808f4884 1977 31606cb13f9241f40f44e537d302c64a 1978 y[28] 4f1f4ab949b9feefadcb71ab50ef27d6 1979 d6ca8510f150c85fb525bf25703df720 1980 y[29] 9b6066f09c37280d59128d2f0f637c7d 1981 7d7fad4ed1c1ea04e628d221e3d8db77 1982 y[30] b7c878c9411cafc5071a34a00f4cf077 1983 38912753dfce48f07576f0d4f94f42c6 1984 y[31] d76f7ce973e9367095ba7e9a3649b7f4 1985 61d9f9ac1332a4d1044c96aefee67676 1986 y[32] 401b64457c54d65fef6500c59cdfb69a 1987 f7b6dddfcb0f086278dd8ad0686078df 1989 y[33] b0f3f79cd893d314168648499898fbc0 1990 ced5f95b74e8ff14d735cdea968bee74 1991 -------------------------------------------- 1992 LMS type 00000005 # LM_SHA256_M32_H5 1993 path[0] d8b8112f9200a5e50c4a262165bd342c 1994 d800b8496810bc716277435ac376728d 1995 path[1] 129ac6eda839a6f357b5a04387c5ce97 1996 382a78f2a4372917eefcbf93f63bb591 1997 path[2] 12f5dbe400bd49e4501e859f885bf073 1998 6e90a509b30a26bfac8c17b5991c157e 1999 path[3] b5971115aa39efd8d564a6b90282c316 2000 8af2d30ef89d51bf14654510a12b8a14 2001 path[4] 4cca1848cf7da59cc2b3d9d0692dd2a2 2002 0ba3863480e25b1b85ee860c62bf5136 2003 -------------------------------------------- 2004 LMS public key 2005 LMS type 00000005 # LM_SHA256_M32_H5 2006 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2007 I d2f14ff6346af964569f7d6cb880a1b6 2008 K 6c5004917da6eafe4d9ef6c6407b3db0 2009 e5485b122d9ebe15cda93cfec582d7ab 2010 -------------------------------------------- 2011 final_signature: 2012 -------------------------------------------- 2013 LMS signature 2014 q 0000000a 2015 -------------------------------------------- 2016 LMOTS signature 2017 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2018 C 0703c491e7558b35011ece3592eaa5da 2019 4d918786771233e8353bc4f62323185c 2020 y[0] 95cae05b899e35dffd71705470620998 2021 8ebfdf6e37960bb5c38d7657e8bffeef 2022 y[1] 9bc042da4b4525650485c66d0ce19b31 2023 7587c6ba4bffcc428e25d08931e72dfb 2024 y[2] 6a120c5612344258b85efdb7db1db9e1 2025 865a73caf96557eb39ed3e3f426933ac 2026 y[3] 9eeddb03a1d2374af7bf771855774562 2027 37f9de2d60113c23f846df26fa942008 2028 y[4] a698994c0827d90e86d43e0df7f4bfcd 2029 b09b86a373b98288b7094ad81a0185ac 2030 y[5] 100e4f2c5fc38c003c1ab6fea479eb2f 2031 5ebe48f584d7159b8ada03586e65ad9c 2032 y[6] 969f6aecbfe44cf356888a7b15a3ff07 2033 4f771760b26f9c04884ee1faa329fbf4 2034 y[7] e61af23aee7fa5d4d9a5dfcf43c4c26c 2035 e8aea2ce8a2990d7ba7b57108b47dabf 2036 y[8] beadb2b25b3cacc1ac0cef346cbb90fb 2037 044beee4fac2603a442bdf7e507243b7 2038 y[9] 319c9944b1586e899d431c7f91bcccc8 2039 690dbf59b28386b2315f3d36ef2eaa3c 2040 y[10] f30b2b51f48b71b003dfb08249484201 2041 043f65f5a3ef6bbd61ddfee81aca9ce6 2042 y[11] 0081262a00000480dcbc9a3da6fbef5c 2043 1c0a55e48a0e729f9184fcb1407c3152 2044 y[12] 9db268f6fe50032a363c9801306837fa 2045 fabdf957fd97eafc80dbd165e435d0e2 2046 y[13] dfd836a28b354023924b6fb7e48bc0b3 2047 ed95eea64c2d402f4d734c8dc26f3ac5 2048 y[14] 91825daef01eae3c38e3328d00a77dc6 2049 57034f287ccb0f0e1c9a7cbdc828f627 2050 y[15] 205e4737b84b58376551d44c12c3c215 2051 c812a0970789c83de51d6ad787271963 2052 y[16] 327f0a5fbb6b5907dec02c9a90934af5 2053 a1c63b72c82653605d1dcce51596b3c2 2054 y[17] b45696689f2eb382007497557692caac 2055 4d57b5de9f5569bc2ad0137fd47fb47e 2056 y[18] 664fcb6db4971f5b3e07aceda9ac130e 2057 9f38182de994cff192ec0e82fd6d4cb7 2058 y[19] f3fe00812589b7a7ce51544045643301 2059 6b84a59bec6619a1c6c0b37dd1450ed4 2060 y[20] f2d8b584410ceda8025f5d2d8dd0d217 2061 6fc1cf2cc06fa8c82bed4d944e71339e 2062 y[21] ce780fd025bd41ec34ebff9d4270a322 2063 4e019fcb444474d482fd2dbe75efb203 2064 y[22] 89cc10cd600abb54c47ede93e08c114e 2065 db04117d714dc1d525e11bed8756192f 2066 y[23] 929d15462b939ff3f52f2252da2ed64d 2067 8fae88818b1efa2c7b08c8794fb1b214 2068 y[24] aa233db3162833141ea4383f1a6f120b 2069 e1db82ce3630b3429114463157a64e91 2070 y[25] 234d475e2f79cbf05e4db6a9407d72c6 2071 bff7d1198b5c4d6aad2831db61274993 2072 y[26] 715a0182c7dc8089e32c8531deed4f74 2073 31c07c02195eba2ef91efb5613c37af7 2074 y[27] ae0c066babc69369700e1dd26eddc0d2 2075 16c781d56e4ce47e3303fa73007ff7b9 2076 y[28] 49ef23be2aa4dbf25206fe45c20dd888 2077 395b2526391a724996a44156beac8082 2078 y[29] 12858792bf8e74cba49dee5e8812e019 2079 da87454bff9e847ed83db07af3137430 2080 y[30] 82f880a278f682c2bd0ad6887cb59f65 2081 2e155987d61bbf6a88d36ee93b6072e6 2082 y[31] 656d9ccbaae3d655852e38deb3a2dcf8 2083 058dc9fb6f2ab3d3b3539eb77b248a66 2084 y[32] 1091d05eb6e2f297774fe6053598457c 2085 c61908318de4b826f0fc86d4bb117d33 2086 y[33] e865aa805009cc2918d9c2f840c4da43 2087 a703ad9f5b5806163d7161696b5a0adc 2088 -------------------------------------------- 2089 LMS type 00000005 # LM_SHA256_M32_H5 2090 path[0] d5c0d1bebb06048ed6fe2ef2c6cef305 2091 b3ed633941ebc8b3bec9738754cddd60 2092 path[1] e1920ada52f43d055b5031cee6192520 2093 d6a5115514851ce7fd448d4a39fae2ab 2094 path[2] 2335b525f484e9b40d6a4a969394843b 2095 dcf6d14c48e8015e08ab92662c05c6e9 2096 path[3] f90b65a7a6201689999f32bfd368e5e3 2097 ec9cb70ac7b8399003f175c40885081a 2098 path[4] 09ab3034911fe125631051df0408b394 2099 6b0bde790911e8978ba07dd56c73e7ee 2101 Test Case 2 Private Key 2103 -------------------------------------------- 2104 (note: procedure in Appendix A is used) 2105 SEED 000102030405060708090a0b0c0d0e0f 2106 101112131415161718191a1b1c1d1e1f 2107 I d08fabd4a2091ff0a8cb4ed834e74534 2108 -------------------------------------------- 2109 -------------------------------------------- 2111 Test Case 2 Public Key 2113 -------------------------------------------- 2114 HSS public key 2115 levels 00000002 2116 -------------------------------------------- 2117 LMS type 00000006 # LM_SHA256_M32_H10 2118 LMOTS type 00000003 # LMOTS_SHA256_N32_W4 2119 I d08fabd4a2091ff0a8cb4ed834e74534 2120 K 32a58885cd9ba0431235466bff9651c6 2121 c92124404d45fa53cf161c28f1ad5a8e 2122 -------------------------------------------- 2123 -------------------------------------------- 2124 Test Case 2 Message 2126 -------------------------------------------- 2127 Message 54686520656e756d65726174696f6e20 The enumeration 2128 696e2074686520436f6e737469747574 in the Constitut 2129 696f6e2c206f66206365727461696e20 ion, of certain 2130 7269676874732c207368616c6c206e6f rights, shall no 2131 7420626520636f6e7374727565642074 t be construed t 2132 6f2064656e79206f7220646973706172 o deny or dispar 2133 616765206f7468657273207265746169 age others retai 2134 6e6564206279207468652070656f706c ned by the peopl 2135 652e0a e.. 2136 -------------------------------------------- 2138 Test Case 2 Signature 2140 -------------------------------------------- 2141 HSS signature 2142 Nspk 00000001 2143 sig[0]: 2144 -------------------------------------------- 2145 LMS signature 2146 q 00000003 2147 -------------------------------------------- 2148 LMOTS signature 2149 LMOTS type 00000003 # LMOTS_SHA256_N32_W4 2150 C 3d46bee8660f8f215d3f96408a7a64cf 2151 1c4da02b63a55f62c666ef5707a914ce 2152 y[0] 0674e8cb7a55f0c48d484f31f3aa4af9 2153 719a74f22cf823b94431d01c926e2a76 2154 y[1] bb71226d279700ec81c9e95fb11a0d10 2155 d065279a5796e265ae17737c44eb8c59 2156 y[2] 4508e126a9a7870bf4360820bdeb9a01 2157 d9693779e416828e75bddd7d8c70d50a 2158 y[3] 0ac8ba39810909d445f44cb5bb58de73 2159 7e60cb4345302786ef2c6b14af212ca1 2160 y[4] 9edeaa3bfcfe8baa6621ce88480df237 2161 1dd37add732c9de4ea2ce0dffa53c926 2162 y[5] 49a18d39a50788f4652987f226a1d481 2163 68205df6ae7c58e049a25d4907edc1aa 2164 y[6] 90da8aa5e5f7671773e941d805536021 2165 5c6b60dd35463cf2240a9c06d694e9cb 2166 y[7] 54e7b1e1bf494d0d1a28c0d31acc7516 2167 1f4f485dfd3cb9578e836ec2dc722f37 2168 y[8] ed30872e07f2b8bd0374eb57d22c614e 2169 09150f6c0d8774a39a6e168211035dc5 2170 y[9] 2988ab46eaca9ec597fb18b4936e66ef 2171 2f0df26e8d1e34da28cbb3af75231372 2173 y[10] 0c7b345434f72d65314328bbb030d0f0 2174 f6d5e47b28ea91008fb11b05017705a8 2175 y[11] be3b2adb83c60a54f9d1d1b2f476f9e3 2176 93eb5695203d2ba6ad815e6a111ea293 2177 y[12] dcc21033f9453d49c8e5a6387f588b1e 2178 a4f706217c151e05f55a6eb7997be09d 2179 y[13] 56a326a32f9cba1fbe1c07bb49fa04ce 2180 cf9df1a1b815483c75d7a27cc88ad1b1 2181 y[14] 238e5ea986b53e087045723ce16187ed 2182 a22e33b2c70709e53251025abde89396 2183 y[15] 45fc8c0693e97763928f00b2e3c75af3 2184 942d8ddaee81b59a6f1f67efda0ef81d 2185 y[16] 11873b59137f67800b35e81b01563d18 2186 7c4a1575a1acb92d087b517a8833383f 2187 y[17] 05d357ef4678de0c57ff9f1b2da61dfd 2188 e5d88318bcdde4d9061cc75c2de3cd47 2189 y[18] 40dd7739ca3ef66f1930026f47d9ebaa 2190 713b07176f76f953e1c2e7f8f271a6ca 2191 y[19] 375dbfb83d719b1635a7d8a138919579 2192 44b1c29bb101913e166e11bd5f34186f 2193 y[20] a6c0a555c9026b256a6860f4866bd6d0 2194 b5bf90627086c6149133f8282ce6c9b3 2195 y[21] 622442443d5eca959d6c14ca8389d12c 2196 4068b503e4e3c39b635bea245d9d05a2 2197 y[22] 558f249c9661c0427d2e489ca5b5dde2 2198 20a90333f4862aec793223c781997da9 2199 y[23] 8266c12c50ea28b2c438e7a379eb106e 2200 ca0c7fd6006e9bf612f3ea0a454ba3bd 2201 y[24] b76e8027992e60de01e9094fddeb3349 2202 883914fb17a9621ab929d970d101e45f 2203 y[25] 8278c14b032bcab02bd15692d21b6c5c 2204 204abbf077d465553bd6eda645e6c306 2205 y[26] 5d33b10d518a61e15ed0f092c3222628 2206 1a29c8a0f50cde0a8c66236e29c2f310 2207 y[27] a375cebda1dc6bb9a1a01dae6c7aba8e 2208 bedc6371a7d52aacb955f83bd6e4f84d 2209 y[28] 2949dcc198fb77c7e5cdf6040b0f84fa 2210 f82808bf985577f0a2acf2ec7ed7c0b0 2211 y[29] ae8a270e951743ff23e0b2dd12e9c3c8 2212 28fb5598a22461af94d568f29240ba28 2213 y[30] 20c4591f71c088f96e095dd98beae456 2214 579ebbba36f6d9ca2613d1c26eee4d8c 2215 y[31] 73217ac5962b5f3147b492e8831597fd 2216 89b64aa7fde82e1974d2f6779504dc21 2217 y[32] 435eb3109350756b9fdabe1c6f368081 2218 bd40b27ebcb9819a75d7df8bb07bb05d 2219 y[33] b1bab705a4b7e37125186339464ad8fa 2220 aa4f052cc1272919fde3e025bb64aa8e 2222 y[34] 0eb1fcbfcc25acb5f718ce4f7c2182fb 2223 393a1814b0e942490e52d3bca817b2b2 2224 y[35] 6e90d4c9b0cc38608a6cef5eb153af08 2225 58acc867c9922aed43bb67d7b33acc51 2226 y[36] 9313d28d41a5c6fe6cf3595dd5ee63f0 2227 a4c4065a083590b275788bee7ad875a7 2228 y[37] f88dd73720708c6c6c0ecf1f43bbaada 2229 e6f208557fdc07bd4ed91f88ce4c0de8 2230 y[38] 42761c70c186bfdafafc444834bd3418 2231 be4253a71eaf41d718753ad07754ca3e 2232 y[39] ffd5960b0336981795721426803599ed 2233 5b2b7516920efcbe32ada4bcf6c73bd2 2234 y[40] 9e3fa152d9adeca36020fdeeee1b7395 2235 21d3ea8c0da497003df1513897b0f547 2236 y[41] 94a873670b8d93bcca2ae47e64424b74 2237 23e1f078d9554bb5232cc6de8aae9b83 2238 y[42] fa5b9510beb39ccf4b4e1d9c0f19d5e1 2239 7f58e5b8705d9a6837a7d9bf99cd1338 2240 y[43] 7af256a8491671f1f2f22af253bcff54 2241 b673199bdb7d05d81064ef05f80f0153 2242 y[44] d0be7919684b23da8d42ff3effdb7ca0 2243 985033f389181f47659138003d712b5e 2244 y[45] c0a614d31cc7487f52de8664916af79c 2245 98456b2c94a8038083db55391e347586 2246 y[46] 2250274a1de2584fec975fb09536792c 2247 fbfcf6192856cc76eb5b13dc4709e2f7 2248 y[47] 301ddff26ec1b23de2d188c999166c74 2249 e1e14bbc15f457cf4e471ae13dcbdd9c 2250 y[48] 50f4d646fc6278e8fe7eb6cb5c94100f 2251 a870187380b777ed19d7868fd8ca7ceb 2252 y[49] 7fa7d5cc861c5bdac98e7495eb0a2cee 2253 c1924ae979f44c5390ebedddc65d6ec1 2254 y[50] 1287d978b8df064219bc5679f7d7b264 2255 a76ff272b2ac9f2f7cfc9fdcfb6a5142 2256 y[51] 8240027afd9d52a79b647c90c2709e06 2257 0ed70f87299dd798d68f4fadd3da6c51 2258 y[52] d839f851f98f67840b964ebe73f8cec4 2259 1572538ec6bc131034ca2894eb736b3b 2260 y[53] da93d9f5f6fa6f6c0f03ce43362b8414 2261 940355fb54d3dfdd03633ae108f3de3e 2262 y[54] bc85a3ff51efeea3bc2cf27e1658f178 2263 9ee612c83d0f5fd56f7cd071930e2946 2264 y[55] beeecaa04dccea9f97786001475e0294 2265 bc2852f62eb5d39bb9fbeef75916efe4 2266 y[56] 4a662ecae37ede27e9d6eadfdeb8f8b2 2267 b2dbccbf96fa6dbaf7321fb0e701f4d4 2268 y[57] 29c2f4dcd153a2742574126e5eaccc77 2269 686acf6e3ee48f423766e0fc466810a9 2271 y[58] 05ff5453ec99897b56bc55dd49b99114 2272 2f65043f2d744eeb935ba7f4ef23cf80 2273 y[59] cc5a8a335d3619d781e7454826df720e 2274 ec82e06034c44699b5f0c44a8787752e 2275 y[60] 057fa3419b5bb0e25d30981e41cb1361 2276 322dba8f69931cf42fad3f3bce6ded5b 2277 y[61] 8bfc3d20a2148861b2afc14562ddd27f 2278 12897abf0685288dcc5c4982f8260268 2279 y[62] 46a24bf77e383c7aacab1ab692b29ed8 2280 c018a65f3dc2b87ff619a633c41b4fad 2281 y[63] b1c78725c1f8f922f6009787b1964247 2282 df0136b1bc614ab575c59a16d089917b 2283 y[64] d4a8b6f04d95c581279a139be09fcf6e 2284 98a470a0bceca191fce476f9370021cb 2285 y[65] c05518a7efd35d89d8577c990a5e1996 2286 1ba16203c959c91829ba7497cffcbb4b 2287 y[66] 294546454fa5388a23a22e805a5ca35f 2288 956598848bda678615fec28afd5da61a 2289 -------------------------------------------- 2290 LMS type 00000006 # LM_SHA256_M32_H10 2291 path[0] b326493313053ced3876db9d23714818 2292 1b7173bc7d042cefb4dbe94d2e58cd21 2293 path[1] a769db4657a103279ba8ef3a629ca84e 2294 e836172a9c50e51f45581741cf808315 2295 path[2] 0b491cb4ecbbabec128e7c81a46e62a6 2296 7b57640a0a78be1cbf7dd9d419a10cd8 2297 path[3] 686d16621a80816bfdb5bdc56211d72c 2298 a70b81f1117d129529a7570cf79cf52a 2299 path[4] 7028a48538ecdd3b38d3d5d62d262465 2300 95c4fb73a525a5ed2c30524ebb1d8cc8 2301 path[5] 2e0c19bc4977c6898ff95fd3d310b0ba 2302 e71696cef93c6a552456bf96e9d075e3 2303 path[6] 83bb7543c675842bafbfc7cdb88483b3 2304 276c29d4f0a341c2d406e40d4653b7e4 2305 path[7] d045851acf6a0a0ea9c710b805cced46 2306 35ee8c107362f0fc8d80c14d0ac49c51 2307 path[8] 6703d26d14752f34c1c0d2c4247581c1 2308 8c2cf4de48e9ce949be7c888e9caebe4 2309 path[9] a415e291fd107d21dc1f084b11582082 2310 49f28f4f7c7e931ba7b3bd0d824a4570 2311 -------------------------------------------- 2312 LMS public key 2313 LMS type 00000005 # LM_SHA256_M32_H5 2314 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2315 I 215f83b7ccb9acbcd08db97b0d04dc2b 2316 K a1cd035833e0e90059603f26e07ad2aa 2317 d152338e7a5e5984bcd5f7bb4eba40b7 2318 -------------------------------------------- 2319 final_signature: 2320 -------------------------------------------- 2321 LMS signature 2322 q 00000004 2323 -------------------------------------------- 2324 LMOTS signature 2325 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2326 C 0eb1ed54a2460d512388cad533138d24 2327 0534e97b1e82d33bd927d201dfc24ebb 2328 y[0] 11b3649023696f85150b189e50c00e98 2329 850ac343a77b3638319c347d7310269d 2330 y[1] 3b7714fa406b8c35b021d54d4fdada7b 2331 9ce5d4ba5b06719e72aaf58c5aae7aca 2332 y[2] 057aa0e2e74e7dcfd17a0823429db629 2333 65b7d563c57b4cec942cc865e29c1dad 2334 y[3] 83cac8b4d61aacc457f336e6a10b6632 2335 3f5887bf3523dfcadee158503bfaa89d 2336 y[4] c6bf59daa82afd2b5ebb2a9ca6572a60 2337 67cee7c327e9039b3b6ea6a1edc7fdc3 2338 y[5] df927aade10c1c9f2d5ff446450d2a39 2339 98d0f9f6202b5e07c3f97d2458c69d3c 2340 y[6] 8190643978d7a7f4d64e97e3f1c4a08a 2341 7c5bc03fd55682c017e2907eab07e5bb 2342 y[7] 2f190143475a6043d5e6d5263471f4ee 2343 cf6e2575fbc6ff37edfa249d6cda1a09 2344 y[8] f797fd5a3cd53a066700f45863f04b6c 2345 8a58cfd341241e002d0d2c0217472bf1 2346 y[9] 8b636ae547c1771368d9f317835c9b0e 2347 f430b3df4034f6af00d0da44f4af7800 2348 y[10] bc7a5cf8a5abdb12dc718b559b74cab9 2349 090e33cc58a955300981c420c4da8ffd 2350 y[11] 67df540890a062fe40dba8b2c1c548ce 2351 d22473219c534911d48ccaabfb71bc71 2352 y[12] 862f4a24ebd376d288fd4e6fb06ed870 2353 5787c5fedc813cd2697e5b1aac1ced45 2354 y[13] 767b14ce88409eaebb601a93559aae89 2355 3e143d1c395bc326da821d79a9ed41dc 2356 y[14] fbe549147f71c092f4f3ac522b5cc572 2357 90706650487bae9bb5671ecc9ccc2ce5 2358 y[15] 1ead87ac01985268521222fb9057df7e 2359 d41810b5ef0d4f7cc67368c90f573b1a 2360 y[16] c2ce956c365ed38e893ce7b2fae15d36 2361 85a3df2fa3d4cc098fa57dd60d2c9754 2362 y[17] a8ade980ad0f93f6787075c3f680a2ba 2363 1936a8c61d1af52ab7e21f416be09d2a 2364 y[18] 8d64c3d3d8582968c2839902229f85ae 2365 e297e717c094c8df4a23bb5db658dd37 2366 y[19] 7bf0f4ff3ffd8fba5e383a48574802ed 2367 545bbe7a6b4753533353d73706067640 2368 y[20] 135a7ce517279cd683039747d218647c 2369 86e097b0daa2872d54b8f3e508598762 2370 y[21] 9547b830d8118161b65079fe7bc59a99 2371 e9c3c7380e3e70b7138fe5d9be255150 2372 y[22] 2b698d09ae193972f27d40f38dea264a 2373 0126e637d74ae4c92a6249fa103436d3 2374 y[23] eb0d4029ac712bfc7a5eacbdd7518d6d 2375 4fe903a5ae65527cd65bb0d4e9925ca2 2376 y[24] 4fd7214dc617c150544e423f450c99ce 2377 51ac8005d33acd74f1bed3b17b7266a4 2378 y[25] a3bb86da7eba80b101e15cb79de9a207 2379 852cf91249ef480619ff2af8cabca831 2380 y[26] 25d1faa94cbb0a03a906f683b3f47a97 2381 c871fd513e510a7a25f283b196075778 2382 y[27] 496152a91c2bf9da76ebe089f4654877 2383 f2d586ae7149c406e663eadeb2b5c7e8 2384 y[28] 2429b9e8cb4834c83464f079995332e4 2385 b3c8f5a72bb4b8c6f74b0d45dc6c1f79 2386 y[29] 952c0b7420df525e37c15377b5f09843 2387 19c3993921e5ccd97e097592064530d3 2388 y[30] 3de3afad5733cbe7703c5296263f7734 2389 2efbf5a04755b0b3c997c4328463e84c 2390 y[31] aa2de3ffdcd297baaaacd7ae646e44b5 2391 c0f16044df38fabd296a47b3a838a913 2392 y[32] 982fb2e370c078edb042c84db34ce36b 2393 46ccb76460a690cc86c302457dd1cde1 2394 y[33] 97ec8075e82b393d542075134e2a17ee 2395 70a5e187075d03ae3c853cff60729ba4 2396 -------------------------------------------- 2397 LMS type 00000005 # LM_SHA256_M32_H5 2398 path[0] 4de1f6965bdabc676c5a4dc7c35f97f8 2399 2cb0e31c68d04f1dad96314ff09e6b3d 2400 path[1] e96aeee300d1f68bf1bca9fc58e40323 2401 36cd819aaf578744e50d1357a0e42867 2402 path[2] 04d341aa0a337b19fe4bc43c2e79964d 2403 4f351089f2e0e41c7c43ae0d49e7f404 2404 path[3] b0f75be80ea3af098c9752420a8ac0ea 2405 2bbb1f4eeba05238aef0d8ce63f0c6e5 2406 path[4] e4041d95398a6f7f3e0ee97cc1591849 2407 d4ed236338b147abde9f51ef9fd4e1c1 2409 Authors' Addresses 2410 David McGrew 2411 Cisco Systems 2412 13600 Dulles Technology Drive 2413 Herndon, VA 20171 2414 USA 2416 Email: mcgrew@cisco.com 2418 Michael Curcio 2419 Cisco Systems 2420 7025-2 Kit Creek Road 2421 Research Triangle Park, NC 27709-4987 2422 USA 2424 Email: micurcio@cisco.com 2426 Scott Fluhrer 2427 Cisco Systems 2428 170 West Tasman Drive 2429 San Jose, CA 2430 USA 2432 Email: sfluhrer@cisco.com