idnits 2.17.1 draft-mcgrew-hash-sigs-02.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 -- The document date (July 4, 2014) is 3584 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 1907 -- Looks like a reference, but probably isn't: '1' on line 1907 -- Looks like a reference, but probably isn't: '20' on line 829 -- Looks like a reference, but probably isn't: '32' on line 873 -- Looks like a reference, but probably isn't: '64' on line 879 -- Looks like a reference, but probably isn't: '265' on line 547 -- Looks like a reference, but probably isn't: '133' on line 549 -- Looks like a reference, but probably isn't: '67' on line 551 -- Looks like a reference, but probably isn't: '34' on line 553 -- Looks like a reference, but probably isn't: '264' on line 630 -- Looks like a reference, but probably isn't: '2' on line 786 -- Looks like a reference, but probably isn't: '30' on line 831 -- Looks like a reference, but probably isn't: '49' on line 833 -- Looks like a reference, but probably isn't: '75' on line 835 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 16 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group D. McGrew 3 Internet-Draft M. Curcio 4 Intended status: Informational Cisco Systems 5 Expires: January 5, 2015 July 4, 2014 7 Hash-Based Signatures 8 draft-mcgrew-hash-sigs-02 10 Abstract 12 This note describes a digital signature system based on cryptographic 13 hash functions, following the seminal work in this area. It 14 specifies a one-time signature scheme based on the work of Lamport, 15 Diffie, Winternitz, and Merkle (LDWM), and a general signature 16 scheme, Merkle Tree Signatures (MTS). These systems provide 17 asymmetric authentication without using large integer mathematics and 18 can achieve a high security level. They are suitable for compact 19 implementations, are relatively simple to implement, and naturally 20 resist side-channel attacks. Unlike most other signature systems, 21 hash-based signatures would still be secure even if it proves 22 feasible for an attacker to build a quantum computer. 24 Status of this Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on January 5, 2015. 41 Copyright Notice 43 Copyright (c) 2014 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 1.1. Conventions Used In This Document . . . . . . . . . . . . 5 61 2. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 62 2.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 6 63 2.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 6 64 2.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 6 65 2.2. Functions . . . . . . . . . . . . . . . . . . . . . . . . 7 67 3. LDWM One-Time Signatures . . . . . . . . . . . . . . . . . . . 9 68 3.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . . 9 69 3.2. Hashing Functions . . . . . . . . . . . . . . . . . . . . 9 70 3.3. Signature Methods . . . . . . . . . . . . . . . . . . . . 10 71 3.4. Private Key . . . . . . . . . . . . . . . . . . . . . . . 10 72 3.5. Public Key . . . . . . . . . . . . . . . . . . . . . . . . 11 73 3.6. Checksum . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 3.7. Signature Generation . . . . . . . . . . . . . . . . . . . 12 75 3.8. Signature Verification . . . . . . . . . . . . . . . . . . 13 76 3.9. Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 13 77 3.10. Formats . . . . . . . . . . . . . . . . . . . . . . . . . 13 79 4. Merkle Tree Signatures . . . . . . . . . . . . . . . . . . . . 17 80 4.1. Private Key . . . . . . . . . . . . . . . . . . . . . . . 17 81 4.2. MTS Public Key . . . . . . . . . . . . . . . . . . . . . . 17 82 4.3. MTS Signature . . . . . . . . . . . . . . . . . . . . . . 18 83 4.3.1. MTS Signature Generation . . . . . . . . . . . . . . . 19 84 4.4. MTS Signature Verification . . . . . . . . . . . . . . . . 19 85 4.5. MTS Formats . . . . . . . . . . . . . . . . . . . . . . . 20 87 5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 23 89 6. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 91 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 93 8. Security Considerations . . . . . . . . . . . . . . . . . . . 28 94 8.1. Security of LDWM Checksum . . . . . . . . . . . . . . . . 29 95 8.2. Security Conjectures . . . . . . . . . . . . . . . . . . . 29 96 8.3. Post-Quantum Security . . . . . . . . . . . . . . . . . . 30 98 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31 100 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32 101 10.1. Normative References . . . . . . . . . . . . . . . . . . . 32 102 10.2. Informative References . . . . . . . . . . . . . . . . . . 32 104 Appendix A. LDWM Parameter Options . . . . . . . . . . . . . . . 33 106 Appendix B. Example Data for Testing . . . . . . . . . . . . . . 35 107 B.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . . 35 108 B.2. Key Generation . . . . . . . . . . . . . . . . . . . . . . 35 109 B.3. Signature Generation . . . . . . . . . . . . . . . . . . . 41 110 B.4. Signature Verification . . . . . . . . . . . . . . . . . . 45 111 B.5. Intermediate Calculation Values . . . . . . . . . . . . . 45 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51 115 1. Introduction 117 One-time signature systems, and general purpose signature systems 118 built out of one-time signature systems, have been known since 1979 119 [Merkle79], were well studied in the 1990s, and have benefited from 120 renewed development in the last decade. The characteristics of these 121 signature systems are small private and public keys and fast 122 signature generation and verification, but large signatures and 123 relatively slow key generation. In recent years there has been 124 interest in these systems because of their post-quantum security (see 125 Section 8.3) and their suitability for compact implementations. 127 This note describes the original Lamport-Diffie-Winternitz-Merkle 128 (LDWM) one-time signature system (following Merkle 1979 but also 129 using a technique from Merkle's later work [C:Merkle87][C: 130 Merkle89a][C:Merkle89b]) and Merkle tree signature system (following 131 Merkle 1979) with enough specificity to ensure interoperability 132 between implementations. 134 A signature system provides asymmetric message authentication. The 135 key generation algorithm produces a public/private key pair. A 136 message is signed by a private key, producing a signature, and a 137 message/signature pair can be verified by a public key. A One-Time 138 Signature (OTS) system can be used to sign exactly one message 139 securely. A general signature system can be used to sign multiple 140 messages. The Merkle Tree Signatures (MTS) is a general signature 141 system that uses an OTS system as a component. In principle the MTS 142 can be used with any OTS system, but in this note we describe its use 143 with the LDWM system. 145 This note is structured as follows. Notation is introduced in 146 Section 2. The LDWM signature system is described in Section 3, and 147 the Merkle tree signature system is described in Section 4. 148 Sufficient detail is provided to ensure interoperability. Appendix B 149 describes test considerations and contains test cases that can be 150 used to validate an implementation. The IANA registry for these 151 signature systems is described in Section 7. Security considerations 152 are presented in Section 8. 154 1.1. Conventions Used In This Document 156 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 157 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 158 document are to be interpreted as described in [RFC2119]. 160 2. Notation 162 2.1. Data Types 164 Bytes and byte strings are the fundamental data types. A single byte 165 is denoted as a pair of hexadecimal digits with a leading "0x". A 166 byte string is an ordered sequence of zero or more bytes and is 167 denoted as an ordered sequence of hexadecimal characters with a 168 leading "0x". For example, 0xe534f0 is a byte string with a length 169 of three. An array of byte strings is an ordered set, indexed 170 starting at zero, in which all strings have the same length. 172 2.1.1. Operators 174 When a and b are real numbers, mathematical operators are defined as 175 follows: 177 ^ : a ^ b denotes the result of a raised to the power of b 179 * : a * b denotes the product of a multiplied by b 181 / : a / b denotes the quotient of a divided by b 183 % : a % b denotes the remainder of the integer division of a by b 185 + : a + b denotes the sum of a and b 187 - : a - b denotes the difference of a and b 189 The standard order of operations is used when evaluating arithmetic 190 expressions. 192 If A and B are bytes, then A AND B denotes the bitwise logical and 193 operation. 195 When B is a byte and i is an integer, then B >> i denotes the logical 196 right-shift operation. Similarly, B << i denotes the logical left- 197 shift operation. 199 If S and T are byte strings, then S || T denotes the concatenation of 200 S and T. 202 The i^th byte string in an array A is denoted as A[i]. 204 2.1.2. Strings of w-bit elements 206 If S is a byte string, then byte(S, i) denotes its i^th byte, where 207 byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes 208 the range of bytes from the i^th to the j^th byte, inclusive. For 209 example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 210 2) is 0x0406. 212 A byte string can be considered to be a string of w-bit unsigned 213 integers; the correspondence is defined by the function coef(S, i, w) 214 as follows: 216 If S is a string, i is a positive integer, and w is a member of the 217 set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S 218 is interpreted as a sequence of w-bit values. That is, 220 coef(S, i, w) = (2^w - 1) AND 221 ( byte(S, floor(i * w / 8)) >> 222 (8 - (w * (i % (8 / w)) + w)) ) 224 For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and 225 coef(S, 0, 4) is 1. 227 S (represented as bits) 228 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 229 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 230 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 231 ^ 232 | 233 coef(S, 7, 1) 235 S (represented as four-bit values) 236 +-----------+-----------+-----------+-----------+ 237 | 1 | 2 | 3 | 4 | 238 +-----------+-----------+-----------+-----------+ 239 ^ 240 | 241 coef(S, 0, 4) 243 The return value of coef is an unsigned integer. If i is larger than 244 the number of w-bit values in S, then coef(S, i, w) is undefined, and 245 an attempt to compute that value should raise an error. 247 2.2. Functions 249 If r is a non-negative real number, then we define the following 250 functions: 252 ceil(r) : returns the smallest integer larger than r 253 floor(r) : returns the largest integer smaller than r 255 lg(r) : returns the base-2 logarithm of r 257 When F is a function that takes r-byte strings as input and returns 258 r-byte strings as output, we denote the repeated applications of F 259 with itself a non-negative, integral number of times i as F^i. 261 Thus for any m-byte string x , 263 F^i(x) = / F( F^(i-1)(x) ) for i > 0 264 \ x for i = 0. 266 For example, F^2(x) = F(F(x)). 268 3. LDWM One-Time Signatures 270 This section defines LDWM signatures. The signature is used to 271 validate the authenticity of a message by associating a secret 272 private key with a shared public key. These are one-time signatures; 273 each private key MUST be used only one time to sign any given 274 message. 276 As part of the signing process, a digest of the original message is 277 computed using the collision-resistant hash function H (see 278 Section 3.2), and the resulting digest is signed. 280 3.1. Parameters 282 The signature system uses the parameters m, n, and w; they are all 283 positive integers. The algorithm description also uses the values p 284 and ls. These parameters are summarized as follows: 286 m : the length in bytes of each element of an LDWM signature 288 n : the length in bytes of the result of the hash function 290 w : the Winternitz parameter; it is a member of the set 291 { 1, 2, 4, 8 } 293 p : the number of m-byte string elements that make up the LDWM 294 signature 296 ls : the number of left-shift bits used in the checksum function C 297 (defined in Section 3.6). 299 The values of m and n are determined by the functions selected for 300 use as part of the LDWM algorithm. They are chosen to ensure an 301 appropriate level of security. The parameter w can be chosen to set 302 the number of bytes in the signature; it has little effect on 303 security. Note however, that there is a larger computational cost to 304 generate and verify a shorter signature. The values of p and ls are 305 dependent on the choices of the parameters n and w, as described in 306 Appendix A. A table illustrating various combinations of n, w, p, 307 and ls is provided in Table 4. 309 3.2. Hashing Functions 311 The LDWM algorithm uses a collision-resistant hash function H and a 312 one way (preimage resistant) function F. H accepts byte strings of 313 any length, and returns an n-byte string. F has m-byte inputs and 314 m-byte outputs. 316 3.3. Signature Methods 318 To fully describe a LDWM signature method, the parameters m, n, and 319 w, as well as the functions H and F MUST be specified. This section 320 defines several LDWM signature systems, each of which is identified 321 by a name. Values for p and ls are provided as a convenience. 323 +--------------------+--------+-----------+----+----+---+-----+----+ 324 | Name | H | F | m | n | w | p | ls | 325 +--------------------+--------+-----------+----+----+---+-----+----+ 326 | LDWM_SHA512_M64_W1 | SHA512 | SHA512 | 32 | 32 | 1 | 265 | 7 | 327 | | | | | | | | | 328 | LDWM_SHA512_M64_W2 | SHA512 | SHA512 | 32 | 32 | 2 | 133 | 6 | 329 | | | | | | | | | 330 | LDWM_SHA512_M64_W4 | SHA512 | SHA512 | 32 | 32 | 4 | 67 | 4 | 331 | | | | | | | | | 332 | LDWM_SHA512_M64_W8 | SHA512 | SHA512 | 32 | 32 | 8 | 34 | 0 | 333 | | | | | | | | | 334 | LDWM_SHA256_M32_W1 | SHA256 | SHA256 | 32 | 32 | 1 | 265 | 7 | 335 | | | | | | | | | 336 | LDWM_SHA256_M32_W2 | SHA256 | SHA256 | 32 | 32 | 2 | 133 | 6 | 337 | | | | | | | | | 338 | LDWM_SHA256_M32_W4 | SHA256 | SHA256 | 32 | 32 | 4 | 67 | 4 | 339 | | | | | | | | | 340 | LDWM_SHA256_M32_W8 | SHA256 | SHA256 | 32 | 32 | 8 | 34 | 0 | 341 | | | | | | | | | 342 | LDWM_SHA256_M20_W1 | SHA256 | SHA256-20 | 20 | 32 | 1 | 265 | 7 | 343 | | | | | | | | | 344 | LDWM_SHA256_M20_W2 | SHA256 | SHA256-20 | 20 | 32 | 2 | 133 | 6 | 345 | | | | | | | | | 346 | LDWM_SHA256_M20_W4 | SHA256 | SHA256-20 | 20 | 32 | 4 | 67 | 4 | 347 | | | | | | | | | 348 | LDWM_SHA256_M20_W8 | SHA256 | SHA256-20 | 20 | 32 | 8 | 34 | 0 | 349 +--------------------+--------+-----------+----+----+---+-----+----+ 351 Table 1 353 Here SHA512 and SHA256 denotes the NIST standard hash functions 354 [FIPS180]. SHA256-20 denotes the SHA256 hash function with its final 355 output truncated to return the leftmost 20 bytes. 357 3.4. Private Key 359 The LDWM private key is an array of size p containing m-byte strings. 360 Let x denote the private key. This private key must be used to sign 361 one and only one message. It must therefore be unique from all other 362 private keys. The following algorithm shows pseudocode for 363 generating x. 365 Algorithm 0: Generating a Private Key 367 for ( i = 0; i < p; i = i + 1 ) { 368 set x[i] to a uniformly random m-byte string 369 } 370 return x 372 An implementation MAY use a pseudorandom method to compute x[i], as 373 suggested in [Merkle79], page 46. The details of the pseudorandom 374 method do not affect interoperability, but the cryptographic strength 375 MUST match that of the LDWM algorithm. 377 3.5. Public Key 379 The LDWM public key is generated from the private key by applying the 380 function F^(2^w - 1) to each individual element of x, then hashing 381 all of the resulting values. The following algorithm shows 382 pseudocode for generating the public key, where the array x is the 383 private key. 385 Algorithm 1: Generating a Public Key From a Private Key 387 e = 2^w - 1 388 for ( i = 0; i < p; i = i + 1 ) { 389 y[i] = F^e(x[i]) 390 } 391 return H(y[0] || y[1] || ... || y[p-1]) 393 3.6. Checksum 395 A checksum is used to ensure that any forgery attempt that 396 manipulates the elements of an existing signature will be detected. 397 The security property that it provides is detailed in Section 8. 399 The checksum value is calculated using a non-negative integer, sum, 400 whose width is sized an integer number of w-bit fields such that it 401 is capable of holding the difference of the total possible number of 402 applications of the function F as defined in the signing algorithm of 403 Section 3.7 and the total actual number. In the worst case (i.e. the 404 actual number of times F is iteratively applied is 0), the sum is 405 (2^w - 1) * ceil(8*n/w). Thus for the purposes of this document, 406 which describes signature methods based on H = SHA256 (n = 32 bytes) 407 and w = { 1, 2, 4, 8 }, let sum be a 16-bit non-negative integer for 408 all combinations of n and w. The calculation uses the parameter ls 409 defined in Section 3.1 and calculated in Appendix A, which indicates 410 the number of bits used in the left-shift operation. The checksum 411 function C is defined as follows, where S denotes the byte string 412 that is input to that function. 414 Algorithm 2: Checksum Calculation 416 sum = 0 417 for ( i = 0; i < u; i = i + 1 ) { 418 sum = sum + (2^w - 1) - coef(S, i, w) 419 } 420 return (sum << ls) 422 Because of the left-shift operation, the rightmost bits of the result 423 of C will often be zeros. Due to the value of p, these bits will not 424 be used during signature generation or verification. 426 Implementation Note: Based on the previous fact, an implementation 427 MAY choose to optimize the width of sum to (v * w) bits and set ls 428 to 0. The rationale for this is given that (2^w - 1) * 429 ceil(8*n/w) is the maximum value of sum and the value of (2^w - 1) 430 is represented by w bits, the result of adding u w-bit numbers, 431 where u = ceil(8*n/w), requires at most (ceil(lg(u)) + w) bits. 432 Dividing by w and taking the next largest integer gives the total 433 required number of w-bit fields and gives (ceil(lg(u)) / w) + 1, 434 or v. Thus sum requires a minimum width of (v * w) bits and no 435 left-shift operation is performed. 437 3.7. Signature Generation 439 The LDWM signature is generated by using H to compute the hash of the 440 message, concatenating the checksum of the hash to the hash itself, 441 then considering the resulting value as a sequence of w-bit values, 442 and using using each of the the w-bit values to determine the number 443 of times to apply the function F to the corresponding element of the 444 private key. The outputs of the function F are concatenated together 445 and returned as the signature. The pseudocode for this procedure is 446 shown below. 448 Algorithm 3: Generating a Signature From a Private Key and a Message 450 V = ( H(message) || C(H(message)) ) 451 for ( i = 0; i < p; i = i + 1 ) { 452 a = coef(V, i, w) 453 y[i] = F^a(x[i]) 454 } 455 return (y[0] || y[1] || ... || y[p-1]) 457 Note that this algorithm results in a signature whose elements are 458 intermediate values of the elements computed by the public key 459 algorithm in Section 3.5. 461 The signature should be provided by the signer to the verifier, along 462 with the message and the public key. 464 3.8. Signature Verification 466 In order to verify a message with its signature (an array of m-byte 467 strings, denoted as y), the receiver must "complete" the series of 468 applications of F, using the w-bit values of the message hash and its 469 checksum. This computation should result in a value that matches the 470 provided public key. 472 Algorithm 4: Verifying a Signature and Message Using a Public Key 474 V = ( H(message) || C(H(message)) ) 475 for ( i = 0; i < p; i = i + 1 ) { 476 a = (2^w - 1) - coef(V, i, w) 477 z[i] = F^a(y'[i]) 478 } 479 if public key is equal to H(z[0] || z[1] || ... || z[p-1]) 480 return 1 (message signature is valid) 481 else 482 return 0 (message signature is invalid) 484 3.9. Notes 486 A future version of this specification may define a method for 487 computing the signature of a very short message in which the hash is 488 not applied to the message during the signature computation. That 489 would allow the signatures to have reduced size. 491 3.10. Formats 493 The signature and public key formats are formally defined using XDR 494 [RFC4506] in order to provide an unambiguous, machine readable 495 definition. For clarity, we also include a private key format as 496 well, though consistency is not needed for interoperability and an 497 implementation MAY use any private key format. Though XDR is used, 498 these formats are simple and easy to parse without any special tools. 499 To avoid the need to convert to and from network / host byte order, 500 the enumeration values are all palindromes. The definitions are as 501 follows: 503 /* 504 * ots_algorithm_type identifies a particular signature algorithm 505 */ 506 enum ots_algorithm_type { 507 ots_reserved = 0, 508 ldwm_sha256_m20_w1 = 0x01000001, 509 ldwm_sha256_m20_w2 = 0x02000002, 510 ldwm_sha256_m20_w4 = 0x03000003, 511 ldwm_sha256_m20_w8 = 0x04000004, 512 ldwm_sha256_m32_w1 = 0x05000005, 513 ldwm_sha256_m32_w2 = 0x06000006, 514 ldwm_sha256_m32_w4 = 0x07000007, 515 ldwm_sha256_m32_w8 = 0x08000008, 516 ldwm_sha512_m64_w1 = 0x09000009, 517 ldwm_sha512_m64_w2 = 0x0a00000a, 518 ldwm_sha512_m64_w4 = 0x0b00000b, 519 ldwm_sha512_m64_w8 = 0x0c00000c 520 }; 522 /* 523 * byte string 524 */ 525 typedef opaque bytestring20[20]; 526 typedef opaque bytestring32[32]; 527 typedef opaque bytestring64[64]; 529 union ots_signature switch (ots_algorithm_type type) { 530 case ldwm_sha256_m20_w1: 531 bytestring20 y_m20_p265[265]; 532 case ldwm_sha256_m20_w2: 533 bytestring20 y_m20_p133[133]; 534 case ldwm_sha256_m20_w4: 535 bytestring20 y_m20_p67[67]; 536 case ldwm_sha256_m20_w8: 537 bytestring20 y_m20_p34[34]; 538 case ldwm_sha256_m32_w1: 539 bytestring32 y_m32_p265[265]; 540 case ldwm_sha256_m32_w2: 541 bytestring32 y_m3_p133[133]; 542 case ldwm_sha256_m32_w4: 543 bytestring32 y_m32_y_p67[67]; 544 case ldwm_sha256_m32_w8: 545 bytestring32 y_m32_p34[34]; 546 case ldwm_sha512_m64_w1: 547 bytestring64 y_m64_p265[265]; 548 case ldwm_sha512_m64_w2: 549 bytestring64 y_m64_p133[133]; 550 case ldwm_sha512_m64_w4: 551 bytestring64 y_m64_y_p67[67]; 552 case ldwm_sha512_m64_w8: 553 bytestring64 y_m64_p34[34]; 554 default: 555 void; /* error condition */ 556 }; 557 union ots_public_key switch (ots_algorithm_type type) { 558 case ldwm_sha256_m20_w1: 559 case ldwm_sha256_m20_w2: 560 case ldwm_sha256_m20_w4: 561 case ldwm_sha256_m20_w8: 562 case ldwm_sha256_m32_w1: 563 case ldwm_sha256_m32_w2: 564 case ldwm_sha256_m32_w4: 565 case ldwm_sha256_m32_w8: 566 bytestring32 y32; 567 case ldwm_sha512_m64_w1: 568 case ldwm_sha512_m64_w2: 569 case ldwm_sha512_m64_w4: 570 case ldwm_sha512_m64_w8: 571 bytestring64 y64; 572 default: 573 void; /* error condition */ 574 }; 576 union ots_private_key switch (ots_algorithm_type type) { 577 case ldwm_sha256_m20_w1: 578 case ldwm_sha256_m20_w2: 579 case ldwm_sha256_m20_w4: 580 case ldwm_sha256_m20_w8: 581 bytestring20 x20; 582 case ldwm_sha256_m32_w1: 583 case ldwm_sha256_m32_w2: 584 case ldwm_sha256_m32_w4: 585 case ldwm_sha256_m32_w8: 586 bytestring32 x32; 587 case ldwm_sha512_m64_w1: 588 case ldwm_sha512_m64_w2: 589 case ldwm_sha512_m64_w4: 590 case ldwm_sha512_m64_w8: 591 bytestring64 y64; 592 default: 593 void; /* error condition */ 594 }; 596 Though the data formats are formally defined by XDR, we diagram the 597 format as well as a convenience to the reader. An example of the 598 format of an ldwm_signature is illustrated below, for 599 ldwm_sha256_m32_w1. An ots_signature consists of a 32-bit unsigned 600 integer that indicates the ots_algorithm_type, followed by other 601 data, whose format depends only on the ots_algorithm_type. In the 602 case of LDWM, the data is an array of equal-length byte strings. The 603 number of bytes in each byte string, and the number of elements in 604 the array, are determined by the ots_algorithm_type field. In the 605 case of ldwm_sha256_m32_w1, the array has 265 elements, each of which 606 is a 32-byte string. The XDR array y_m32_p265 denotes the array y as 607 used in the algorithm descriptions above, using the parameters of 608 m=32 and p=265 for ldwm_sha256_m32_w1. 610 A verifier MUST check the ots_algorithm_type field, and a 611 verification operation on a signature with an unknown 612 ldwm_algorithm_type MUST return FAIL. 614 +---------------------------------+ 615 | ots_algorithm_type | 616 +---------------------------------+ 617 | | 618 | y_m32_p265[0] | 619 | | 620 +---------------------------------+ 621 | | 622 | y_m32_p265[1] | 623 | | 624 +---------------------------------+ 625 | | 626 ~ .... ~ 627 | | 628 +---------------------------------+ 629 | | 630 | y_m32_p265[264] | 631 | | 632 +---------------------------------+ 634 4. Merkle Tree Signatures 636 Merkle Tree Signatures (MTS) are a method for signing a potentially 637 large but fixed number of messages. An MTS system uses two 638 cryptographic components: a one-time signature method and a 639 collision-resistant hash function. Each MTS public/private key pair 640 is associated with a perfect k-ary tree, each node of which contains 641 an n-byte value. Each leaf of the tree contains the value of the 642 public key of an LDWM public/private key pair. The value contained 643 by the root of the tree is the MTS public key. Each interior node is 644 computed by applying the hash function to the concatenation of the 645 values of its children nodes. 647 An MTS system has the following parameters: 649 k : the number of children nodes of an interior node, 651 h : the height (number of levels - 1) in the tree, and 653 n : the number of bytes associated with each node. 655 There are k^h leaves in the tree. 657 4.1. Private Key 659 An MTS private key consists of k^h one-time signature private keys 660 and the leaf number of the next LDWM private key that has not yet 661 been used. The leaf number is initialized to zero when the MTS 662 private key is created. 664 An MTS private key MAY be generated pseudorandomly from a secret 665 value, in which case the secret value MUST be at least n bytes long, 666 be uniformly random, and MUST NOT be used for any other purpose than 667 the generation of the MTS private key. The details of how this 668 process is done do not affect interoperability; that is, the public 669 key verification operation is independent of these details. 671 4.2. MTS Public Key 673 An MTS public key is defined as follows, where we denote the public 674 key associated with the i^th LDWM private key as ldwm_public_key(i). 676 The MTS public key can be computed using the following algorithm or 677 any equivalent method. The algorithm uses a stack of hashes for data 678 and a separate stack of integers to keep track of the level of the 679 Merkle tree. 681 Algorithm 5: Generating an MTS Public Key From an MTS Private Key 683 for ( i = 0; i < num_ldwm_keys; i = i + k ) { 684 level = 0; 685 for ( j = 0; j < k; j = j + 1 ) { 686 push ldwm_public_key(i+j) onto the data stack 687 push level onto the integer stack 688 } 689 while ( height of the integer stack >= k ) { 690 if level of the top k elements on the integer stack are equal { 691 hash_init() 692 siblings = "" 693 repeat ( k ) { 694 siblings = (pop(data stack) || siblings) 695 level = pop(integer stack) 696 } 697 hash_update(siblings) 698 push hash_final() onto the data stack 699 push (level + 1) onto the integer stack 700 } 701 } 702 } 703 public_key = pop(data stack) 705 Note that this pseudocode expects, as was defined earlier, the Merkle 706 Tree to be perfect. That is, all h^k leaves of the tree have equal 707 depth. Also, neither stack ever contains more than h*(k-1)+1 708 elements. For typical parameters, it will hold roughly 20 32-byte 709 values. 711 4.3. MTS Signature 713 An MTS signature consists of 715 an LDWM signature, 717 a node number that identifies the leaf node associated with the 718 signature, and 720 an array of values that is associated with the path through the 721 tree from the leaf associated with the LDWM signature to the root. 723 The array of values contains contains the siblings of the nodes on 724 the path from the leaf to the root but does not contain the nodes on 725 the path itself. The array for a tree with branching number k and 726 height h will have (k-1)*h values. The first (k-1) values are the 727 siblings of the leaf, the next (k-1) values are the siblings of the 728 parent of the leaf, and so on. 730 4.3.1. MTS Signature Generation 732 To compute the MTS signature of a message with an MTS private key, 733 the signer first computes the LDWM signature of the message using the 734 leaf number of the next unused LDWM private key. Before releasing 735 the signature, the leaf number in the MTS private key MUST be 736 incremented to prevent the LDWM private key from being used again. 737 The node number in the signature is set to the leaf number of the MTS 738 private key that was used in the signature. 740 The array of node values MAY be computed in any way. There are many 741 potential time/storage tradeoffs. The fastest alternative is to 742 store all of the nodes of the tree and set the array in the signature 743 by copying them. The least storage intensive alternative is to 744 recompute all of the nodes for each signature. Note that the details 745 of this procedure are not important for interoperability; it is not 746 necessary to know any of these details in order to perform the 747 signature verification operation. 749 4.4. MTS Signature Verification 751 An MTS signature is verified by first using the LDWM signature 752 verification algorithm to compute the LDWM public key from the LDWM 753 signature and the message. The value of the leaf associated with the 754 LDWM signature is assigned to the public key. Then the root of the 755 tree is computed from the leaf value and the node array (path[]) as 756 described below. If the root value matches the public key, then the 757 signature is valid; otherwise, the signature fails. 759 Algorithm 6: Computing the MTS Root Value 761 n = node number 762 v = leaf 763 step = 0 764 for ( i = 0; i < h; i = i + 1 ) { 765 position = n % k 766 hash_init() 767 for ( j = 0; j < position; j = j + 1 ) { 768 hash_update(path[step + j]) 769 } 770 hash_update(v) 771 for ( j = position; j < (k-1); j = j + 1 ) { 772 hash_update(path[step + j]) 773 } 774 v = hash_final() 775 n = floor(n/k) 776 step = step + (k-1) 777 } 779 Upon completion, v contains the value of the root of the Merkle Tree 780 for comparison. 782 This algorithm uses the typical init/update/final interface to hash 783 functions; the result of the invocations hash_init(), 784 hash_update(N[1]), hash_update(N[2]), ... , hash_update(N[n]), v = 785 hash_final(), in that order, is identical to that of the invocation 786 of H(N[1] || N[2] || ... || N[n]). 788 This algorithm works because the leaves of the MTS tree are numbered 789 starting at zero. Therefore leaf n is in the position (n % k) in the 790 highest level of the tree. 792 The verifier MAY cache interior node values that have been computed 793 during a successful signature verification for use in subsequent 794 signature verifications. However, any implementation that does so 795 MUST make sure any nodes that are cached during a signature 796 verification process are deleted if that process does not result in a 797 successful match between the root of the tree and the MTS public key. 799 A full test example that combines the LDWM OTS and MTS algorithms is 800 given in Appendix B. 802 4.5. MTS Formats 804 MTS signatures and public keys are defined using XDR syntax as 805 follows: 807 enum mts_algorithm_type { 808 mts_reserved = 0x00000000, 809 mts_sha256_k2_h20 = 0x01000001, 810 mts_sha256_k4_h10 = 0x02000002, 811 mts_sha256_k8_h7 = 0x03000003, 812 mts_sha256_k16_h5 = 0x04000004, 813 mts_sha512_k2_h20 = 0x05000005, 814 mts_sha512_k4_h10 = 0x06000006, 815 mts_sha512_k8_h7 = 0x07000007, 816 mts_sha512_k16_h5 = 0x08000008 817 }; 819 union mts_path switch (mts_algorithm_type type) { 820 case mts_sha256_k2_h20: 821 bytestring32 path_n32_t20[20]; 822 case mts_sha256_k4_h10: 823 bytestring32 path_n32_t30[30]; 824 case mts_sha256_k8_h7: 825 bytestring32 path_n32_t49[49]; 826 case mts_sha256_k16_h5: 827 bytestring32 path_n32_t75[75]; 828 case mts_sha512_k2_h20: 829 bytestring64 path_n64_t20[20]; 830 case mts_sha512_k4_h10: 831 bytestring64 path_n64_t30[30]; 832 case mts_sha512_k8_h7: 833 bytestring64 path_n64_t49[49]; 834 case mts_sha512_k16_h5: 835 bytestring64 path_n64_t75[75]; 836 default: 837 void; /* error condition */ 838 }; 840 struct mts_signature { 841 ots_signature ots_sig; 842 unsigned int signature_leaf_number; 843 mts_path nodes; 844 }; 846 struct mts_public_key_n32 { 847 ots_algorithm_type ots_alg_type; 848 opaque value[32]; /* public key */ 849 }; 851 struct mts_public_key_n64 { 852 ots_algorithm_type ots_alg_type; 853 opaque value[64]; /* public key */ 854 }; 855 union mts_public_key switch (mts_algorithm_type type) { 856 case mts_sha256_k2_h20: 857 case mts_sha256_k4_h10: 858 case mts_sha256_k8_h7: 859 case mts_sha256_k16_h5: 860 mts_public_key_n32 z_n32; 861 case mts_sha512_k2_h20: 862 case mts_sha512_k4_h10: 863 case mts_sha512_k8_h7: 864 case mts_sha512_k16_h5: 865 mts_public_key_n64 z_n64; 866 default: 867 void; /* error condition */ 868 }; 870 struct mts_private_key_n32 { 871 ots_algorithm_type ots_alg_type; 872 unsigned int next_ldwm_leaf_number; /* leaf # for next signature */ 873 opaque value[32]; /* private key */ 874 }; 876 struct mts_private_key_n64 { 877 ots_algorithm_type ots_alg_type; 878 unsigned int next_ldwm_leaf_number; /* leaf # for next signature */ 879 opaque value[64]; /* private key */ 880 }; 882 union mts_private_key switch (mts_algorithm_type mts_alg_type) { 883 case mts_sha256_k2_h20: 884 case mts_sha256_k4_h10: 885 case mts_sha256_k8_h7: 886 case mts_sha256_k16_h5: 887 mts_private_key_n32 body_n32; 888 case mts_sha512_k2_h20: 889 case mts_sha512_k4_h10: 890 case mts_sha512_k8_h7: 891 case mts_sha512_k16_h5: 892 mts_private_key_n64 body_n64; 893 default: 894 void; /* error condition */ 895 }; 897 5. Rationale 899 The goal of this note is to describe the LDWM and MTS algorithms 900 following the original references and present the modern security 901 analysis of those algorithms. Other signature methods are out of 902 scope and may be interesting follow-on work. 904 The signature and public key formats are designed so that they are 905 easy to parse. Each format starts with a 32-bit enumeration value 906 that indicates all of the details of the signature algorithm and 907 hence defines all of the information that is needed in order to parse 908 the format. 910 The enumeration values used in this note are palindromes, which have 911 the same byte representation in either host order or network order. 912 This fact allows an implementation to omit the conversion between 913 byte order for those enumerations. Note however that the leaf number 914 field used in the MTS signature and keys must be properly converted 915 to and from network byte order; this is the only field that requires 916 such conversion. There are 2^32 XDR enumeration values, 2^16 of 917 which are palindromes, which is more than enough for the foreseeable 918 future. If there is a need for more assignments, non-palindromes can 919 be assigned. 921 6. History 923 This is the initial version of this draft. 925 This section is to be removed by the RFC editor upon publication. 927 7. IANA Considerations 929 The Internet Assigned Numbers Authority (IANA) is requested to create 930 two registries: one for OTS signatures, which includes all of the 931 LDWM signatures as defined in Section 3, and one for Merkle Tree 932 Signatures, as defined in Section 4. Additions to these registries 933 require that a specification be documented in an RFC or another 934 permanent and readily available reference in sufficient detail that 935 interoperability between independent implementations is possible. 936 Each entry in the registry contains the following elements: 938 a short name, such as "MTS_SHA256_K16_H5", 940 a positive number, and 942 a reference to a specification that completely defines the 943 signature method test cases that can be used to verify the 944 correctness of an implementation. 946 Requests to add an entry to the registry MUST include the name and 947 the reference. The number is assigned by IANA. These number 948 assignments SHOULD use the smallest available palindromic number. 949 Submitters SHOULD have their requests reviewed by the IRTF Crypto 950 Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants 951 that are unfamiliar with IANA processes should visit 952 http://www.iana.org. 954 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 955 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 956 are reserved for private use; no attempt will be made to prevent 957 multiple sites from using the same value in different (and 958 incompatible) ways [RFC2434]. 960 The LDWM registry is as follows. 962 +--------------------+-----------+--------------------+ 963 | Name | Reference | Numeric Identifier | 964 +--------------------+-----------+--------------------+ 965 | LDWM_SHA256_M20_W1 | Section 3 | 0x01000001 | 966 | | | | 967 | LDWM_SHA256_M20_W2 | Section 3 | 0x02000002 | 968 | | | | 969 | LDWM_SHA256_M20_W4 | Section 3 | 0x03000003 | 970 | | | | 971 | LDWM_SHA256_M20_W8 | Section 3 | 0x04000004 | 972 | | | | 973 | LDWM_SHA256_M32_W1 | Section 3 | 0x05000005 | 974 | | | | 975 | LDWM_SHA256_M32_W2 | Section 3 | 0x06000006 | 976 | | | | 977 | LDWM_SHA256_M32_W4 | Section 3 | 0x07000007 | 978 | | | | 979 | LDWM_SHA256_M32_W8 | Section 3 | 0x08000008 | 980 | | | | 981 | LDWM_SHA512_M64_W1 | Section 3 | 0x09000009 | 982 | | | | 983 | LDWM_SHA512_M64_W2 | Section 3 | 0x0a00000a | 984 | | | | 985 | LDWM_SHA512_M64_W4 | Section 3 | 0x0b00000b | 986 | | | | 987 | LDWM_SHA512_M64_W8 | Section 3 | 0x0c00000c | 988 +--------------------+-----------+--------------------+ 990 Table 2 992 The MTS registry is as follows. 994 +-------------------+-----------+--------------------+ 995 | Name | Reference | Numeric Identifier | 996 +-------------------+-----------+--------------------+ 997 | MTS_SHA256_K2_H20 | Section 4 | 0x01000001 | 998 | | | | 999 | MTS_SHA256_K4_H10 | Section 4 | 0x02000002 | 1000 | | | | 1001 | MTS_SHA256_K8_H7 | Section 4 | 0x03000003 | 1002 | | | | 1003 | MTS_SHA256_K16_H5 | Section 4 | 0x04000004 | 1004 | | | | 1005 | MTS_SHA512_K2_H20 | Section 4 | 0x05000005 | 1006 | | | | 1007 | MTS_SHA512_K4_H10 | Section 4 | 0x06000006 | 1008 | | | | 1009 | MTS_SHA512_K8_H7 | Section 4 | 0x07000007 | 1010 | | | | 1011 | MTS_SHA512_K16_H5 | Section 4 | 0x08000008 | 1012 +-------------------+-----------+--------------------+ 1014 Table 3 1016 An IANA registration of a signature system does not constitute an 1017 endorsement of that system or its security. 1019 8. Security Considerations 1021 The security goal of a signature system is to prevent forgeries. A 1022 successful forgery occurs when an attacker who does not know the 1023 private key associated with a public key can find a message and 1024 signature that are valid with that public key (that is, the Signature 1025 Verification algorithm applied to that signature and message and 1026 public key will return "valid"). Such an attacker, in the strongest 1027 case, may have the ability to forge valid signatures for an arbitrary 1028 number of other messages. 1030 The security of the algorithms defined in this note can be roughly 1031 described as follows. For a security level of roughly 128 bits, 1032 assuming that there are no quantum computers, use the LDWM algorithms 1033 with m=32 and MTS with n=32. For a security level of roughly 128 1034 bits, assuming that there are quantum computers, use the LDWM 1035 algorithms with m=64 and the MTS algorithms with n=64. For the 1036 smallest possible signatures that provide a currently adequate 1037 security level, use the LDWM algorithms with m=20 and MTS algorithms 1038 with n=32. We emphasize that this is a rough estimate, and not a 1039 security proof. 1041 LDWM signatures rely on the fact that, given an m-byte string y, it 1042 is prohibitively expensive to compute a value x such that F^i(x) = y 1043 for any i. Informally, F is said to be a "one-way" function, or a 1044 preimage-resistant function. Both LDWM and MTS signatures rely on 1045 the fact that H is collision-resistant, that is, it is prohibitively 1046 expensive for an attacker to find two byte strings a and b such that 1047 H(a) = H(b). 1049 There are several formal security proofs for one time signatures and 1050 Merkle tree signatures in the cryptographic literature. Several of 1051 these analyze variants of those algorithms, and are not directly 1052 applicable to the original algorithms; thus caution is needed when 1053 applying these analyses. The MTS scheme has been shown to provide 1054 roughly b bits of security when used with a hash function with an 1055 output size of 2*b bits [BDM08]. (A cryptographic scheme has b bits 1056 of security when an attacker must perform O(2^b) computations to 1057 defeat it.) More precisely, that analysis shows that MTS is 1058 existentially unforgeable under an adaptive chosen message attack. 1059 However, the analysis assumes that the hash function is chosen 1060 uniformly at random from a family of hash functions, and thus is not 1061 completely applicable. Similarly, LDWM with w=1 has been shown to be 1062 existentially unforgeable under an adaptive chosen message attack, 1063 when F is a one-way function [BDM08], when F is chosen uniformly at 1064 random from a family of one-way functions; when F has c-bit inputs 1065 and outputs, it provides roughly b bits of security. LDWM 1066 signatures, as specified in this note, have been shown to be secure 1067 based on the collision resistance of F [C:Dods05]; that analysis 1068 provides a lower bound on security (and it appears to be pessimistic, 1069 especially in the case of the m=20 signatures). 1071 It may be desirable to adapt this specification in a way that better 1072 aligns with the security proofs. In particular, a random "salt" 1073 value could be generated along with the key, used as an additional 1074 input to F and H, and then provided as part of the public key. This 1075 change appears to make the analysis of [BDM08] applicable, and it 1076 would improve the resistance of these signature schemes against key 1077 collision attacks, that is, scenarios in which an attacker 1078 concurrently attacks many signatures made with many private keys. 1080 8.1. Security of LDWM Checksum 1082 To show the security of LDWM checksum, we consider the signature y of 1083 a message with a private key x and let h = H(message) and 1084 c = C(H(message)) (see Section 3.7). To attempt a forgery, an 1085 attacker may try to change the values of h and c. Let h' and c' 1086 denote the values used in the forgery attempt. If for some integer j 1087 in the range 0 to (u-1), inclusive, 1089 a' = coef(h', j, w), 1091 a = coef(h, j, w), and 1093 a' > a 1095 then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by 1096 iteratively applying function F to the j^th term of the signature an 1097 additional (a' - a) times. However, as a result of the increased 1098 number of hashing iterations, the checksum value c' will decrease 1099 from its original value of c. Thus a valid signature's checksum will 1100 have, for some number k in the range u to (p-1), inclusive, 1102 b' = coef(c', k, w), 1104 b = coef(c, k, w), and 1106 b' < b 1108 Due to the one-way property of F, the attacker cannot easily compute 1109 F^b'(x[k]) from F^b(x[k]) = y[k]. 1111 8.2. Security Conjectures 1113 LDWM and MTS signatures rely on a minimum of security conjectures. 1114 In particular, their security does not rely on the computational 1115 difficulty of factoring composites with large prime factors (as does 1116 RSA) or the difficulty of computing the discrete logarithm in a 1117 finite field (as does DSA) or an elliptic curve group (as does 1118 ECDSA). All of these signature schemes also rely on the security of 1119 the hash function that they use, but with LDWM and MTS, the security 1120 of the hash function is sufficient. 1122 8.3. Post-Quantum Security 1124 A post-quantum cryptosystem is a system that is secure against 1125 quantum computers that have more than a trivial number of quantum 1126 bits. It is open to conjecture whether or not it is feasible to 1127 build such a machine. 1129 The LDWM and Merkle signature systems are post-quantum secure if they 1130 are used with an appropriate underlying hash function, in which the 1131 size of m and n are double what they would be otherwise, in order to 1132 protect against quantum square root attacks due to Grover's 1133 algorithm. In contrast, the signature systems in wide use (RSA, DSA, 1134 and ECDSA) are not post-quantum secure. 1136 9. Acknowledgements 1138 Thanks are due to Chirag Shroff for constructive feedback, and to 1139 Andreas Hulsing, Burt Kaliski, Eric Osterweil, Ahmed Kosba, and Russ 1140 Housley for valuable detailed review. 1142 10. References 1144 10.1. Normative References 1146 [FIPS180] National Institute of Standards and Technology, "Secure 1147 Hash Standard (SHS)", FIPS 180-4, March 2012. 1149 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1150 Requirement Levels", BCP 14, RFC 2119, March 1997. 1152 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1153 IANA Considerations Section in RFCs", BCP 26, RFC 2434, 1154 October 1998. 1156 [RFC4506] Eisler, M., "XDR: External Data Representation Standard", 1157 STD 67, RFC 4506, May 2006. 1159 10.2. Informative References 1161 [BDM08] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based 1162 Digital Signature Schemes", Technische Universitat 1163 Darmstadt Technical Report https:// 1164 www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/ 1165 hashbasedcrypto.pdf, 2008. 1167 [C:Dods05] 1168 Dods, C., Smart, N., and M. Stam, "Hash Based Digital 1169 Signature Schemes", Lecture Notes in Computer Science vol. 1170 3796 Cryptography and Coding, 2005. 1172 [C:Merkle87] 1173 Merkle, R., "A Digital Signature Based on a Conventional 1174 Encryption Function", Lecture Notes in Computer 1175 Science crypto87vol, 1988. 1177 [C:Merkle89a] 1178 Merkle, R., "A Certified Digital Signature", Lecture Notes 1179 in Computer Science crypto89vol, 1990. 1181 [C:Merkle89b] 1182 Merkle, R., "One Way Hash Functions and DES", Lecture 1183 Notes in Computer Science crypto89vol, 1990. 1185 [Merkle79] 1186 Merkle, R., "Secrecy, Authentication, and Public Key 1187 Systems", Stanford University Information Systems 1188 Laboratory Technical Report 1979-1, 1979. 1190 Appendix A. LDWM Parameter Options 1192 A table illustrating various combinations of n and w with the 1193 associated values of u, v, ls, and p is provided in Table 4. 1195 The parameters u, v, ls, and p are computed as follows: 1197 u = ceil(8*n/w) 1198 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) 1199 ls = (number of bits in sum) - (v * w) 1200 p = u + v 1202 Here u and v represent the number of w-bit fields required to contain 1203 the hash of the message and the checksum byte strings, respectively. 1204 The "number of bits in sum" is defined according to Section 3.6. And 1205 as the value of p is the number of w-bit elements of ( H(message) || 1206 C(H(message)) ), it is also equivalently the number of byte strings 1207 that form the private key and the number of byte strings in the 1208 signature. 1210 +---------+------------+-----------+-----------+-------+------------+ 1211 | Hash | Winternitz | w-bit | w-bit | Left | Total | 1212 | Length | Parameter | Elements | Elements | Shift | Number of | 1213 | in | (w) | in Hash | in | (ls) | w-bit | 1214 | Bytes | | (u) | Checksum | | Elements | 1215 | (n) | | | (v) | | (p) | 1216 +---------+------------+-----------+-----------+-------+------------+ 1217 | 20 | 1 | 160 | 8 | 8 | 168 | 1218 | | | | | | | 1219 | 20 | 2 | 80 | 4 | 8 | 84 | 1220 | | | | | | | 1221 | 20 | 4 | 40 | 3 | 4 | 43 | 1222 | | | | | | | 1223 | 20 | 8 | 20 | 2 | 0 | 22 | 1224 | | | | | | | 1225 | 32 | 1 | 256 | 9 | 7 | 265 | 1226 | | | | | | | 1227 | 32 | 2 | 128 | 5 | 6 | 133 | 1228 | | | | | | | 1229 | 32 | 4 | 64 | 3 | 4 | 67 | 1230 | | | | | | | 1231 | 32 | 8 | 32 | 2 | 0 | 34 | 1232 | | | | | | | 1233 | 48 | 1 | 384 | 9 | 7 | 393 | 1234 | | | | | | | 1235 | 48 | 2 | 192 | 5 | 6 | 197 | 1236 | | | | | | | 1237 | 48 | 4 | 96 | 3 | 4 | 99 | 1238 | | | | | | | 1239 | 48 | 8 | 48 | 2 | 0 | 50 | 1240 | | | | | | | 1241 | 64 | 1 | 512 | 10 | 6 | 522 | 1242 | | | | | | | 1243 | 64 | 2 | 256 | 5 | 6 | 261 | 1244 | | | | | | | 1245 | 64 | 4 | 128 | 3 | 4 | 131 | 1246 | | | | | | | 1247 | 64 | 8 | 64 | 2 | 0 | 66 | 1248 +---------+------------+-----------+-----------+-------+------------+ 1250 Table 4 1252 Appendix B. Example Data for Testing 1254 As with all cryptosystems, implementations of LDWM signatures and 1255 Merkle signatures need to be tested before they are used. This 1256 section contains sample data generated from the signing and 1257 verification operations of software that implements the algorithms 1258 described in this document. 1260 B.1. Parameters 1262 The example contained in this section demonstrates the calculations 1263 of LDWM_SHA256_M20_W4 using a Merkle Tree Signature of degree 4 and 1264 height 2. This corresponds to the following parameter values: 1266 +----+----+---+----+----+---+---+ 1267 | m | n | w | p | ls | k | h | 1268 +----+----+---+----+----+---+---+ 1269 | 20 | 32 | 4 | 67 | 4 | 4 | 2 | 1270 +----+----+---+----+----+---+---+ 1272 Table 5 1274 The non-standard size of the Merkle tree (h = 2) has been selected 1275 specifically for this example to reduce the amount of data presented. 1277 B.2. Key Generation 1279 The LDWM algorithm does not define a required method of key 1280 generation. This is left to the implementer. The selected method, 1281 however, must satisfy the requirement that the private keys of the 1282 one-time signatures are uniformly random, independent, and 1283 unpredicable. In addition, all LDWM key pairs must be generated in 1284 advance in order to calculate the value of the Merkle public key. 1286 For the test data presented here, a summary of the key generation 1287 method is as follows: 1289 1. MTS Private Key - Set mts_private_key to a pseudorandomly 1290 generated n-byte value. 1292 2. OTS Private Keys - Use the mts_private_key as a key derivation 1293 key input to some key derivation function, thereby producing n^k 1294 derived keys. Then use each derived key as an input to the same 1295 function again to further derive p elements of n-bytes each. 1296 This accomplishes the result of Algorithm 0 of Section 3.4 for 1297 each leaf of the Merkle tree. 1299 3. OTS Public Keys - For each OTS private key, calculate the 1300 corresponding OTS public key as in Algorithm 1 of Section 3.5. 1302 4. MTS Public Key - Each OTS public key is the value of a leaf on 1303 the Merkle tree. Calculate the MTS public key using the 1304 pseudocode algorithm of Section 4.2 or some equivalent 1305 implementation. 1307 The above steps result in the following data values associated with 1308 the first leaf of the Merkle tree, leaf 0. 1310 +-------------------------------------------------------------------+ 1311 | MTS Private Key | 1312 +-------------------------------------------------------------------+ 1313 | 0x0f677ff1b4cbf10baec89959f051f203 | 1314 | 3371492da02f62dd61d6fbd1cee1bd14 | 1315 +-------------------------------------------------------------------+ 1317 Table 6 1319 +-----------------+-------------------------------------------------+ 1320 | Key Element | OTS Private Key 0 Element (x[i]) | 1321 | Index (i) | | 1322 +-----------------+-------------------------------------------------+ 1323 | 0 | 0xbfb757383fb08d324629115a84daf00b | 1324 | | 188d5695303c83c184e1ec7a501c431f | 1325 | | | 1326 | 1 | 0x7ce628fb82003a2829aab708432787d0 | 1327 | | fc735a29d671c7d790068b453dc8c913 | 1328 | | | 1329 | 2 | 0x8174929461329d15068a4645a34412bd | 1330 | | 446d4c9e757463a7d5164efd50e05c93 | 1331 | | | 1332 | 3 | 0xf283f3480df668de4daa74bb0e4c5531 | 1333 | | 5bc00f7d008bb6311e59a5bbca910fd7 | 1334 | | | 1335 | 4 | 0xe62708eaf9c13801622563780302a068 | 1336 | | 0ba9d39c078daa5ebc3160e1d80a1ea7 | 1337 | | | 1338 | 5 | 0x1f002efad2bfb4275e376af7138129e3 | 1339 | | 3e88cf7512ec1dcdc7df8d5270bc0fd7 | 1340 | | | 1341 | 6 | 0x8ed5a703e9200658d18bc4c05dd0ca8a | 1342 | | 356448a26f3f4fe4e0418b52bd6750a2 | 1343 | | | 1344 | 7 | 0xc74e56d61450c5387e86ddad5a8121c8 | 1345 | | 8b1bc463e64f248a1f1d91d950957726 | 1346 | | | 1347 | 8 | 0x629f18b6a2a4ea65fff4cf758b57333f | 1348 | | e1d34af05b1cd7763696899c9869595f | 1349 | | | 1350 | 9 | 0x1741c31fdbb4864712f6b17fadc05d45 | 1351 | | 926c831c7a755b7d7af57ac316ba6c2a | 1352 | | | 1353 | 10 | 0xe59a7b81490c5d1333a9cdd48b9cb364 | 1354 | | 56821517a3a13cb7a8ed381d4d5f3545 | 1355 | | | 1356 | 11 | 0x3ba97fe8b2967dd74c8b10f31fc5f527 | 1357 | | a23b89c1266202a4d7c281e1f41fa020 | 1358 | | | 1359 | 12 | 0xa262a9287cc979aaa59225d75df51b82 | 1360 | | 57b92e780d1ab14c4ac3ecdac58f1280 | 1361 | | | 1362 | 13 | 0x9dfe0af1a3d9064338d96cb8eae88baa | 1363 | | 6a69265538873b4c17265fa9d573bcff | 1364 | | | 1365 | 14 | 0xde9c5c6a5c6a274eabe90ed2a8e6148c | 1366 | | 720196d237a839aaf5868af8da4d0829 | 1367 | | | 1368 | 15 | 0x5de81ec17090a82cb722f616362d3808 | 1369 | | 30f04841191e44f1f81b9880164b14cd | 1370 | | | 1371 | 16 | 0xc0d047000604105bad657d9fa2f9ef10 | 1372 | | 1cfd9490f4668b700d738f2fa9e1d11a | 1373 | | | 1374 | 17 | 0xf45297ef310941e1e855f97968129bb1 | 1375 | | 73379193919f7b0fee9c037ae507c2d2 | 1376 | | | 1377 | 18 | 0x46ef43a877f023e5e66bbcd4f06b839f | 1378 | | 3bfb2b64de25cd67d1946b0711989129 | 1379 | | | 1380 | 19 | 0x46e2a599861bd9e8722ad1b55b8f0139 | 1381 | | 305fcf8b6077d545d4488c4bcb652f29 | 1382 | | | 1383 | 20 | 0xe1ad4d2d296971e4b0b7a57de305779e | 1384 | | 82319587b58d3ef4daeb08f630bd5684 | 1385 | | | 1386 | 21 | 0x7a07fa7aed97cb54ae420a0e6a58a153 | 1387 | | 38110f7743cab8353371f8ca710a4409 | 1388 | | | 1389 | 22 | 0x40601f6c4b35362dd4948d5687b5cb6b | 1390 | | 5ec8b2ec59c2f06fd50f8919ebeaae92 | 1391 | | | 1392 | 23 | 0xa061b0ba9f493c4991be5cd3a9d15360 | 1393 | | a9eb94f6f7adc28dddf174074f3df3c4 | 1394 | | | 1395 | 24 | 0xcf1546a814ff16099cebf1fe0db1ace5 | 1396 | | 1c272fda9846fbb535815924b0077fa4 | 1397 | | | 1398 | 25 | 0xcbb06f13155ce4e56c85a32661c90142 | 1399 | | 8b630a4c37ea5c7062156f07f6b3efff | 1400 | | | 1401 | 26 | 0x1181ee7fc03342415094e36191eb450a | 1402 | | 11cdea9c6f6cdc34de79cee0ba5bf230 | 1403 | | | 1404 | 27 | 0xe9f1d429b343bb897881d2a19ef363cd | 1405 | | 1ab4117cbaad54dc292b74b8af9f5cf2 | 1406 | | | 1407 | 28 | 0x87f34b2551ef542f579fa65535c5036f | 1408 | | 80eb83be4c898266ffc531da2e1a9122 | 1409 | | | 1410 | 29 | 0x9b4b467852fe33a03a872572707342fd | 1411 | | ddeae64841225186babf353fa2a0cd09 | 1412 | | | 1413 | 30 | 0x19d58cd240ab5c80be6ddf5f60d18159 | 1414 | | 2dca2be40118c1fdd46e0f14dffbcc7d | 1415 | | | 1416 | 31 | 0x5c9ad386547ba82939e49c9c74a8eccf | 1417 | | 1cea60aa327b5d2d0a66b1ca48912d6d | 1418 | | | 1419 | 32 | 0xf49083e502400ffae9273c6de92a301e | 1420 | | 7bda1537cab085e5adfa9eb746e8eca9 | 1421 | | | 1422 | 33 | 0x4074e1812d69543ce3c1ce706f6e0b45 | 1423 | | f5f26f4ef39b34caa709335fd71e8fc0 | 1424 | | | 1425 | 34 | 0x1256612b0ca8398e97b247ae564b74b1 | 1426 | | 3839b3b1cf0a0dd8ba629a2c58355f84 | 1427 | | | 1428 | 35 | 0xbab3989f00fd2c327bbfb35a218cc3ce | 1429 | | 49d6b34cbf8b6e8919e90c4eff400ca9 | 1430 | | | 1431 | 36 | 0x96b52a5d395a5615b73dae65586ac5c8 | 1432 | | 7f9dd3b9b3f82dbf509b5881f0643fa8 | 1433 | | | 1434 | 37 | 0x5d05ca4c644e1c41ccdaedbd2415d4f0 | 1435 | | 9b4a1b940b51fe823dff7617b8ee8304 | 1436 | | | 1437 | 38 | 0xd96aab95ef6248e235d91d0f23b64727 | 1438 | | a6675adfc64efea72f6f8b4a47996c0d | 1439 | | | 1440 | 39 | 0xfd9c384d52d3ac27c4f4898fcc15e83a | 1441 | | c182f97ea63f7d489283e2cc7e6ed180 | 1442 | | | 1443 | 40 | 0xc86eaed6a9e3fbe5b262c1fa1f099f7c | 1444 | | 35ece71d9e467fab7a371dbcf400b544 | 1445 | | | 1446 | 41 | 0xf462b3719a2ed8778155638ff814dbf4 | 1447 | | 2b107bb5246ee3dd82abf97787e6a69e | 1448 | | | 1449 | 42 | 0x014670912e3eb74936ebb64168b447e4 | 1450 | | 2522b57c2540ac4b49b9ae356c01eca6 | 1451 | | | 1452 | 43 | 0x2b411096e0ca16587830d3acd673e858 | 1453 | | 863fedc4cea046587cba0556d2bf9884 | 1454 | | | 1455 | 44 | 0xa73917c74730582e8e1815b8a07b1896 | 1456 | | 2ac05e500e045676be3f1495fcfa18ca | 1457 | | | 1458 | 45 | 0xa4ab61e6962fe39a255dbf8a46d25110 | 1459 | | 0d127fab08db59512653607bda24302c | 1460 | | | 1461 | 46 | 0x9b910ca516413f376b9eba4b0d571b22 | 1462 | | 253c2a9646131ac9a2af5f615f7322b8 | 1463 | | | 1464 | 47 | 0xfc1b4ce627c77ad35a21ea9ded2cce91 | 1465 | | b3758a758224e35cf2918153a513d64c | 1466 | | | 1467 | 48 | 0xc1902d8e8c02d9442581d7e053a2798a | 1468 | | a84d77a74b6e7f2cc5096d50646c890f | 1469 | | | 1470 | 49 | 0xb3f47e2e8e2dcdd890ea00934b9d8234 | 1471 | | 830dbc4a30ac996b144f12b3e463c77f | 1472 | | | 1473 | 50 | 0x8188d1ecfc6ae6118911f2b9b3a6c7a1 | 1474 | | e5f909aa8b5c0aab8c69f1a7d436c307 | 1475 | | | 1476 | 51 | 0xca42d985974c7b870bc76494604eff49 | 1477 | | 2676c942c6cb7c75d4938805885dd054 | 1478 | | | 1479 | 52 | 0xbe58851ebe566057e1ee16b8c604a473 | 1480 | | 4c373af622660b2a82357ac6effb4566 | 1481 | | | 1482 | 53 | 0xc22d493f7a5642fceba2404dbefa8f95 | 1483 | | 6323fac87fac425f6de8d23c9e8b20ca | 1484 | | | 1485 | 54 | 0x1a76c1ffa467906173fd0245b0cd6639 | 1486 | | e6013ca79c4ed92426ee69ff5beeac0b | 1487 | | | 1488 | 55 | 0xbc6c0cb7808f379af1b7b7327436ad65 | 1489 | | c05458f2d0a6923c333e5129c4c99671 | 1490 | | | 1491 | 56 | 0xfbb04488c3c088dc5e63d13e6a701036 | 1492 | | 6109ca4c5f4b0a8d37780187e2e9930e | 1493 | | | 1494 | 57 | 0xaec10811569d4d72e3a1baf71a886b75 | 1495 | | eba6dc07ed027af0b2beffa71f9b43c8 | 1496 | | | 1497 | 58 | 0xf5529be3b7a19212e8baa970d2420bf4 | 1498 | | 123f678267f96c1c3ef26ab610cb0061 | 1499 | | | 1500 | 59 | 0x172ba1ba0b701eeafe00692d1eb90181 | 1501 | | 8ccaefaeb8f799395da81711766d1f43 | 1502 | | | 1503 | 60 | 0xfe1f8c15825208f3a21346b894b3d94e | 1504 | | 4f3aa29cbc194a7b2c8a810c4c509042 | 1505 | | | 1506 | 61 | 0x2e81c66cc914ea1b0fa5942fe9780d54 | 1507 | | 8c0b330e3bf73f0cb0bda4bc9c9e6ff4 | 1508 | | | 1509 | 62 | 0xfc3453aec5cc19a6a4bda4bc25931604 | 1510 | | 704bf4386cd65780c6e73214c1da85ba | 1511 | | | 1512 | 63 | 0x4e8000c587dc917888e7e3d817672c0a | 1513 | | ef812788cc8579afa7e9b2e566309003 | 1514 | | | 1515 | 64 | 0xba667ca0e44a8601a0fde825d4d2cf1b | 1516 | | b9cf467041e04af84c9d0cd9fd8dc784 | 1517 | | | 1518 | 65 | 0x4965db75f81c8a596680753ce70a94c6 | 1519 | | 156253bb426947de1d7662dd7e05e9a8 | 1520 | | | 1521 | 66 | 0x2c23cc3e5ca37dec279c506101a3d8d9 | 1522 | | f1e4f99b2a33741b59f8bddba7455419 | 1523 +-----------------+-------------------------------------------------+ 1525 Table 7 1527 Using the value of the OTS private key above, the corresponding 1528 public key is given below. Intermediate values of the SHA256-20 1529 function F^(2^w - 1)(x[i]) are provided in Table 13. 1531 +-------------------------------------------------------------------+ 1532 | OTS Public Key 0 | 1533 +-------------------------------------------------------------------+ 1534 | 0x2db55a72075fcfab5aedbef77bf6b371 | 1535 | dfb489d6e61ad2884a248345e6910618 | 1536 +-------------------------------------------------------------------+ 1538 Table 8 1540 Following the creation of all OTS public/private key pairs, the OTS 1541 public keys in Table 14 are used to determine the MTS public key 1542 below. Intermediate values of the interior nodes of the Merkle tree 1543 are provided in Table 15. 1545 +-------------------------------------------------------------------+ 1546 | MTS Public Key | 1547 +-------------------------------------------------------------------+ 1548 | 0x6610803d9a3546fb0a7895f6a4a0cfed | 1549 | 3a07d45e51d096e204b018e677453235 | 1550 +-------------------------------------------------------------------+ 1552 Table 9 1554 B.3. Signature Generation 1556 In order to test signature generation, a text file containing the 1557 content "Hello world!\n", where '\n' represents the ASCII line feed 1558 character, was created and signed. A raw hex dump of the file 1559 contents is shown in the table below. 1561 +-------------------------------+-----------------------------------+ 1562 | Hexadecimal Byte Values | ASCII Representation | 1563 | | ('.' is substituted for | 1564 | | non-printing characters) | 1565 +-------------------------------+-----------------------------------+ 1566 | 0x48 0x65 0x6c 0x6c 0x6f 0x20 | Hello world!. | 1567 | 0x77 0x6f 0x72 0x6c 0x64 0x21 | | 1568 | 0x0a | | 1569 +-------------------------------+-----------------------------------+ 1571 Table 10 1573 The SHA256 hash of the text file is provided below. 1575 +-------------------------------------------------------------------+ 1576 | SHA256 Hash of Signed File (H("Hello world!\n")) | 1577 +-------------------------------------------------------------------+ 1578 | 0x0ba904eae8773b70c75333db4de2f3ac | 1579 | 45a8ad4ddba1b242f0b3cfc199391dd8 | 1580 +-------------------------------------------------------------------+ 1582 Table 11 1584 This value was subsequently used in Algorithm 3 of Section 3.7 to 1585 create the one-time signature of the message. Algorithm 2 of 1586 Section 3.6 was applied to calculate a checksum of 0x1cc. The 1587 resulting signature is shown in the following table. 1589 +---------+------------+--------------------------------------------+ 1590 | OTS | Function | OTS Element (y[i] = F^a(x[i])) | 1591 | Element | Iteration | | 1592 | Index | Count | | 1593 | (i) | (a = coef( | | 1594 | | H(msg) || | | 1595 | | C(H(msg)), | | 1596 | | i, w )) | | 1597 +---------+------------+--------------------------------------------+ 1598 | 0 | 0 | 0xbfb757383fb08d324629115a84daf00b188d5695 | 1599 | | | | 1600 | 1 | 11 | 0x4af079e885ddfd3245f29778d265e868a3bfeaa4 | 1601 | | | | 1602 | 2 | 10 | 0xfbad1928bfc57b22bcd949192452293d07d6b9ad | 1603 | | | | 1604 | 3 | 9 | 0xb98063e184b4cb949a51e1bb76d99d4249c0b448 | 1605 | | | | 1606 | 4 | 0 | 0xe62708eaf9c13801622563780302a0680ba9d39c | 1607 | | | | 1608 | 5 | 4 | 0x39343cba3ffa6d75074ce89831b3f3436108318c | 1609 | | | | 1610 | 6 | 14 | 0xfe08aa73607aec5664188a9dacdc34a295588c9a | 1611 | | | | 1612 | 7 | 10 | 0xd3346382119552d1ceb92a78597a00c956372bf0 | 1613 | | | | 1614 | 8 | 14 | 0xf1dd245ec587c0a7a1b754cc327b27c839a6e46a | 1615 | | | | 1616 | 9 | 8 | 0xa5f158adc1decaf0c1edc1a3a5d8958d726627b5 | 1617 | | | | 1618 | 10 | 7 | 0x06d2990f62f22f0c943a418473678e3ffdbff482 | 1619 | | | | 1620 | 11 | 7 | 0xf3390b8d6e5229ae9c5d4c3f45e10455d8241a49 | 1621 | | | | 1622 | 12 | 3 | 0x22dd5f9d3c89180caa0f695203d8cf90f3c359be | 1623 | | | | 1624 | 13 | 11 | 0x67999c4043f95de5f07d82b741347a3eb6ac0c25 | 1625 | | | | 1626 | 14 | 7 | 0xc4ffe472d48adeb37c7360da70711462013b7a4e | 1627 | | | | 1628 | 15 | 0 | 0x5de81ec17090a82cb722f616362d380830f04841 | 1629 | | | | 1630 | 16 | 12 | 0x2f892c824af65cc749f912a36dfa8ade2e4c3fd1 | 1631 | | | | 1632 | 17 | 7 | 0xb644393e8030924403b594fb5cacd8b2d28862e2 | 1633 | | | | 1634 | 18 | 5 | 0x31b8d2908911dbbf5ba1f479a854808945d9e948 | 1635 | | | | 1636 | 19 | 3 | 0xa9a02269d24eb8fed6fb86101cbd0d8977219fb1 | 1637 | 20 | 3 | 0xe4aae6e6a9fe1b0d5099513f170c111dee95714d | 1638 | | | | 1639 | 21 | 3 | 0xd79c16e7f2d4dd790e28bab0d562298c864e31e9 | 1640 | | | | 1641 | 22 | 13 | 0xc29678f0bb4744597e04156f532646c98a0b42e8 | 1642 | | | | 1643 | 23 | 11 | 0x57b31d75743ff0f9bcf2db39d9b6224110b8d27b | 1644 | | | | 1645 | 24 | 4 | 0x0a336d93aac081a2d849c612368b8cbb2fa9563a | 1646 | | | | 1647 | 25 | 13 | 0x917be0c94770a7bb12713a4bae801fb3c1c43002 | 1648 | | | | 1649 | 26 | 14 | 0x91586feaadcf691b6cb07c16c8a2ed0884666e84 | 1650 | | | | 1651 | 27 | 2 | 0xdd4e4b720fb2517c4bc6f91ccb8725118e5770c6 | 1652 | | | | 1653 | 28 | 15 | 0x491f6ec665f54c4b3cffaa02ec594d31e6e26c0e | 1654 | | | | 1655 | 29 | 3 | 0x4f5a082c9d9c9714701de0bf426e9f893484618c | 1656 | | | | 1657 | 30 | 10 | 0x11f7017313f0c9549c5d415a8abc25243028514d | 1658 | | | | 1659 | 31 | 12 | 0x6839a994fccb9cb76241d809146906a3d13f89f1 | 1660 | | | | 1661 | 32 | 4 | 0x71cd1d9163d7cd563936837c61d97bb1a5337cc0 | 1662 | | | | 1663 | 33 | 5 | 0x77c9034ffc0f9219841aa8e1edbfb62017ef9fd1 | 1664 | | | | 1665 | 34 | 10 | 0xad9f6034017d35c338ac35778dd6c4c1abe4472a | 1666 | | | | 1667 | 35 | 8 | 0x4a1c396b22e4f5cc2428045b36d13737c4007515 | 1668 | | | | 1669 | 36 | 10 | 0x98cb57b779c5fd3f361cd5debc243303ae5baefd | 1670 | | | | 1671 | 37 | 13 | 0x29857298f274d6bf595eadc89e5464ccf9608a6c | 1672 | | | | 1673 | 38 | 4 | 0x95e35a26815a3ae9ad84a24464b174a29364da18 | 1674 | | | | 1675 | 39 | 13 | 0x4afeb3b95b5b333759c0acdd96ce3f26314bb22b | 1676 | | | | 1677 | 40 | 13 | 0x325a37ee5e349b22b13b54b24be5145344e7b8f3 | 1678 | | | | 1679 | 41 | 11 | 0x4f772c93f56fd6958ce135f02847996c67e1f2ef | 1680 | | | | 1681 | 42 | 10 | 0xd4f6d91c577594060be328b013c9e9b0e8a2e5d8 | 1682 | | | | 1683 | 43 | 1 | 0x717e1a81c325cdccacb6e9fd9e92dd3e1bb84ae8 | 1684 | | | | 1685 | 44 | 11 | 0x1dd363724ec66c090a1228dfa1cd3d9cc806f346 | 1686 | | | | 1687 | 45 | 2 | 0x64b4110476dd0beea78714c5ab71278818792cfa | 1688 | | | | 1689 | 46 | 4 | 0xe22290e740056a144af50f0b10962b5bcc18fc82 | 1690 | | | | 1691 | 47 | 2 | 0x34fd87046a183f4732a52bb7805ce207eebdafc5 | 1692 | | | | 1693 | 48 | 15 | 0xbd2fdc5e4e8d0ed7c48c1bad9c2f7793fc2c9303 | 1694 | | | | 1695 | 49 | 0 | 0xb3f47e2e8e2dcdd890ea00934b9d8234830dbc4a | 1696 | | | | 1697 | 50 | 11 | 0xcd29719c56cdb507030e6132132179e5807e1d3b | 1698 | | | | 1699 | 51 | 3 | 0xf9edb9b301916217de0d746a0542316bebe9e806 | 1700 | | | | 1701 | 52 | 12 | 0x7a3801cbfe0cafed863d81210c1ec721eede49e5 | 1702 | | | | 1703 | 53 | 15 | 0x5caba3ec960efa210f5f3e1c22c567ca475ef3ec | 1704 | | | | 1705 | 54 | 12 | 0xf911b5d148e1b03fe6983c53411f76ea78772379 | 1706 | | | | 1707 | 55 | 1 | 0x06da2baa75c6ef752bf59f3812fa042ff8181209 | 1708 | | | | 1709 | 56 | 9 | 0x2b29f5aa2f34af51a78a5fac586004f749c6e6dc | 1710 | | | | 1711 | 57 | 9 | 0x55e033ababac0845cc9142e24f9ef0a641c51cbe | 1712 | | | | 1713 | 58 | 3 | 0xb62d207bb700071fba8a68312ca204ce4d994c33 | 1714 | | | | 1715 | 59 | 9 | 0x551d5c00fad905bdb99c4f70ec7590a10d3ff8ca | 1716 | | | | 1717 | 60 | 1 | 0x0d03b1845b5f8838d735142f185f9cf8f8d2db6c | 1718 | | | | 1719 | 61 | 13 | 0x3b5d9e49e7ede41cd9aa5a09f72a0384fd4ff511 | 1720 | | | | 1721 | 62 | 13 | 0xa766b0278d14a9b7d32bf0307c0737a8ecf82ab1 | 1722 | | | | 1723 | 63 | 8 | 0xca85296f354e6e3d2a96ab497c01e5ccd4530cf1 | 1724 | | | | 1725 | 64 | 1 | 0x7bb29db7dd8aaaf1cd11487cea0d13730edb1df3 | 1726 | | | | 1727 | 65 | 12 | 0x547ef341b3cf3208753bb1b62d85a4e3fc2cffe0 | 1728 | | | | 1729 | 66 | 12 | 0xb890e1a99da4b2e0a9dde42f82f92d0946327cee | 1730 +---------+------------+--------------------------------------------+ 1732 Table 12 1734 Finally, based on the fact that the message is the first to be signed 1735 by the Merkle tree (i.e. using leaf node 0), the values of the leaf 1736 and interior nodes that compose the authentication path from leaf to 1737 root are determined as described in Section 4.3. These values are 1738 marked with an asterisk ('*') in Table 14 and Table 15. 1740 B.4. Signature Verification 1742 The signature verification step was provided the following items: 1744 1. OTS = (y[0] || y[1] || ... || y[p-1]) - from Table 12. 1746 2. Authentication Path = concatenation of (k-1)*h Merkle tree node 1747 values - from Table 14 and Table 15. 1749 3. Message Number = leaf number of Merkle tree. 1751 4. Merkle Public Key = root of Merkle tree - from Table 9. 1753 Using Algorithm 4 of Section 3.8 as a start, the potential OTS public 1754 key was calculated from the value of the OTS. Since the actual OTS 1755 public key was not provided to the verifier, the calculated key was 1756 checked for validity using the pseudocode algorithm of Section 4.4 1757 and the provided values of the Authentication Path and Message 1758 Number. Since the message was valid, the calculated value of the 1759 root matched the Merkle public key. Otherwise, verification would 1760 have failed. 1762 B.5. Intermediate Calculation Values 1764 +----------------------+--------------------------------------------+ 1765 | Key Element Index | SHA256-20 Result for w = 4 (F^15(x[i])) | 1766 | (i) | | 1767 +----------------------+--------------------------------------------+ 1768 | 0 | 0x6eff4b0c224874ecc4e4f4500da53dbe2a030e45 | 1769 | | | 1770 | 1 | 0x58ac2c6c451c7779d67efefdb12e5c3d85475a94 | 1771 | | | 1772 | 2 | 0xb1f3e42e29c710d69268eed1bbdb7f5a500b7937 | 1773 | | | 1774 | 3 | 0x51d28e573aac2b84d659abb961c32c465e911b55 | 1775 | | | 1776 | 4 | 0xa0ed62bccac5888f5000ca6a01e5ffefd442a1c6 | 1777 | | | 1778 | 5 | 0x44da9e145666322422c1e2b5e21627e05aeb4367 | 1779 | | | 1780 | 6 | 0x04e7ff9213c2655f28364f659c35d3086d7414e1 | 1781 | | | 1782 | 7 | 0x414cdb3215408b9722a02577eeb71f9e016e4251 | 1783 | | | 1784 | 8 | 0xa3ab06b90a2b20f631175daa9454365a4f408e9e | 1785 | | | 1786 | 9 | 0xe38acfd3c0a03faa82a0f4aeac1a7c04983fad25 | 1787 | | | 1788 | 10 | 0xd95a289094ccce8ad9ff1d5f9e38297f9bb306ff | 1789 | | | 1790 | 11 | 0x593d148b22e33c32f18b66340bdaffceb3ad1a55 | 1791 | | | 1792 | 12 | 0x16b53fbea11dc7ab70c8336ec3c23881ae5d51bf | 1793 | | | 1794 | 13 | 0xa639ca0cf871188cadd0020832c4f06e6ebd5f98 | 1795 | | | 1796 | 14 | 0xe3ab3e0c5ad79d6c8c2a7e9a79856d4380941fe0 | 1797 | | | 1798 | 15 | 0x8368c2933dabcde69c373867a9bf2dc78df97bea | 1799 | | | 1800 | 16 | 0xe3609fca11545da156a7779ae565b1e3c87902c0 | 1801 | | | 1802 | 17 | 0xab029e62c7011772dc0589d79fad01aacf8d2177 | 1803 | | | 1804 | 18 | 0xa8310f1c27c1aa481192de07d4397b8c4716e25f | 1805 | | | 1806 | 19 | 0xdbdbb14dbd9a5f03c1849af24b69b9e3f80faca2 | 1807 | | | 1808 | 20 | 0x1a17399d555dec07d3d4f6d54b2b87d2bcaa398b | 1809 | | | 1810 | 21 | 0xf81c66cc522bfb203232e44d0003ed65d2462867 | 1811 | | | 1812 | 22 | 0x202a625b8c5f22de6ea081af6da077cf5c63202f | 1813 | | | 1814 | 23 | 0x2e080f3591f5ff3d5de39c2698846cc107a09816 | 1815 | | | 1816 | 24 | 0xa1d9c78c22f9810e3b7db2d59ad9f5fdd259f4d4 | 1817 | | | 1818 | 25 | 0x658eeb85ebe0f4542c4d32dced2d7226929266b2 | 1819 | | | 1820 | 26 | 0x67fae1a784f919577afc091504d82d31b4ba9fc7 | 1821 | | | 1822 | 27 | 0xfc39fb43677fb2d433a6292f19c6e7320279655a | 1823 | | | 1824 | 28 | 0x491f6ec665f54c4b3cffaa02ec594d31e6e26c0e | 1825 | | | 1826 | 29 | 0x17cec813a5781409b11d2e4a85f62301c2fd8873 | 1827 | | | 1828 | 30 | 0xc578eb105454d900c053eb55833db607aa5757e0 | 1829 | | | 1830 | 31 | 0xaed094323290a41fd4b546919620e2f6b23916c8 | 1831 | | | 1832 | 32 | 0x192b5a87b5124dc287e06cdd4ec7c0c11f67dda6 | 1833 | | | 1834 | 33 | 0x4e9e2bdc1b0204d1ceeb68fb4159e752c40b9608 | 1835 | | | 1836 | 34 | 0xf34c57ad9ce45d67fd32dc2737e6263bcc5cc61f | 1837 | | | 1838 | 35 | 0xf73bd27d376186310f83cc66e72060aeaccde371 | 1839 | | | 1840 | 36 | 0xeea482511acd8be783e9be42b48799653b222db4 | 1841 | | | 1842 | 37 | 0xa2e53196fec8676065b8f32b3e8498e66a4af3cf | 1843 | | | 1844 | 38 | 0x670c98185157e1b28d38f7dafb00796b434c8316 | 1845 | | | 1846 | 39 | 0x441afbb265b93595389aaa66325de792f343f209 | 1847 | | | 1848 | 40 | 0x7b6c50d20b5edc0bc90eb4b289770514cbc8d547 | 1849 | | | 1850 | 41 | 0xfde6e862a7ba3534893a3e630e209a24be590b1e | 1851 | | | 1852 | 42 | 0xc59611200c20b2e73dfb24c84cedf4792d6daf10 | 1853 | | | 1854 | 43 | 0x66e3527bee88373d18f91b230b53b569361f0a15 | 1855 | | | 1856 | 44 | 0xd0fd79c7116198e689275fec9b4c46f4aac73293 | 1857 | | | 1858 | 45 | 0x65f07406ad4241e7cf4174c5f284267292cdbc32 | 1859 | | | 1860 | 46 | 0x7b1b5535d45f46542e2b876245b66ea83cde3d8f | 1861 | | | 1862 | 47 | 0x7a11620934eb0eb17e10e4a8bbd52aa4b020da0e | 1863 | | | 1864 | 48 | 0xbd2fdc5e4e8d0ed7c48c1bad9c2f7793fc2c9303 | 1865 | | | 1866 | 49 | 0x00432602437252a0622a30676dbaaef3023328b9 | 1867 | | | 1868 | 50 | 0x09a9c4b25034466a5acd7ff681af1c27e8f97577 | 1869 | | | 1870 | 51 | 0x4b31481d52aa5e1a261064bbd87ea46479a6be23 | 1871 | | | 1872 | 52 | 0xaca2ad4aa1264618ab633bf11cbca3cc8fa43091 | 1873 | | | 1874 | 53 | 0x5caba3ec960efa210f5f3e1c22c567ca475ef3ec | 1875 | | | 1876 | 54 | 0x353e3ffcedfd9500141921cf2aebc2e111364dad | 1877 | | | 1878 | 55 | 0xe1c498c32169c869174ccf2f1e71e7202f45fba7 | 1879 | | | 1880 | 56 | 0x5b8519a40d4305813936c7c00a96f5b4ceb603f1 | 1881 | | | 1882 | 57 | 0x3b942ae6a6bd328d08804ade771a0775bb3ff8f8 | 1883 | | | 1884 | 58 | 0x6f3be60ee1c34372599b8d634be72e168453bf10 | 1885 | | | 1886 | 59 | 0xf700c70bac24db0aab1257940661f5b57da6e817 | 1887 | | | 1888 | 60 | 0x85ccf60624b13663a290fa808c6bbecaf89523cd | 1889 | | | 1890 | 61 | 0xd049be55ab703c44f42167d5d9e939c830df960f | 1891 | | | 1892 | 62 | 0xd27a178ccc3b364c7e03d2266093a0d1dfdd9d51 | 1893 | | | 1894 | 63 | 0xd73c53fdddbe196b9ab56fcc5c9a4a57ad868cd1 | 1895 | | | 1896 | 64 | 0xb59a70a7372f0c121fa71727baaf6588eccec400 | 1897 | | | 1898 | 65 | 0x9b5bf379f989f9a499799c12a3202db58b084eed | 1899 | | | 1900 | 66 | 0xccabf40f3c1dacf114b5e5f98a73103b4c1f9b55 | 1901 +----------------------+--------------------------------------------+ 1903 Table 13 1905 +-----------+------------------------------------+------------------+ 1906 | MTS Leaf | OTS Public Key | Member of | 1907 | (Level 3) | (H(x[0] || x[1] || ... || x[p-1])) | Authentication | 1908 | Node | | Path of | 1909 | Number | | Message 0 | 1910 +-----------+------------------------------------+------------------+ 1911 | 0 | 0x2db55a72075fcfab5aedbef77bf6b371 | | 1912 | | dfb489d6e61ad2884a248345e6910618 | | 1913 | | | | 1914 | 1 | 0x8c6c6a1215bfe7fda10b7754e73cd984 | * | 1915 | | a64823b1ab9d5f50feda6b151c0fee6d | | 1916 | | | | 1917 | 2 | 0xc1fb91de68b3059c273e53596108ec7c | * | 1918 | | f39923757597fe86439e91ce1c25fc84 | | 1919 | | | | 1920 | 3 | 0x1b511189baee50251335695b74d67c40 | * | 1921 | | 5a04eddaa79158a9090cc7c3eb204cbf | | 1922 | | | | 1923 | 4 | 0xf3bcf088ccf9d00338b6c87e8f822da6 | | 1924 | | 8ec471f88d1561193b3c017d20b3c971 | | 1925 | | | | 1926 | 5 | 0x40584c059e6cc72fb61f7bd1b9c28e73 | | 1927 | | c689551e6e7de6b0b9b730fab9237531 | | 1928 | | | | 1929 | 6 | 0x1b1d09de1ca16ca890036e018d7e73de | | 1930 | | b39b07de80c19dcc5e55a699f021d880 | | 1931 | | | | 1932 | 7 | 0x83a82632acaac5418716f4f357f5007f | | 1933 | | 719d604525dbe1831c09a2ead9400a52 | | 1934 | | | | 1935 | 8 | 0xccb8b2a1d60f731b5f51910eb427e211 | | 1936 | | 96090d5cd2a077f33968b425301e3fbd | | 1937 | | | | 1938 | 9 | 0x616767ebf3c1f3ec662d8c57c630c6ae | | 1939 | | b31853fd40a18c3d831f5490610c1f16 | | 1940 | | | | 1941 | 10 | 0x5a4b3e157b66327c75d7f01304d188e2 | | 1942 | | cecd1b6168240c11a01775d581b01fb6 | | 1943 | | | | 1944 | 11 | 0xf25744b8a1c2184ba38521801bf4727c | | 1945 | | 407b85eb5aef8884d8fbb1c12e2f6108 | | 1946 | | | | 1947 | 12 | 0xaf8189f51874999162890f72e0ef25e6 | | 1948 | | f76b4ab94dc53569bdd66507f5ab0d8e | | 1949 | | | | 1950 | 13 | 0x96251e396756686645f35cd059da329f | | 1951 | | 7083838d56c9ccacebbaf8486af18844 | | 1952 | | | | 1953 | 14 | 0x773d5206e40065d3553c3c2ed2500122 | | 1954 | | e3ee6fd2c91f35a57f084dc839aab1fc | | 1955 | | | | 1956 | 15 | 0xcda7fae67ce2c3ed29ce426fdcd3f2a8 | | 1957 | | eb699e47a67a52f1c94e89726ffe97fa | | 1958 +-----------+------------------------------------+------------------+ 1960 Table 14 1962 +------------+------------------------------------+-----------------+ 1963 | MTS | Node Value | Member of | 1964 | Interior | (H(child_0 || child_1 || ... || | Authentication | 1965 | (Level 2) | child_k-1)) | Path of | 1966 | Node | | Message 0 | 1967 | Number | | | 1968 +------------+------------------------------------+-----------------+ 1969 | 0 | 0xb6a310deb55ed48004133ece2aebb25e | | 1970 | | d74defb77ebd8d63c79a42b5b4191b0c | | 1971 | | | | 1972 | 1 | 0x71a0c8b767ade2c97ebac069383e4dfb | * | 1973 | | a1c06d5fd3f69a775711ea6470747664 | | 1974 | | | | 1975 | 2 | 0x91109fa97662dc88ae63037391ac2650 | * | 1976 | | f6c664ac2448b54800a1df748953af31 | | 1977 | | | | 1978 | 3 | 0xd277fb8c89689525f90de567068d6c93 | * | 1979 | | 565df3588b97223276ef8e9495468996 | | 1980 +------------+------------------------------------+-----------------+ 1982 Table 15 1984 Authors' Addresses 1986 David McGrew 1987 Cisco Systems 1988 13600 Dulles Technology Drive 1989 Herndon, VA 20171 1990 USA 1992 Email: mcgrew@cisco.com 1994 Michael Curcio 1995 Cisco Systems 1996 7025-2 Kit Creek Road 1997 Research Triangle Park, NC 27709-4987 1998 USA 2000 Email: micurcio@cisco.com