idnits 2.17.1 draft-mcgrew-hash-sigs-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 9 instances of too long lines in the document, the longest one being 30 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (June 20, 2017) is 2502 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 1956 -- Looks like a reference, but probably isn't: '1' on line 1958 == Missing Reference: 'Nnv' is mentioned on line 929, but not defined == Missing Reference: 'L-1' is mentioned on line 1006, but not defined == Missing Reference: 'Nspk-1' is mentioned on line 981, but not defined == Missing Reference: 'Nspk' is mentioned on line 981, but not defined -- Looks like a reference, but probably isn't: '32' on line 1950 -- Looks like a reference, but probably isn't: '265' on line 1041 -- Looks like a reference, but probably isn't: '133' on line 1046 -- Looks like a reference, but probably isn't: '67' on line 1051 -- Looks like a reference, but probably isn't: '34' on line 1056 -- Looks like a reference, but probably isn't: '5' on line 1896 -- Looks like a reference, but probably isn't: '10' on line 1906 -- Looks like a reference, but probably isn't: '15' on line 1916 -- Looks like a reference, but probably isn't: '20' on line 1926 -- Looks like a reference, but probably isn't: '25' on line 1936 -- Looks like a reference, but probably isn't: '16' on line 1918 -- Looks like a reference, but probably isn't: '2' on line 1960 -- Looks like a reference, but probably isn't: '3' on line 1962 -- Looks like a reference, but probably isn't: '4' on line 1964 -- Looks like a reference, but probably isn't: '6' on line 1898 -- Looks like a reference, but probably isn't: '7' on line 1900 -- Looks like a reference, but probably isn't: '8' on line 1902 -- Looks like a reference, but probably isn't: '9' on line 1904 -- Looks like a reference, but probably isn't: '11' on line 1908 -- Looks like a reference, but probably isn't: '12' on line 1910 -- Looks like a reference, but probably isn't: '13' on line 1912 -- Looks like a reference, but probably isn't: '14' on line 1914 -- Looks like a reference, but probably isn't: '17' on line 1920 -- Looks like a reference, but probably isn't: '18' on line 1922 -- Looks like a reference, but probably isn't: '19' on line 1924 -- Looks like a reference, but probably isn't: '21' on line 1928 -- Looks like a reference, but probably isn't: '22' on line 1930 -- Looks like a reference, but probably isn't: '23' on line 1932 -- Looks like a reference, but probably isn't: '24' on line 1934 -- Looks like a reference, but probably isn't: '26' on line 1938 -- Looks like a reference, but probably isn't: '27' on line 1940 -- Looks like a reference, but probably isn't: '28' on line 1942 -- Looks like a reference, but probably isn't: '29' on line 1944 -- Looks like a reference, but probably isn't: '30' on line 1946 -- Looks like a reference, but probably isn't: '31' on line 1948 -- Looks like a reference, but probably isn't: '33' on line 1952 == Unused Reference: 'Grover96' is defined on line 1583, but no explicit reference was found in the text == Unused Reference: 'Katz16' is defined on line 1588, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 3979 (Obsoleted by RFC 8179) ** Obsolete normative reference: RFC 4879 (Obsoleted by RFC 8179) Summary: 4 errors (**), 0 flaws (~~), 7 warnings (==), 40 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: December 22, 2017 Cisco Systems 6 June 20, 2017 8 Hash-Based Signatures 9 draft-mcgrew-hash-sigs-07 11 Abstract 13 This note describes a digital signature system based on cryptographic 14 hash functions, following the seminal work in this area of Lamport, 15 Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in 16 1995. It specifies a one-time signature scheme and a general 17 signature scheme. These systems provide asymmetric authentication 18 without using large integer mathematics and can achieve a high 19 security level. They are suitable for compact implementations, are 20 relatively simple to implement, and naturally resist side-channel 21 attacks. Unlike most other signature systems, hash-based signatures 22 would still be secure even if it proves feasible for an attacker to 23 build a quantum computer. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on December 22, 2017. 42 Copyright Notice 44 Copyright (c) 2017 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 61 2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 63 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 5 64 3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 5 65 3.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 6 66 3.2. Security string . . . . . . . . . . . . . . . . . . . . . 7 67 3.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 8 68 3.4. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 8 69 4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 8 70 4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 9 71 4.2. Parameter Sets . . . . . . . . . . . . . . . . . . . . . 10 72 4.3. Private Key . . . . . . . . . . . . . . . . . . . . . . . 10 73 4.4. Public Key . . . . . . . . . . . . . . . . . . . . . . . 11 74 4.5. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 11 75 4.6. Signature Generation . . . . . . . . . . . . . . . . . . 12 76 4.7. Signature Verification . . . . . . . . . . . . . . . . . 13 77 5. Leighton Micali Signatures . . . . . . . . . . . . . . . . . 15 78 5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 16 79 5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 16 80 5.3. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 17 81 5.4. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 18 82 5.4.1. LMS Signature Generation . . . . . . . . . . . . . . 18 83 5.5. LMS Signature Verification . . . . . . . . . . . . . . . 19 84 6. Hierarchical signatures . . . . . . . . . . . . . . . . . . . 20 85 6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 21 86 6.2. Signature Generation . . . . . . . . . . . . . . . . . . 22 87 6.3. Signature Verification . . . . . . . . . . . . . . . . . 23 88 7. Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 89 8. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 26 90 9. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 91 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 92 11. Intellectual Property . . . . . . . . . . . . . . . . . . . . 30 93 11.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 30 94 12. Security Considerations . . . . . . . . . . . . . . . . . . . 30 95 12.1. Stateful signature algorithm . . . . . . . . . . . . . . 32 96 12.2. Security of LM-OTS Checksum . . . . . . . . . . . . . . 33 98 13. Comparison with other work . . . . . . . . . . . . . . . . . 33 99 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 34 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 34 101 15.1. Normative References . . . . . . . . . . . . . . . . . . 34 102 15.2. Informative References . . . . . . . . . . . . . . . . . 35 103 Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 36 104 Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 37 105 Appendix C. An iterative algorithm for computing an LMS public 106 key . . . . . . . . . . . . . . . . . . . . . . . . 38 107 Appendix D. Example Implementation . . . . . . . . . . . . . . . 39 108 Appendix E. Test Cases . . . . . . . . . . . . . . . . . . . . . 39 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 44 111 1. Introduction 113 One-time signature systems, and general purpose signature systems 114 built out of one-time signature systems, have been known since 1979 115 [Merkle79], were well studied in the 1990s [USPTO5432852], and have 116 benefited from renewed attention in the last decade. The 117 characteristics of these signature systems are small private and 118 public keys and fast signature generation and verification, but large 119 signatures and relatively slow key generation. In recent years there 120 has been interest in these systems because of their post-quantum 121 security and their suitability for compact verifier implementations. 123 This note describes the Leighton and Micali adaptation [USPTO5432852] 124 of the original Lamport-Diffie-Winternitz-Merkle one-time signature 125 system [Merkle79] [C:Merkle87][C:Merkle89a][C:Merkle89b] and general 126 signature system [Merkle79] with enough specificity to ensure 127 interoperability between implementations. 129 A signature system provides asymmetric message authentication. The 130 key generation algorithm produces a public/private key pair. A 131 message is signed by a private key, producing a signature, and a 132 message/signature pair can be verified by a public key. A One-Time 133 Signature (OTS) system can be used to sign at most one message 134 securely, but cannot securely sign more than one. An N-time 135 signature system can be used to sign N or fewer messages securely. A 136 Merkle tree signature scheme is an N-time signature system that uses 137 an OTS system as a component. 139 In this note we describe the Leighton-Micali Signature (LMS) system, 140 which is a variant of the Merkle scheme, and a Hierarchical Signature 141 System (HSS) built on top of it that can efficiently scale to larger 142 numbers of signatures. We denote the one-time signature scheme 143 incorporate in LMS as LM-OTS. This note is structured as follows. 144 Notation is introduced in Section 3. The LM-OTS signature system is 145 described in Section 4, and the LMS and HSS N-time signature systems 146 are described in Section 5 and Section 6, respectively. Sufficient 147 detail is provided to ensure interoperability. The public formats 148 are described in Section 7. The rationale for design decisions are 149 given in Section 8. The IANA registry for these signature systems is 150 described in Section 10. Security considerations are presented in 151 Section 12. 153 1.1. Conventions Used In This Document 155 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 156 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 157 document are to be interpreted as described in [RFC2119]. 159 2. Interface 161 The LMS signing algorithm is stateful; it modifies and updates the 162 private key as a side effect of generating a signature. Once a 163 particular value of the private key is used to sign one message, it 164 MUST NOT be used to sign another. 166 The key generation algorithm takes as input an indication of the 167 parameters for the signature system. If it is successful, it 168 returns both a private key and a public key. Otherwise, it 169 returns an indication of failure. 171 The signing algorithm takes as input the message to be signed and 172 the current value of the private key. If successful, it returns a 173 signature and the next value of the private key, if there is such 174 a value. After the private key of an N-time signature system has 175 signed N messages, the signing algorithm returns the signature and 176 an indication that there is no next value of the private key that 177 can be used for signing. If unsuccessful, it returns an 178 indication of failure. 180 The verification algorithm takes as input the public key, a 181 message, and a signature, and returns an indication of whether or 182 not the signature and message pair are valid. 184 A message/signature pair are valid if the signature was returned by 185 the signing algorithm upon input of the message and the private key 186 corresponding to the public key; otherwise, the signature and message 187 pair are not valid with probability very close to one. 189 3. Notation 190 3.1. Data Types 192 Bytes and byte strings are the fundamental data types. A single byte 193 is denoted as a pair of hexadecimal digits with a leading "0x". A 194 byte string is an ordered sequence of zero or more bytes and is 195 denoted as an ordered sequence of hexadecimal characters with a 196 leading "0x". For example, 0xe534f0 is a byte string with a length 197 of three. An array of byte strings is an ordered set, indexed 198 starting at zero, in which all strings have the same length. 200 Unsigned integers are converted into byte strings by representing 201 them in network byte order. To make the number of bytes in the 202 representation explicit, we define the functions u8str(X), u16str(X), 203 and u32str(X), which take a non-negative integer X as input and 204 return one, two, and four byte strings, respectively. We also make 205 use of the function strTou32(S), which takes a four byte string S as 206 input and returns a non-negative integer; the identity 207 u32str(strTou32(S)) = S holds for any four-byte string S. 209 3.1.1. Operators 211 When a and b are real numbers, mathematical operators are defined as 212 follows: 214 ^ : a ^ b denotes the result of a raised to the power of b 216 * : a * b denotes the product of a multiplied by b 218 / : a / b denotes the quotient of a divided by b 220 % : a % b denotes the remainder of the integer division of a by b 222 + : a + b denotes the sum of a and b 224 - : a - b denotes the difference of a and b 226 The standard order of operations is used when evaluating arithmetic 227 expressions. 229 When B is a byte and i is an integer, then B >> i denotes the logical 230 right-shift operation. Similarly, B << i denotes the logical left- 231 shift operation. 233 If S and T are byte strings, then S || T denotes the concatenation of 234 S and T. If S and T are equal length byte strings, then S AND T 235 denotes the bitwise logical and operation. 237 The i^th element in an array A is denoted as A[i]. 239 3.1.2. Strings of w-bit elements 241 If S is a byte string, then byte(S, i) denotes its i^th byte, where 242 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 243 the range of bytes from the i^th to the j^th byte, inclusive. For 244 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 245 2) is 0x0406. 247 A byte string can be considered to be a string of w-bit unsigned 248 integers; the correspondence is defined by the function coef(S, i, w) 249 as follows: 251 If S is a string, i is a positive integer, and w is a member of the 252 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 253 is interpreted as a sequence of w-bit values. That is, 255 coef(S, i, w) = (2^w - 1) AND 256 ( byte(S, floor(i * w / 8)) >> 257 (8 - (w * (i % (8 / w)) + w)) ) 259 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 260 coef(S, 0, 4) is 1. 262 S (represented as bits) 263 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 264 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 265 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 266 ^ 267 | 268 coef(S, 7, 1) 270 S (represented as four-bit values) 271 +-----------+-----------+-----------+-----------+ 272 | 1 | 2 | 3 | 4 | 273 +-----------+-----------+-----------+-----------+ 274 ^ 275 | 276 coef(S, 0, 4) 278 The return value of coef is an unsigned integer. If i is larger than 279 the number of w-bit values in S, then coef(S, i, w) is undefined, and 280 an attempt to compute that value should raise an error. 282 3.2. Security string 284 To improve security against attacks that amortize their effort 285 against multiple invocations of the hash function, Leighton and 286 Micali introduce a "security string" that is distinct for each 287 invocation of that function. Whenever this process computes a hash, 288 the string being hashed will start with a string formed from the 289 below fields. These fields are: 291 I - a 16 byte identifier for the LMS public/private key pair. It 292 MUST be chosen uniformly at random, or via a pseudorandom process, 293 at the time that a key pair is generated, in order to minimize the 294 probability that any specific value of I be used for a large 295 number of different LMS private keys. This is always bytes 0-15 296 of the hash. 298 r - in the LMS N-time signature scheme, the node number r 299 associated with a particular node of a hash tree is used as an 300 input to the hash used to compute that node. This value is 301 represented as a 32-bit (four byte) unsigned integer in network 302 byte order. Either r or q (depending on the domain separate 303 parameter) will be bytes 16-19 of the hash. 305 q - in the LMS N-time signature scheme, each LM-OTS signature is 306 associated with the leaf of a hash tree, and q is set to the leaf 307 number. This ensures that a distinct value of q is used for each 308 distinct LM-OTS public/private key pair. This value is 309 represented as a 32-bit (four byte) unsigned integer in network 310 byte order. Either r or q (depending on the domain separate 311 parameter) will be bytes 16-19 of the hash. 313 D - a domain separation parameter, which is a two byte identifier 314 that takes on different values in the different contexts in which 315 the hash function is invoked. D occurs in bytes 20, 21 of the 316 hash, and takes on the following values: 318 D_PBLC = 0x8080 when computing the hash of all of the iterates 319 in the LM-OTS algorithm 321 D_MESG = 0x8181 when computing the hash of the message in the 322 LM-OTS algorithms 324 D_LEAF = 0x8282 when computing the hash of the leaf of an LMS 325 tree 327 D_INTR = 0x8383 when computing the hash of an interior node of 328 an LMS tree 329 i = a value between 0 and 264; this is used in the LM-OTS 330 scheme, when either computing the iterations of the Winternitz 331 chain, or when using the suggested LM-OTS private key 332 generation process. The value is also the index of the LM-OTS 333 private key element upon which H is being applied. It is 334 represented as a 16-bit (two byte) unsigned integer in network 335 byte order. 337 j - in the LM-OTS scheme, j is the iteration number used when the 338 private key element is being iteratively hashed. It is 339 represented as an 8-bit (one byte) unsigned integer and is present 340 if D is a value between 0 and 264. If present, it occurs at byte 341 22 of the hash. 343 C - an n-byte randomizer that is included with the message 344 whenever it is being hashed to improve security. C MUST be chosen 345 uniformly at random, or via a pseudorandom process. It is present 346 if D=D_MESG, and it occurs at bytes 22-53 of the hash. 348 3.3. Functions 350 If r is a non-negative real number, then we define the following 351 functions: 353 ceil(r) : returns the smallest integer larger than r 355 floor(r) : returns the largest integer smaller than r 357 lg(r) : returns the base-2 logarithm of r 359 3.4. Typecodes 361 A typecode is an unsigned integer that is associated with a 362 particular data format. The format of the LM-OTS, LMS, and HSS 363 signatures and public keys all begin with a typecode that indicates 364 the precise details used in that format. These typecodes are 365 represented as four-byte unsigned integers in network byte order; 366 equivalently, they are XDR enumerations (see Section 7). 368 4. LM-OTS One-Time Signatures 370 This section defines LM-OTS signatures. The signature is used to 371 validate the authenticity of a message by associating a secret 372 private key with a shared public key. These are one-time signatures; 373 each private key MUST be used at most one time to sign any given 374 message. 376 As part of the signing process, a digest of the original message is 377 computed using the cryptographic hash function H (see Section 4.1), 378 and the resulting digest is signed. 380 In order to facilitate its use in an N-time signature system, the LM- 381 OTS key generation, signing, and verification algorithms all take as 382 input a diversification parameter q. When the LM-OTS signature 383 system is used outside of an N-time signature system, this value 384 SHOULD be set to the all-zero value. 386 4.1. Parameters 388 The signature system uses the parameters n and w, which are both 389 positive integers. The algorithm description also makes use of the 390 internal parameters p and ls, which are dependent on n and w. These 391 parameters are summarized as follows: 393 n : the number of bytes of the output of the hash function 395 w : the width (number of bits) of the Winternitz coefficients; it 396 is a member of the set { 1, 2, 4, 8 } 398 p : the number of n-byte string elements that make up the LM-OTS 399 signature 401 ls : the number of left-shift bits used in the checksum function 402 Cksm (defined in Section 4.5). 404 H : a second-preimage-resistant cryptographic hash function that 405 accepts byte strings of any length, and returns an n-byte string. 407 For more background on the cryptographic security requirements on H, 408 see the Section 12. 410 The value of n is determined by the functions selected for use as 411 part of the LM-OTS algorithm; the choice of this value has a strong 412 effect on the security of the system. The parameter w determines the 413 length of the Winternitz chains computed as a part of the OTS 414 signature (which involve 2^w-1 invocations of the hash function); it 415 has little effect on security. Increasing w will shorten the 416 signature, but at a cost of a larger computation to generate and 417 verify a signature. The values of p and ls are dependent on the 418 choices of the parameters n and w, as described in Appendix B. A 419 table illustrating various combinations of n, w, p, and ls is 420 provided in Table 1. 422 4.2. Parameter Sets 424 To fully describe a LM-OTS signature method, the parameters n and w, 425 as well as the function H, MUST be specified. This section defines 426 several LM-OTS methods, each of which is identified by a name. The 427 values for p and ls are provided as a convenience. 429 +---------------------+--------+----+---+-----+----+ 430 | Name | H | n | w | p | ls | 431 +---------------------+--------+----+---+-----+----+ 432 | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 433 | | | | | | | 434 | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 435 | | | | | | | 436 | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 437 | | | | | | | 438 | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 439 +---------------------+--------+----+---+-----+----+ 441 Table 1 443 Here SHA256 denotes the NIST standard hash function [FIPS180]. 445 4.3. Private Key 447 The LM-OTS private key consists of a typecode indicating the 448 particular LM-OTS algorithm, an array x[] containing p n-byte 449 strings, and the 16 byte string I and the 4 byte string q. This 450 private key MUST be used to sign (at most) one message. The 451 following algorithm shows pseudocode for generating a private key. 453 Algorithm 0: Generating a Private Key 455 1. set type to the typecode of the algorithm 457 2. set n and p according to the typecode and Table 1 459 3. compute the array x as follows: 460 for ( i = 0; i < p; i = i + 1 ) { 461 set x[i] to a uniformly random n-byte string 462 } 464 4. return u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] 466 An implementation MAY use a pseudorandom method to compute x[i], as 467 suggested in [Merkle79], page 46. The details of the pseudorandom 468 method do not affect interoperability, but the cryptographic strength 469 MUST match that of the LM-OTS algorithm. Appendix A provides an 470 example of a pseudorandom method for computing LM-OTS private key. 472 4.4. Public Key 474 The LM-OTS public key is generated from the private key by 475 iteratively applying the function H to each individual element of x, 476 for 2^w - 1 iterations, then hashing all of the resulting values. 478 The public key is generated from the private key using the following 479 algorithm, or any equivalent process. 481 Algorithm 1: Generating a One Time Signature Public Key From a 482 Private Key 484 1. set type to the typecode of the algorithm 486 2. set the integers n, p, and w according to the typecode and Table 1 488 3. determine x, I and q from the private key 490 4. compute the string K as follows: 491 for ( i = 0; i < p; i = i + 1 ) { 492 tmp = x[i] 493 for ( j = 0; j < 2^w - 1; j = j + 1 ) { 494 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 495 } 496 y[i] = tmp 497 } 498 K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) 500 5. return u32str(type) || I || u32str(q) || K 502 The public key is the value returned by Algorithm 1. 504 4.5. Checksum 506 A checksum is used to ensure that any forgery attempt that 507 manipulates the elements of an existing signature will be detected. 508 The security property that it provides is detailed in Section 12. 509 The checksum function Cksm is defined as follows, where S denotes the 510 n-byte string that is input to that function, and the value sum is a 511 16-bit unsigned integer: 513 Algorithm 2: Checksum Calculation 515 sum = 0 516 for ( i = 0; i < (n*8/w); i = i + 1 ) { 517 sum = sum + (2^w - 1) - coef(S, i, w) 518 } 519 return (sum << ls) 521 Because of the left-shift operation, the rightmost bits of the result 522 of Cksm will often be zeros. Due to the value of p, these bits will 523 not be used during signature generation or verification. 525 4.6. Signature Generation 527 The LM-OTS signature of a message is generated by first prepending 528 the LM key identifier I, the LM leaf identifier q, the value D_MESG 529 and the randomizer C to the message, then computing the hash, and 530 then concatenating the checksum of the hash to the hash itself, then 531 considering the resulting value as a sequence of w-bit values, and 532 using each of the w-bit values to determine the number of times to 533 apply the function H to the corresponding element of the private key. 534 The outputs of the function H are concatenated together and returned 535 as the signature. The pseudocode for this procedure is shown below. 537 Algorithm 3: Generating a One Time Signature From a Private Key and a 538 Message 540 1. set type to the typecode of the algorithm 542 2. set n, p, and w according to the typecode and Table 1 544 3. determine x, I and q from the private key 546 4. set C to a uniformly random n-byte string 548 5. compute the array y as follows: 549 Q = H(I || u32str(q) || u16str(D_MESG) || C || message) 550 for ( i = 0; i < p; i = i + 1 ) { 551 a = coef(Q || Cksm(Q), i, w) 552 tmp = x[i] 553 for ( j = 0; j < a; j = j + 1 ) { 554 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 555 } 556 y[i] = tmp 557 } 559 6. return u32str(type) || C || y[0] || ... || y[p-1] 561 Note that this algorithm results in a signature whose elements are 562 intermediate values of the elements computed by the public key 563 algorithm in Section 4.4. 565 The signature is the string returned by Algorithm 3. Section 7 566 specifies the typecode and more formally defines the encoding and 567 decoding of the string. 569 4.7. Signature Verification 571 In order to verify a message with its signature (an array of n-byte 572 strings, denoted as y), the receiver must "complete" the chain of 573 iterations of H using the w-bit coefficients of the string resulting 574 from the concatenation of the message hash and its checksum. This 575 computation should result in a value that matches the provided public 576 key. 578 Algorithm 4a: Verifying a Signature and Message Using a Public Key 580 1. if the public key is not at least four bytes long, return INVALID 582 2. parse pubtype, I, q, and K from the public key as follows: 583 a. pubtype = strTou32(first 4 bytes of public key) 585 b. if pubtype is not equal to sigtype, return INVALID 587 c. if the public key is not exactly 24 + n bytes long, 588 return INVALID 590 c. I = next 16 bytes of public key 592 d. q = strTou32(next 4 bytes of public key) 594 e. K = next n bytes of public key 596 3. compute the public key candidate Kc from the signature, 597 message, and the identifiers I and q obtained from the 598 public key, using Algorithm 4b. If Algorithm 4b returns 599 INVALID, then return INVALID. 601 4. if Kc is equal to K, return VALID; otherwise, return INVALID 603 Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, 604 Message, Signature Typecode Type , and identifiers I, q 606 1. if the signature is not at least four bytes long, return INVALID 608 2. parse sigtype, C, and y from the signature as follows: 609 a. sigtype = strTou32(first 4 bytes of signature) 611 b. if sigtype is not equal to Type, return INVALID 613 c. set n and p according to the sigtype and Table 1; if the 614 signature is not exactly 4 + n * (p+1) bytes long, return INVALID 616 d. C = next n bytes of signature 618 e. y[0] = next n bytes of signature 619 y[1] = next n bytes of signature 620 ... 621 y[p-1] = next n bytes of signature 623 3. compute the string Kc as follows 624 Q = H(I || u32str(q) || u16str(D_MESG) || C || message) 625 for ( i = 0; i < p; i = i + 1 ) { 626 a = coef(Q || Cksm(Q), i, w) 627 tmp = y[i] 628 for ( j = a; j < 2^w - 1; j = j + 1 ) { 629 tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) 630 } 631 z[i] = tmp 632 } 633 Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1]) 635 4. return Kc 637 5. Leighton Micali Signatures 639 The Leighton Micali Signature (LMS) method can sign a potentially 640 large but fixed number of messages. An LMS system uses two 641 cryptographic components: a one-time signature method and a hash 642 function. Each LMS public/private key pair is associated with a 643 perfect binary tree, each node of which contains an m-byte value. 644 Each leaf of the tree contains the value of the public key of an LM- 645 OTS public/private key pair. The value contained by the root of the 646 tree is the LMS public key. Each interior node is computed by 647 applying the hash function to the concatenation of the values of its 648 children nodes. 650 Each node of the tree is associated with a node number, an unsigned 651 integer that is denoted as node_num in the algorithms below, which is 652 computed as follows. The root node has node number 1; for each node 653 with node number N < 2^h, its left child has node number 2*N, while 654 its right child has node number 2*N+1. The result of this is that 655 each node within the tree will have a unique node number, and the 656 leaves will have node numbers 2^h, (2^h)+1, (2^h)+2, ..., 657 (2^h)+(2^h)-1. In general, the j^th node at level L has node number 658 2^L + j. The node number can conveniently be computed when it is 659 needed in the LMS algorithms, as described in those algorithms. 661 5.1. Parameters 663 An LMS system has the following parameters: 665 h : the height (number of levels - 1) in the tree, and 667 m : the number of bytes associated with each node. 669 H : a second-preimage-resistant cryptographic hash function that 670 accepts byte strings of any length, and returns an m-byte string. 671 H SHOULD be the same as in Section 4.1, but MAY be different. 673 There are 2^h leaves in the tree. The hash function used within the 674 LMS system SHOULD be the same as the hash function used within the 675 LM-OTS system used to generate the leaves. 677 +--------------------+--------+----+----+ 678 | Name | H | m | h | 679 +--------------------+--------+----+----+ 680 | LMS_SHA256_M32_H5 | SHA256 | 32 | 5 | 681 | | | | | 682 | LMS_SHA256_M32_H10 | SHA256 | 32 | 10 | 683 | | | | | 684 | LMS_SHA256_M32_H15 | SHA256 | 32 | 15 | 685 | | | | | 686 | LMS_SHA256_M32_H20 | SHA256 | 32 | 20 | 687 | | | | | 688 | LMS_SHA256_M32_H25 | SHA256 | 32 | 25 | 689 +--------------------+--------+----+----+ 691 Table 2 693 5.2. LMS Private Key 695 An LMS private key consists of an array OTS_PRIV[] of 2^h LM-OTS 696 private keys, and the leaf number q of the next LM-OTS private key 697 that has not yet been used. The q^th element of OTS_PRIV[] is 698 generated using Algorithm 0 with the identifiers I, q. The leaf 699 number q is initialized to zero when the LMS private key is created. 700 The process is as follows: 702 Algorithm 5: Computing an LMS Private Key. 704 1. determine h and m from the typecode and Table 2. 706 2. compute the array OTS_PRIV[] as follows: 707 for ( q = 0; q < 2^h; q = q + 1) { 708 OTS_PRIV[q] = LM-OTS private key with identifiers I, q 709 } 711 3. q = 0 713 An LMS private key MAY be generated pseudorandomly from a secret 714 value, in which case the secret value MUST be at least m bytes long, 715 be uniformly random, and MUST NOT be used for any other purpose than 716 the generation of the LMS private key. The details of how this 717 process is done do not affect interoperability; that is, the public 718 key verification operation is independent of these details. 719 Appendix A provides an example of a pseudorandom method for computing 720 an LMS private key. 722 5.3. LMS Public Key 724 An LMS public key is defined as follows, where we denote the public 725 key associated with the i^th LM-OTS private key as OTS_PUB[i], with i 726 ranging from 0 to (2^h)-1. Each instance of an LMS public/private 727 key pair is associated with a perfect binary tree, and the nodes of 728 that tree are indexed from 1 to 2^(h+1)-1. Each node is associated 729 with an m-byte string, and the string for the r^th node is denoted as 730 T[r] and is defined as 732 T[r]=/ H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB[r-2^h]) if r >= 2^h, 733 \ H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1]) otherwise. 735 The LMS public key is the string u32str(type) || I || T[1]. 736 Section 7 specifies the format of the type variable. The value I is 737 the private key identifier (whose length is denoted by the parameter 738 set), and is the value used for all computations for the same LMS 739 tree. The value T[1] can be computed via recursive application of 740 the above equation, or by any equivalent method. An iterative 741 procedure is outlined in Appendix C. 743 5.4. LMS Signature 745 An LMS signature consists of 747 the number q of the leaf associated with the LM-OTS signature, as 748 a four-byte unsigned integer in network byte order, 750 an LM-OTS signature, and 752 a typecode indicating the particular LMS algorithm, 754 an array of h m-byte values that is associated with the path 755 through the tree from the leaf associated with the LM-OTS 756 signature to the root. 758 Symbolically, the signature can be represented as u32str(q) || 759 ots_signature || u32str(type) || path[0] || path[1] || ... || 760 path[h-1]. Section 7 specifies the typecode and more formally 761 defines the format. The array of values contains the siblings of the 762 nodes on the path from the leaf to the root but does not contain the 763 nodes on the path themselves. The array for a tree with height h 764 will have h values. The first value is the sibling of the leaf, the 765 next value is the sibling of the parent of the leaf, and so on up the 766 path to the root. 768 5.4.1. LMS Signature Generation 770 To compute the LMS signature of a message with an LMS private key, 771 the signer first computes the LM-OTS signature of the message using 772 the leaf number of the next unused LM-OTS private key. The leaf 773 number q in the signature is set to the leaf number of the LMS 774 private key that was used in the signature. Before releasing the 775 signature, the leaf number q in the LMS private key MUST be 776 incremented, to prevent the LM-OTS private key from being used again. 777 If the LMS private key is maintained in nonvolatile memory, then the 778 implementation MUST ensure that the incremented value has been stored 779 before releasing the signature. 781 The array of node values in the signature MAY be computed in any way. 782 There are many potential time/storage tradeoffs that can be applied. 783 The fastest alternative is to store all of the nodes of the tree and 784 set the array in the signature by copying them. The least storage 785 intensive alternative is to recompute all of the nodes for each 786 signature. Note that the details of this procedure are not important 787 for interoperability; it is not necessary to know any of these 788 details in order to perform the signature verification operation. 789 The internal nodes of the tree need not be kept secret, and thus a 790 node-caching scheme that stores only internal nodes can sidestep the 791 need for strong protections. 793 Several useful time/storage tradeoffs are described in the 'Small- 794 Memory LM Schemes' section of [USPTO5432852]. 796 5.5. LMS Signature Verification 798 An LMS signature is verified by first using the LM-OTS signature 799 verification algorithm (Algorithm 4b) to compute the LM-OTS public 800 key from the LM-OTS signature and the message. The value of that 801 public key is then assigned to the associated leaf of the LMS tree, 802 then the root of the tree is computed from the leaf value and the 803 array path[] as described in Algorithm 6 below. If the root value 804 matches the public key, then the signature is valid; otherwise, the 805 signature fails. 807 Algorithm 6: LMS Signature Verification 809 1. if the public key is not at least four bytes long, return 810 INVALID 812 2. parse pubtype, I, and T[1] from the public key as follows: 814 a. pubtype = strTou32(first 4 bytes of public key) 816 b. if the public key is not exactly 4 + LenI + m bytes 817 long, return INVALID 819 c. I = next LenI bytes of the public key 821 d. T[1] = next m bytes of the public key 823 6. compute the candidate LMS root value Tc from the signature, 824 message, identifier and pubtype using Algorithm 6b. 826 7. if Tc is equal to T[1], return VALID; otherwise, return INVALID 828 Algorithm 6b: Computing an LMS Public Key Candidate from a Signature, 829 Message, Identifier, and algorithm typecode 831 1. if the signature is not at least eight bytes long, return INVALID 833 2. parse sigtype, q, ots_signature, and path from the signature as 834 follows: 836 a. q = strTou32(first 4 bytes of signature) 837 b. otssigtype = strTou32(next 4 bytes of signature) 839 c. if otssigtype is not the OTS typecode from the public key, return INVALID 841 d. set n, p according to otssigtype and Table 1; if the 842 signature is not at least 12 + n * (p + 1) bytes long, return INVALID 844 e. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature 846 f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1)) 848 f. if sigtype is not the LM typecode from the public key, return INVALID 850 g. set m, h according to sigtype and Table 2 852 h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID 854 i. set path as follows: 855 path[0] = next m bytes of signature 856 path[1] = next m bytes of signature 857 ... 858 path[h-1] = next m bytes of signature 860 5. Kc = candidate public key computed by applying Algorithm 4b 861 to the signature ots_signature, the message, and the 862 identifiers I, q 864 6. compute the candidate LMS root value Tc as follows: 865 node_num = 2^h + q 866 tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) 867 i = 0 868 while (node_num > 1) { 869 if (node_num is odd): 870 tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) 871 else: 872 tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i]) 873 node_num = node_num/2 874 i = i + 1 875 } 876 Tc = tmp 878 7. return Tc 880 6. Hierarchical signatures 882 In scenarios where it is necessary to minimize the time taken by the 883 public key generation process, a Hierarchical N-time Signature System 884 (HSS) can be used. Leighton and Micali describe a scheme in which an 885 LMS public key is used to sign a second LMS public key, which is then 886 distributed along with the signatures generated with the second 887 public key [USPTO5432852]. This hierarchical scheme, which we 888 describe in this section, uses an LMS scheme as a component. HSS, in 889 essence, utilizes a tree of LMS trees, in which the HSS public key 890 contains the public key of the LMS tree at the root, and an HSS 891 signature is associated with a path from the root of the HSS tree to 892 one of its leaves. Compared to LMS, HSS has a much reduced public 893 key generation time, as only the root tree needs to be generated 894 prior to the distribution of the HSS public key. 896 Each level of the hierarchy is associated with a distinct LMS public 897 key, private key, signature, and identifier. The number of levels is 898 denoted L, and is between one and eight, inclusive. The following 899 notation is used, where i is an integer between 0 and L-1 inclusive, 900 and the root of the hierarchy is level 0: 902 prv[i] is the LMS private key of the i^th level, 904 pub[i] is the LMS public key of the i^th level (which includes the 905 identifier I as well as the key value K), 907 sig[i] is the LMS signature of the i^th level, 909 In this section, we say that an N-time private key is exhausted when 910 it has generated N signatures, and thus it can no longer be used for 911 signing. 913 HSS allows L=1, in which case the HSS public key and signature 914 formats are essentially the LMS public key and signature formats, 915 prepended by a fixed field. Since HSS with L=1 has very little 916 overhead compared to LMS, all implementations MUST support HSS in 917 order to maximize interoperability. 919 6.1. Key Generation 921 When an HSS key pair is generated, the key pair for each level MUST 922 have its own identifier I. 924 To generate an HSS private and public key pair, new LMS private and 925 public keys are generated for prv[i] and pub[i] for i=0, ... , L-1. 926 These key pairs, and their identifiers, MUST be generated 927 independently. All of the information of the leaf level L-1, 928 including the private key, MUST NOT be stored in nonvolatile memory. 929 Letting Nnv denote the lowest level for which prv[Nnv] is stored in 930 nonvolatile memory, there are Nnv nonvolatile levels, and L-Nnv 931 volatile levels. For security, Nnv should be as close to one as 932 possible (see Section 12.1). 934 The public key of the HSS scheme is consists of the number of levels 935 L, followed by pub[0], the public key of the top level. 937 The HSS private key consists of prv[0], ... , prv[L-1]. The values 938 pub[0] and prv[0] do not change, though the values of pub[i] and 939 prv[i] are dynamic for i > 0, and are changed by the signature 940 generation algorithm. 942 6.2. Signature Generation 944 To sign a message using the private key prv, the following steps are 945 performed: 947 If prv[L-1] is exhausted, then determine the smallest integer d 948 such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] 949 are exhausted. If d is equal to zero, then the HSS key pair is 950 exhausted, and it MUST NOT generate any more signatures. 951 Otherwise, the key pairs for levels d through L-1 must be 952 regenerated during the signature generation process, as follows. 953 For i from d to L-1, a new LMS public and private key pair with a 954 new identifier is generated, pub[i] and prv[i] are set to those 955 values, then the public key pub[i] is signed with prv[i-1], and 956 sig[i-1] is set to the resulting value. 958 The message is signed with prv[L-1], and the value sig[L-1] is set 959 to that result. 961 The value of the HSS signature is set as follows. We let 962 signed_pub_key denote an array of octet strings, where 963 signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk- 964 1, inclusive, where Nspk = L-1 denotes the number of signed public 965 keys. Then the HSS signature is u32str(Nspk) || 966 signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]. 968 Note that the number of signed_pub_key elements in the signature 969 is indicated by the value Nspk that appears in the initial four 970 bytes of the signature. 972 In the specific case of L=1, the format of an HSS signature is 974 u32str(0) || sig[0] 976 In the general case, the format of an HSS signature is 978 u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk] 980 which is equivalent to 981 u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk] 983 6.3. Signature Verification 985 To verify a signature sig and message using the public key pub, the 986 following steps are performed: 988 The signature S is parsed into its components as follows: 990 L' = strTou32(first four bytes of S) 991 if L' is not equal to the number of levels L in pub: 992 return INVALID 993 for (i = 0; i < L; i = i + 1) { 994 siglist[i] = next LMS signature parsed from S 995 publist[i] = next LMS public key parsed from S 996 } 997 siglist[L-1] = next LMS signature parsed from S 999 key = pub 1000 for (i = 0; i < L; i = i + 1) { 1001 sig = siglist[i] 1002 msg = publist[i] 1003 if (lms_verify(msg, key, sig) != VALID): 1004 return INVALID 1005 key = msg 1006 return lms_verify(message, key, siglist[L-1]) 1008 Since the length of an LMS signature cannot be known without parsing 1009 it, the HSS signature verification algorithm makes use of an LMS 1010 signature parsing routine that takes as input a string consisting of 1011 an LMS signature with an arbitrary string appended to it, and returns 1012 both the LMS signature and the appended string. The latter is passed 1013 on for further processing. 1015 7. Formats 1017 The signature and public key formats are formally defined using the 1018 External Data Representation (XDR) [RFC4506] in order to provide an 1019 unambiguous, machine readable definition. For clarity, we also 1020 include a private key format as well, though consistency is not 1021 needed for interoperability and an implementation MAY use any private 1022 key format. Though XDR is used, these formats are simple and easy to 1023 parse without any special tools. An illustration of the layout of 1024 data in these objects is provided below. The definitions are as 1025 follows: 1027 /* one-time signatures */ 1029 enum ots_algorithm_type { 1030 lmots_reserved = 0, 1031 lmots_sha256_n32_w1 = 1, 1032 lmots_sha256_n32_w2 = 2, 1033 lmots_sha256_n32_w4 = 3, 1034 lmots_sha256_n32_w8 = 4 1035 }; 1037 typedef opaque bytestring32[32]; 1039 struct lmots_signature_n32_p265 { 1040 bytestring32 C; 1041 bytestring32 y[265]; 1042 }; 1044 struct lmots_signature_n32_p133 { 1045 bytestring32 C; 1046 bytestring32 y[133]; 1047 }; 1049 struct lmots_signature_n32_p67 { 1050 bytestring32 C; 1051 bytestring32 y[67]; 1052 }; 1054 struct lmots_signature_n32_p34 { 1055 bytestring32 C; 1056 bytestring32 y[34]; 1057 }; 1059 union ots_signature switch (ots_algorithm_type type) { 1060 case lmots_sha256_n32_w1: 1061 lmots_signature_n32_p265 sig_n32_p265; 1062 case lmots_sha256_n32_w2: 1063 lmots_signature_n32_p133 sig_n32_p133; 1064 case lmots_sha256_n32_w4: 1065 lmots_signature_n32_p67 sig_n32_p67; 1066 case lmots_sha256_n32_w8: 1067 lmots_signature_n32_p34 sig_n32_p34; 1068 default: 1069 void; /* error condition */ 1070 }; 1072 /* hash based signatures (hbs) */ 1073 enum hbs_algorithm_type { 1074 hbs_reserved = 0, 1075 lms_sha256_n32_h5 = 5, 1076 lms_sha256_n32_h10 = 6, 1077 lms_sha256_n32_h15 = 7, 1078 lms_sha256_n32_h20 = 8, 1079 lms_sha256_n32_h25 = 9, 1080 }; 1082 /* leighton micali signatures (lms) */ 1084 union lms_path switch (hbs_algorithm_type type) { 1085 case lms_sha256_n32_h5: 1086 bytestring32 path_n32_h5[5]; 1087 case lms_sha256_n32_h10: 1088 bytestring32 path_n32_h10[10]; 1089 case lms_sha256_n32_h15: 1090 bytestring32 path_n32_h15[15]; 1091 case lms_sha256_n32_h20: 1092 bytestring32 path_n32_h20[20]; 1093 case lms_sha256_n32_h25: 1094 bytestring32 path_n32_h25[25]; 1095 default: 1096 void; /* error condition */ 1097 }; 1099 struct lms_signature { 1100 unsigned int q; 1101 ots_signature lmots_sig; 1102 lms_path nodes; 1103 }; 1105 struct lms_key_n32 { 1106 ots_algorithm_type ots_alg_type; 1107 opaque I[16]; 1108 opaque K[32]; 1109 }; 1111 union hbs_public_key switch (hbs_algorithm_type type) { 1112 case lms_sha256_n32_h5: 1113 case lms_sha256_n32_h10: 1114 case lms_sha256_n32_h15: 1115 case lms_sha256_n32_h20: 1116 case lms_sha256_n32_h25: 1117 lms_key_n32 z_n32; 1118 default: 1119 void; /* error condition */ 1120 }; 1121 /* hierarchical signature system (hss) */ 1123 struct hss_public_key { 1124 unsigned int L; 1125 hbs_public_key pub; 1126 }; 1128 struct signed_public_key { 1129 hbs_signature sig; 1130 hbs_public_key pub; 1131 } 1133 struct hss_signature { 1134 signed_public_key signed_keys<7>; 1135 hbs_signature sig_of_message; 1136 }; 1138 Many of the objects start with a typecode. A verifier MUST check 1139 each of these typecodes, and a verification operation on a signature 1140 with an unknown type, or a type that does not correspond to the type 1141 within the public key MUST return INVALID. The expected length of a 1142 variable-length object can be determined from its typecode, and if an 1143 object has a different length, then any signature computed from the 1144 object is INVALID. 1146 8. Rationale 1148 The goal of this note is to describe the LM-OTS, LMS and HSS 1149 algorithms following the original references and present the modern 1150 security analysis of those algorithms. Other signature methods are 1151 out of scope and may be interesting follow-on work. 1153 We adopt the techniques described by Leighton and Micali to mitigate 1154 attacks that amortize their work over multiple invocations of the 1155 hash function. 1157 The values taken by the identifier I across different LMS public/ 1158 private key pairs are chosen randomly in order to improve security. 1159 The analysis of this method in [Fluhrer17] shows that we do not need 1160 uniqueness to ensure security; we do need to ensure that we don't 1161 have a large number of private keys that use the same I value. By 1162 randomly selecting 16 byte I values, the chance that, out of 2^64 1163 private keys, 4 or more of them will use the same I value is 1164 negligible (that is, has probability less than 2^-128). 1166 The reason this size was selected was to optimize the Winternitz hash 1167 chain operation. With the current settings, the value being hashed 1168 is exactly 55 bytes long (for a 32 byte hash function), which SHA-256 1169 can hash in a single hash compression operation. Other hash 1170 functions may be used in future specifications; all the ones that we 1171 will be likely to support (SHA-512/256 and the various SHA-3 hashes) 1172 would work well with a 16 byte I value. 1174 The signature and public key formats are designed so that they are 1175 relatively easy to parse. Each format starts with a 32-bit 1176 enumeration value that indicates the details of the signature 1177 algorithm and provides all of the information that is needed in order 1178 to parse the format. 1180 The Checksum Section 4.5 is calculated using a non-negative integer 1181 "sum", whose width was chosen to be an integer number of w-bit fields 1182 such that it is capable of holding the difference of the total 1183 possible number of applications of the function H as defined in the 1184 signing algorithm of Section 4.6 and the total actual number. In the 1185 case that the number of times H is applied is 0, the sum is (2^w - 1) 1186 * (8*n/w). Thus for the purposes of this document, which describes 1187 signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 1188 4, 8 }, the sum variable is a 16-bit non-negative integer for all 1189 combinations of n and w. The calculation uses the parameter ls 1190 defined in Section 4.1 and calculated in Appendix B, which indicates 1191 the number of bits used in the left-shift operation. 1193 9. History 1195 This is the seventh version of this draft. It has the following 1196 changes from previous versions: 1198 Version 06 1200 Modified the order of the values that were hashed to make it 1201 easier to prove security. 1203 Decreased the size of the I LMS public key identifier to 16 bytes. 1205 Version 05 1207 Clarified the L=1 specific case. 1209 Extended the parameter sets to include an H=25 option 1211 A large number of corrections and clarifications 1213 Added a comparison to XMSS and SPHINCS, and citations to those 1214 algorithms and to the recent Security Standardization Research 1215 2016 publications on the security of LMS and on the state 1216 management in hash-based signatures. 1218 Version 04 1220 Specified that, in the HSS method, the I value was computed from 1221 the I value of the parent LM tree. Previous versions had the I 1222 value extracted from the public key (which meant that all LM trees 1223 of a particular level and public key used the same I value) 1225 Changed the length of the I field based on the parameter set. As 1226 noted in the Rationale section, this allows an implementation to 1227 compute SHA256 n=32 based parameter sets significantly faster. 1229 Modified the XDR of an HSS signature not to use an array of LM 1230 signatures; LM signatures are variable length, and XDR doesn't 1231 support arrays of variable length structures. 1233 Changed the LMS registry to be in a consistent order with the LM- 1234 OTS parameter sets. Also, added LMS parameter sets with height 15 1235 trees 1237 Previous versions 1239 In Algorithms 3 and 4, the message was moved from the initial 1240 position of the input to the function H to the final position, in 1241 the computation of the intermediate variable Q. This was done to 1242 improve security by preventing an attacker that can find a 1243 collision in H from taking advantage of that fact via the forward 1244 chaining property of Merkle-Damgard. 1246 The Hierarchical Signature Scheme was generalized slightly so that 1247 it can use more than two levels. 1249 Several points of confusion were corrected; these had resulted 1250 from incomplete or inconsistent changes from the Merkle approach 1251 of the earlier draft to the Leighton-Micali approach. 1253 This section is to be removed by the RFC editor upon publication. 1255 10. IANA Considerations 1257 The Internet Assigned Numbers Authority (IANA) is requested to create 1258 two registries: one for OTS signatures, which includes all of the LM- 1259 OTS signatures as defined in Section 3, and one for Leighton-Micali 1260 Signatures, as defined in Section 4. Additions to these registries 1261 require that a specification be documented in an RFC or another 1262 permanent and readily available reference in sufficient detail that 1263 interoperability between independent implementations is possible. 1264 Each entry in the registry contains the following elements: 1266 a short name, such as "LMS_SHA256_M32_H10", 1268 a positive number, and 1270 a reference to a specification that completely defines the 1271 signature method test cases that can be used to verify the 1272 correctness of an implementation. 1274 Requests to add an entry to the registry MUST include the name and 1275 the reference. The number is assigned by IANA. Submitters SHOULD 1276 have their requests reviewed by the IRTF Crypto Forum Research Group 1277 (CFRG) at cfrg@ietf.org. Interested applicants that are unfamiliar 1278 with IANA processes should visit http://www.iana.org. 1280 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1281 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1282 are reserved for private use; no attempt will be made to prevent 1283 multiple sites from using the same value in different (and 1284 incompatible) ways [RFC2434]. 1286 The LM-OTS registry is as follows. 1288 +----------------------+-----------+--------------------+ 1289 | Name | Reference | Numeric Identifier | 1290 +----------------------+-----------+--------------------+ 1291 | LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 | 1292 | | | | 1293 | LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 | 1294 | | | | 1295 | LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 | 1296 | | | | 1297 | LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 | 1298 +----------------------+-----------+--------------------+ 1300 Table 3 1302 The LMS registry is as follows. 1304 +--------------------+-----------+--------------------+ 1305 | Name | Reference | Numeric Identifier | 1306 +--------------------+-----------+--------------------+ 1307 | LMS_SHA256_M32_H5 | Section 5 | 0x00000005 | 1308 | | | | 1309 | LMS_SHA256_M32_H10 | Section 5 | 0x00000006 | 1310 | | | | 1311 | LMS_SHA256_M32_H15 | Section 5 | 0x00000007 | 1312 | | | | 1313 | LMS_SHA256_M32_H20 | Section 5 | 0x00000008 | 1314 | | | | 1315 | LMS_SHA256_M32_H25 | Section 5 | 0x00000009 | 1316 +--------------------+-----------+--------------------+ 1318 Table 4 1320 An IANA registration of a signature system does not constitute an 1321 endorsement of that system or its security. 1323 11. Intellectual Property 1325 This draft is based on U.S. patent 5,432,852, which issued over 1326 twenty years ago and is thus expired. 1328 11.1. Disclaimer 1330 This document is not intended as legal advice. Readers are advised 1331 to consult with their own legal advisers if they would like a legal 1332 interpretation of their rights. 1334 The IETF policies and processes regarding intellectual property and 1335 patents are outlined in [RFC3979] and [RFC4879] and at 1336 https://datatracker.ietf.org/ipr/about. 1338 12. Security Considerations 1340 The hash function H MUST have second preimage resistance: it must be 1341 computationally infeasible for an attacker that is given one message 1342 M to be able to find a second message M' such that H(M) = H(M'). 1344 The security goal of a signature system is to prevent forgeries. A 1345 successful forgery occurs when an attacker who does not know the 1346 private key associated with a public key can find a message and 1347 signature that are valid with that public key (that is, the Signature 1348 Verification algorithm applied to that signature and message and 1349 public key will return VALID). Such an attacker, in the strongest 1350 case, may have the ability to forge valid signatures for an arbitrary 1351 number of other messages. 1353 LMS is provably secure in the random oracle model, where the hash 1354 compression function is considered the random oracle, as shown by 1355 [Fluhrer17]. Corollary 1 of that paper states: 1357 If we have no more than 2^64 randomly chosen LMS private keys, 1358 allow the attacker access to a signing oracle and a SHA-256 hash 1359 compression oracle, and allow a maximum of 2^120 hash compression 1360 computations, then the probability of an attacker being able to 1361 generate a single forgery against any of those LMS keys is less 1362 than 2^-129. 1364 The format of the inputs to the hash function H have the property 1365 that each invocation of that function has an input that is repeated 1366 by a small bounded number of other inputs (due to potential repeats 1367 of the I value), and in particular, will vary somewhere in the first 1368 23 bytes of the value being hashed. This property is important for a 1369 proof of security in the random oracle model. The formats used 1370 during key generation and signing are 1372 I || u32str(q) || u16str(i) || u8str(j) || tmp 1373 I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1] 1374 I || u32str(q) || u16str(D_MESG) || C || message 1375 I || u32str(r) || u16str(D_LEAF) || OTS_PUB[r-2^h] 1376 I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1] 1377 I || u32str(q) || u16str(j) || u8str(0xff) || SEED 1379 Each hash type listed is distinct; at locations 20, 21 of each hash, 1380 there exists either a fixed value D_PBLC, D_MESG, D_LEAF, D_INTR, or 1381 a 16 bit value (i or j). These fixed values are distinct from each 1382 other, and large (over 32768), while the 16 bit values are small 1383 (currently no more than 265; possibly being slightly larger if larger 1384 hash functions are supported; hence the hash invocations with i/j 1385 will not collide any of the D_PBLC, D_MESG, D_LEAF, D_INTR hashes. 1386 The only other collision possibility is the Winternitz chain hash 1387 colliding with the recommended pseudorandom key generation process; 1388 here, at location 22, the Winternitz chain function has the value 1389 u8str(j), where j is a value between 0 and 254, while location 22 of 1390 the recommended pseudorandom key generation process has value 255. 1392 For the Winternitz chaining function, D_PBLC, and D_MESG, the value 1393 of I || u32str(q) is distinct for each LMS leaf (or equivalently, for 1394 each q value). For the Winternitz chaining function, the value of 1395 u16str(i) || u8str(j) is distinct for each invocation of H for a 1396 given leaf. For D_PBLC and D_MESG, the input format is used only 1397 once for each value of q, and thus distinctness is assured. The 1398 formats for D_INTR and D_LEAF are used exactly once for each value of 1399 r, which ensures their distinctness. For the recommended 1400 pseuddorandom key generation process, for a given value of I, q and j 1401 are distinct for each invocation of H. 1403 The value of I is chosen uniformly at random from the set of all 128 1404 bit strings. If 2^64 public keys are generated (and hence 2^64 1405 random I values), there is a nontrivial probability of a duplicate 1406 (which would imply duplicate prefixes. However, there will be an 1407 extremely high probability there there will not be a four-way 1408 collision (that is, any I value used for four distinct LMS keys; 1409 probability < 2^-132), and hence the number of repeats for any 1410 specific prefix will be limited to 3. This can be shown (in 1411 [Fluhrer17]) to have only a limited ebffect on the security of the 1412 system. 1414 12.1. Stateful signature algorithm 1416 The LMS signature system, like all N-time signature systems, requires 1417 that the signer maintain state across different invocations of the 1418 signing algorithm, to ensure that none of the component one-time 1419 signature systems are used more than once. This section calls out 1420 some important practical considerations around this statefulness. 1422 In a typical computing environment, a private key will be stored in 1423 non-volatile media such as on a hard drive. Before it is used to 1424 sign a message, it will be read into an application's Random Access 1425 Memory (RAM). After a signature is generated, the value of the 1426 private key will need to be updated by writing the new value of the 1427 private key into non-volatile storage. It is essential for security 1428 that the application ensure that this value is actually written into 1429 that storage, yet there may be one or more memory caches between it 1430 and the application. Memory caching is commonly done in the file 1431 system, and in a physical memory unit on the hard disk that is 1432 dedicated to that purpose. To ensure that the updated value is 1433 written to physical media, the application may need to take several 1434 special steps. In a POSIX environment, for instance, the O_SYNC flag 1435 (for the open() system call) will cause invocations of the write() 1436 system call to block the calling process until the data has been to 1437 the underlying hardware. However, if that hardware has its own 1438 memory cache, it must be separately dealt with using an operating 1439 system or device specific tool such as hdparm to flush the on-drive 1440 cache, or turn off write caching for that drive. Because these 1441 details vary across different operating systems and devices, this 1442 note does not attempt to provide complete guidance; instead, we call 1443 the implementer's attention to these issues. 1445 When hierarchical signatures are used, an easy way to minimize the 1446 private key synchronization issues is to have the private key for the 1447 second level resident in RAM only, and never write that value into 1448 non-volatile memory. A new second level public/private key pair will 1449 be generated whenever the application (re)starts; thus, failures such 1450 as a power outage or application crash are automatically 1451 accommodated. Implementations SHOULD use this approach wherever 1452 possible. 1454 12.2. Security of LM-OTS Checksum 1456 To show the security of LM-OTS checksum, we consider the signature y 1457 of a message with a private key x and let h = H(message) and 1458 c = Cksm(H(message)) (see Section 4.6). To attempt a forgery, an 1459 attacker may try to change the values of h and c. Let h' and c' 1460 denote the values used in the forgery attempt. If for some integer j 1461 in the range 0 to u, where u = ceil(8*n/w) is the size of the range 1462 that the checksum value can over), inclusive, 1464 a' = coef(h', j, w), 1466 a = coef(h, j, w), and 1468 a' > a 1470 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1471 iteratively applying function F to the j^th term of the signature an 1472 additional (a' - a) times. However, as a result of the increased 1473 number of hashing iterations, the checksum value c' will decrease 1474 from its original value of c. Thus a valid signature's checksum will 1475 have, for some number k in the range u to (p-1), inclusive, 1477 b' = coef(c', k, w), 1479 b = coef(c, k, w), and 1481 b' < b 1483 Due to the one-way property of F, the attacker cannot easily compute 1484 F^b'(x[k]) from F^b(x[k]) = y[k]. 1486 13. Comparison with other work 1488 The eXtended Merkle Signature Scheme (XMSS) [XMSS] is similar to HSS 1489 in several ways. Both are stateful hash based signature schemes, and 1490 both use a hierarchical approach, with a Merkle tree at each level of 1491 the hierarchy. XMSS signatures are slightly shorter than HSS 1492 signatures, for equivalent security and an equal number of 1493 signatures. 1495 HSS has several advantages over XMSS. HSS operations are roughly 1496 four times faster than the comparable XMSS ones, when SHA256 is used 1497 as the underlying hash. This occurs because the hash operation done 1498 as a part of the Winternitz iterations dominates performance, and 1499 XMSS performs four compression function invocations (two for the PRF, 1500 two for the F function) where HSS need only perform one. 1501 Additionally, HSS is somewhat simpler, and it admits a single-level 1502 tree in a simple way (as described in Section 6.2). 1504 Another advantage of HSS is the fact that it can use a stateless 1505 hash-based signature scheme in its non-volatile levels, while 1506 continuing to use LMS in its volatile levels, and thus realize a 1507 hybrid stateless/stateful scheme as described in [STMGMT]. While we 1508 conjecture that hybrid schemes will offer lower computation times and 1509 signature sizes than purely stateless schemes, the details are 1510 outside the scope of this note. HSS is therefore amenable to future 1511 extensions that will enable it to be used in environments in which a 1512 purely stateful scheme would be too brittle. 1514 SPHINCS [SPHINCS] is a purely stateless hash based signature scheme. 1515 While that property benefits security, its signature sizes and 1516 generation times are an order of magnitude (or more) larger than 1517 those of HSS, making it more difficult to adopt in some practical 1518 scenarios. 1520 14. Acknowledgements 1522 Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric 1523 Osterweil, Ahmed Kosba, Russ Housley and Philip Lafrance for 1524 constructive suggestions and valuable detailed review. We especially 1525 acknowledge Jerry Solinas, Laurie Law, and Kevin Igoe, who pointed 1526 out the security benefits of the approach of Leighton and Micali 1527 [USPTO5432852] and Jonathan Katz, who gave us security guidance. 1529 15. References 1531 15.1. Normative References 1533 [FIPS180] National Institute of Standards and Technology, "Secure 1534 Hash Standard (SHS)", FIPS 180-4, March 2012. 1536 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1537 Requirement Levels", BCP 14, RFC 2119, 1538 DOI 10.17487/RFC2119, March 1997, 1539 . 1541 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1542 IANA Considerations Section in RFCs", RFC 2434, 1543 DOI 10.17487/RFC2434, October 1998, 1544 . 1546 [RFC3979] Bradner, S., Ed., "Intellectual Property Rights in IETF 1547 Technology", RFC 3979, DOI 10.17487/RFC3979, March 2005, 1548 . 1550 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1551 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1552 2006, . 1554 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1555 Procedure in RFC 3979", RFC 4879, DOI 10.17487/RFC4879, 1556 April 2007, . 1558 [USPTO5432852] 1559 Leighton, T. and S. Micali, "Large provably fast and 1560 secure digital signature schemes from secure hash 1561 functions", U.S. Patent 5,432,852, July 1995. 1563 15.2. Informative References 1565 [C:Merkle87] 1566 Merkle, R., "A Digital Signature Based on a Conventional 1567 Encryption Function", Lecture Notes in Computer 1568 Science crypto87vol, 1988. 1570 [C:Merkle89a] 1571 Merkle, R., "A Certified Digital Signature", Lecture Notes 1572 in Computer Science crypto89vol, 1990. 1574 [C:Merkle89b] 1575 Merkle, R., "One Way Hash Functions and DES", Lecture 1576 Notes in Computer Science crypto89vol, 1990. 1578 [Fluhrer17] 1579 Fluhrer, S., "Further analysis of a proposed hash-based 1580 signature standard", 1581 EPrint http://eprint.iacr.org/2017/553.pdf, 2017. 1583 [Grover96] 1584 Grover, L., "A fast quantum mechanical algorithm for 1585 database search", 28th ACM Symposium on the Theory of 1586 Computing p. 212, 1996. 1588 [Katz16] Katz, J., "Analysis of a proposed hash-based signature 1589 standard", Security Standardization Research (SSR) 1590 Conference http://www.cs.umd.edu/~jkatz/papers/ 1591 HashBasedSigs-SSR16.pdf, 2016. 1593 [Merkle79] 1594 Merkle, R., "Secrecy, Authentication, and Public Key 1595 Systems", Stanford University Information Systems 1596 Laboratory Technical Report 1979-1, 1979. 1598 [SPHINCS] Bernstein, D., Hopwood, D., Hulsing, A., Lange, T., 1599 Niederhagen, R., Papachristadoulou, L., Schneider, M., 1600 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical 1601 Stateless Hash-Based Signatures.", Annual International 1602 Conference on the Theory and Applications of Cryptographic 1603 Techniques Springer., 2015. 1605 [STMGMT] McGrew, D., Fluhrer, S., Kampanakis, P., Gazdag, S., 1606 Butin, D., and J. Buchmann, "State Management for Hash- 1607 based Signatures.", Security Standardization Resarch (SSR) 1608 Conference 224., 2016. 1610 [XMSS] Buchmann, J., Dahmen, E., and . Andreas Hulsing, "XMSS-a 1611 practical forward secure signature scheme based on minimal 1612 security assumptions.", International Workshop on Post- 1613 Quantum Cryptography Springer Berlin., 2011. 1615 Appendix A. Pseudorandom Key Generation 1617 An implementation MAY use the following pseudorandom process for 1618 generating an LMS private key. 1620 SEED is an m-byte value that is generated uniformly at random at 1621 the start of the process, 1623 I is LMS key pair identifier, 1625 q denotes the LMS leaf number of an LM-OTS private key, 1627 x_q denotes the x array of private elements in the LM-OTS private 1628 key with leaf number q, 1630 j is an index of the private key element, and 1632 H is the hash function used in LM-OTS. 1634 The elements of the LM-OTS private keys are computed as: 1636 x_q[j] = H(I || u32str(q) || u16str(j) || u8str(0xff) || SEED). 1638 This process stretches the m-byte random value SEED into a (much 1639 larger) set of pseudorandom values, using a unique counter in each 1640 invocation of H. The format of the inputs to H are chosen so that 1641 they are distinct from all other uses of H in LMS and LM-OTS. A 1642 careful reader will note that this is similar to the hash we perform 1643 when iterating through the Winternitz chain; however in that chain, 1644 the iteration index will vary between 0 and 254 maximum (for W=8), 1645 while the corresponding value in this formula is 255. This algorithm 1646 is included in the proof of security in [Fluhrer17] and hence this 1647 method is safe when used within the LMS system; however any other 1648 cryptographical secure method of generating private keys would also 1649 be safe. 1651 Appendix B. LM-OTS Parameter Options 1653 A table illustrating various combinations of n and w with the 1654 associated values of u, v, ls, and p is provided in Table 5. 1656 The parameters u, v, ls, and p are computed as follows: 1658 u = ceil(8*n/w) 1659 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1660 ls = (number of bits in sum) - (v * w) 1661 p = u + v 1663 Here u and v represent the number of w-bit fields required to contain 1664 the hash of the message and the checksum byte strings, respectively. 1665 The "number of bits in sum" is defined according to Section 4.5. And 1666 as the value of p is the number of w-bit elements of 1667 ( H(message) || Cksm(H(message)) ), it is also equivalently the 1668 number of byte strings that form the private key and the number of 1669 byte strings in the signature. 1671 +---------+------------+-----------+-----------+-------+------------+ 1672 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1673 | Length | Parameter | Elements | Elements | Shift | Number of | 1674 | in | (w) | in Hash | in | (ls) | w-bit | 1675 | Bytes | | (u) | Checksum | | Elements | 1676 | (n) | | | (v) | | (p) | 1677 +---------+------------+-----------+-----------+-------+------------+ 1678 | 16 | 1 | 128 | 8 | 8 | 137 | 1679 | | | | | | | 1680 | 16 | 2 | 64 | 4 | 8 | 68 | 1681 | | | | | | | 1682 | 16 | 4 | 32 | 3 | 4 | 35 | 1683 | | | | | | | 1684 | 16 | 8 | 16 | 2 | 0 | 18 | 1685 | | | | | | | 1686 | 32 | 1 | 256 | 9 | 7 | 265 | 1687 | | | | | | | 1688 | 32 | 2 | 128 | 5 | 6 | 133 | 1689 | | | | | | | 1690 | 32 | 4 | 64 | 3 | 4 | 67 | 1691 | | | | | | | 1692 | 32 | 8 | 32 | 2 | 0 | 34 | 1693 +---------+------------+-----------+-----------+-------+------------+ 1695 Table 5 1697 Appendix C. An iterative algorithm for computing an LMS public key 1699 The LMS public key can be computed using the following algorithm or 1700 any equivalent method. The algorithm uses a stack of hashes for 1701 data. It also makes use of a hash function with the typical 1702 init/update/final interface to hash functions; the result of the 1703 invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , 1704 hash_update(N[n]), v = hash_final(), in that order, is identical to 1705 that of the invocation of H(N[1] || N[2] || ... || N[n]). 1707 Generating an LMS Public Key From an LMS Private Key 1709 for ( i = 0; i < num_lmots_keys; i = i + 1 ) { 1710 r = i + num_lmots_keys; 1711 temp = H(I || OTS_PUBKEY[i] || u32str(r) || D_LEAF) 1712 j = i; 1713 while (j % 2 == 1) { 1714 r = (r - 1)/2; j = (j-1) / 2; 1715 left_size = pop(data stack); 1716 temp = H(I || left_side || temp || u32str(r) || D_INTR) 1717 } 1718 push temp onto the data stack 1719 } 1720 public_key = pop(data stack) 1722 Note that this pseudocode expects that all 2^h leaves of the tree 1723 have equal depth; that is, num_lmots_keys to be a power of 2. The 1724 maximum depth of the stack will be h-1 elements, that is, a total of 1725 (h-1)*n bytes; for the currently defined parameter sets, this will 1726 never be more than 768 bytes of data. 1728 Appendix D. Example Implementation 1730 An example implementation can be found online at 1731 http://github.com/davidmcgrew/hash-sigs/. 1733 Appendix E. Test Cases 1735 This section provides test cases that can be used to verify or debug 1736 an implementation. This data is formatted with the name of the 1737 elements on the left, and the value of the elements on the right, in 1738 hexadecimal. The concatenation of all of the values within a public 1739 key or signature produces that public key or signature, and values 1740 that do not fit within a single line are listed across successive 1741 lines. 1743 Test Case 1 Public Key 1745 -------------------------------------------- 1746 HSS public key 1747 levels 00000002 1748 -------------------------------------------- 1749 LMS type 00000005 # LM_SHA256_M32_H5 1750 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1751 I 61a5d57d37f5e46bfb7520806b07a1b8 1752 K 50650e3b31fe4a773ea29a07f09cf2ea 1753 30e579f0df58ef8e298da0434cb2b878 1754 -------------------------------------------- 1755 -------------------------------------------- 1757 Test Case 1 Message 1759 -------------------------------------------- 1760 Message 54686520706f77657273206e6f742064 |The powers not d| 1761 656c65676174656420746f2074686520 |elegated to the | 1762 556e6974656420537461746573206279 |United States by| 1763 2074686520436f6e737469747574696f | the Constitutio| 1764 6e2c206e6f722070726f686962697465 |n, nor prohibite| 1765 6420627920697420746f207468652053 |d by it to the S| 1766 74617465732c20617265207265736572 |tates, are reser| 1767 76656420746f20746865205374617465 |ved to the State| 1768 7320726573706563746976656c792c20 |s respectively, | 1769 6f7220746f207468652070656f706c65 |or to the people| 1770 2e0a |..| 1771 -------------------------------------------- 1773 Test Case 1 Signature 1775 -------------------------------------------- 1776 HSS signature 1777 Nspk 00000001 1778 sig[0]: 1779 -------------------------------------------- 1780 LMS signature 1781 q 00000005 1782 -------------------------------------------- 1783 LMOTS signature 1784 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1785 C d32b56671d7eb98833c49b433c272586 1786 bc4a1c8a8970528ffa04b966f9426eb9 1787 y[0] 965a25bfd37f196b9073f3d4a232feb6 1788 9128ec45146f86292f9dff9610a7bf95 1789 y[1] a64c7f60f6261a62043f86c70324b770 1790 7f5b4a8a6e19c114c7be866d488778a0 1792 y[2] e05fd5c6509a6e61d559cf1a77a970de 1793 927d60c70d3de31a7fa0100994e162a2 1794 y[3] 582e8ff1b10cd99d4e8e413ef469559f 1795 7d7ed12c838342f9b9c96b83a4943d16 1796 y[4] 81d84b15357ff48ca579f19f5e71f184 1797 66f2bbef4bf660c2518eb20de2f66e3b 1798 y[5] 14784269d7d876f5d35d3fbfc7039a46 1799 2c716bb9f6891a7f41ad133e9e1f6d95 1800 y[6] 60b960e7777c52f060492f2d7c660e14 1801 71e07e72655562035abc9a701b473ecb 1802 y[7] c3943c6b9c4f2405a3cb8bf8a691ca51 1803 d3f6ad2f428bab6f3a30f55dd9625563 1804 y[8] f0a75ee390e385e3ae0b906961ecf41a 1805 e073a0590c2eb6204f44831c26dd768c 1806 y[9] 35b167b28ce8dc988a3748255230cef9 1807 9ebf14e730632f27414489808afab1d1 1808 y[10] e783ed04516de012498682212b078105 1809 79b250365941bcc98142da13609e9768 1810 y[11] aaf65de7620dabec29eb82a17fde35af 1811 15ad238c73f81bdb8dec2fc0e7f93270 1812 y[12] 1099762b37f43c4a3c20010a3d72e2f6 1813 06be108d310e639f09ce7286800d9ef8 1814 y[13] a1a40281cc5a7ea98d2adc7c7400c2fe 1815 5a101552df4e3cccfd0cbf2ddf5dc677 1816 y[14] 9cbbc68fee0c3efe4ec22b83a2caa3e4 1817 8e0809a0a750b73ccdcf3c79e6580c15 1818 y[15] 4f8a58f7f24335eec5c5eb5e0cf01dcf 1819 4439424095fceb077f66ded5bec73b27 1820 y[16] c5b9f64a2a9af2f07c05e99e5cf80f00 1821 252e39db32f6c19674f190c9fbc506d8 1822 y[17] 26857713afd2ca6bb85cd8c107347552 1823 f30575a5417816ab4db3f603f2df56fb 1824 y[18] c413e7d0acd8bdd81352b2471fc1bc4f 1825 1ef296fea1220403466b1afe78b94f7e 1826 y[19] cf7cc62fb92be14f18c2192384ebceaf 1827 8801afdf947f698ce9c6ceb696ed70e9 1828 y[20] e87b0144417e8d7baf25eb5f70f09f01 1829 6fc925b4db048ab8d8cb2a661ce3b57a 1830 y[21] da67571f5dd546fc22cb1f97e0ebd1a6 1831 5926b1234fd04f171cf469c76b884cf3 1832 y[22] 115cce6f792cc84e36da58960c5f1d76 1833 0f32c12faef477e94c92eb75625b6a37 1834 y[23] 1efc72d60ca5e908b3a7dd69fef02491 1835 50e3eebdfed39cbdc3ce9704882a2072 1836 y[24] c75e13527b7a581a556168783dc1e975 1837 45e31865ddc46b3c957835da252bb732 1838 y[25] 8d3ee2062445dfb85ef8c35f8e1f3371 1839 af34023cef626e0af1e0bc017351aae2 1841 y[26] ab8f5c612ead0b729a1d059d02bfe18e 1842 fa971b7300e882360a93b025ff97e9e0 1843 y[27] eec0f3f3f13039a17f88b0cf808f4884 1844 31606cb13f9241f40f44e537d302c64a 1845 y[28] 4f1f4ab949b9feefadcb71ab50ef27d6 1846 d6ca8510f150c85fb525bf25703df720 1847 y[29] 9b6066f09c37280d59128d2f0f637c7d 1848 7d7fad4ed1c1ea04e628d221e3d8db77 1849 y[30] b7c878c9411cafc5071a34a00f4cf077 1850 38912753dfce48f07576f0d4f94f42c6 1851 y[31] d76f7ce973e9367095ba7e9a3649b7f4 1852 61d9f9ac1332a4d1044c96aefee67676 1853 y[32] 401b64457c54d65fef6500c59cdfb69a 1854 f7b6dddfcb0f086278dd8ad0686078df 1855 y[33] b0f3f79cd893d314168648499898fbc0 1856 ced5f95b74e8ff14d735cdea968bee74 1857 -------------------------------------------- 1858 LMS type 00000005 # LM_SHA256_M32_H5 1859 path[0] d8b8112f9200a5e50c4a262165bd342c 1860 d800b8496810bc716277435ac376728d 1861 path[1] 129ac6eda839a6f357b5a04387c5ce97 1862 382a78f2a4372917eefcbf93f63bb591 1863 path[2] 12f5dbe400bd49e4501e859f885bf073 1864 6e90a509b30a26bfac8c17b5991c157e 1865 path[3] b5971115aa39efd8d564a6b90282c316 1866 8af2d30ef89d51bf14654510a12b8a14 1867 path[4] 4cca1848cf7da59cc2b3d9d0692dd2a2 1868 0ba3863480e25b1b85ee860c62bf5136 1869 -------------------------------------------- 1870 LMS public key 1871 LMS type 00000005 # LM_SHA256_M32_H5 1872 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1873 I d2f14ff6346af964569f7d6cb880a1b6 1874 K 6c5004917da6eafe4d9ef6c6407b3db0 1875 e5485b122d9ebe15cda93cfec582d7ab 1876 -------------------------------------------- 1877 final_signature: 1878 -------------------------------------------- 1879 LMS signature 1880 q 0000000a 1881 -------------------------------------------- 1882 LMOTS signature 1883 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 1884 C 0703c491e7558b35011ece3592eaa5da 1885 4d918786771233e8353bc4f62323185c 1886 y[0] 95cae05b899e35dffd71705470620998 1887 8ebfdf6e37960bb5c38d7657e8bffeef 1888 y[1] 9bc042da4b4525650485c66d0ce19b31 1889 7587c6ba4bffcc428e25d08931e72dfb 1890 y[2] 6a120c5612344258b85efdb7db1db9e1 1891 865a73caf96557eb39ed3e3f426933ac 1892 y[3] 9eeddb03a1d2374af7bf771855774562 1893 37f9de2d60113c23f846df26fa942008 1894 y[4] a698994c0827d90e86d43e0df7f4bfcd 1895 b09b86a373b98288b7094ad81a0185ac 1896 y[5] 100e4f2c5fc38c003c1ab6fea479eb2f 1897 5ebe48f584d7159b8ada03586e65ad9c 1898 y[6] 969f6aecbfe44cf356888a7b15a3ff07 1899 4f771760b26f9c04884ee1faa329fbf4 1900 y[7] e61af23aee7fa5d4d9a5dfcf43c4c26c 1901 e8aea2ce8a2990d7ba7b57108b47dabf 1902 y[8] beadb2b25b3cacc1ac0cef346cbb90fb 1903 044beee4fac2603a442bdf7e507243b7 1904 y[9] 319c9944b1586e899d431c7f91bcccc8 1905 690dbf59b28386b2315f3d36ef2eaa3c 1906 y[10] f30b2b51f48b71b003dfb08249484201 1907 043f65f5a3ef6bbd61ddfee81aca9ce6 1908 y[11] 0081262a00000480dcbc9a3da6fbef5c 1909 1c0a55e48a0e729f9184fcb1407c3152 1910 y[12] 9db268f6fe50032a363c9801306837fa 1911 fabdf957fd97eafc80dbd165e435d0e2 1912 y[13] dfd836a28b354023924b6fb7e48bc0b3 1913 ed95eea64c2d402f4d734c8dc26f3ac5 1914 y[14] 91825daef01eae3c38e3328d00a77dc6 1915 57034f287ccb0f0e1c9a7cbdc828f627 1916 y[15] 205e4737b84b58376551d44c12c3c215 1917 c812a0970789c83de51d6ad787271963 1918 y[16] 327f0a5fbb6b5907dec02c9a90934af5 1919 a1c63b72c82653605d1dcce51596b3c2 1920 y[17] b45696689f2eb382007497557692caac 1921 4d57b5de9f5569bc2ad0137fd47fb47e 1922 y[18] 664fcb6db4971f5b3e07aceda9ac130e 1923 9f38182de994cff192ec0e82fd6d4cb7 1924 y[19] f3fe00812589b7a7ce51544045643301 1925 6b84a59bec6619a1c6c0b37dd1450ed4 1926 y[20] f2d8b584410ceda8025f5d2d8dd0d217 1927 6fc1cf2cc06fa8c82bed4d944e71339e 1928 y[21] ce780fd025bd41ec34ebff9d4270a322 1929 4e019fcb444474d482fd2dbe75efb203 1930 y[22] 89cc10cd600abb54c47ede93e08c114e 1931 db04117d714dc1d525e11bed8756192f 1932 y[23] 929d15462b939ff3f52f2252da2ed64d 1933 8fae88818b1efa2c7b08c8794fb1b214 1934 y[24] aa233db3162833141ea4383f1a6f120b 1935 e1db82ce3630b3429114463157a64e91 1936 y[25] 234d475e2f79cbf05e4db6a9407d72c6 1937 bff7d1198b5c4d6aad2831db61274993 1938 y[26] 715a0182c7dc8089e32c8531deed4f74 1939 31c07c02195eba2ef91efb5613c37af7 1940 y[27] ae0c066babc69369700e1dd26eddc0d2 1941 16c781d56e4ce47e3303fa73007ff7b9 1942 y[28] 49ef23be2aa4dbf25206fe45c20dd888 1943 395b2526391a724996a44156beac8082 1944 y[29] 12858792bf8e74cba49dee5e8812e019 1945 da87454bff9e847ed83db07af3137430 1946 y[30] 82f880a278f682c2bd0ad6887cb59f65 1947 2e155987d61bbf6a88d36ee93b6072e6 1948 y[31] 656d9ccbaae3d655852e38deb3a2dcf8 1949 058dc9fb6f2ab3d3b3539eb77b248a66 1950 y[32] 1091d05eb6e2f297774fe6053598457c 1951 c61908318de4b826f0fc86d4bb117d33 1952 y[33] e865aa805009cc2918d9c2f840c4da43 1953 a703ad9f5b5806163d7161696b5a0adc 1954 -------------------------------------------- 1955 LMS type 00000005 # LM_SHA256_M32_H5 1956 path[0] d5c0d1bebb06048ed6fe2ef2c6cef305 1957 b3ed633941ebc8b3bec9738754cddd60 1958 path[1] e1920ada52f43d055b5031cee6192520 1959 d6a5115514851ce7fd448d4a39fae2ab 1960 path[2] 2335b525f484e9b40d6a4a969394843b 1961 dcf6d14c48e8015e08ab92662c05c6e9 1962 path[3] f90b65a7a6201689999f32bfd368e5e3 1963 ec9cb70ac7b8399003f175c40885081a 1964 path[4] 09ab3034911fe125631051df0408b394 1965 6b0bde790911e8978ba07dd56c73e7ee 1967 Authors' Addresses 1969 David McGrew 1970 Cisco Systems 1971 13600 Dulles Technology Drive 1972 Herndon, VA 20171 1973 USA 1975 Email: mcgrew@cisco.com 1977 Michael Curcio 1978 Cisco Systems 1979 7025-2 Kit Creek Road 1980 Research Triangle Park, NC 27709-4987 1981 USA 1983 Email: micurcio@cisco.com 1984 Scott Fluhrer 1985 Cisco Systems 1986 170 West Tasman Drive 1987 San Jose, CA 1988 USA 1990 Email: sfluhrer@cisco.com