idnits 2.17.1 draft-mcgrew-hash-sigs-13.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 1016 has weird spacing: '... leaf lea...' -- The document date (September 6, 2018) is 2058 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: '32' on line 2671 -- Looks like a reference, but probably isn't: '265' on line 428 -- Looks like a reference, but probably isn't: '133' on line 433 -- Looks like a reference, but probably isn't: '67' on line 438 -- Looks like a reference, but probably isn't: '34' on line 2500 -- Looks like a reference, but probably isn't: '5' on line 2617 -- Looks like a reference, but probably isn't: '10' on line 2627 -- Looks like a reference, but probably isn't: '15' on line 2637 -- Looks like a reference, but probably isn't: '20' on line 2647 -- Looks like a reference, but probably isn't: '25' on line 2657 -- Looks like a reference, but probably isn't: '16' on line 2639 -- Looks like a reference, but probably isn't: '0' on line 2677 -- Looks like a reference, but probably isn't: '1' on line 2679 -- Looks like a reference, but probably isn't: '2' on line 2681 -- Looks like a reference, but probably isn't: '4' on line 2685 -- Looks like a reference, but probably isn't: '6' on line 2619 -- Looks like a reference, but probably isn't: '7' on line 2621 == Missing Reference: 'L-1' is mentioned on line 1380, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 1394, but not defined == Missing Reference: 'Nspk' is mentioned on line 1420, but not defined == Missing Reference: 'L-2' is mentioned on line 1380, but not defined -- Looks like a reference, but probably isn't: '3' on line 2683 -- Looks like a reference, but probably isn't: '8' on line 2623 -- Looks like a reference, but probably isn't: '9' on line 2625 -- Looks like a reference, but probably isn't: '11' on line 2629 -- Looks like a reference, but probably isn't: '12' on line 2631 -- Looks like a reference, but probably isn't: '13' on line 2633 -- Looks like a reference, but probably isn't: '14' on line 2635 -- Looks like a reference, but probably isn't: '17' on line 2641 -- Looks like a reference, but probably isn't: '18' on line 2643 -- Looks like a reference, but probably isn't: '19' on line 2645 -- Looks like a reference, but probably isn't: '21' on line 2649 -- Looks like a reference, but probably isn't: '22' on line 2651 -- Looks like a reference, but probably isn't: '23' on line 2653 -- Looks like a reference, but probably isn't: '24' on line 2655 -- Looks like a reference, but probably isn't: '26' on line 2659 -- Looks like a reference, but probably isn't: '27' on line 2661 -- Looks like a reference, but probably isn't: '28' on line 2663 -- Looks like a reference, but probably isn't: '29' on line 2665 -- Looks like a reference, but probably isn't: '30' on line 2667 -- Looks like a reference, but probably isn't: '31' on line 2669 -- Looks like a reference, but probably isn't: '33' on line 2673 -- Looks like a reference, but probably isn't: '35' on line 2502 -- Looks like a reference, but probably isn't: '36' on line 2504 -- Looks like a reference, but probably isn't: '37' on line 2506 -- Looks like a reference, but probably isn't: '38' on line 2508 -- Looks like a reference, but probably isn't: '39' on line 2510 -- Looks like a reference, but probably isn't: '40' on line 2512 -- Looks like a reference, but probably isn't: '41' on line 2514 -- Looks like a reference, but probably isn't: '42' on line 2516 -- Looks like a reference, but probably isn't: '43' on line 2518 -- Looks like a reference, but probably isn't: '44' on line 2520 -- Looks like a reference, but probably isn't: '45' on line 2522 -- Looks like a reference, but probably isn't: '46' on line 2524 -- Looks like a reference, but probably isn't: '47' on line 2526 -- Looks like a reference, but probably isn't: '48' on line 2528 -- Looks like a reference, but probably isn't: '49' on line 2530 -- Looks like a reference, but probably isn't: '50' on line 2532 -- Looks like a reference, but probably isn't: '51' on line 2535 -- Looks like a reference, but probably isn't: '52' on line 2537 -- Looks like a reference, but probably isn't: '53' on line 2539 -- Looks like a reference, but probably isn't: '54' on line 2541 -- Looks like a reference, but probably isn't: '55' on line 2543 -- Looks like a reference, but probably isn't: '56' on line 2545 -- Looks like a reference, but probably isn't: '57' on line 2547 -- Looks like a reference, but probably isn't: '58' on line 2549 -- Looks like a reference, but probably isn't: '59' on line 2551 -- Looks like a reference, but probably isn't: '60' on line 2553 -- Looks like a reference, but probably isn't: '61' on line 2555 -- Looks like a reference, but probably isn't: '62' on line 2557 -- Looks like a reference, but probably isn't: '63' on line 2559 -- Looks like a reference, but probably isn't: '64' on line 2561 -- Looks like a reference, but probably isn't: '65' on line 2563 -- Looks like a reference, but probably isn't: '66' on line 2565 == Unused Reference: 'Grover96' is defined on line 1939, but no explicit reference was found in the text == Unused Reference: 'Katz16' is defined on line 1944, 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: 3 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: March 10, 2019 Cisco Systems 6 September 6, 2018 8 Hash-Based Signatures 9 draft-mcgrew-hash-sigs-13 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 This document is a product of the Crypto Forum Research Group (CFRG) 26 in the IRTF. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at https://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on March 10, 2019. 45 Copyright Notice 47 Copyright (c) 2018 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (https://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 63 1.1. CFRG Note on Post-Quantum Cryptography . . . . . . . . . 5 64 1.2. Intellectual Property . . . . . . . . . . . . . . . . . . 6 65 1.2.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . 6 66 1.3. Conventions Used In This Document . . . . . . . . . . . . 6 67 2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 6 68 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 7 69 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 7 70 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 7 71 3.1.2. Functions . . . . . . . . . . . . . . . . . . . . . . 8 72 3.1.3. Strings of w-bit elements . . . . . . . . . . . . . . 8 73 3.2. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 9 74 3.3. Notation and Formats . . . . . . . . . . . . . . . . . . 9 75 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 12 76 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 12 77 4.2. Private Key . . . . . . . . . . . . . . . . . . . . . . . 14 78 4.3. Public Key . . . . . . . . . . . . . . . . . . . . . . . 15 79 4.4. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 15 80 4.5. Signature Generation . . . . . . . . . . . . . . . . . . 16 81 4.6. Signature Verification . . . . . . . . . . . . . . . . . 17 82 5. Leighton-Micali Signatures . . . . . . . . . . . . . . . . . 19 83 5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 20 84 5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 21 85 5.3. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 21 86 5.4. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 22 87 5.4.1. LMS Signature Generation . . . . . . . . . . . . . . 24 88 5.4.2. LMS Signature Verification . . . . . . . . . . . . . 24 89 6. Hierarchical signatures . . . . . . . . . . . . . . . . . . . 26 90 6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 29 91 6.2. Signature Generation . . . . . . . . . . . . . . . . . . 30 92 6.3. Signature Verification . . . . . . . . . . . . . . . . . 32 93 6.4. Parameter Set Recommendations . . . . . . . . . . . . . . 32 94 7. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 34 95 7.1. Security String . . . . . . . . . . . . . . . . . . . . . 35 96 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36 97 9. Security Considerations . . . . . . . . . . . . . . . . . . . 38 98 9.1. Hash Formats . . . . . . . . . . . . . . . . . . . . . . 39 99 9.2. Stateful signature algorithm . . . . . . . . . . . . . . 40 100 9.3. Security of LM-OTS Checksum . . . . . . . . . . . . . . . 41 101 10. Comparison with other work . . . . . . . . . . . . . . . . . 42 102 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 42 103 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 42 104 12.1. Normative References . . . . . . . . . . . . . . . . . . 42 105 12.2. Informative References . . . . . . . . . . . . . . . . . 43 106 Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 44 107 Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 45 108 Appendix C. An iterative algorithm for computing an LMS public 109 key . . . . . . . . . . . . . . . . . . . . . . . . 46 110 Appendix D. Method for deriving authentication path for a 111 signature . . . . . . . . . . . . . . . . . . . . . 47 112 Appendix E. Example Implementation . . . . . . . . . . . . . . . 48 113 Appendix F. Test Cases . . . . . . . . . . . . . . . . . . . . . 48 114 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60 116 1. Introduction 118 One-time signature systems, and general purpose signature systems 119 built out of one-time signature systems, have been known since 1979 120 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 121 benefited from renewed attention in the last decade. The 122 characteristics of these signature systems are small private and 123 public keys and fast signature generation and verification, but large 124 signatures and moderately slow key generation (in comparison with RSA 125 and ECDSA). Private keys can be made very small by appropriate key 126 generation, for example, as described in Appendix A. In recent years 127 there has been interest in these systems because of their post- 128 quantum security and their suitability for compact verifier 129 implementations. 131 This note describes the Leighton and Micali adaptation [USPTO5432852] 132 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 133 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 134 signature system [Merkle79] with enough specificity to ensure 135 interoperability between implementations. 137 A signature system provides asymmetric message authentication. The 138 key generation algorithm produces a public/private key pair. A 139 message is signed by a private key, producing a signature, and a 140 message/signature pair can be verified by a public key. A One-Time 141 Signature (OTS) system can be used to sign one message securely, but 142 will become insecure if more than one is signed with the same public/ 143 private key pair. An N-time signature system can be used to sign N 144 or fewer messages securely. A Merkle tree signature scheme is an 145 N-time signature system that uses an OTS system as a component. 147 In the Merkle scheme, a binary tree of height h is used to hold 2^h 148 OTS key pairs. Each interior node of the tree holds a value which is 149 the hash of the values of its two children nodes. The public key of 150 the tree is the value of the root node (a recursive hash of the OTS 151 public keys), while the private key of the tree is the collection of 152 all the OTS private keys, together with the index of the next OTS 153 private key to sign the next message with. 155 In this note we describe the Leighton-Micali Signature (LMS) system, 156 which is a variant of the Merkle scheme, and a Hierarchical Signature 157 System (HSS) built on top of it that can efficiently scale to larger 158 numbers of signatures. In order to support signing a large number of 159 messages on resource constrained systems, the Merkle tree can be 160 subdivided into a number of smaller trees. Only the bottom-most tree 161 is used to sign messages, while trees above that are used to sign the 162 public keys of their children. For example, in the simplest case 163 with 2 levels with both levels consisting of height h trees, the root 164 tree is used to sign 2^h trees with 2^h OTS key pairs, and each 165 second level tree has 2^h OTS key pairs, for a total of 2^(2h) bottom 166 level key pairs, and so can sign 2^(2h) messages. The advantage of 167 this scheme is that only the active trees need to be instantiated, 168 which saves both time (for key generation) and space (for key 169 storage). On the other hand, using a multilevel signature scheme 170 inceases the size of the signature, as well as the signature 171 verification time. 173 This note is structured as follows. Notes on postquantum 174 cryptography are discussed in Section 1.1. Intellectual Property 175 issues are discussed in Section 1.2. The notation used within this 176 note is defined in Section 3, and the public formats are described in 177 Section 3.3. The LM-OTS signature system is described in Section 4, 178 and the LMS and HSS N-time signature systems are described in 179 Section 5 and Section 6, respectively. Sufficient detail is provided 180 to ensure interoperability. The rationale for the design decisions 181 is given in Section 7. The IANA registry for these signature systems 182 is described in Section 8. Security considerations are presented in 183 Section 9. Comparison with another hash based signature algorithm 184 (XMSS) is in Section 10. 186 This document represents the rough consensus of the CFRG. 188 1.1. CFRG Note on Post-Quantum Cryptography 190 All post-quantum algorithms documented by the Crypto Forum Research 191 Group (CFRG) are today considered ready for experimentation and 192 further engineering development (e.g., to establish the impact of 193 performance and sizes on IETF protocols). However, at the time of 194 writing, we do not have significant deployment experience with such 195 algorithms. 197 Many of these algorithms come with specific restrictions, e.g., 198 change of classical interface or less cryptanalysis of proposed 199 parameters than established schemes. CFRG has consensus that all 200 documents describing post-quantum technologies include the above 201 paragraph and a clear additional warning about any specific 202 restrictions, especially as those might affect use or deployment of 203 the specific scheme. That guidance may be changed over time via 204 document updates. 206 Additionally, for LMS: 208 CFRG consensus is that we are confident in the cryptographic security 209 of the signature schemes described in this document against quantum 210 computers, given the current state of the research community's 211 knowledge about quantum algorithms. Indeed, we are confident that 212 the security of a significant part of the Internet could be made 213 dependent on the signature schemes defined in this document, if 214 developers take care of the following. 216 In contrast to traditional signature schemes, the signature schemes 217 described in this document are stateful, meaning the secret key 218 changes over time. If a secret key state is used twice, no 219 cryptographic security guarantees remain. In consequence, it becomes 220 feasible to forge a signature on a new message. This is a new 221 property that most developers will not be familiar with and requires 222 careful handling of secret keys. Developers should not use the 223 schemes described here except in systems that prevent the reuse of 224 secret key states. 226 Note that the fact that the schemes described in this document are 227 stateful also implies that classical APIs for digital signatures 228 cannot be used without modification. The API MUST be able to handle 229 a secret key state; in particular, this means that the API MUST allow 230 to return an updated secret key state. 232 1.2. Intellectual Property 234 This draft is based on U.S. patent 5,432,852, which was issued over 235 twenty years ago and is thus expired. 237 1.2.1. Disclaimer 239 This document is not intended as legal advice. Readers are advised 240 to consult with their own legal advisers if they would like a legal 241 interpretation of their rights. 243 The IETF policies and processes regarding intellectual property and 244 patents are outlined in [RFC3979] and [RFC4879] and at 245 https://datatracker.ietf.org/ipr/about. 247 1.3. Conventions Used In This Document 249 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 250 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 251 document are to be interpreted as described in [RFC2119]. 253 2. Interface 255 The LMS signing algorithm is stateful; it modifies and updates the 256 private key as a side effect of generating a signature. Once a 257 particular value of the private key is used to sign one message, it 258 MUST NOT be used to sign another. 260 The key generation algorithm takes as input an indication of the 261 parameters for the signature system. If it is successful, it returns 262 both a private key and a public key. Otherwise, it returns an 263 indication of failure. 265 The signing algorithm takes as input the message to be signed and the 266 current value of the private key. If successful, it returns a 267 signature and the next value of the private key, if there is such a 268 value. After the private key of an N-time signature system has 269 signed N messages, the signing algorithm returns the signature and an 270 indication that there is no next value of the private key that can be 271 used for signing. If unsuccessful, it returns an indication of 272 failure. 274 The verification algorithm takes as input the public key, a message, 275 and a signature, and returns an indication of whether or not the 276 signature and message pair is valid. 278 A message/signature pair is valid if the signature was returned by 279 the signing algorithm upon input of the message and the private key 280 corresponding to the public key; otherwise, the signature and message 281 pair is not valid with probability very close to one. 283 3. Notation 285 3.1. Data Types 287 Bytes and byte strings are the fundamental data types. A single byte 288 is denoted as a pair of hexadecimal digits with a leading "0x". A 289 byte string is an ordered sequence of zero or more bytes and is 290 denoted as an ordered sequence of hexadecimal characters with a 291 leading "0x". For example, 0xe534f0 is a byte string with a length 292 of three. An array of byte strings is an ordered set, indexed 293 starting at zero, in which all strings have the same length. 295 Unsigned integers are converted into byte strings by representing 296 them in network byte order. To make the number of bytes in the 297 representation explicit, we define the functions u8str(X), u16str(X), 298 and u32str(X), which take a non-negative integer X as input and 299 return one, two, and four byte strings, respectively. We also make 300 use of the function strTou32(S), which takes a four-byte string S as 301 input and returns a non-negative integer; the identity 302 u32str(strTou32(S)) = S holds for any four-byte string S. 304 3.1.1. Operators 306 When a and b are real numbers, mathematical operators are defined as 307 follows: 309 ^ : a ^ b denotes the result of a raised to the power of b 311 * : a * b denotes the product of a multiplied by b 313 / : a / b denotes the quotient of a divided by b 315 % : a % b denotes the remainder of the integer division of a by b 316 (with a and b being restricted to integers in this case) 318 + : a + b denotes the sum of a and b 320 - : a - b denotes the difference of a and b 322 AND : a AND b denotes the bitwise AND of the two nonnegative 323 integers a and b (represented in binary notation) 325 The standard order of operations is used when evaluating arithmetic 326 expressions. 328 When B is a byte and i is an integer, then B >> i denotes the logical 329 right-shift operation by i bit positions. Similarly, B << i denotes 330 the logical left-shift operation. 332 If S and T are byte strings, then S || T denotes the concatenation of 333 S and T. If S and T are equal length byte strings, then S AND T 334 denotes the bitwise logical and operation. 336 The i-th element in an array A is denoted as A[i]. 338 3.1.2. Functions 340 If r is a non-negative real number, then we define the following 341 functions: 343 ceil(r) : returns the smallest integer greater than or equal to r 345 floor(r) : returns the largest integer less than or equal to r 347 lg(r) : returns the base-2 logarithm of r 349 3.1.3. Strings of w-bit elements 351 If S is a byte string, then byte(S, i) denotes its i-th byte, where 352 the index starts at 0 at the left. Hence, byte(S, 0) is the leftmost 353 byte of S, byte(S, 1) is the second byte at the left and (assuming S 354 is n bytes long) byte(S, n-1) is the rightmost byte of S. In 355 addition, bytes(S, i, j) denotes the range of bytes from the i-th to 356 the j-th byte, inclusive. For example, if S = 0x02040608, then 357 byte(S, 0) is 0x02 and bytes(S, 1, 2) is 0x0406. 359 A byte string can be considered to be a string of w-bit unsigned 360 integers; the correspondence is defined by the function coef(S, i, w) 361 as follows: 363 If S is a string, i is a positive integer, and w is a member of the 364 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i-th, w-bit value, if S 365 is interpreted as a sequence of w-bit values. That is, 367 coef(S, i, w) = (2^w - 1) AND 368 ( byte(S, floor(i * w / 8)) >> 369 (8 - (w * (i % (8 / w)) + w)) ) 371 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 372 coef(S, 0, 4) is 1. 374 S (represented as bits) 375 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 376 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 377 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 378 ^ 379 | 380 coef(S, 7, 1) 382 S (represented as four-bit values) 383 +-----------+-----------+-----------+-----------+ 384 | 1 | 2 | 3 | 4 | 385 +-----------+-----------+-----------+-----------+ 386 ^ 387 | 388 coef(S, 0, 4) 390 The return value of coef is an unsigned integer. If i is larger than 391 the number of w-bit values in S, then coef(S, i, w) is undefined, and 392 an attempt to compute that value MUST raise an error. 394 3.2. Typecodes 396 A typecode is an unsigned integer that is associated with a 397 particular data format. The format of the LM-OTS, LMS, and HSS 398 signatures and public keys all begin with a typecode that indicates 399 the precise details used in that format. These typecodes are 400 represented as four-byte unsigned integers in network byte order; 401 equivalently, they are XDR enumerations (see Section 3.3). 403 3.3. Notation and Formats 405 The signature and public key formats are formally defined using the 406 External Data Representation (XDR) [RFC4506] in order to provide an 407 unambiguous, machine readable definition. For clarity, we also 408 include a private key format as well, though consistency is not 409 needed for interoperability and an implementation MAY use any private 410 key format. Though XDR is used, these formats are simple and easy to 411 parse without any special tools. An illustration of the layout of 412 data in these objects is provided below. The definitions are as 413 follows: 415 /* one-time signatures */ 416 enum lmots_algorithm_type { 417 lmots_reserved = 0, 418 lmots_sha256_n32_w1 = 1, 419 lmots_sha256_n32_w2 = 2, 420 lmots_sha256_n32_w4 = 3, 421 lmots_sha256_n32_w8 = 4 422 }; 424 typedef opaque bytestring32[32]; 426 struct lmots_signature_n32_p265 { 427 bytestring32 C; 428 bytestring32 y[265]; 429 }; 431 struct lmots_signature_n32_p133 { 432 bytestring32 C; 433 bytestring32 y[133]; 434 }; 436 struct lmots_signature_n32_p67 { 437 bytestring32 C; 438 bytestring32 y[67]; 439 }; 441 struct lmots_signature_n32_p34 { 442 bytestring32 C; 443 bytestring32 y[34]; 444 }; 446 union lmots_signature switch (lmots_algorithm_type type) { 447 case lmots_sha256_n32_w1: 448 lmots_signature_n32_p265 sig_n32_p265; 449 case lmots_sha256_n32_w2: 450 lmots_signature_n32_p133 sig_n32_p133; 451 case lmots_sha256_n32_w4: 452 lmots_signature_n32_p67 sig_n32_p67; 453 case lmots_sha256_n32_w8: 454 lmots_signature_n32_p34 sig_n32_p34; 455 default: 456 void; /* error condition */ 457 }; 459 /* hash based signatures (hbs) */ 461 enum lms_algorithm_type { 462 lms_reserved = 0, 463 lms_sha256_n32_h5 = 5, 464 lms_sha256_n32_h10 = 6, 465 lms_sha256_n32_h15 = 7, 466 lms_sha256_n32_h20 = 8, 467 lms_sha256_n32_h25 = 9, 468 }; 470 /* leighton-micali signatures (lms) */ 472 union lms_path switch (lms_algorithm_type type) { 473 case lms_sha256_n32_h5: 474 bytestring32 path_n32_h5[5]; 475 case lms_sha256_n32_h10: 476 bytestring32 path_n32_h10[10]; 477 case lms_sha256_n32_h15: 478 bytestring32 path_n32_h15[15]; 479 case lms_sha256_n32_h20: 480 bytestring32 path_n32_h20[20]; 481 case lms_sha256_n32_h25: 482 bytestring32 path_n32_h25[25]; 483 default: 484 void; /* error condition */ 485 }; 487 struct lms_signature { 488 unsigned int q; 489 lmots_signature lmots_sig; 490 lms_path nodes; 491 }; 493 struct lms_key_n32 { 494 lmots_algorithm_type ots_alg_type; 495 opaque I[16]; 496 opaque K[32]; 497 }; 499 union lms_public_key switch (lms_algorithm_type type) { 500 case lms_sha256_n32_h5: 501 case lms_sha256_n32_h10: 502 case lms_sha256_n32_h15: 503 case lms_sha256_n32_h20: 504 case lms_sha256_n32_h25: 505 lms_key_n32 z_n32; 506 default: 507 void; /* error condition */ 508 }; 510 /* hierarchical signature system (hss) */ 511 struct hss_public_key { 512 unsigned int L; 513 lms_public_key pub; 514 }; 516 struct signed_public_key { 517 lms_signature sig; 518 lms_public_key pub; 519 } 521 struct hss_signature { 522 signed_public_key signed_keys<7>; 523 lms_signature sig_of_message; 524 }; 526 4. LM-OTS One-Time Signatures 528 This section defines LM-OTS signatures. The signature is used to 529 validate the authenticity of a message by associating a secret 530 private key with a shared public key. These are one-time signatures; 531 each private key MUST be used at most one time to sign any given 532 message. 534 As part of the signing process, a digest of the original message is 535 computed using the cryptographic hash function H (see Section 4.1), 536 and the resulting digest is signed. 538 In order to facilitate its use in an N-time signature system, the LM- 539 OTS key generation, signing, and verification algorithms all take as 540 input parameters I and q. The parameter I is a 16 byte string, which 541 indicates which Merkle tree this LM-OTS is used with. The parameter 542 q is a 32 bit integer which indicates the leaf of the Merkle tree 543 where the OTS public key appears. These parameters are used as part 544 of the security string, as listed in Section 7.1. When the LM-OTS 545 signature system is used outside of an N-time signature system, the 546 value I MAY be used to differentiate this one time signatures from 547 others; however the value q MUST be set to the all-zero value. 549 4.1. Parameters 551 The signature system uses the parameters n and w, which are both 552 positive integers. The algorithm description also makes use of the 553 internal parameters p and ls, which are dependent on n and w. These 554 parameters are summarized as follows: 556 n : the number of bytes of the output of the hash function 557 w : the width (in bits) of the Winternitz coefficients; that is, 558 the number of bits from the hash or checksum that is used with a 559 single Winternitz chain. It is a member of the set { 1, 2, 4, 8 } 561 p : the number of n-byte string elements that make up the LM-OTS 562 signature. This is a function of n and w; the values for the 563 defined parameter sets are lited in Table 1; it can also be 564 computed by the algorithm given in Appendix B. 566 ls : the number of left-shift bits used in the checksum function 567 Cksm (defined in Section 4.4) 569 H : a second-preimage-resistant cryptographic hash function that 570 accepts byte strings of any length, and returns an n-byte string 572 For more background on the cryptographic security requirements on H, 573 see the Section 9. 575 The value of n is determined by the hash function selected for use as 576 part of the LM-OTS algorithm; the choice of this value has a strong 577 effect on the security of the system. The parameter w determines the 578 length of the Winternitz chains computed as a part of the OTS 579 signature (which involve 2^w-1 invocations of the hash function); it 580 has little effect on security. Increasing w will shorten the 581 signature, but at a cost of a larger computation to generate and 582 verify a signature. The values of p and ls are dependent on the 583 choices of the parameters n and w, as described in Appendix B. A 584 table illustrating various combinations of n, w, p and ls, along with 585 the resulting signature length, is provided in Table 1. 587 The value of w describes a space/time trade-off; increasing the value 588 of w will cause the signature to shrink (by decreasing the value of 589 p) while increasing the amount of time needed to perform operations 590 with it (generate the public key, generate and verify the signature); 591 in general, the LM-OTS signature is 4+n*(p+1) bytes long, and public 592 key generation will take p*(2^w-1)+1 hash computations (and signature 593 generation and verification will take approximately half that on 594 average). 596 +---------------------+--------+----+---+-----+----+---------+ 597 | Parameter Set Name | H | n | w | p | ls | sig_len | 598 +---------------------+--------+----+---+-----+----+---------+ 599 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 8516 | 600 | | | | | | | | 601 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 4292 | 602 | | | | | | | | 603 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 2180 | 604 | | | | | | | | 605 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 1124 | 606 +---------------------+--------+----+---+-----+----+---------+ 608 Table 1 610 Here SHA256 denotes the SHA-256 hash fucntion defined in NIST 611 standard [FIPS180]. 613 4.2. Private Key 615 The format of the LM-OTS private key is an internal matter to the 616 implementation, and this document does not attempt to define it. One 617 possibility is that the private key may consist of a typecode 618 indicating the particular LM-OTS algorithm, an array x[] containing p 619 n-byte strings, and the 16-byte string I and the 4 byte string q. 620 This private key MUST be used to sign (at most) one message. The 621 following algorithm shows pseudocode for generating a private key. 623 Algorithm 0: Generating a Private Key 625 1. retrieve the values of q and I (the 16-byte identifier of the 626 LMS public/private keypair) from the LMS tree that this LM-OTS 627 private key will be used with 629 2. set type to the typecode of the algorithm 631 3. set n and p according to the typecode and Table 1 633 4. compute the array x as follows: 634 for ( i = 0; i < p; i = i + 1 ) { 635 set x[i] to a uniformly random n-byte string 636 } 638 5. return u32str(type) || I || u32str(q) || x[0] || x[1] || ... 639 || x[p-1] 641 An implementation MAY use a pseudorandom method to compute x[i], as 642 suggested in [Merkle79], page 46. The details of the pseudorandom 643 method do not affect interoperability, but the cryptographic strength 644 MUST match that of the LM-OTS algorithm. Appendix A provides an 645 example of a pseudorandom method for computing the LM-OTS private 646 key. 648 4.3. Public Key 650 The LM-OTS public key is generated from the private key by 651 iteratively applying the function H to each individual element of x, 652 for 2^w - 1 iterations, then hashing all of the resulting values. 654 The public key is generated from the private key using the following 655 algorithm, or any equivalent process. 657 Algorithm 1: Generating a One Time Signature Public Key From a 658 Private Key 660 1. set type to the typecode of the algorithm 662 2. set the integers n, p, and w according to the typecode and Table 1 664 3. determine x, I and q from the private key 666 4. compute the string K as follows: 667 for ( i = 0; i < p; i = i + 1 ) { 668 tmp = x[i] 669 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 670 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 671 } 672 y[i] = tmp 673 } 674 K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) 676 5. return u32str(type) || I || u32str(q) || K 678 where D_PBLC is the fixed two byte value 0x8080, which is used to 679 distinguish the last hash from every other hash in this system. 681 The public key is the value returned by Algorithm 1. 683 4.4. Checksum 685 A checksum is used to ensure that any forgery attempt that 686 manipulates the elements of an existing signature will be detected. 687 This checksum is needed because an attacker can freely advance any of 688 the Winternitz chains. That is, if this checksum were not present, 689 then an attacker who could find a hash that has every digit larger 690 than the valid hash could replace it (and adjust the Winternitz 691 chains). The security property that it provides is detailed in 692 Section 9. The checksum function Cksm is defined as follows, where S 693 denotes the n-byte string that is input to that function, and the 694 value sum is a 16-bit unsigned integer: 696 Algorithm 2: Checksum Calculation 698 sum = 0 699 for ( i = 0; i < (n*8/w); i = i + 1 ) { 700 sum = sum + (2^w - 1) - coef(S, i, w) 701 } 702 return (sum << ls) 704 ls is the parameter that shifts the significant bits of the checksum 705 into the positions that will actually be used by the coef function 706 when encoding the digits of the checksum. The actual ls parameter is 707 a function of the n and w parameters; the values for the currently 708 defined parameter sets is shown in table 1. It is calculated by the 709 algorithm given in Appendix B. 711 Because of the left-shift operation, the rightmost bits of the result 712 of Cksm will often be zeros. Due to the value of p, these bits will 713 not be used during signature generation or verification. 715 4.5. Signature Generation 717 The LM-OTS signature of a message is generated by first prepending 718 the LMS key identifier I, the LMS leaf identifier q, the value D_MESG 719 (0x8181) and the randomizer C to the message, then computing the 720 hash, and then concatenating the checksum of the hash to the hash 721 itself, then considering the resulting value as a sequence of w-bit 722 values, and using each of the w-bit values to determine the number of 723 times to apply the function H to the corresponding element of the 724 private key. The outputs of the function H are concatenated together 725 and returned as the signature. The pseudocode for this procedure is 726 shown below. 728 Algorithm 3: Generating a One Time Signature From a Private Key and a 729 Message 731 1. set type to the typecode of the algorithm 733 2. set n, p, and w according to the typecode and Table 1 735 3. determine x, I and q from the private key 737 4. set C to a uniformly random n-byte string 739 5. compute the array y as follows: 740 Q = H(I || u32str(q) || u16str(D_MESG) || C || message) 741 for ( i = 0; i < p; i = i + 1 ) { 742 a = coef(Q || Cksm(Q), i, w) 743 tmp = x[i] 744 for ( j = 0; j < a; j = j + 1 ) { 745 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 746 } 747 y[i] = tmp 748 } 750 6. return u32str(type) || C || y[0] || ... || y[p-1] 752 Note that this algorithm results in a signature whose elements are 753 intermediate values of the elements computed by the public key 754 algorithm in Section 4.3. 756 The signature is the string returned by Algorithm 3. Section 3.3 757 specifies the typecode and more formally defines the encoding and 758 decoding of the string. 760 4.6. Signature Verification 762 In order to verify a message with its signature (an array of n-byte 763 strings, denoted as y), the receiver must "complete" the chain of 764 iterations of H using the w-bit coefficients of the string resulting 765 from the concatenation of the message hash and its checksum. This 766 computation should result in a value that matches the provided public 767 key. 769 Algorithm 4a: Verifying a Signature and Message Using a Public Key 771 1. if the public key is not at least four bytes long, 772 return INVALID 774 2. parse pubtype, I, q, and K from the public key as follows: 775 a. pubtype = strTou32(first 4 bytes of public key) 777 b. set n according to the pubkey and Table 1; if the public key 778 is not exactly 24 + n bytes long, return INVALID 780 c. I = next 16 bytes of public key 782 d. q = strTou32(next 4 bytes of public key) 784 e. K = next n bytes of public key 786 3. compute the public key candidate Kc from the signature, 787 message, pubtype and the identifiers I and q obtained from the 788 public key, using Algorithm 4b. If Algorithm 4b returns 789 INVALID, then return INVALID. 791 4. if Kc is equal to K, return VALID; otherwise, return INVALID 793 Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, 794 Message, Signature Typecode pubtype, and identifiers I, q 796 1. if the signature is not at least four bytes long, return INVALID 798 2. parse sigtype, C, and y from the signature as follows: 799 a. sigtype = strTou32(first 4 bytes of signature) 801 b. if sigtype is not equal to pubtype, return INVALID 803 c. set n and p according to the pubtype and Table 1; if the 804 signature is not exactly 4 + n * (p+1) bytes long, return INVALID 806 d. C = next n bytes of signature 808 e. y[0] = next n bytes of signature 809 y[1] = next n bytes of signature 810 ... 811 y[p-1] = next n bytes of signature 813 3. compute the string Kc as follows 814 Q = H(I || u32str(q) || u16str(D_MESG) || C || message) 815 for ( i = 0; i < p; i = i + 1 ) { 816 a = coef(Q || Cksm(Q), i, w) 817 tmp = y[i] 818 for ( j = a; j < 2^w - 1; j = j + 1 ) { 819 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 820 } 821 z[i] = tmp 822 } 823 Kc = H(I || u32str(q) || u16str(D_PBLC) || 824 z[0] || z[1] || ... || z[p-1]) 826 4. return Kc 828 5. Leighton-Micali Signatures 830 The Leighton-Micali Signature (LMS) method can sign a potentially 831 large but fixed number of messages. An LMS system uses two 832 cryptographic components: a one-time signature method and a hash 833 function. Each LMS public/private key pair is associated with a 834 perfect binary tree, each node of which contains an m-byte value, 835 where m is the output length of the hash function. Each leaf of the 836 tree contains the value of the public key of an LM-OTS public/private 837 key pair. The value contained by the root of the tree is the LMS 838 public key. Each interior node is computed by applying the hash 839 function to the concatenation of the values of its children nodes. 841 Each node of the tree is associated with a node number, an unsigned 842 integer that is denoted as node_num in the algorithms below, which is 843 computed as follows. The root node has node number 1; for each node 844 with node number N < 2^h (where h is the height of the tree), its 845 left child has node number 2*N, while its right child has node number 846 2*N+1. The result of this is that each node within the tree will 847 have a unique node number, and the leaves will have node numbers 2^h, 848 (2^h)+1, (2^h)+2, ..., (2^h)+(2^h)-1. In general, the j-th node at 849 level i has node number 2^i + j. The node number can conveniently be 850 computed when it is needed in the LMS algorithms, as described in 851 those algorithms. 853 5.1. Parameters 855 An LMS system has the following parameters: 857 h : the height of the tree, and 859 m : the number of bytes associated with each node. 861 H : a second-preimage-resistant cryptographic hash function that 862 accepts byte strings of any length, and returns an m-byte string. 864 There are 2^h leaves in the tree. 866 The overall strength of the LMS signatures is governed by the weaker 867 of the hash function used within the LM-OTS and the hash function 868 used within the LMS system. In order to minimize the risk, these two 869 hash functions SHOULD be the same (so that an attacker could not take 870 advantage of the weaker hash function choice). 872 +--------------------+--------+----+----+ 873 | Name | H | m | h | 874 +--------------------+--------+----+----+ 875 | LMS_SHA256_M32_H5 | SHA256 | 32 | 5 | 876 | | | | | 877 | LMS_SHA256_M32_H10 | SHA256 | 32 | 10 | 878 | | | | | 879 | LMS_SHA256_M32_H15 | SHA256 | 32 | 15 | 880 | | | | | 881 | LMS_SHA256_M32_H20 | SHA256 | 32 | 20 | 882 | | | | | 883 | LMS_SHA256_M32_H25 | SHA256 | 32 | 25 | 884 +--------------------+--------+----+----+ 886 Table 2 888 5.2. LMS Private Key 890 The format of the LMS private key is an internal matter to the 891 implementation, and this document does not attempt to define it. One 892 possibility is that it may consist of an array OTS_PRIV[] of 2^h LM- 893 OTS private keys, and the leaf number q of the next LM-OTS private 894 key that has not yet been used. The q-th element of OTS_PRIV[] is 895 generated using Algorithm 0 with the identifiers I, q. The leaf 896 number q is initialized to zero when the LMS private key is created. 897 The process is as follows: 899 Algorithm 5: Computing an LMS Private Key. 901 1. determine h and m from the typecode and Table 2. 903 2. set I to a uniformly random 16-byte string 905 3. compute the array OTS_PRIV[] as follows: 906 for ( q = 0; q < 2^h; q = q + 1) { 907 OTS_PRIV[q] = LM-OTS private key with identifiers I, q 908 } 910 4. q = 0 912 An LMS private key MAY be generated pseudorandomly from a secret 913 value, in which case the secret value MUST be at least m bytes long, 914 be uniformly random, and MUST NOT be used for any other purpose than 915 the generation of the LMS private key. The details of how this 916 process is done do not affect interoperability; that is, the public 917 key verification operation is independent of these details. 918 Appendix A provides an example of a pseudorandom method for computing 919 an LMS private key. 921 The signature generation logic uses q as the next leaf to use, hence 922 step 4 starts it off at the left-most one. Because the signature 923 proces increments q after the signature operation, the first 924 signature will have q=0. 926 5.3. LMS Public Key 928 An LMS public key is defined as follows, where we denote the public 929 key final hash value (namely, the K value computed in Algorithm 1) 930 associated with the i-th LM-OTS private key as OTS_PUB_HASH[i], with 931 i ranging from 0 to (2^h)-1. Each instance of an LMS public/private 932 key pair is associated with a balanced binary tree, and the nodes of 933 that tree are indexed from 1 to 2^(h+1)-1. Each node is associated 934 with an m-byte string, and the string for the r-th node is denoted as 935 T[r] and is defined as 936 if r >= 2^h: 937 H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h]) 938 else 939 H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1]) 941 where D_LEAF is the fixed two byte value 0x8282, and D_INTR is the 942 fixed two byte value 0x8383, both of which are used to distinguish 943 this hash from every other hash in this system. 945 When we have r >= 2^h, then we are processing a leaf node (and thus 946 hashing only a single LM-OTS public key). When we have r < 2^h, then 947 we are processing an internal node, that is, a node with two child 948 nodes that we need to combine. 950 The LMS public key is the string 952 u32str(type) || u32str(otstype) || I || T[1] 954 Section 3.3 specifies the format of the type variable. The value 955 otstype is the parameter set for the LM-OTS public/private keypairs 956 used. The value I is the private key identifier, and is the value 957 used for all computations for the same LMS tree. The value T[1] can 958 be computed via recursive application of the above equation, or by 959 any equivalent method. An iterative procedure is outlined in 960 Appendix C. 962 5.4. LMS Signature 964 An LMS signature consists of 966 the number q of the leaf associated with the LM-OTS signature, as 967 a four-byte unsigned integer in network byte order, 969 an LM-OTS signature, 971 a typecode indicating the particular LMS algorithm, 973 an array of h m-byte values that is associated with the path 974 through the tree from the leaf associated with the LM-OTS 975 signature to the root. 977 Symbolically, the signature can be represented as 979 u32str(q) || lmots_signature || u32str(type) || 980 path[0] || path[1] || path[2] || ... || path[h-1] 982 Section 3.3 specifies the typecode and more formally defines the 983 format. The array for a tree with height h will have h values and 984 contains the values of the siblings of (that is, is adjacent to) the 985 nodes on the path from the leaf to the root, where the sibling to 986 node A is the other node which shares node A's parent. In the 987 signature, 0 is counted from the bottom level of the tree, and so 988 path[0] is the value of the node adjacent to leaf node q; path[1] is 989 the second level node that is adjacent to leaf node q's parent, and 990 so up the tree until we get to path[h-1], which is the value of the 991 next-to-the-top level node that leaf node q does not reside in. 993 Below is a simple example of the authentication path for h=3 and q=2. 994 The leaf marked OTS is the one time signature which is used to sign 995 the actual message. The nodes on the path from the OTS public key to 996 the root are marked with a *, while the nodes that are used within 997 the path array are marked with a **. The values in the path array 998 are those nodes which are siblings of the nodes on the path; path[0] 999 is the leaf** node that is adjacent to the OTS public key (which is 1000 the start of the path); path[1] is the T[4]** node which is the 1001 sibling of the second node T[5]* on the path, and path[2] is the 1002 T[3]** node which is the sibling of the third node T[2]* on the path. 1004 Root 1005 | 1006 --------------------------------- 1007 | | 1008 T[2]* T[3]** 1009 | | 1010 ------------------ ----------------- 1011 | | | | 1012 T[4]** T[5]* T[6] T[7] 1013 | | | | 1014 --------- ---------- -------- --------- 1015 | | | | | | | | 1016 leaf leaf OTS leaf** leaf leaf leaf leaf 1018 The idea behind this authentication path is that it allows us to 1019 validate the OTS hash with using h path array values and hash 1020 computations. What the verifier does is recompute the hashes up the 1021 path; first, he hashes the given OTS and path[0] value, giving a 1022 tentative T[5]' value. Then, he hashes his path[1] and tentative 1023 T[5]' value to get a tentative T[2]' value. Then, he hashes that and 1024 the path[2] value to get a tentative Root' value. If that value is 1025 the known public key of the Merkle tree, then we can assume that the 1026 value T[2]' he got was the correct T[2] value in the original tree, 1027 and so the T[5]' value he got was the correct T[5] value in the 1028 original tree, and so the OTS public key is the same as in the 1029 original, and hence is correct. 1031 5.4.1. LMS Signature Generation 1033 To compute the LMS signature of a message with an LMS private key, 1034 the signer first computes the LM-OTS signature of the message using 1035 the leaf number of the next unused LM-OTS private key. The leaf 1036 number q in the signature is set to the leaf number of the LMS 1037 private key that was used in the signature. Before releasing the 1038 signature, the leaf number q in the LMS private key MUST be 1039 incremented, to prevent the LM-OTS private key from being used again. 1040 If the LMS private key is maintained in nonvolatile memory, then the 1041 implementation MUST ensure that the incremented value has been stored 1042 before releasing the signature. The issue this tries to prevent is a 1043 scenario where a) we generate a signature, using one LM-OTS private 1044 key, and release it to the application, b) before we update the 1045 nonvolatile memory, we crash, and c) we reboot, and generate a second 1046 signature using the same LM-OTS private key; with two different 1047 signatures using the same LM-OTS private key, someone could 1048 potentially generate a forged signature of a third message. 1050 The array of node values in the signature MAY be computed in any way. 1051 There are many potential time/storage tradeoffs that can be applied. 1052 The fastest alternative is to store all of the nodes of the tree and 1053 set the array in the signature by copying them; pseudocode to do so 1054 appears in Appendix D. The least storage intensive alternative is to 1055 recompute all of the nodes for each signature. Note that the details 1056 of this procedure are not important for interoperability; it is not 1057 necessary to know any of these details in order to perform the 1058 signature verification operation. The internal nodes of the tree 1059 need not be kept secret, and thus a node-caching scheme that stores 1060 only internal nodes can sidestep the need for strong protections. 1062 Several useful time/storage tradeoffs are described in the 'Small- 1063 Memory LM Schemes' section of [USPTO5432852]. 1065 5.4.2. LMS Signature Verification 1067 An LMS signature is verified by first using the LM-OTS signature 1068 verification algorithm (Algorithm 4b) to compute the LM-OTS public 1069 key from the LM-OTS signature and the message. The value of that 1070 public key is then assigned to the associated leaf of the LMS tree, 1071 then the root of the tree is computed from the leaf value and the 1072 array path[] as described in Algorithm 6 below. If the root value 1073 matches the public key, then the signature is valid; otherwise, the 1074 signature fails. 1076 Algorithm 6: LMS Signature Verification 1078 1. if the public key is not at least eight bytes long, return 1079 INVALID 1081 2. parse pubtype, I, and T[1] from the public key as follows: 1083 a. pubtype = strTou32(first 4 bytes of public key) 1085 b. ots_typecode = strTou32(next 4 bytes of public key) 1087 c. set m according to pubtype, based on Table 2 1089 d. if the public key is not exactly 24 + m bytes 1090 long, return INVALID 1092 e. I = next 16 bytes of the public key 1094 f. T[1] = next m bytes of the public key 1096 3. compute the LMS Public Key Candidate Tc from the signature, 1097 message, identifier, pubtype and ots_typecode using Algorithm 6a. 1099 4. if Tc is equal to T[1], return VALID; otherwise, return INVALID 1101 Algorithm 6a: Computing an LMS Public Key Candidate from a Signature, 1102 Message, Identifier, and algorithm typecode 1104 1. if the signature is not at least eight bytes long, return INVALID 1106 2. parse sigtype, q, lmots_signature, and path from the signature as 1107 follows: 1109 a. q = strTou32(first 4 bytes of signature) 1111 b. otssigtype = strTou32(next 4 bytes of signature) 1113 c. if otssigtype is not the OTS typecode from the public key, 1114 return INVALID 1116 d. set n, p according to otssigtype and Table 1; if the 1117 signature is not at least 12 + n * (p + 1) bytes long, 1118 return INVALID 1120 e. lmots_signature = bytes 4 through 7 + n * (p + 1) 1121 of signature 1123 f. sigtype = strTou32(bytes 8 + n * (p + 1)) through 1124 11 + n * (p + 1) of signature) 1126 f. if sigtype is not the LM typecode from the public key, 1127 return INVALID 1129 g. set m, h according to sigtype and Table 2 1131 h. if q >= 2^h or the signature is not exactly 1132 12 + n * (p + 1) + m * h bytes long, 1133 return INVALID 1135 i. set path as follows: 1136 path[0] = next m bytes of signature 1137 path[1] = next m bytes of signature 1138 ... 1139 path[h-1] = next m bytes of signature 1141 3. Kc = candidate public key computed by applying Algorithm 4b 1142 to the signature lmots_signature, the message, and the 1143 identifiers I, q 1145 4. compute the candidate LMS root value Tc as follows: 1146 node_num = 2^h + q 1147 tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) 1148 i = 0 1149 while (node_num > 1) { 1150 if (node_num is odd): 1151 tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) 1152 else: 1153 tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i]) 1154 node_num = node_num/2 1155 i = i + 1 1156 } 1157 Tc = tmp 1159 5. return Tc 1161 6. Hierarchical signatures 1163 In scenarios where it is necessary to minimize the time taken by the 1164 public key generation process, a Hierarchical N-time Signature System 1165 (HSS) can be used. This hierarchical scheme, which we describe in 1166 this section, uses the LMS scheme as a component. In HSS, we have a 1167 sequence of L LMS trees, where the public key for the first LMS tree 1168 is included in the public key of the HSS system, and where each LMS 1169 private key signs the next LMS public key, and where the last LMS 1170 private key signs the actual message. For example, if we have a 1171 three level hierarchy (L=3), then to sign a message, we would have: 1173 The first LMS private key (level 0) signs a level 1 LMS public 1174 key. 1176 The second LMS private key (level 1) signs a level 2 LMS public 1177 key. 1179 The third LMS private key (level 2) signs the message. 1181 The root of the level 0 LMS tree is contained in the HSS public key. 1183 To verify the LMS signature, we would verify all the signatures: 1185 We would verify that the level 1 LMS public key is correctly 1186 signed by the level 0 signature. 1188 We would verify that the level 2 LMS public key is correctly 1189 signed by the level 1 signature. 1191 We would verify that the message is correctly signed by the level 1192 2 signature. 1194 We would accept the HSS signature only if all the signatures 1195 validated. 1197 During the signature generation process, we sign messages with the 1198 lowest (level L-1) LMS tree. Once we have used all the leafs in that 1199 tree to sign messages, we would discard it, generate a fresh LMS 1200 tree, and sign it with the next (level L-2) LMS tree (and when that 1201 is used up, recursively generate and sign a fresh level L-2 LMS 1202 tree). 1204 HSS, in essence, utilizes a tree of LMS trees. There is a single LMS 1205 tree at level 0 (the root). Each LMS tree (actually, the private key 1206 corresponding to the LMS tree) at level i is used to sign 2^h objects 1207 (where h is the height of trees at level i). If i < L-1, then each 1208 object will be another LMS tree (actually, the public key) at level 1209 i+1; if i = L-1, we've reached the bottom of the HSS tree, and so 1210 each object is a message from the application. The HSS public key 1211 contains the public key of the LMS tree at the root, and an HSS 1212 signature is associated with a path from the root of the HSS tree to 1213 the leaf. 1215 Compared to LMS, HSS has a much reduced public key generation time, 1216 as only the root tree needs to be generated prior to the distribution 1217 of the HSS public key. For example, a L=3 tree (with h=10 at each 1218 level) would have 1 level 0 LMS tree, 2^10 level 1 LMS trees (with 1219 each such level 1 public key signed by one of the 1024 level 0 OTS 1220 public keys), and 2^20 level 2 LMS trees. Only 1024 OTS public keys 1221 need to be computed to generate the HSS public key (as you need to 1222 compute only the level 0 LMS tree to compute that value; you can, of 1223 course, decide to compute the initial level 1 and level 2 LMS trees). 1224 And, the 2^20 level 2 LMS trees can jointly sign a total of over a 1225 billion messages. In contrast, a single LMS tree that could sign a 1226 billion messages would require a billion OTS public keys to be 1227 computed first (even if h=30 were allowed in a supported parameter 1228 set). 1230 Each LMS tree within the hierarchy is associated with a distinct LMS 1231 public key, private key, signature, and identifier. The number of 1232 levels is denoted L, and is between one and eight, inclusive. The 1233 following notation is used, where i is an integer between 0 and L-1 1234 inclusive, and the root of the hierarchy is level 0: 1236 prv[i] is the current LMS private key of the i-th level, 1238 pub[i] is the current LMS public key of the i-th level (which 1239 includes the identifier I as well as the root node value K), 1241 sig[i] is the LMS signature of public key pub[i+1] generated using 1242 the private key prv[i], 1244 In this section, we say that an N-time private key is exhausted when 1245 it has generated N signatures, and thus it can no longer be used for 1246 signing. 1248 For i > 0, the values prv[i], pub[i] and sig[i] will be updated over 1249 time, as private keys are exhausted, and replaced by newer keys. 1251 HSS allows L=1, in which case the HSS public key and signature 1252 formats are essentially the LMS public key and signature formats, 1253 prepended by a fixed field. Since HSS with L=1 has very little 1254 overhead compared to LMS, all implementations MUST support HSS in 1255 order to maximize interoperability. 1257 We specifically allow different LMS levels to use different parameter 1258 sets. For example, the 0-th LMS public key (the root) may use the 1259 LMS_SHA256_M32_H15 parameter set, while the 1-th public key may use 1260 LMS_SHA256_M32_H10. There are practical reasons to allow this; for 1261 one, the signer may decide to store parts of the 0-th LMS tree (that 1262 it needs to construct while computing the public key) to accelerate 1263 later operations. As the 0-th tree is never updated, these internal 1264 nodes will never need to be recomputed. In addition, during the 1265 signature generation operation, almost all the operations involved 1266 with updating the authentication path occurs with the bottom (L-1th) 1267 LMS public key; hence it may be useful to make the tree that 1268 implements that to be shorter. 1270 A close reading of the HSS verification pseudocode would show that it 1271 would allow the parameters of the non-top LMS public keys to change 1272 over time; for example, the signer might initially have the 1-th LMS 1273 public key to use LMS_SHA256_M32_H10, but when that tree is 1274 exhausted, the signer might replace it with LMS_SHA256_M32_H15 LMS 1275 public key. While this would work with the example verification 1276 pseudocode, the signer MUST NOT change the parameter sets for a 1277 specific level. This prohibition is to support verifiers that may 1278 keep state over the course of several signature verifications. 1280 6.1. Key Generation 1282 When an HSS key pair is generated, the key pair for each level MUST 1283 have its own identifier I. 1285 To generate an HSS private and public key pair, new LMS private and 1286 public keys are generated for prv[i] and pub[i] for i=0, ... , L-1. 1287 These key pairs, and their identifiers, MUST be generated 1288 independently. 1290 The public key of the HSS scheme consists of the number of levels L, 1291 followed by pub[0], the public key of the top level. 1293 The HSS private key consists of prv[0], ... , prv[L-1]. The value of 1294 pub[0] does not change (and, except for the index q, the value of 1295 prv[0] need not change), though the values of pub[i] and prv[i] are 1296 dynamic for i > 0, and are changed by the signature generation 1297 algorithm. 1299 Here is some pseudocode that explains this key generation logic 1301 Algorithm 7: Generating an HSS keypair 1303 1. generate L LMS key pairs, as specified in sections 5.2 and 5.3 1305 2. sign each child key pair with the private key of its parent: 1306 i = 0 1307 while (i < L-1) { 1308 sig[i] = lms_signature( pub[i+1], priv[i] ) 1309 i = i + 1 1310 } 1312 3. return u32str(L) || pub[0] 1314 Note that the generation of the non-root LMS key pair, and the 1315 operations of step 2 can be delayed until the generation of the first 1316 signature, should it be advantageous for the implementation to do so. 1318 6.2. Signature Generation 1320 To sign a message using an HSS keypair, the following steps are 1321 performed: 1323 If prv[L-1] is exhausted, then determine the smallest integer d 1324 such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] 1325 are exhausted. If d is equal to zero, then the HSS key pair is 1326 exhausted, and it MUST NOT generate any more signatures. 1327 Otherwise, the key pairs for levels d through L-1 must be 1328 regenerated during the signature generation process, as follows. 1329 For i from d to L-1, a new LMS public and private key pair with a 1330 new identifier is generated, pub[i] and prv[i] are set to those 1331 values, then the public key pub[i] is signed with prv[i-1], and 1332 sig[i-1] is set to the resulting value. 1334 The message is signed with prv[L-1], and the value sig[L-1] is set 1335 to that result. 1337 The value of the HSS signature is set as follows. We let 1338 signed_pub_key denote an array of octet strings, where 1339 signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk- 1340 1, inclusive, where Nspk = L-1 denotes the number of signed public 1341 keys. Then the HSS signature is u32str(Nspk) || 1342 signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]. 1344 Note that the number of signed_pub_key elements in the signature 1345 is indicated by the value Nspk that appears in the initial four 1346 bytes of the signature. 1348 Here is some pseudocode of the above logic 1349 Algorithm 8: Generating an HSS signature 1351 1. If the message-signing key prv[L-1] is exhausted, regenerate that 1352 key pair, together with any parent key pairs that might be 1353 necessary. 1354 If the root key pair is exhausted, then the HSS key pair is 1355 exhausted and it MUST NOT generate any more signatures. 1357 d = L 1358 while (prv[d-1].q == 2^(prv[d-1].h)) { 1359 if (d == 0) 1360 return FAILURE 1361 d = d - 1 1362 } 1363 while (d < L) { 1364 create lms keypair pub[d], prv[d] 1365 sig[d-1] = lms_signature( pub[d], prv[d-1] ) 1366 d = d + 1 1367 } 1369 2. sign the message 1370 sig[L-1] = lms_signature( msg, prv[L-1] ) 1372 3. Create the list of signed public keys 1373 i = 0; 1374 while (i < L-1) { 1375 signed_pub_key[i] = sig[i] || pub[i+1] 1376 i = i + 1 1377 } 1379 4. return u32str(L-1) || signed_pub_key[0] || ... 1380 || signed_pub_key[L-2] || sig[L-1] 1382 In the specific case of L=1, the format of an HSS signature is 1384 u32str(0) || sig[0] 1386 In the general case, the format of an HSS signature is 1388 u32str(Nspk) || signed_pub_key[0] || ... 1389 || signed_pub_key[Nspk-1] || sig[Nspk] 1391 which is equivalent to 1393 u32str(Nspk) || sig[0] || pub[1] || ... 1394 || sig[Nspk-1] || pub[Nspk] || sig[Nspk] 1396 6.3. Signature Verification 1398 To verify a signature S and message using the public key pub, the 1399 following steps are performed: 1401 The signature S is parsed into its components as follows: 1403 Nspk = strTou32(first four bytes of S) 1404 if Nspk+1 is not equal to the number of levels L in pub: 1405 return INVALID 1406 for (i = 0; i < Nspk; i = i + 1) { 1407 siglist[i] = next LMS signature parsed from S 1408 publist[i] = next LMS public key parsed from S 1409 } 1410 siglist[Nspk] = next LMS signature parsed from S 1412 key = pub 1413 for (i = 0; i < Nspk; i = i + 1) { 1414 sig = siglist[i] 1415 msg = publist[i] 1416 if (lms_verify(msg, key, sig) != VALID): 1417 return INVALID 1418 key = msg 1419 } 1420 return lms_verify(message, key, siglist[Nspk]) 1422 Since the length of an LMS signature cannot be known without parsing 1423 it, the HSS signature verification algorithm makes use of an LMS 1424 signature parsing routine that takes as input a string consisting of 1425 an LMS signature with an arbitrary string appended to it, and returns 1426 both the LMS signature and the appended string. The latter is passed 1427 on for further processing. 1429 6.4. Parameter Set Recommendations 1431 As for guidance as to the number of LMS level, and the size of each, 1432 any discussion of performance is implementation specific. In 1433 general, the sole drawback for a single LMS tree is the time it takes 1434 to generate the public key; as every LM-OTS public key needs to be 1435 generated, the time this takes can be substantial. For a two level 1436 tree, only the top level LMS tree and the initial bottom level LMS 1437 tree needs to be generated initially (before the first signature is 1438 generated); this will in general be significantly quicker. 1440 To give a general idea on the trade-offs available, we include some 1441 measurements taken with the github.com/cisco/hash-sigs LMS 1442 implementation, taken on a 3.3 GHz Xeon processor, with threading 1443 enabled. We tried various parameter sets, all with W=8 (which 1444 minimizes signature size, while increasing time). These are here to 1445 give a guideline as to what's possible; for the computational time, 1446 your mileage may vary, depending on the computing resources you have. 1447 The machine these tests were performed on does not have the SHA-256 1448 extensions; you could possibly do significantly better. 1450 +---------+------------+---------+-------------+ 1451 | ParmSet | KeyGenTime | SigSize | KeyLifetime | 1452 +---------+------------+---------+-------------+ 1453 | 15 | 6 sec | 1616 | 30 seconds | 1454 | | | | | 1455 | 20 | 3 min | 1776 | 16 minutes | 1456 | | | | | 1457 | 25 | 1.5 hour | 1936 | 9 hours | 1458 | | | | | 1459 | 15/10 | 6 sec | 3172 | 9 hours | 1460 | | | | | 1461 | 15/15 | 6 sec | 3332 | 12 days | 1462 | | | | | 1463 | 20/10 | 3 min | 3332 | 12 days | 1464 | | | | | 1465 | 20/15 | 3 min | 3492 | 1 year | 1466 | | | | | 1467 | 25/10 | 1.5 hour | 3492 | 1 year | 1468 | | | | | 1469 | 25/15 | 1.5 hour | 3652 | 34 years | 1470 +---------+------------+---------+-------------+ 1472 Table 3 1474 ParmSet: this is the height of the Merkle tree(s); parameter sets 1475 listed as a single integer have L=1, and consist a single Merkle tree 1476 of that height; parameter sets with L=2 are listed as x/y, with x 1477 being the height of the top level Merkle tree, and y being the bottom 1478 level. 1480 KeyGenTime: the measured key generation time; that is, the time 1481 needed to generate the public private key pair. 1483 SigSize: the size of a signature (in bytes) 1485 KeyLifetime: the lifetime of a key, assuming we generated 1000 1486 signatures per second. In practice, we're not likely to get anywhere 1487 close to 1000 signatures per second sustained; if you have a more 1488 appropriate figure for your scenario, this column is pretty easy to 1489 recompute. 1491 As for signature generation or verification times, those are 1492 moderately insensitive to the above parameter settings (except for 1493 the Winternitz setting, and the number of Merkle trees for 1494 verification). Tests on the same machine (without multithreading) 1495 gave approximately 4msec to sign a short message, 2.6msec to verify; 1496 these tests used a two level ParmSet; a single level would 1497 approximately halve the verification time. All times can be 1498 significantly improved (by perhaps a factor of 8) by using a 1499 parameter set with W=4; however that also about doubles the signature 1500 size. 1502 7. Rationale 1504 The goal of this note is to describe the LM-OTS, LMS and HSS 1505 algorithms following the original references and present the modern 1506 security analysis of those algorithms. Other signature methods are 1507 out of scope and may be interesting follow-on work. 1509 We adopt the techniques described by Leighton and Micali to mitigate 1510 attacks that amortize their work over multiple invocations of the 1511 hash function. 1513 The values taken by the identifier I across different LMS public/ 1514 private key pairs are chosen randomly in order to improve security. 1515 The analysis of this method in [Fluhrer17] shows that we do not need 1516 uniqueness to ensure security; we do need to ensure that we don't 1517 have a large number of private keys that use the same I value. By 1518 randomly selecting 16 byte I values, the chance that, out of 2^64 1519 private keys, 4 or more of them will use the same I value is 1520 negligible (that is, has probability less than 2^-128). 1522 The reason 16 bytes I values were selected was to optimize the 1523 Winternitz hash chain operation. With the current settings, the 1524 value being hashed is exactly 55 bytes long (for a 32 byte hash 1525 function), which SHA-256 can hash in a single hash compression 1526 operation. Other hash functions may be used in future 1527 specifications; all the ones that we will be likely to support (SHA- 1528 512/256 and the various SHA-3 hashes) would work well with a 16-byte 1529 I value. 1531 The signature and public key formats are designed so that they are 1532 relatively easy to parse. Each format starts with a 32-bit 1533 enumeration value that indicates the details of the signature 1534 algorithm and provides all of the information that is needed in order 1535 to parse the format. 1537 The Checksum Section 4.4 is calculated using a non-negative integer 1538 "sum", whose width was chosen to be an integer number of w-bit fields 1539 such that it is capable of holding the difference of the total 1540 possible number of applications of the function H as defined in the 1541 signing algorithm of Section 4.5 and the total actual number. In the 1542 case that the number of times H is applied is 0, the sum is (2^w - 1) 1543 * (8*n/w). Thus for the purposes of this document, which describes 1544 signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 1545 4, 8 }, the sum variable is a 16-bit non-negative integer for all 1546 combinations of n and w. The calculation uses the parameter ls 1547 defined in Section 4.1 and calculated in Appendix B, which indicates 1548 the number of bits used in the left-shift operation. 1550 7.1. Security String 1552 To improve security against attacks that amortize their effort 1553 against multiple invocations of the hash function, Leighton and 1554 Micali introduce a "security string" that is distinct for each 1555 invocation of that function. Whenever this process computes a hash, 1556 the string being hashed will start with a string formed from the 1557 below fields. These fields will appear in fixed locations in the 1558 value we compute the hash of, and so we list where in the hash these 1559 fields would be present. These fields that make up this string are: 1561 I - a 16-byte identifier for the LMS public/private key pair. It 1562 MUST be chosen uniformly at random, or via a pseudorandom process, 1563 at the time that a key pair is generated, in order to minimize the 1564 probability that any specific value of I be used for a large 1565 number of different LMS private keys. This is always bytes 0-15 1566 of the value being hashed. 1568 r - in the LMS N-time signature scheme, the node number r 1569 associated with a particular node of a hash tree is used as an 1570 input to the hash used to compute that node. This value is 1571 represented as a 32-bit (four byte) unsigned integer in network 1572 byte order. Either r or q (depending on the domain separation 1573 parameter) will be bytes 16-19 of the value being hashed. 1575 q - in the LMS N-time signature scheme, each LM-OTS signature is 1576 associated with the leaf of a hash tree, and q is set to the leaf 1577 number. This ensures that a distinct value of q is used for each 1578 distinct LM-OTS public/private key pair. This value is 1579 represented as a 32-bit (four byte) unsigned integer in network 1580 byte order. Either r or q (depending on the domain separation 1581 parameter) will be bytes 16-19 of the value being hashed. 1583 D - a domain separation parameter, which is a two byte identifier 1584 that takes on different values in the different contexts in which 1585 the hash function is invoked. D occurs in bytes 20, 21 of the 1586 value being hashed and takes on the following values: 1588 D_PBLC = 0x8080 when computing the hash of all of the iterates 1589 in the LM-OTS algorithm 1591 D_MESG = 0x8181 when computing the hash of the message in the 1592 LM-OTS algorithms 1594 D_LEAF = 0x8282 when computing the hash of the leaf of an LMS 1595 tree 1597 D_INTR = 0x8383 when computing the hash of an interior node of 1598 an LMS tree 1600 i - a value between 0 and 264; this is used in the LM-OTS scheme, 1601 when either computing the iterations of the Winternitz chain, or 1602 when using the suggested LM-OTS private key generation process. 1603 It is represented as a 16-bit (two-byte) unsigned integer in 1604 network byte order. If present, it occurs at bytes 20, 21 of the 1605 value being hashed. 1607 j - in the LM-OTS scheme, j is the iteration number used when the 1608 private key element is being iteratively hashed. It is 1609 represented as an 8-bit (one byte) unsigned integer and is present 1610 if i is a value between 0 and 264. If present, it occurs at bytes 1611 22 to 21+n of the value being hashed. 1613 C - an n-byte randomizer that is included with the message 1614 whenever it is being hashed to improve security. C MUST be chosen 1615 uniformly at random, or via a pseudorandom process. It is present 1616 if D=D_MESG, and it occurs at bytes 22 to 21+n of the value being 1617 hashed. 1619 8. IANA Considerations 1621 The Internet Assigned Numbers Authority (IANA) is requested to create 1622 two registries: one for OTS signatures, which includes all of the LM- 1623 OTS signatures as defined in Section 4, and one for Leighton-Micali 1624 Signatures, as defined in Section 5. 1626 Additions to these registries require that a specification be 1627 documented in an RFC or another permanent and readily available 1628 reference in sufficient detail that interoperability between 1629 independent implementations is possible. IANA SHOULD verify that all 1630 applications for additions to these registries hve first been 1631 reviewed by the IRTF Crypto Forum Research Group (CFRG). 1633 Each entry in the registry contains the following elements: 1635 a short name, such as "LMS_SHA256_M32_H10", 1636 a positive number, and 1638 a reference to a specification that completely defines the 1639 signature method test cases that can be used to verify the 1640 correctness of an implementation. 1642 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1643 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1644 are reserved for private use; no attempt will be made to prevent 1645 multiple sites from using the same value in different (and 1646 incompatible) ways [RFC2434]. 1648 The LM-OTS registry is as follows. 1650 +----------------------+-----------+--------------------+ 1651 | Name | Reference | Numeric Identifier | 1652 +----------------------+-----------+--------------------+ 1653 | Reserved | | 0x00000000 | 1654 | | | | 1655 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 | 1656 | | | | 1657 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 | 1658 | | | | 1659 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 | 1660 | | | | 1661 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 | 1662 +----------------------+-----------+--------------------+ 1664 Table 4 1666 The LMS registry is as follows. 1668 +--------------------+-----------+--------------------+ 1669 | Name | Reference | Numeric Identifier | 1670 +--------------------+-----------+--------------------+ 1671 | Reserved | | 0x0 - 0x4 | 1672 | | | | 1673 | LMS_SHA256_M32_H5 | Section 5 | 0x00000005 | 1674 | | | | 1675 | LMS_SHA256_M32_H10 | Section 5 | 0x00000006 | 1676 | | | | 1677 | LMS_SHA256_M32_H15 | Section 5 | 0x00000007 | 1678 | | | | 1679 | LMS_SHA256_M32_H20 | Section 5 | 0x00000008 | 1680 | | | | 1681 | LMS_SHA256_M32_H25 | Section 5 | 0x00000009 | 1682 +--------------------+-----------+--------------------+ 1684 Table 5 1686 An IANA registration of a signature system does not constitute an 1687 endorsement of that system or its security. 1689 The LM-OTS and the LMS registries currently occupy a disjoint set of 1690 values. This coincidence is a historical accident; the correctness 1691 of the system does not depend on this. IANA is not required to 1692 maintain this situation. 1694 9. Security Considerations 1696 The hash function H MUST have second preimage resistance: it must be 1697 computationally infeasible for an attacker that is given one message 1698 M to be able to find a second message M' such that H(M) = H(M'). 1700 The security goal of a signature system is to prevent forgeries. A 1701 successful forgery occurs when an attacker who does not know the 1702 private key associated with a public key can find a message (distinct 1703 from all previously signed ones) and signature that is valid with 1704 that public key (that is, the Signature Verification algorithm 1705 applied to that signature and message and public key will return 1706 VALID). Such an attacker, in the strongest case, may have the 1707 ability to forge valid signatures for an arbitrary number of other 1708 messages. 1710 LMS is provably secure in the random oracle model, where the hash 1711 compression function is considered the random oracle, as shown by 1712 [Fluhrer17]. Corollary 1 of that paper states: 1714 If we have no more than 2^64 randomly chosen LMS private keys, 1715 allow the attacker access to a signing oracle and a SHA-256 hash 1716 compression oracle, and allow a maximum of 2^120 hash compression 1717 computations, then the probability of an attacker being able to 1718 generate a single forgery against any of those LMS keys is less 1719 than 2^-129. 1721 Many of the objects within the public key and the signature start 1722 with a typecode. A verifier MUST check each of these typecodes, and 1723 a verification operation on a signature with an unknown type, or a 1724 type that does not correspond to the type within the public key MUST 1725 return INVALID. The expected length of a variable-length object can 1726 be determined from its typecode, and if an object has a different 1727 length, then any signature computed from the object is INVALID. 1729 9.1. Hash Formats 1731 The format of the inputs to the hash function H have the property 1732 that each invocation of that function has an input that is repeated 1733 by a small bounded number of other inputs (due to potential repeats 1734 of the I value), and in particular, will vary somewhere in the first 1735 23 bytes of the value being hashed. This property is important for a 1736 proof of security in the random oracle model. 1738 The formats used during key generation and signing (including the 1739 recommended pseudorandom key generation procedure in Appendix A): 1741 I || u32str(q) || u16str(i) || u8str(j) || tmp 1742 I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1] 1743 I || u32str(q) || u16str(D_MESG) || C || message 1744 I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h] 1745 I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1] 1746 I || u32str(q) || u16str(i) || u8str(0xff) || SEED 1748 Each hash type listed is distinct; at locations 20, 21 of the value 1749 being hashed, there exists either a fixed value D_PBLC, D_MESG, 1750 D_LEAF, D_INTR, or a 16 bit value i. These fixed values are distinct 1751 from each other, and are large (over 32768), while the 16 bit values 1752 of i are small (currently no more than 265; possibly being slightly 1753 larger if larger hash functions are supported); hence the range of 1754 possible values of i will not collide any of the D_PBLC, D_MESG, 1755 D_LEAF, D_INTR identifiers. The only other collision possibility is 1756 the Winternitz chain hash colliding with the recommended pseudorandom 1757 key generation process; here, at location 22 of the value being 1758 hashed, the Winternitz chain function has the value u8str(j), where j 1759 is a value between 0 and 254, while location 22 of the recommended 1760 pseudorandom key generation process has value 255. 1762 For the Winternitz chaining function, D_PBLC, and D_MESG, the value 1763 of I || u32str(q) is distinct for each LMS leaf (or equivalently, for 1764 each q value). For the Winternitz chaining function, the value of 1765 u16str(i) || u8str(j) is distinct for each invocation of H for a 1766 given leaf. For D_PBLC and D_MESG, the input format is used only 1767 once for each value of q, and thus distinctness is assured. The 1768 formats for D_INTR and D_LEAF are used exactly once for each value of 1769 r, which ensures their distinctness. For the recommended 1770 pseudorandom key generation process, for a given value of I, q and j 1771 are distinct for each invocation of H. 1773 The value of I is chosen uniformly at random from the set of all 128 1774 bit strings. If 2^64 public keys are generated (and hence 2^64 1775 random I values), there is a nontrivial probability of a duplicate 1776 (which would imply duplicate prefixes). However, there will be an 1777 extremely high probability there will not be a four-way collision 1778 (that is, any I value used for four distinct LMS keys; probability < 1779 2^-132), and hence the number of repeats for any specific prefix will 1780 be limited to at most 3. This is shown (in [Fluhrer17]) to have only 1781 a limited effect on the security of the system. 1783 9.2. Stateful signature algorithm 1785 The LMS signature system, like all N-time signature systems, requires 1786 that the signer maintain state across different invocations of the 1787 signing algorithm, to ensure that none of the component one-time 1788 signature systems are used more than once. This section calls out 1789 some important practical considerations around this statefulness. 1790 These issues are discussed in greater detail in [STMGMT]. 1792 In a typical computing environment, a private key will be stored in 1793 non-volatile media such as on a hard drive. Before it is used to 1794 sign a message, it will be read into an application's Random Access 1795 Memory (RAM). After a signature is generated, the value of the 1796 private key will need to be updated by writing the new value of the 1797 private key into non-volatile storage. It is essential for security 1798 that the application ensure that this value is actually written into 1799 that storage, yet there may be one or more memory caches between it 1800 and the application. Memory caching is commonly done in the file 1801 system, and in a physical memory unit on the hard disk that is 1802 dedicated to that purpose. To ensure that the updated value is 1803 written to physical media, the application may need to take several 1804 special steps. In a POSIX environment, for instance, the O_SYNC flag 1805 (for the open() system call) will cause invocations of the write() 1806 system call to block the calling process until the data has been 1807 written to the underlying hardware. However, if that hardware has 1808 its own memory cache, it must be separately dealt with using an 1809 operating system or device specific tool such as hdparm to flush the 1810 on-drive cache, or turn off write caching for that drive. Because 1811 these details vary across different operating systems and devices, 1812 this note does not attempt to provide complete guidance; instead, we 1813 call the implementer's attention to these issues. 1815 When hierarchical signatures are used, an easy way to minimize the 1816 private key synchronization issues is to have the private key for the 1817 second level resident in RAM only, and never write that value into 1818 non-volatile memory. A new second level public/private key pair will 1819 be generated whenever the application (re)starts; thus, failures such 1820 as a power outage or application crash are automatically 1821 accommodated. Implementations SHOULD use this approach wherever 1822 possible. 1824 9.3. Security of LM-OTS Checksum 1826 To show the security of LM-OTS checksum, we consider the signature y 1827 of a message with a private key x and let h = H(message) and 1828 c = Cksm(H(message)) (see Section 4.5). To attempt a forgery, an 1829 attacker may try to change the values of h and c. Let h' and c' 1830 denote the values used in the forgery attempt. If for some integer j 1831 in the range 0 to u, where u = ceil(8*n/w) is the size of the range 1832 that the checksum value can cover, inclusive, 1834 a' = coef(h', j, w), 1836 a = coef(h, j, w), and 1838 a' > a 1840 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1841 iteratively applying function F to the j-th term of the signature an 1842 additional (a' - a) times. However, as a result of the increased 1843 number of hashing iterations, the checksum value c' will decrease 1844 from its original value of c. Thus a valid signature's checksum will 1845 have, for some number k in the range u to (p-1), inclusive, 1847 b' = coef(c', k, w), 1849 b = coef(c, k, w), and 1851 b' < b 1853 Due to the one-way property of F, the attacker cannot easily compute 1854 F^b'(x[k]) from F^b(x[k]) = y[k]. 1856 10. Comparison with other work 1858 The eXtended Merkle Signature Scheme (XMSS) [XMSS], [RFC8391] is 1859 similar to HSS in several ways. Both are stateful hash based 1860 signature schemes, and both use a hierarchical approach, with a 1861 Merkle tree at each level of the hierarchy. XMSS signatures are 1862 slightly shorter than HSS signatures, for equivalent security and an 1863 equal number of signatures. 1865 HSS has several advantages over XMSS. HSS operations are roughly 1866 four times faster than the comparable XMSS ones, when SHA256 is used 1867 as the underlying hash. This occurs because the hash operation done 1868 as a part of the Winternitz iterations dominates performance, and 1869 XMSS performs four compression function invocations (two for the PRF, 1870 two for the F function) where HSS needs only perform one. 1871 Additionally, HSS is somewhat simpler (as each hash invocation is 1872 just a prefix followed by the data being hashed). 1874 11. Acknowledgements 1876 Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric 1877 Osterweil, Ahmed Kosba, Russ Housley, Philip Lafrance, Alexander 1878 Truskovsky, Mark Peruzel for constructive suggestions and valuable 1879 detailed review. We especially acknowledge Jerry Solinas, Laurie 1880 Law, and Kevin Igoe, who pointed out the security benefits of the 1881 approach of Leighton and Micali [USPTO5432852] and Jonathan Katz, who 1882 gave us security guidance, and Bruno Couillard and Jim Goodman for an 1883 especially thorough review. 1885 12. References 1887 12.1. Normative References 1889 [FIPS180] National Institute of Standards and Technology, "Secure 1890 Hash Standard (SHS)", FIPS 180-4, March 2012. 1892 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1893 Requirement Levels", BCP 14, RFC 2119, 1894 DOI 10.17487/RFC2119, March 1997, 1895 . 1897 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1898 IANA Considerations Section in RFCs", RFC 2434, 1899 DOI 10.17487/RFC2434, October 1998, 1900 . 1902 [RFC3979] Bradner, S., Ed., "Intellectual Property Rights in IETF 1903 Technology", RFC 3979, DOI 10.17487/RFC3979, March 2005, 1904 . 1906 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1907 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1908 2006, . 1910 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1911 Procedure in RFC 3979", RFC 4879, DOI 10.17487/RFC4879, 1912 April 2007, . 1914 [USPTO5432852] 1915 Leighton, T. and S. Micali, "Large provably fast and 1916 secure digital signature schemes from secure hash 1917 functions", U.S. Patent 5,432,852, July 1995. 1919 12.2. Informative References 1921 [C:Merkle87] 1922 Merkle, R., "A Digital Signature Based on a Conventional 1923 Encryption Function", Lecture Notes in Computer 1924 Science crypto87vol, 1988. 1926 [C:Merkle89a] 1927 Merkle, R., "A Certified Digital Signature", Lecture Notes 1928 in Computer Science crypto89vol, 1990. 1930 [C:Merkle89b] 1931 Merkle, R., "One Way Hash Functions and DES", Lecture 1932 Notes in Computer Science crypto89vol, 1990. 1934 [Fluhrer17] 1935 Fluhrer, S., "Further analysis of a proposed hash-based 1936 signature standard", 1937 EPrint https://eprint.iacr.org/2017/553.pdf, 2017. 1939 [Grover96] 1940 Grover, L., "A fast quantum mechanical algorithm for 1941 database search", 28th ACM Symposium on the Theory of 1942 Computing p. 212, 1996. 1944 [Katz16] Katz, J., "Analysis of a proposed hash-based signature 1945 standard", Security Standardization Research (SSR) 1946 Conference 1947 https://www.cs.umd.edu/~jkatz/papers/HashBasedSigs- 1948 SSR16.pdf, 2016. 1950 [Merkle79] 1951 Merkle, R., "Secrecy, Authentication, and Public Key 1952 Systems", Stanford University Information Systems 1953 Laboratory Technical Report 1979-1, 1979. 1955 [RFC8391] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. 1956 Mohaisen, "XMSS: eXtended Merkle Signature Scheme", 1957 RFC 8391, DOI 10.17487/RFC8391, May 2018, 1958 . 1960 [STMGMT] McGrew, D., Fluhrer, S., Kampanakis, P., Gazdag, S., 1961 Butin, D., and J. Buchmann, "State Management for Hash- 1962 based Signatures.", Security Standardization Resarch (SSR) 1963 Conference 224., 2016. 1965 [XMSS] Buchmann, J., Dahmen, E., and Andreas Huelsing, "XMSS-a 1966 practical forward secure signature scheme based on minimal 1967 security assumptions.", International Workshop on Post- 1968 Quantum Cryptography Springer Berlin., 2011. 1970 Appendix A. Pseudorandom Key Generation 1972 An implementation MAY use the following pseudorandom process for 1973 generating an LMS private key. 1975 SEED is an m-byte value that is generated uniformly at random at 1976 the start of the process, 1978 I is LMS key pair identifier, 1980 q denotes the LMS leaf number of an LM-OTS private key, 1982 x_q denotes the x array of private elements in the LM-OTS private 1983 key with leaf number q, 1985 i is the index of the private key element, and 1987 H is the hash function used in LM-OTS. 1989 The elements of the LM-OTS private keys are computed as: 1991 x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED). 1993 This process stretches the m-byte random value SEED into a (much 1994 larger) set of pseudorandom values, using a unique counter in each 1995 invocation of H. The format of the inputs to H are chosen so that 1996 they are distinct from all other uses of H in LMS and LM-OTS. A 1997 careful reader will note that this is similar to the hash we perform 1998 when iterating through the Winternitz chain; however in that chain, 1999 the iteration index will vary between 0 and 254 maximum (for W=8), 2000 while the corresponding value in this formula is 255. This algorithm 2001 is included in the proof of security in [Fluhrer17] and hence this 2002 method is safe when used within the LMS system; however any other 2003 cryptographical secure method of generating private keys would also 2004 be safe. 2006 Appendix B. LM-OTS Parameter Options 2008 The LM-OTS one time signature method uses several internal 2009 parameters, which are a function of the selected parameter set. 2010 These internal parameters set: 2012 p - This is the number of independent Winternitz chains used in 2013 the signature; it will be the number of w-bit digits needed to 2014 hold the n-bit hash (u in the below equations), along with the 2015 number of digits needed to hold the checksum (v in the below 2016 equations) 2018 ls - This is the size of the shift needed to move the checksum so 2019 that it appears in the checksum digits 2021 ls is needed because, while we express the checksum internally as a 2022 16 bit value, we don't always express all 16 bits in the signature; 2023 for example, if w=4, we might use only the top 12 bits. Because we 2024 read the checksum in network order, this means that, without the 2025 shift, we'll use the higher order bits (which may be always 0), and 2026 omit the lower order bits (where the checksum value actually 2027 resides). This shift is here to ensure that the parts of the 2028 checksum we need to express (for security) actually contribute to the 2029 signature; when multiple such shifts are possible, we take the 2030 minimal value. 2032 The parameters ls, and p are computed as follows: 2034 u = ceil(8*n/w) 2035 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 2036 ls = 16 - (v * w) 2037 p = u + v 2039 Here u and v represent the number of w-bit fields required to contain 2040 the hash of the message and the checksum byte strings, respectively. 2041 And as the value of p is the number of w-bit elements of 2042 ( H(message) || Cksm(H(message)) ), it is also equivalently the 2043 number of byte strings that form the private key and the number of 2044 byte strings in the signature. The value 16 in the ls computation of 2045 ls corresponds to the 16 bits value used for the sum variable in 2046 Algorithm 2 in Section 4.4 2048 A table illustrating various combinations of n and w with the 2049 associated values of u, v, ls, and p is provided in Table 6. 2051 +---------+------------+-----------+-----------+-------+------------+ 2052 | Hash | Winternitz | w-bit | w-bit | Left | Total | 2053 | Length | Parameter | Elements | Elements | Shift | Number of | 2054 | in | (w) | in Hash | in | (ls) | w-bit | 2055 | Bytes | | (u) | Checksum | | Elements | 2056 | (n) | | | (v) | | (p) | 2057 +---------+------------+-----------+-----------+-------+------------+ 2058 | 32 | 1 | 256 | 9 | 7 | 265 | 2059 | | | | | | | 2060 | 32 | 2 | 128 | 5 | 6 | 133 | 2061 | | | | | | | 2062 | 32 | 4 | 64 | 3 | 4 | 67 | 2063 | | | | | | | 2064 | 32 | 8 | 32 | 2 | 0 | 34 | 2065 +---------+------------+-----------+-----------+-------+------------+ 2067 Table 6 2069 Appendix C. An iterative algorithm for computing an LMS public key 2071 The LMS public key can be computed using the following algorithm or 2072 any equivalent method. The algorithm uses a stack of hashes for 2073 data. It also makes use of a hash function with the typical 2074 init/update/final interface to hash functions; the result of the 2075 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 2076 hash_update(N[n]), v = hash_final(), in that order, is identical to 2077 that of the invocation of H(N[1] || N[2] || ... || N[n]). 2079 Generating an LMS Public Key from an LMS Private Key 2081 for ( i = 0; i < 2^h; i = i + 1 ) { 2082 r = i + num_lmots_keys; 2083 temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i]) 2084 j = i; 2085 while (j % 2 == 1) { 2086 r = (r - 1)/2; 2087 j = (j-1) / 2; 2088 left_side = pop(data stack); 2089 temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp) 2090 } 2091 push temp onto the data stack 2092 } 2093 public_key = pop(data stack) 2095 Note that this pseudocode expects that all 2^h leaves of the tree 2096 have equal depth; that is, num_lmots_keys to be a power of 2. The 2097 maximum depth of the stack will be h-1 elements, that is, a total of 2098 (h-1)*n bytes; for the currently defined parameter sets, this will 2099 never be more than 768 bytes of data. 2101 Appendix D. Method for deriving authentication path for a signature 2103 The LMS signature consists of u32str(q) || lmots_signature || 2104 u32str(type) || path[0] || path[1] || ... || path[h-1]. This 2105 appendix shows one method of constructing this signature, assuming 2106 that the implementation has stored the T[] array that was used to 2107 construct the public key. Note that this is not the only possible 2108 method; other methods exist which don't assume that you have the 2109 entire T[] array in memory. To construct a signature, you perform 2110 the following algorithm: 2112 Generating an LMS Signature 2114 1. set type to the typecode of the LMS algorithm 2116 2. extract h from the typecode according to table 2 2118 3. create the LM-OTS signature for the message: 2119 ots_signature = lmots_sign(message, LMS_PRIV[q]) 2121 4. compute the array path as follows: 2122 i = 0 2123 r = 2^h + q 2124 while (i < h) { 2125 temp = (r / 2^i) xor 1 2126 path[i] = T[temp] 2127 i = i + 1 2128 } 2130 5. S = u32str(q) || ots_signature || u32str(type) || 2131 path[0] || path[1] || ... || path[h-1] 2133 6. q = q + 1 2135 7. return S 2137 where 'xor' is the bitwise exclusive-or operation, and / is integer 2138 division (that is, rounded down to an integer value) 2140 Appendix E. Example Implementation 2142 An example implementation can be found online at 2143 https://github.com/cisco/hash-sigs. 2145 Appendix F. Test Cases 2147 This section provides test cases that can be used to verify or debug 2148 an implementation. This data is formatted with the name of the 2149 elements on the left, and the value of the elements on the right, in 2150 hexadecimal. The concatenation of all of the values within a public 2151 key or signature produces that public key or signature, and values 2152 that do not fit within a single line are listed across successive 2153 lines. 2155 Test Case 1 Public Key 2157 -------------------------------------------- 2158 HSS public key 2159 levels 00000002 2160 -------------------------------------------- 2161 LMS type 00000005 # LM_SHA256_M32_H5 2162 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2163 I 61a5d57d37f5e46bfb7520806b07a1b8 2164 K 50650e3b31fe4a773ea29a07f09cf2ea 2165 30e579f0df58ef8e298da0434cb2b878 2166 -------------------------------------------- 2167 -------------------------------------------- 2169 Test Case 1 Message 2171 -------------------------------------------- 2172 Message 54686520706f77657273206e6f742064 |The powers not d| 2173 656c65676174656420746f2074686520 |elegated to the | 2174 556e6974656420537461746573206279 |United States by| 2175 2074686520436f6e737469747574696f | the Constitutio| 2176 6e2c206e6f722070726f686962697465 |n, nor prohibite| 2177 6420627920697420746f207468652053 |d by it to the S| 2178 74617465732c20617265207265736572 |tates, are reser| 2179 76656420746f20746865205374617465 |ved to the State| 2180 7320726573706563746976656c792c20 |s respectively, | 2181 6f7220746f207468652070656f706c65 |or to the people| 2182 2e0a |..| 2183 -------------------------------------------- 2185 Test Case 1 Signature 2187 -------------------------------------------- 2188 HSS signature 2189 Nspk 00000001 2190 sig[0]: 2191 -------------------------------------------- 2192 LMS signature 2193 q 00000005 2194 -------------------------------------------- 2195 LMOTS signature 2196 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2197 C d32b56671d7eb98833c49b433c272586 2198 bc4a1c8a8970528ffa04b966f9426eb9 2199 y[0] 965a25bfd37f196b9073f3d4a232feb6 2200 9128ec45146f86292f9dff9610a7bf95 2201 y[1] a64c7f60f6261a62043f86c70324b770 2202 7f5b4a8a6e19c114c7be866d488778a0 2204 y[2] e05fd5c6509a6e61d559cf1a77a970de 2205 927d60c70d3de31a7fa0100994e162a2 2206 y[3] 582e8ff1b10cd99d4e8e413ef469559f 2207 7d7ed12c838342f9b9c96b83a4943d16 2208 y[4] 81d84b15357ff48ca579f19f5e71f184 2209 66f2bbef4bf660c2518eb20de2f66e3b 2210 y[5] 14784269d7d876f5d35d3fbfc7039a46 2211 2c716bb9f6891a7f41ad133e9e1f6d95 2212 y[6] 60b960e7777c52f060492f2d7c660e14 2213 71e07e72655562035abc9a701b473ecb 2214 y[7] c3943c6b9c4f2405a3cb8bf8a691ca51 2215 d3f6ad2f428bab6f3a30f55dd9625563 2216 y[8] f0a75ee390e385e3ae0b906961ecf41a 2217 e073a0590c2eb6204f44831c26dd768c 2218 y[9] 35b167b28ce8dc988a3748255230cef9 2219 9ebf14e730632f27414489808afab1d1 2220 y[10] e783ed04516de012498682212b078105 2221 79b250365941bcc98142da13609e9768 2222 y[11] aaf65de7620dabec29eb82a17fde35af 2223 15ad238c73f81bdb8dec2fc0e7f93270 2224 y[12] 1099762b37f43c4a3c20010a3d72e2f6 2225 06be108d310e639f09ce7286800d9ef8 2226 y[13] a1a40281cc5a7ea98d2adc7c7400c2fe 2227 5a101552df4e3cccfd0cbf2ddf5dc677 2228 y[14] 9cbbc68fee0c3efe4ec22b83a2caa3e4 2229 8e0809a0a750b73ccdcf3c79e6580c15 2230 y[15] 4f8a58f7f24335eec5c5eb5e0cf01dcf 2231 4439424095fceb077f66ded5bec73b27 2232 y[16] c5b9f64a2a9af2f07c05e99e5cf80f00 2233 252e39db32f6c19674f190c9fbc506d8 2234 y[17] 26857713afd2ca6bb85cd8c107347552 2235 f30575a5417816ab4db3f603f2df56fb 2236 y[18] c413e7d0acd8bdd81352b2471fc1bc4f 2237 1ef296fea1220403466b1afe78b94f7e 2238 y[19] cf7cc62fb92be14f18c2192384ebceaf 2239 8801afdf947f698ce9c6ceb696ed70e9 2240 y[20] e87b0144417e8d7baf25eb5f70f09f01 2241 6fc925b4db048ab8d8cb2a661ce3b57a 2242 y[21] da67571f5dd546fc22cb1f97e0ebd1a6 2243 5926b1234fd04f171cf469c76b884cf3 2244 y[22] 115cce6f792cc84e36da58960c5f1d76 2245 0f32c12faef477e94c92eb75625b6a37 2246 y[23] 1efc72d60ca5e908b3a7dd69fef02491 2247 50e3eebdfed39cbdc3ce9704882a2072 2248 y[24] c75e13527b7a581a556168783dc1e975 2249 45e31865ddc46b3c957835da252bb732 2250 y[25] 8d3ee2062445dfb85ef8c35f8e1f3371 2251 af34023cef626e0af1e0bc017351aae2 2253 y[26] ab8f5c612ead0b729a1d059d02bfe18e 2254 fa971b7300e882360a93b025ff97e9e0 2255 y[27] eec0f3f3f13039a17f88b0cf808f4884 2256 31606cb13f9241f40f44e537d302c64a 2257 y[28] 4f1f4ab949b9feefadcb71ab50ef27d6 2258 d6ca8510f150c85fb525bf25703df720 2259 y[29] 9b6066f09c37280d59128d2f0f637c7d 2260 7d7fad4ed1c1ea04e628d221e3d8db77 2261 y[30] b7c878c9411cafc5071a34a00f4cf077 2262 38912753dfce48f07576f0d4f94f42c6 2263 y[31] d76f7ce973e9367095ba7e9a3649b7f4 2264 61d9f9ac1332a4d1044c96aefee67676 2265 y[32] 401b64457c54d65fef6500c59cdfb69a 2266 f7b6dddfcb0f086278dd8ad0686078df 2267 y[33] b0f3f79cd893d314168648499898fbc0 2268 ced5f95b74e8ff14d735cdea968bee74 2269 -------------------------------------------- 2270 LMS type 00000005 # LM_SHA256_M32_H5 2271 path[0] d8b8112f9200a5e50c4a262165bd342c 2272 d800b8496810bc716277435ac376728d 2273 path[1] 129ac6eda839a6f357b5a04387c5ce97 2274 382a78f2a4372917eefcbf93f63bb591 2275 path[2] 12f5dbe400bd49e4501e859f885bf073 2276 6e90a509b30a26bfac8c17b5991c157e 2277 path[3] b5971115aa39efd8d564a6b90282c316 2278 8af2d30ef89d51bf14654510a12b8a14 2279 path[4] 4cca1848cf7da59cc2b3d9d0692dd2a2 2280 0ba3863480e25b1b85ee860c62bf5136 2281 -------------------------------------------- 2282 LMS public key 2283 LMS type 00000005 # LM_SHA256_M32_H5 2284 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2285 I d2f14ff6346af964569f7d6cb880a1b6 2286 K 6c5004917da6eafe4d9ef6c6407b3db0 2287 e5485b122d9ebe15cda93cfec582d7ab 2288 -------------------------------------------- 2289 final_signature: 2290 -------------------------------------------- 2291 LMS signature 2292 q 0000000a 2293 -------------------------------------------- 2294 LMOTS signature 2295 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2296 C 0703c491e7558b35011ece3592eaa5da 2297 4d918786771233e8353bc4f62323185c 2298 y[0] 95cae05b899e35dffd71705470620998 2299 8ebfdf6e37960bb5c38d7657e8bffeef 2300 y[1] 9bc042da4b4525650485c66d0ce19b31 2301 7587c6ba4bffcc428e25d08931e72dfb 2302 y[2] 6a120c5612344258b85efdb7db1db9e1 2303 865a73caf96557eb39ed3e3f426933ac 2304 y[3] 9eeddb03a1d2374af7bf771855774562 2305 37f9de2d60113c23f846df26fa942008 2306 y[4] a698994c0827d90e86d43e0df7f4bfcd 2307 b09b86a373b98288b7094ad81a0185ac 2308 y[5] 100e4f2c5fc38c003c1ab6fea479eb2f 2309 5ebe48f584d7159b8ada03586e65ad9c 2310 y[6] 969f6aecbfe44cf356888a7b15a3ff07 2311 4f771760b26f9c04884ee1faa329fbf4 2312 y[7] e61af23aee7fa5d4d9a5dfcf43c4c26c 2313 e8aea2ce8a2990d7ba7b57108b47dabf 2314 y[8] beadb2b25b3cacc1ac0cef346cbb90fb 2315 044beee4fac2603a442bdf7e507243b7 2316 y[9] 319c9944b1586e899d431c7f91bcccc8 2317 690dbf59b28386b2315f3d36ef2eaa3c 2318 y[10] f30b2b51f48b71b003dfb08249484201 2319 043f65f5a3ef6bbd61ddfee81aca9ce6 2320 y[11] 0081262a00000480dcbc9a3da6fbef5c 2321 1c0a55e48a0e729f9184fcb1407c3152 2322 y[12] 9db268f6fe50032a363c9801306837fa 2323 fabdf957fd97eafc80dbd165e435d0e2 2324 y[13] dfd836a28b354023924b6fb7e48bc0b3 2325 ed95eea64c2d402f4d734c8dc26f3ac5 2326 y[14] 91825daef01eae3c38e3328d00a77dc6 2327 57034f287ccb0f0e1c9a7cbdc828f627 2328 y[15] 205e4737b84b58376551d44c12c3c215 2329 c812a0970789c83de51d6ad787271963 2330 y[16] 327f0a5fbb6b5907dec02c9a90934af5 2331 a1c63b72c82653605d1dcce51596b3c2 2332 y[17] b45696689f2eb382007497557692caac 2333 4d57b5de9f5569bc2ad0137fd47fb47e 2334 y[18] 664fcb6db4971f5b3e07aceda9ac130e 2335 9f38182de994cff192ec0e82fd6d4cb7 2336 y[19] f3fe00812589b7a7ce51544045643301 2337 6b84a59bec6619a1c6c0b37dd1450ed4 2338 y[20] f2d8b584410ceda8025f5d2d8dd0d217 2339 6fc1cf2cc06fa8c82bed4d944e71339e 2340 y[21] ce780fd025bd41ec34ebff9d4270a322 2341 4e019fcb444474d482fd2dbe75efb203 2342 y[22] 89cc10cd600abb54c47ede93e08c114e 2343 db04117d714dc1d525e11bed8756192f 2344 y[23] 929d15462b939ff3f52f2252da2ed64d 2345 8fae88818b1efa2c7b08c8794fb1b214 2346 y[24] aa233db3162833141ea4383f1a6f120b 2347 e1db82ce3630b3429114463157a64e91 2348 y[25] 234d475e2f79cbf05e4db6a9407d72c6 2349 bff7d1198b5c4d6aad2831db61274993 2350 y[26] 715a0182c7dc8089e32c8531deed4f74 2351 31c07c02195eba2ef91efb5613c37af7 2352 y[27] ae0c066babc69369700e1dd26eddc0d2 2353 16c781d56e4ce47e3303fa73007ff7b9 2354 y[28] 49ef23be2aa4dbf25206fe45c20dd888 2355 395b2526391a724996a44156beac8082 2356 y[29] 12858792bf8e74cba49dee5e8812e019 2357 da87454bff9e847ed83db07af3137430 2358 y[30] 82f880a278f682c2bd0ad6887cb59f65 2359 2e155987d61bbf6a88d36ee93b6072e6 2360 y[31] 656d9ccbaae3d655852e38deb3a2dcf8 2361 058dc9fb6f2ab3d3b3539eb77b248a66 2362 y[32] 1091d05eb6e2f297774fe6053598457c 2363 c61908318de4b826f0fc86d4bb117d33 2364 y[33] e865aa805009cc2918d9c2f840c4da43 2365 a703ad9f5b5806163d7161696b5a0adc 2366 -------------------------------------------- 2367 LMS type 00000005 # LM_SHA256_M32_H5 2368 path[0] d5c0d1bebb06048ed6fe2ef2c6cef305 2369 b3ed633941ebc8b3bec9738754cddd60 2370 path[1] e1920ada52f43d055b5031cee6192520 2371 d6a5115514851ce7fd448d4a39fae2ab 2372 path[2] 2335b525f484e9b40d6a4a969394843b 2373 dcf6d14c48e8015e08ab92662c05c6e9 2374 path[3] f90b65a7a6201689999f32bfd368e5e3 2375 ec9cb70ac7b8399003f175c40885081a 2376 path[4] 09ab3034911fe125631051df0408b394 2377 6b0bde790911e8978ba07dd56c73e7ee 2379 Test Case 2 Private Key 2381 -------------------------------------------- 2382 (note: procedure in Appendix A is used) 2383 SEED 000102030405060708090a0b0c0d0e0f 2384 101112131415161718191a1b1c1d1e1f 2385 I d08fabd4a2091ff0a8cb4ed834e74534 2386 -------------------------------------------- 2387 -------------------------------------------- 2388 Test Case 2 Public Key 2390 -------------------------------------------- 2391 HSS public key 2392 levels 00000002 2393 -------------------------------------------- 2394 LMS type 00000006 # LM_SHA256_M32_H10 2395 LMOTS type 00000003 # LMOTS_SHA256_N32_W4 2396 I d08fabd4a2091ff0a8cb4ed834e74534 2397 K 32a58885cd9ba0431235466bff9651c6 2398 c92124404d45fa53cf161c28f1ad5a8e 2399 -------------------------------------------- 2400 -------------------------------------------- 2402 Test Case 2 Message 2404 -------------------------------------------- 2405 Message 54686520656e756d65726174696f6e20 The enumeration 2406 696e2074686520436f6e737469747574 in the Constitut 2407 696f6e2c206f66206365727461696e20 ion, of certain 2408 7269676874732c207368616c6c206e6f rights, shall no 2409 7420626520636f6e7374727565642074 t be construed t 2410 6f2064656e79206f7220646973706172 o deny or dispar 2411 616765206f7468657273207265746169 age others retai 2412 6e6564206279207468652070656f706c ned by the peopl 2413 652e0a e.. 2414 -------------------------------------------- 2416 Test Case 2 Signature 2418 -------------------------------------------- 2419 HSS signature 2420 Nspk 00000001 2421 sig[0]: 2422 -------------------------------------------- 2423 LMS signature 2424 q 00000003 2425 -------------------------------------------- 2426 LMOTS signature 2427 LMOTS type 00000003 # LMOTS_SHA256_N32_W4 2428 C 3d46bee8660f8f215d3f96408a7a64cf 2429 1c4da02b63a55f62c666ef5707a914ce 2430 y[0] 0674e8cb7a55f0c48d484f31f3aa4af9 2431 719a74f22cf823b94431d01c926e2a76 2432 y[1] bb71226d279700ec81c9e95fb11a0d10 2433 d065279a5796e265ae17737c44eb8c59 2434 y[2] 4508e126a9a7870bf4360820bdeb9a01 2435 d9693779e416828e75bddd7d8c70d50a 2437 y[3] 0ac8ba39810909d445f44cb5bb58de73 2438 7e60cb4345302786ef2c6b14af212ca1 2439 y[4] 9edeaa3bfcfe8baa6621ce88480df237 2440 1dd37add732c9de4ea2ce0dffa53c926 2441 y[5] 49a18d39a50788f4652987f226a1d481 2442 68205df6ae7c58e049a25d4907edc1aa 2443 y[6] 90da8aa5e5f7671773e941d805536021 2444 5c6b60dd35463cf2240a9c06d694e9cb 2445 y[7] 54e7b1e1bf494d0d1a28c0d31acc7516 2446 1f4f485dfd3cb9578e836ec2dc722f37 2447 y[8] ed30872e07f2b8bd0374eb57d22c614e 2448 09150f6c0d8774a39a6e168211035dc5 2449 y[9] 2988ab46eaca9ec597fb18b4936e66ef 2450 2f0df26e8d1e34da28cbb3af75231372 2451 y[10] 0c7b345434f72d65314328bbb030d0f0 2452 f6d5e47b28ea91008fb11b05017705a8 2453 y[11] be3b2adb83c60a54f9d1d1b2f476f9e3 2454 93eb5695203d2ba6ad815e6a111ea293 2455 y[12] dcc21033f9453d49c8e5a6387f588b1e 2456 a4f706217c151e05f55a6eb7997be09d 2457 y[13] 56a326a32f9cba1fbe1c07bb49fa04ce 2458 cf9df1a1b815483c75d7a27cc88ad1b1 2459 y[14] 238e5ea986b53e087045723ce16187ed 2460 a22e33b2c70709e53251025abde89396 2461 y[15] 45fc8c0693e97763928f00b2e3c75af3 2462 942d8ddaee81b59a6f1f67efda0ef81d 2463 y[16] 11873b59137f67800b35e81b01563d18 2464 7c4a1575a1acb92d087b517a8833383f 2465 y[17] 05d357ef4678de0c57ff9f1b2da61dfd 2466 e5d88318bcdde4d9061cc75c2de3cd47 2467 y[18] 40dd7739ca3ef66f1930026f47d9ebaa 2468 713b07176f76f953e1c2e7f8f271a6ca 2469 y[19] 375dbfb83d719b1635a7d8a138919579 2470 44b1c29bb101913e166e11bd5f34186f 2471 y[20] a6c0a555c9026b256a6860f4866bd6d0 2472 b5bf90627086c6149133f8282ce6c9b3 2473 y[21] 622442443d5eca959d6c14ca8389d12c 2474 4068b503e4e3c39b635bea245d9d05a2 2475 y[22] 558f249c9661c0427d2e489ca5b5dde2 2476 20a90333f4862aec793223c781997da9 2477 y[23] 8266c12c50ea28b2c438e7a379eb106e 2478 ca0c7fd6006e9bf612f3ea0a454ba3bd 2479 y[24] b76e8027992e60de01e9094fddeb3349 2480 883914fb17a9621ab929d970d101e45f 2481 y[25] 8278c14b032bcab02bd15692d21b6c5c 2482 204abbf077d465553bd6eda645e6c306 2483 y[26] 5d33b10d518a61e15ed0f092c3222628 2484 1a29c8a0f50cde0a8c66236e29c2f310 2486 y[27] a375cebda1dc6bb9a1a01dae6c7aba8e 2487 bedc6371a7d52aacb955f83bd6e4f84d 2488 y[28] 2949dcc198fb77c7e5cdf6040b0f84fa 2489 f82808bf985577f0a2acf2ec7ed7c0b0 2490 y[29] ae8a270e951743ff23e0b2dd12e9c3c8 2491 28fb5598a22461af94d568f29240ba28 2492 y[30] 20c4591f71c088f96e095dd98beae456 2493 579ebbba36f6d9ca2613d1c26eee4d8c 2494 y[31] 73217ac5962b5f3147b492e8831597fd 2495 89b64aa7fde82e1974d2f6779504dc21 2496 y[32] 435eb3109350756b9fdabe1c6f368081 2497 bd40b27ebcb9819a75d7df8bb07bb05d 2498 y[33] b1bab705a4b7e37125186339464ad8fa 2499 aa4f052cc1272919fde3e025bb64aa8e 2500 y[34] 0eb1fcbfcc25acb5f718ce4f7c2182fb 2501 393a1814b0e942490e52d3bca817b2b2 2502 y[35] 6e90d4c9b0cc38608a6cef5eb153af08 2503 58acc867c9922aed43bb67d7b33acc51 2504 y[36] 9313d28d41a5c6fe6cf3595dd5ee63f0 2505 a4c4065a083590b275788bee7ad875a7 2506 y[37] f88dd73720708c6c6c0ecf1f43bbaada 2507 e6f208557fdc07bd4ed91f88ce4c0de8 2508 y[38] 42761c70c186bfdafafc444834bd3418 2509 be4253a71eaf41d718753ad07754ca3e 2510 y[39] ffd5960b0336981795721426803599ed 2511 5b2b7516920efcbe32ada4bcf6c73bd2 2512 y[40] 9e3fa152d9adeca36020fdeeee1b7395 2513 21d3ea8c0da497003df1513897b0f547 2514 y[41] 94a873670b8d93bcca2ae47e64424b74 2515 23e1f078d9554bb5232cc6de8aae9b83 2516 y[42] fa5b9510beb39ccf4b4e1d9c0f19d5e1 2517 7f58e5b8705d9a6837a7d9bf99cd1338 2518 y[43] 7af256a8491671f1f2f22af253bcff54 2519 b673199bdb7d05d81064ef05f80f0153 2520 y[44] d0be7919684b23da8d42ff3effdb7ca0 2521 985033f389181f47659138003d712b5e 2522 y[45] c0a614d31cc7487f52de8664916af79c 2523 98456b2c94a8038083db55391e347586 2524 y[46] 2250274a1de2584fec975fb09536792c 2525 fbfcf6192856cc76eb5b13dc4709e2f7 2526 y[47] 301ddff26ec1b23de2d188c999166c74 2527 e1e14bbc15f457cf4e471ae13dcbdd9c 2528 y[48] 50f4d646fc6278e8fe7eb6cb5c94100f 2529 a870187380b777ed19d7868fd8ca7ceb 2530 y[49] 7fa7d5cc861c5bdac98e7495eb0a2cee 2531 c1924ae979f44c5390ebedddc65d6ec1 2532 y[50] 1287d978b8df064219bc5679f7d7b264 2533 a76ff272b2ac9f2f7cfc9fdcfb6a5142 2535 y[51] 8240027afd9d52a79b647c90c2709e06 2536 0ed70f87299dd798d68f4fadd3da6c51 2537 y[52] d839f851f98f67840b964ebe73f8cec4 2538 1572538ec6bc131034ca2894eb736b3b 2539 y[53] da93d9f5f6fa6f6c0f03ce43362b8414 2540 940355fb54d3dfdd03633ae108f3de3e 2541 y[54] bc85a3ff51efeea3bc2cf27e1658f178 2542 9ee612c83d0f5fd56f7cd071930e2946 2543 y[55] beeecaa04dccea9f97786001475e0294 2544 bc2852f62eb5d39bb9fbeef75916efe4 2545 y[56] 4a662ecae37ede27e9d6eadfdeb8f8b2 2546 b2dbccbf96fa6dbaf7321fb0e701f4d4 2547 y[57] 29c2f4dcd153a2742574126e5eaccc77 2548 686acf6e3ee48f423766e0fc466810a9 2549 y[58] 05ff5453ec99897b56bc55dd49b99114 2550 2f65043f2d744eeb935ba7f4ef23cf80 2551 y[59] cc5a8a335d3619d781e7454826df720e 2552 ec82e06034c44699b5f0c44a8787752e 2553 y[60] 057fa3419b5bb0e25d30981e41cb1361 2554 322dba8f69931cf42fad3f3bce6ded5b 2555 y[61] 8bfc3d20a2148861b2afc14562ddd27f 2556 12897abf0685288dcc5c4982f8260268 2557 y[62] 46a24bf77e383c7aacab1ab692b29ed8 2558 c018a65f3dc2b87ff619a633c41b4fad 2559 y[63] b1c78725c1f8f922f6009787b1964247 2560 df0136b1bc614ab575c59a16d089917b 2561 y[64] d4a8b6f04d95c581279a139be09fcf6e 2562 98a470a0bceca191fce476f9370021cb 2563 y[65] c05518a7efd35d89d8577c990a5e1996 2564 1ba16203c959c91829ba7497cffcbb4b 2565 y[66] 294546454fa5388a23a22e805a5ca35f 2566 956598848bda678615fec28afd5da61a 2567 -------------------------------------------- 2568 LMS type 00000006 # LM_SHA256_M32_H10 2569 path[0] b326493313053ced3876db9d23714818 2570 1b7173bc7d042cefb4dbe94d2e58cd21 2571 path[1] a769db4657a103279ba8ef3a629ca84e 2572 e836172a9c50e51f45581741cf808315 2573 path[2] 0b491cb4ecbbabec128e7c81a46e62a6 2574 7b57640a0a78be1cbf7dd9d419a10cd8 2575 path[3] 686d16621a80816bfdb5bdc56211d72c 2576 a70b81f1117d129529a7570cf79cf52a 2577 path[4] 7028a48538ecdd3b38d3d5d62d262465 2578 95c4fb73a525a5ed2c30524ebb1d8cc8 2579 path[5] 2e0c19bc4977c6898ff95fd3d310b0ba 2580 e71696cef93c6a552456bf96e9d075e3 2581 path[6] 83bb7543c675842bafbfc7cdb88483b3 2582 276c29d4f0a341c2d406e40d4653b7e4 2584 path[7] d045851acf6a0a0ea9c710b805cced46 2585 35ee8c107362f0fc8d80c14d0ac49c51 2586 path[8] 6703d26d14752f34c1c0d2c4247581c1 2587 8c2cf4de48e9ce949be7c888e9caebe4 2588 path[9] a415e291fd107d21dc1f084b11582082 2589 49f28f4f7c7e931ba7b3bd0d824a4570 2590 -------------------------------------------- 2591 LMS public key 2592 LMS type 00000005 # LM_SHA256_M32_H5 2593 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2594 I 215f83b7ccb9acbcd08db97b0d04dc2b 2595 K a1cd035833e0e90059603f26e07ad2aa 2596 d152338e7a5e5984bcd5f7bb4eba40b7 2597 -------------------------------------------- 2598 final_signature: 2599 -------------------------------------------- 2600 LMS signature 2601 q 00000004 2602 -------------------------------------------- 2603 LMOTS signature 2604 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 2605 C 0eb1ed54a2460d512388cad533138d24 2606 0534e97b1e82d33bd927d201dfc24ebb 2607 y[0] 11b3649023696f85150b189e50c00e98 2608 850ac343a77b3638319c347d7310269d 2609 y[1] 3b7714fa406b8c35b021d54d4fdada7b 2610 9ce5d4ba5b06719e72aaf58c5aae7aca 2611 y[2] 057aa0e2e74e7dcfd17a0823429db629 2612 65b7d563c57b4cec942cc865e29c1dad 2613 y[3] 83cac8b4d61aacc457f336e6a10b6632 2614 3f5887bf3523dfcadee158503bfaa89d 2615 y[4] c6bf59daa82afd2b5ebb2a9ca6572a60 2616 67cee7c327e9039b3b6ea6a1edc7fdc3 2617 y[5] df927aade10c1c9f2d5ff446450d2a39 2618 98d0f9f6202b5e07c3f97d2458c69d3c 2619 y[6] 8190643978d7a7f4d64e97e3f1c4a08a 2620 7c5bc03fd55682c017e2907eab07e5bb 2621 y[7] 2f190143475a6043d5e6d5263471f4ee 2622 cf6e2575fbc6ff37edfa249d6cda1a09 2623 y[8] f797fd5a3cd53a066700f45863f04b6c 2624 8a58cfd341241e002d0d2c0217472bf1 2625 y[9] 8b636ae547c1771368d9f317835c9b0e 2626 f430b3df4034f6af00d0da44f4af7800 2627 y[10] bc7a5cf8a5abdb12dc718b559b74cab9 2628 090e33cc58a955300981c420c4da8ffd 2629 y[11] 67df540890a062fe40dba8b2c1c548ce 2630 d22473219c534911d48ccaabfb71bc71 2631 y[12] 862f4a24ebd376d288fd4e6fb06ed870 2632 5787c5fedc813cd2697e5b1aac1ced45 2633 y[13] 767b14ce88409eaebb601a93559aae89 2634 3e143d1c395bc326da821d79a9ed41dc 2635 y[14] fbe549147f71c092f4f3ac522b5cc572 2636 90706650487bae9bb5671ecc9ccc2ce5 2637 y[15] 1ead87ac01985268521222fb9057df7e 2638 d41810b5ef0d4f7cc67368c90f573b1a 2639 y[16] c2ce956c365ed38e893ce7b2fae15d36 2640 85a3df2fa3d4cc098fa57dd60d2c9754 2641 y[17] a8ade980ad0f93f6787075c3f680a2ba 2642 1936a8c61d1af52ab7e21f416be09d2a 2643 y[18] 8d64c3d3d8582968c2839902229f85ae 2644 e297e717c094c8df4a23bb5db658dd37 2645 y[19] 7bf0f4ff3ffd8fba5e383a48574802ed 2646 545bbe7a6b4753533353d73706067640 2647 y[20] 135a7ce517279cd683039747d218647c 2648 86e097b0daa2872d54b8f3e508598762 2649 y[21] 9547b830d8118161b65079fe7bc59a99 2650 e9c3c7380e3e70b7138fe5d9be255150 2651 y[22] 2b698d09ae193972f27d40f38dea264a 2652 0126e637d74ae4c92a6249fa103436d3 2653 y[23] eb0d4029ac712bfc7a5eacbdd7518d6d 2654 4fe903a5ae65527cd65bb0d4e9925ca2 2655 y[24] 4fd7214dc617c150544e423f450c99ce 2656 51ac8005d33acd74f1bed3b17b7266a4 2657 y[25] a3bb86da7eba80b101e15cb79de9a207 2658 852cf91249ef480619ff2af8cabca831 2659 y[26] 25d1faa94cbb0a03a906f683b3f47a97 2660 c871fd513e510a7a25f283b196075778 2661 y[27] 496152a91c2bf9da76ebe089f4654877 2662 f2d586ae7149c406e663eadeb2b5c7e8 2663 y[28] 2429b9e8cb4834c83464f079995332e4 2664 b3c8f5a72bb4b8c6f74b0d45dc6c1f79 2665 y[29] 952c0b7420df525e37c15377b5f09843 2666 19c3993921e5ccd97e097592064530d3 2667 y[30] 3de3afad5733cbe7703c5296263f7734 2668 2efbf5a04755b0b3c997c4328463e84c 2669 y[31] aa2de3ffdcd297baaaacd7ae646e44b5 2670 c0f16044df38fabd296a47b3a838a913 2671 y[32] 982fb2e370c078edb042c84db34ce36b 2672 46ccb76460a690cc86c302457dd1cde1 2673 y[33] 97ec8075e82b393d542075134e2a17ee 2674 70a5e187075d03ae3c853cff60729ba4 2675 -------------------------------------------- 2676 LMS type 00000005 # LM_SHA256_M32_H5 2677 path[0] 4de1f6965bdabc676c5a4dc7c35f97f8 2678 2cb0e31c68d04f1dad96314ff09e6b3d 2679 path[1] e96aeee300d1f68bf1bca9fc58e40323 2680 36cd819aaf578744e50d1357a0e42867 2681 path[2] 04d341aa0a337b19fe4bc43c2e79964d 2682 4f351089f2e0e41c7c43ae0d49e7f404 2683 path[3] b0f75be80ea3af098c9752420a8ac0ea 2684 2bbb1f4eeba05238aef0d8ce63f0c6e5 2685 path[4] e4041d95398a6f7f3e0ee97cc1591849 2686 d4ed236338b147abde9f51ef9fd4e1c1 2688 Authors' Addresses 2690 David McGrew 2691 Cisco Systems 2692 13600 Dulles Technology Drive 2693 Herndon, VA 20171 2694 USA 2696 Email: mcgrew@cisco.com 2698 Michael Curcio 2699 Cisco Systems 2700 7025-2 Kit Creek Road 2701 Research Triangle Park, NC 27709-4987 2702 USA 2704 Email: micurcio@cisco.com 2706 Scott Fluhrer 2707 Cisco Systems 2708 170 West Tasman Drive 2709 San Jose, CA 2710 USA 2712 Email: sfluhrer@cisco.com