idnits 2.17.1 draft-irtf-cfrg-xmss-hash-based-signatures-03.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 (February 15, 2016) is 2965 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 1127 -- Looks like a reference, but probably isn't: '1' on line 2257 -- Looks like a reference, but probably isn't: '2' on line 2261 -- Looks like a reference, but probably isn't: '3' on line 2267 == Missing Reference: '2i' is mentioned on line 877, but not defined -- Looks like a reference, but probably isn't: '32' on line 1915 -- Looks like a reference, but probably isn't: '64' on line 1916 -- Looks like a reference, but probably isn't: '67' on line 1933 -- Looks like a reference, but probably isn't: '131' on line 1936 -- Looks like a reference, but probably isn't: '4' on line 1947 -- Looks like a reference, but probably isn't: '10' on line 1982 -- Looks like a reference, but probably isn't: '16' on line 1985 -- Looks like a reference, but probably isn't: '20' on line 1989 -- Looks like a reference, but probably isn't: '5' on line 2271 -- Looks like a reference, but probably isn't: '8' on line 2093 -- Looks like a reference, but probably isn't: '77' on line 2221 -- Looks like a reference, but probably isn't: '72' on line 2226 -- Looks like a reference, but probably isn't: '87' on line 2230 -- Looks like a reference, but probably isn't: '141' on line 2235 -- Looks like a reference, but probably isn't: '136' on line 2240 -- Looks like a reference, but probably isn't: '151' on line 2244 -- Looks like a reference, but probably isn't: '7' on line 2275 -- Looks like a reference, but probably isn't: '11' on line 2279 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 7539 (Obsoleted by RFC 8439) == Outdated reference: A later version (-15) exists of draft-mcgrew-hash-sigs-03 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 24 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group A. Huelsing 3 Internet-Draft TU Eindhoven 4 Intended status: Informational D. Butin 5 Expires: August 18, 2016 TU Darmstadt 6 S. Gazdag 7 genua GmbH 8 A. Mohaisen 9 SUNY Buffalo 10 February 15, 2016 12 XMSS: Extended Hash-Based Signatures 13 draft-irtf-cfrg-xmss-hash-based-signatures-03 15 Abstract 17 This note describes the eXtended Merkle Signature Scheme (XMSS), a 18 hash-based digital signature system. It follows existing 19 descriptions in scientific literature. The note specifies the WOTS+ 20 one-time signature scheme, a single-tree (XMSS) and a multi-tree 21 variant (XMSS^MT) of XMSS. Both variants use WOTS+ as a main 22 building block. XMSS provides cryptographic digital signatures 23 without relying on the conjectured hardness of mathematical problems. 24 Instead, it is proven that it only relies on the properties of 25 cryptographic hash functions. XMSS provides strong security 26 guarantees and, besides some special instantiations, is even secure 27 when the collision resistance of the underlying hash function is 28 broken. It is suitable for compact implementations, relatively 29 simple to implement, and naturally resists side-channel attacks. 30 Unlike most other signature systems, hash-based signatures withstand 31 attacks using quantum computers. 33 Status of This Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at http://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on August 18, 2016. 50 Copyright Notice 52 Copyright (c) 2016 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 1.1. Conventions Used In This Document . . . . . . . . . . . . 5 69 2. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 5 70 2.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 5 71 2.2. Operators . . . . . . . . . . . . . . . . . . . . . . . . 5 72 2.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 6 73 2.4. Integer to Byte Conversion . . . . . . . . . . . . . . . 6 74 2.5. Hash Function Address Scheme . . . . . . . . . . . . . . 6 75 2.6. Strings of Base w Numbers . . . . . . . . . . . . . . . . 10 76 2.7. Member Functions . . . . . . . . . . . . . . . . . . . . 11 77 3. Primitives . . . . . . . . . . . . . . . . . . . . . . . . . 12 78 3.1. WOTS+ One-Time Signatures . . . . . . . . . . . . . . . . 12 79 3.1.1. WOTS+ Parameters . . . . . . . . . . . . . . . . . . 12 80 3.1.1.1. WOTS+ Functions . . . . . . . . . . . . . . . . . 13 81 3.1.2. WOTS+ Chaining Function . . . . . . . . . . . . . . . 13 82 3.1.3. WOTS+ Private Key . . . . . . . . . . . . . . . . . . 13 83 3.1.4. WOTS+ Public Key . . . . . . . . . . . . . . . . . . 14 84 3.1.5. WOTS+ Signature Generation . . . . . . . . . . . . . 14 85 3.1.6. WOTS+ Signature Verification . . . . . . . . . . . . 16 86 3.1.7. Pseudorandom Key Generation . . . . . . . . . . . . . 16 87 4. Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 88 4.1. XMSS: eXtended Merkle Signature Scheme . . . . . . . . . 17 89 4.1.1. XMSS Parameters . . . . . . . . . . . . . . . . . . . 18 90 4.1.2. XMSS Hash Functions . . . . . . . . . . . . . . . . . 18 91 4.1.3. XMSS Private Key . . . . . . . . . . . . . . . . . . 19 92 4.1.4. Randomized Tree Hashing . . . . . . . . . . . . . . . 19 93 4.1.5. L-Trees . . . . . . . . . . . . . . . . . . . . . . . 19 94 4.1.6. TreeHash . . . . . . . . . . . . . . . . . . . . . . 20 95 4.1.7. XMSS Public Key . . . . . . . . . . . . . . . . . . . 21 96 4.1.8. XMSS Signature . . . . . . . . . . . . . . . . . . . 22 97 4.1.9. XMSS Signature Generation . . . . . . . . . . . . . . 23 98 4.1.10. XMSS Signature Verification . . . . . . . . . . . . . 24 99 4.1.11. Pseudorandom Key Generation . . . . . . . . . . . . . 26 100 4.1.12. Free Index Handling and Partial Secret Keys . . . . . 26 101 4.2. XMSS^MT: Multi-Tree XMSS . . . . . . . . . . . . . . . . 27 102 4.2.1. XMSS^MT Parameters . . . . . . . . . . . . . . . . . 27 103 4.2.2. XMSS Algorithms Without Message Hash . . . . . . . . 27 104 4.2.3. XMSS^MT Private Key . . . . . . . . . . . . . . . . . 27 105 4.2.4. XMSS^MT Public Key . . . . . . . . . . . . . . . . . 28 106 4.2.5. XMSS^MT Signature . . . . . . . . . . . . . . . . . . 29 107 4.2.6. XMSS^MT Signature Generation . . . . . . . . . . . . 30 108 4.2.7. XMSS^MT Signature Verification . . . . . . . . . . . 31 109 4.2.8. Pseudorandom Key Generation . . . . . . . . . . . . . 32 110 4.2.9. Free Index Handling and Partial Secret Keys . . . . . 33 111 5. Parameter Sets . . . . . . . . . . . . . . . . . . . . . . . 33 112 5.1. WOTS+ Parameters . . . . . . . . . . . . . . . . . . . . 33 113 5.2. XMSS Parameters . . . . . . . . . . . . . . . . . . . . . 34 114 5.3. XMSS^MT Parameters . . . . . . . . . . . . . . . . . . . 34 115 6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 35 116 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36 117 8. Security Considerations . . . . . . . . . . . . . . . . . . . 39 118 8.1. Security Proofs . . . . . . . . . . . . . . . . . . . . . 40 119 8.2. Security Assumptions . . . . . . . . . . . . . . . . . . 41 120 8.3. Post-Quantum Security . . . . . . . . . . . . . . . . . . 41 121 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 41 122 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 41 123 10.1. Normative References . . . . . . . . . . . . . . . . . . 41 124 10.2. Informative References . . . . . . . . . . . . . . . . . 42 125 Appendix A. WOTS+ XDR Formats . . . . . . . . . . . . . . . . . 43 126 Appendix B. XMSS XDR Formats . . . . . . . . . . . . . . . . . . 44 127 Appendix C. XMSS^MT XDR Formats . . . . . . . . . . . . . . . . 49 128 Appendix D. Changed since draft-irtf-cfrg-xmss-hash-based- 129 signatures-02 . . . . . . . . . . . . . . . . . . . 54 130 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 55 132 1. Introduction 134 A (cryptographic) digital signature scheme provides asymmetric 135 message authentication. The key generation algorithm produces a key 136 pair consisting of a private and a public key. A message is signed 137 using a private key to produce a signature. A message/signature pair 138 can be verified using a public key. A One-Time Signature (OTS) 139 scheme allows using a key pair to sign exactly one message securely. 140 A many-time signature system can be used to sign multiple messages. 142 One-Time Signature schemes, and Many-Time Signature (MTS) schemes 143 composed of them, were proposed by Merkle in 1979 [Merkle79]. They 144 were well-studied in the 1990s and have regained interest from 2006 145 onwards because of their resistance against quantum-computer-aided 146 attacks. These kinds of signature schemes are called hash-based 147 signature schemes as they are built out of a cryptographic hash 148 function. Hash-based signature schemes generally feature small 149 private and public keys as well as fast signature generation and 150 verification but large signatures and relatively slow key generation. 151 In addition, they are suitable for compact implementations that 152 benefit various applications and are naturally resistant to most 153 kinds of side-channel attacks. 155 Some progress has already been made toward standardizing and 156 introducing hash-based signatures. McGrew and Curcio have published 157 an Internet-Draft [DC15] specifying the Lamport-Diffie-Winternitz- 158 Merkle (LDWM) scheme, also taking into account subsequent adaptations 159 by Leighton and Micali. Independently, Buchmann, Dahmen and Huelsing 160 have proposed XMSS [BDH11], the eXtended Merkle Signature Scheme, 161 offering better efficiency and a modern security proof. Very 162 recently, the stateless hash-based signature scheme SPHINCS was 163 introduced [BHH15], with the intent of being easier to deploy in 164 current applications. A reasonable next step toward introducing 165 hash-based signatures would be to complete the specifications of the 166 basic algorithms - LDWM, XMSS, SPHINCS and/or variants [Kaliski15]. 168 The eXtended Merkle Signature Scheme (XMSS) [BDH11] is the latest 169 stateful hash-based signature scheme. It has the smallest signatures 170 out of such schemes and comes with a multi-tree variant that solves 171 the problem of slow key generation. Moreover, it can be shown that 172 XMSS is secure, making only mild assumptions on the underlying hash 173 function. Especially, it is not required that the cryptographic hash 174 function is collision-resistant for the security of XMSS. 176 This document describes a single-tree and a multi-tree variant of 177 XMSS. It also describes WOTS+, a variant of the Winternitz OTS 178 scheme introduced in [Huelsing13] that is used by XMSS. The schemes 179 are described with enough specificity to ensure interoperability 180 between implementations. 182 This document is structured as follows. Notation is introduced in 183 Section 2. Section 3 describes the WOTS+ signature system. MTS 184 schemes are defined in Section 4: the eXtended Merkle Signature 185 Scheme (XMSS) in Section 4.1, and its Multi-Tree variant (XMSS^MT) in 186 Section 4.2. Parameter sets are described in Section 5. Section 6 187 describes the rationale behind choices in this note. The IANA 188 registry for these signature systems is described in Section 7. 189 Finally, security considerations are presented in Section 8. 191 1.1. Conventions Used In This Document 193 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 194 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 195 document are to be interpreted as described in [RFC2119]. 197 2. Notation 199 2.1. Data Types 201 Bytes and byte strings are the fundamental data types. A byte is a 202 sequence of eight bits. A single byte is denoted as a pair of 203 hexadecimal digits with a leading "0x". A byte string is an ordered 204 sequence of zero or more bytes and is denoted as an ordered sequence 205 of hexadecimal characters with a leading "0x". For example, 0xe534f0 206 is a byte string of length 3. An array of byte strings is an 207 ordered, indexed set starting with index 0 in which all byte strings 208 have identical length. We assume big-endian representation for any 209 data types or structures. 211 2.2. Operators 213 When a and b are integers, mathematical operators are defined as 214 follows: 216 ^ : a ^ b denotes the result of a raised to the power of b. 218 * : a * b denotes the product of a and b. This operator is 219 sometimes used implicitly in the absence of ambiguity, as in usual 220 mathematical notation. 222 / : a / b denotes the quotient of a by b. 224 % : a % b denotes the non-negative remainder of the integer 225 division of a by b. 227 + : a + b denotes the sum of a and b. 229 - : a - b denotes the difference of a and b. 231 The standard order of operations is used when evaluating arithmetic 232 expressions. 234 Arrays are used in the common way, where the i^th element of an array 235 A is denoted A[i]. Byte strings are treated as arrays of bytes where 236 necessary: If X is a byte string, then X[i] denotes its i^th byte, 237 where X[0] is the leftmost byte. 239 If A and B are byte strings of equal length, then: 241 A AND B denotes the bitwise logical conjunction operation. 243 A XOR B denotes the bitwise logical exclusive disjunction 244 operation. 246 When B is a byte and i is an integer, then B >> i denotes the logical 247 right-shift operation. Similarly, B << i denotes the logical left- 248 shift operation. 250 If X is an x-byte string and Y a y-byte string, then X || Y denotes 251 the concatenation of X and Y, with X || Y = X[0] ... X[x-1] Y[0] ... 252 Y[y-1]. 254 2.3. Functions 256 If x is a non-negative real number, then we define the following 257 functions: 259 ceil(x) : returns the smallest integer greater or equal than x. 261 floor(x) : returns the largest integer less or equal than x. 263 lg(x) : returns the logarithm to base 2 of x. 265 2.4. Integer to Byte Conversion 267 If x and y are non-negative integers, we define Z = toByte(x,y) to be 268 the y-byte string containing the binary representation of x in big- 269 endian byte-order. 271 2.5. Hash Function Address Scheme 273 The schemes described in this document randomize each hash function 274 call. This means that aside of the initial message digest, for each 275 hash function call a different key and different bitmask is used. 276 These values are pseudorandomly generated using a pseudorandom 277 generator that takes a seed S and a 16-byte address A. The latter is 278 used to select the A-th n-byte block from the PRG output where n is 279 the security parameter. Here we explain the structure of address A. 280 We explain the construction of the addresses in the following 281 sections where they are used. 283 The schemes in the next two sections use two kinds of hash functions 284 parameterized by security parameter n. For the hash tree 285 constructions a hash function that maps 2n-byte inputs and an n-byte 286 key to n-byte outputs is used. To randomize this function, 3n bytes 287 are needed - n bytes for the key and 2n bytes for a bitmask. For the 288 one-time signature scheme constructions a hash function that maps 289 n-byte inputs and n-byte keys to n-byte outputs is used. To 290 randomize this function, 2n bytes are needed - n bytes for the key 291 and n bytes for a bitmask. Consequently, three addresses are needed 292 for the first function and two addresses for the second one. 294 There are three different address formats for the different use 295 cases. One format for the hashes used in one-time signature schemes, 296 one for hashes used within the main Merkle-tree construction, and one 297 for hashes used in the L-trees. The latter being used to compress 298 one-time public keys. All these formats share as much format as 299 possible. In the following we describe these formats in detail. 301 The structure of an address complies with byte borders, as well as 302 with word borders except for the tree address. The tree address is 303 too long to match word borders. An address is structured as follows. 304 It always starts with a layer address of 8 bits in the most 305 significant bits, followed by a tree address of 40 bits. Following a 306 zero padding of seven bits, the next bit specifies whether it is an 307 OTS or a hash tree address. This OTS bit is set to zero for a tree 308 hash address and to one for an OTS hash address. 310 We first describe the OTS address case as the hash tree case again 311 splits into two cases. In this case, the OTS bit is followed by a 312 zero padding of 16 bits. The padding is followed by a 24-bit OTS 313 address that encodes the index of the OTS key pair within the tree. 314 The next 16 bits encode the chain address followed by 8 bits that 315 encode the address of the hash function call within the chain. The 316 first seven bits of the last byte contain a zero padding. The last 317 bit is the key bit, used to generate two different addresses for one 318 hash function call. The bit is set to one to generate the key. To 319 generate the n-byte bitmask, the key bit is set to zero. 321 An OTS hash address 322 +------------------------+ 323 | layer address (8 bit)| 324 +------------------------+ 325 | tree address (40 bit)| 326 +------------------------+ 327 | Padding = 0 (7 bit)| 328 +------------------------+ 329 | OTS bit = 1 (1 bit)| 330 +------------------------+ 331 | Padding = 0 (16 bit)| 332 +------------------------+ 333 | OTS address (24 bit)| 334 +------------------------+ 335 | chain address (16 bit)| 336 +------------------------+ 337 | hash address (8 bit)| 338 +------------------------+ 339 | Padding = 0 (7 bit)| 340 +------------------------+ 341 | key bit (1 bit)| 342 +------------------------+ 344 Now we describe the hash tree address case. This case again splits 345 into two. The OTS bit is followed by a zero padding of seven bits 346 and an L-tree bit. This bit is set to one in case of an L-tree and 347 set to zero for main tree nodes. We now discuss the L-tree case, 348 which means that the L-tree bit is set to one. In that case the 349 L-tree bit is followed by an L-tree address of 24 bits that encodes 350 the index of the leaf computed with this L-tree. The next 8 bits 351 encode the height of the node inside the L-tree and the following 24 352 bits encode the index of the node at that height, inside the L-tree. 353 After a zero padding of 6 bits, the last two bits are used to 354 generate three different addresses for one node. The first of these 355 bits is set to one to generate the key. In that case the next bit is 356 always zero. To generate the 2n-byte bitmask, the key bit is set to 357 zero. The most significant n bytes are generated using the address 358 with the block bit set to zero. The least significant bytes are 359 generated using the address with the block bit set to one. 361 An L-tree address 362 +------------------------+ 363 | layer address (8 bit)| 364 +------------------------+ 365 | tree address (40 bit)| 366 +------------------------+ 367 | Padding = 0 (7 bit)| 368 +------------------------+ 369 | OTS bit = 0 (1 bit)| 370 +------------------------+ 371 | Padding = 0 (7 bit)| 372 +------------------------+ 373 | L-tree bit = 1 (1 bit)| 374 +------------------------+ 375 | L-tree address (24 bit)| 376 +------------------------+ 377 | tree height (8 bit)| 378 +------------------------+ 379 | tree index (24 bit)| 380 +------------------------+ 381 | Padding = 0 (6 bit)| 382 +------------------------+ 383 | block bit (1 bit)| 384 +------------------------+ 385 | key bit (1 bit)| 386 +------------------------+ 388 We now describe the remaining format for the main tree hash 389 addresses. In this case the L-tree bit is set to zero, followed by a 390 zero padding of 24 bits. The next 8 bits encode the height of the 391 tree node to be computed within the tree, followed by 24 bits that 392 encode the index of this node at that height. After a zero padding 393 of 6 bits the last two bits are used to generate three different 394 addresses for one node as described for the L-tree case. The first 395 of these bits is set to one to generate the key. In that case the 396 latter bit is always zero. To generate the 2n-byte bitmask, the key 397 bit is set to zero. The most significant n bytes are generated using 398 the address with the block bit set to zero. The least significant 399 bytes are generated using the address with the block bit set to one. 401 A hash tree address 402 +------------------------+ 403 | layer address (8 bit)| 404 +------------------------+ 405 | tree address (40 bit)| 406 +------------------------+ 407 | Padding = 0 (7 bit)| 408 +------------------------+ 409 | OTS bit = 0 (1 bit)| 410 +------------------------+ 411 | Padding = 0 (7 bit)| 412 +------------------------+ 413 | L-tree bit = 0 (1 bit)| 414 +------------------------+ 415 | Padding = 0 (24 bit)| 416 +------------------------+ 417 | tree height (8 bit)| 418 +------------------------+ 419 | tree index (24 bit)| 420 +------------------------+ 421 | Padding = 0 (6 bit)| 422 +------------------------+ 423 | block bit (1 bit)| 424 +------------------------+ 425 | key bit (1 bit)| 426 +------------------------+ 428 All fields within these addresses encode unsigned integers. When 429 describing the generation of addresses we use setter-methods that 430 take positive integers and set the bits of a field to the binary 431 representation of that integer of the length of the field. We also 432 assume that setting the L-tree bit to zero, does also set the other 433 padding block to zero. 435 2.6. Strings of Base w Numbers 437 A byte string can be considered as a string of base w numbers, i.e. 438 integers in the set {0, ... , w - 1}. The correspondence is defined 439 by the function base_w(X, w) as follows. If X is a len_X-byte 440 string, w is a member of the set {4, 16}, then base_w(X, w) outputs a 441 length 8 * len_X / lg(w) array of integers between 0 and w - 1. 443 Algorithm 1: base_w(X, w) 445 int in = 0; 446 int out = 0; 447 unsigned int total = 0; 448 int bits = 0; 449 int consumed; 451 for ( consumed = 0; consumed < 8 * len_X; consumed += lg(w) ) { 452 if ( bits == 0 ) { 453 total = X[in]; 454 in++; 455 bits += 8; 456 } 457 bits -= lg(w); 458 basew[out] = (total >> bits) AND (w - 1); 459 out++; 460 } 461 return basew; 463 For example, if X is the (big-endian) byte string 0x1234, then 464 base_w(X, 16) returns the array a = {1, 2, 3, 4}. 466 X (represented as bits) 467 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 468 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 469 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 470 X[0] | X[1] 472 X (represented as base 16 numbers) 473 +-----------+-----------+-----------+-----------+ 474 | 1 | 2 | 3 | 4 | 475 +-----------+-----------+-----------+-----------+ 477 base_w(X, 16) 478 +-----------+-----------+-----------+-----------+ 479 | 1 | 2 | 3 | 4 | 480 +-----------+-----------+-----------+-----------+ 481 a[0] a[1] a[2] a[3] 483 2.7. Member Functions 485 To simplify algorithm descriptions, we assume the existence of member 486 functions. If a complex data structure like a public key PK contains 487 a value X then getX(PK) returns the value of X for this public key. 488 Accordingly, setX(PK, X, Y) sets value X in PK to the value hold by 489 Y. Since camelCase is used for member function names, a value z may 490 be referred to as Z in the function name, e.g. getZ. 492 3. Primitives 494 3.1. WOTS+ One-Time Signatures 496 This section describes the WOTS+ one-time signature system, in a 497 version similar to [Huelsing13]. WOTS+ is a one-time signature 498 scheme; while a private key can be used to sign any message, each 499 private key MUST be used only once to sign a single message. In 500 particular, if a secret key is used to sign two different messages, 501 the scheme becomes insecure. 503 The section starts with an explanation of parameters. Afterwards, 504 the so-called chaining function, which forms the main building block 505 of the WOTS+ scheme, is explained. It follows a description of the 506 algorithms for key generation, signing and verification. Finally, 507 pseudorandom key generation is discussed. 509 3.1.1. WOTS+ Parameters 511 WOTS+ uses the parameters m, n, and w; they all take positive integer 512 values. These parameters are summarized as follows: 514 m : the message length in bytes 516 n : the length, in bytes, of a secret key, public key, or 517 signature element 519 w : the Winternitz parameter; it is a member of the set {4, 16} 521 The parameters are used to compute values len, len_1 and len_2: 523 len : the number of n-byte string elements in a WOTS+ secret key, 524 public key, and signature. It is computed as len = len_1 + len_2, 525 with len_1 = ceil(8m/lg(w)) and len_2 = 526 floor(lg(len_1*(w-1))/lg(w)) + 1 528 The value of n is determined by the cryptographic hash function used 529 for WOTS+. The hash function is chosen to ensure an appropriate 530 level of security. The value of m is the input length that can be 531 processed by the signing algorithm. It is often the length of a 532 message digest. The parameter w can be chosen from the set {4, 16}. 533 A larger value of w results in shorter signatures but slower overall 534 signing operations; it has little effect on security. Choices of w 535 are limited to the values 4 and 16 since these values yield optimal 536 trade-offs and easy implementation. 538 3.1.1.1. WOTS+ Functions 540 The WOTS+ algorithm uses a keyed cryptographic hash function F. F 541 accepts and returns byte strings of length n using keys of length n. 542 Security requirements on F are discussed in Section 8. In addition, 543 WOTS+ uses a pseudorandom generator G. G takes as input an n-byte 544 key and a 16-byte index and generates pseudorandom outputs of length 545 n. Security requirements on G are discussed in Section 8. 547 3.1.2. WOTS+ Chaining Function 549 The chaining function (Algorithm 2) computes an iteration of F on an 550 n-byte input using outputs of G. It takes a hash function address as 551 input. This address will have the first 119 bits set to encode the 552 address of this chain. In each iteration, one output of G is used as 553 key for F and a second output is XORed to the intermediate result 554 before it is processed by F. In the following, ADRS is a 16-byte 555 hash function address as specified in Section 2.5 and SEED is an 556 n-byte string, both used to generate the outputs of G. The chaining 557 function takes as input an n-byte string X, a start index i, a number 558 of steps s, as well as ADRS and SEED. The chaining function returns 559 as output the value obtained by iterating F for s times on input X, 560 using the outputs of G. 562 Algorithm 2: Chaining Function 564 if ( s is equal to 0 ) { 565 return X; 566 } 567 if ( (i+s) > w-1 ) { 568 return NULL; 569 } 570 byte[n] tmp = chain(X, i, s-1, SEED, ADRS); 571 ADRS.setHashAddress(i+s-1); 572 ADRS.setKeyBit(0); 573 BM = G(SEED, ADRS); 574 ADRS.setKeyBit(1); 575 KEY = G(SEED, ADRS); 576 tmp = F(KEY, tmp XOR BM); 577 return tmp; 579 3.1.3. WOTS+ Private Key 581 The private key in WOTS+, denoted by sk, is a length len array of 582 n-byte strings. This private key MUST be only used to sign exactly 583 one message. Each n-byte string MUST either be selected randomly 584 from the uniform distribution or using a cryptographically secure 585 pseudorandom procedure. In the latter case, the security of the used 586 procedure MUST at least match that of the WOTS+ parameters used. For 587 a further discussion on pseudorandom key generation see the end of 588 this section. The following pseudocode (Algorithm 3) describes an 589 algorithm for generating sk. 591 Algorithm 3: Generating a WOTS+ Private Key 593 for ( i = 0; i < len; i = i + 1 ) { 594 set sk[i] to a uniformly random n-byte string; 595 } 596 return sk; 598 3.1.4. WOTS+ Public Key 600 A WOTS+ key pair defines a virtual structure that consists of len 601 hash chains of length w. The len n-byte strings in the secret key 602 each define the start node for one hash chain. The public key 603 consists of the end nodes of these hash chains. Therefore, like the 604 secret key, the public key is also a length len array of n-byte 605 strings. To compute the hash chain, the chaining function (Algorithm 606 2) is used. A hash function address ADRS and a seed SEED has to be 607 provided by the calling algorithm. This address will encode the 608 address of the WOTS+ key pair within a greater structure. Hence, a 609 WOTS+ algorithm MUST NOT manipulate any other fields of ADRS than 610 chain address, hash address and key bit. Please note that the SEED 611 used here is public information also available to a verifier. The 612 following pseudocode (Algorithm 4) describes an algorithm for 613 generating the public key pk, where sk is the private key. 615 Algorithm 4 (WOTS_genPK): Generating a WOTS+ Public Key From a 616 Private Key 618 for ( i = 0; i < len; i = i + 1 ) { 619 ADRS.setChainAddress(i); 620 pk[i] = chain(sk[i], 0, w-1, SEED, ADRS); 621 } 622 return pk; 624 3.1.5. WOTS+ Signature Generation 626 A WOTS+ signature is a length len array of n-byte strings. The WOTS+ 627 signature is generated by mapping a message to len integers between 0 628 and w - 1. To this end, the message is transformed into base w 629 numbers using the base_w function defined in Section 2.6. Next, a 630 checksum is computed and appended to the transformed message as len_2 631 base w numbers using the base_w function. Each of the base w 632 integers is used to select a node from a different hash chain. The 633 signature is formed by concatenating the selected nodes. The 634 pseudocode for signature generation is shown below (Algorithm 5), 635 where M is the message and sig is the resulting signature. 637 Algorithm 5 (WOTS_sign): Generating a signature from a private key 638 and a message 640 csum = 0; 642 // convert message to base w 643 msg = base_w(M,w); 645 // compute checksum 646 for ( i = 0; i < len_1; i = i + 1 ) { 647 csum = csum + w - 1 - msg[i]; 648 } 650 // Convert csum to base w 651 csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); 652 len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); 653 msg = msg || base_w(toByte(csum, len_2_bytes), w); 654 for ( i = 0; i < len; i = i + 1 ) { 655 ADRS.setChainAddress(i); 656 sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS); 657 } 658 return sig; 660 The data format for a signature is given below. 662 WOTS+ Signature 664 +---------------------------------+ 665 | | 666 | sig_ots[0] | n bytes 667 | | 668 +---------------------------------+ 669 | | 670 ~ .... ~ 671 | | 672 +---------------------------------+ 673 | | 674 | sig_ots[len-1] | n bytes 675 | | 676 +---------------------------------+ 678 3.1.6. WOTS+ Signature Verification 680 In order to verify a signature sig on a message M, the verifier 681 computes a WOTS+ public key value from the signature. This can be 682 done by "completing" the chain computations starting from the 683 signature values, using the base w values of the message hash and its 684 checksum. This step, called WOTS_pkFromSig, is described below in 685 Algorithm 6. The result of WOTS_pkFromSig is then compared to the 686 given public key. If the values are equal, the signature is 687 accepted. Otherwise, the signature MUST be rejected. 689 Algorithm 6 (WOTS_pkFromSig): Computing a WOTS+ public key from a 690 message and its signature 692 csum = 0; 694 // convert message to base w 695 msg = base_w(M,w); 697 // compute checksum 698 for ( i = 0; i < len_1; i = i + 1 ) { 699 csum = csum + w - 1 - msg[i]; 700 } 702 // Convert csum to base w 703 csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); 704 len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); 705 msg = msg || base_w(toByte(csum, len_2_bytes), w); 706 for ( i = 0; i < len; i = i + 1 ) { 707 ADRS.setChainAddress(i); 708 tmp_pk[i] = chain(sig[i], msg[i], w-1-msg[i], SEED, ADRS); 709 } 710 return tmp_pk; 712 Note: XMSS uses WOTS_pkFromSig to compute a public key value and 713 delays the comparison to a later point. 715 3.1.7. Pseudorandom Key Generation 717 An implementation MAY use a cryptographically secure pseudorandom 718 method to generate the secret key from a single n-byte value. For 719 example, the method suggested in [BDH11] and explained below MAY be 720 used. Other methods MAY be used. The choice of a pseudorandom 721 method does not affect interoperability, but the cryptographic 722 strength MUST match that of the used WOTS+ parameters. 724 The advantage of generating the secret key elements from a random 725 n-byte string is that only this n-byte string needs to be stored 726 instead of the full secret key. The key can be regenerated when 727 needed. The suggested method from [BDH11] can be described using G. 728 During key generation a uniformly random n-byte string S is sampled 729 from a secure source of randomness. This string S is stored as 730 secret key. The secret key elements are computed as sk[i] = G'(S, 731 toByte(i,16)) whenever needed. Please note that this seed S MUST be 732 different from the seed SEED used to randomize the hash function 733 calls. Also, this seed S MUST be kept secret. 735 4. Schemes 737 In this section, the eXtended Merkle Signature Scheme (XMSS) is 738 described using WOTS+. XMSS comes in two flavors: First, a single- 739 tree variant (XMSS) and second a multi-tree variant (XMSS^MT). Both 740 allow combining a large number of WOTS+ key pairs under a single 741 small public key. The main ingredient added is a binary hash tree 742 construction. XMSS uses a single hash tree while XMSS^MT uses a tree 743 of XMSS key pairs. 745 4.1. XMSS: eXtended Merkle Signature Scheme 747 XMSS is a method for signing a potentially large but fixed number of 748 messages. It is based on the Merkle signature scheme. XMSS uses 749 five cryptographic components: WOTS+ as OTS method, two additional 750 cryptographic hash functions H and H_m, a pseudorandom function 751 PRF_m, and a pseudorandom generator G. One of the main advantages of 752 XMSS with WOTS+ is that it does not rely on the collision resistance 753 of the used hash functions but on weaker properties. Each XMSS 754 public/private key pair is associated with a perfect binary tree, 755 every node of which contains an n-byte value. Each tree leaf 756 contains a special tree hash of a WOTS+ public key value. Each non- 757 leaf tree node is computed by first concatenating the values of its 758 child nodes, computing the XOR with a bitmask, and applying the keyed 759 hash function H to the result. The bitmasks and the keys for the 760 hash function H are generated from a (public) seed that is part of 761 the public key using the pseudorandom generator G. The value 762 corresponding to the root of the XMSS tree forms the XMSS public key 763 together with the seed. 765 To generate a key pair that can be used to sign 2^h messages, a tree 766 of height h is used. XMSS is a stateful signature scheme, meaning 767 that the secret key changes after every signature. To prevent one- 768 time secret keys from being used twice, the WOTS+ key pairs are 769 numbered from 0 to (2^h)-1 according to the related leaf, starting 770 from index 0 for the leftmost leaf. The secret key contains an index 771 that is updated after every signature, such that it contains the 772 index of the next unused WOTS+ key pair. 774 A signature consists of the index of the used WOTS+ key pair, the 775 WOTS+ signature on the message and the so-called authentication path. 776 The latter is a vector of tree nodes that allow a verifier to compute 777 a value for the root of the tree starting from a WOTS+ signature. A 778 verifier computes the root value and compares it to the respective 779 value in the XMSS public key. If they match, the signature is valid. 780 The XMSS secret key consists of all WOTS+ secret keys and the actual 781 index. To reduce storage, a pseudorandom key generation procedure, 782 as described in [BDH11], MAY be used. The security of the used 783 method MUST at least match the security of the XMSS instance. 785 4.1.1. XMSS Parameters 787 XMSS has the following parameters: 789 h : the height (number of levels - 1) of the tree 791 n : the length in bytes of each node 793 m : the length of the message digest 795 w : the Winternitz parameter as defined for WOTS+ in Section 3.1 797 There are N = 2^h leaves in the tree. 799 For XMSS and XMSS^MT, secret and public keys are denoted by SK and 800 PK. For WOTS+, secret and public keys are denoted by sk and pk, 801 respectively. XMSS and XMSS^MT signatures are denoted by Sig. WOTS+ 802 signatures are denoted by sig. 804 4.1.2. XMSS Hash Functions 806 Besides the cryptographic hash function F required by WOTS+, XMSS 807 uses four more functions: 809 A cryptographic hash function H. H accepts n-byte keys and byte 810 strings of length (2 * n) and returns an n-byte string. 812 A cryptographic hash function H_m. H_m accepts 2m-byte keys and 813 byte strings of arbitrary length and returns an m-byte string. 815 A pseudorandom function PRF_m. PRF_m accepts byte strings of 816 arbitrary length and an m-byte key and returns an m-byte string. 818 A pseudorandom generator G. G takes as input an n-byte key and a 819 16-byte index and generates pseudorandom outputs of length n. 821 4.1.3. XMSS Private Key 823 An XMSS private key contains N = 2^h WOTS+ private keys, the leaf 824 index idx of the next WOTS+ private key that has not yet been used 825 and SK_PRF, an m-byte key for the PRF. The leaf index idx is 826 initialized to zero when the XMSS private key is created. The PRF 827 key SK_PRF MUST be sampled from a secure source of randomness that 828 follows the uniform distribution. The WOTS+ secret keys MUST be 829 generated as described in Section 3.1. To reduce the secret key 830 size, a cryptographic pseudorandom method MAY be used as discussed at 831 the end of this section. For the following algorithm descriptions, 832 the existence of a method getWOTS_SK(SK, i) is assumed. This method 833 takes as inputs an XMSS secret key SK and an integer i and outputs 834 the i^th WOTS+ secret key of SK. 836 4.1.4. Randomized Tree Hashing 838 To improve readability we introduce a function RAND_HASH(LEFT, RIGHT, 839 SEED, ADRS) that does the randomized hashing. It takes as input two 840 n-byte values LEFT and RIGHT that represent the left and the right 841 half of the hash function input, the seed SEED for G and the address 842 ADRS of this hash function call. RAND_HASH first uses G with SEED 843 and ADRS to generate a key KEY and n-byte bitmasks BM_0, BM_1. Then 844 it returns the randomized hash H(KEY, (LEFT XOR BM_0)||(RIGHT XOR 845 BM_1)). 847 Algorithm 7: RAND_HASH 849 ADRS.setKeyBit(0); 850 ADRS.setBlockBit(0); 851 BM_0 = G(SEED, ADRS); 852 ADRS.setBlockBit(1); 853 BM_1 = G(SEED, ADRS); 854 ADRS.setKeyBit(1); 855 ADRS.setBlockBit(0); 856 KEY = G(SEED, ADRS); 857 return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); 859 4.1.5. L-Trees 861 To compute the leaves of the binary hash tree, a so-called L-tree is 862 used. An L-tree is an unbalanced binary hash tree, distinct but 863 similar to the main XMSS binary hash tree. The algorithm ltree 864 (Algorithm 8) takes as input a WOTS+ public key pk and compresses it 865 to a single n-byte value pk[0]. Towards this end it also takes an 866 address ADRS as input that encodes the address of the L-tree. The 867 algorithm uses G and the seed SEED generated during public key 868 generation. 870 Algorithm 8: ltree 872 unsigned int len' = len; 873 ADRS.setTreeHeight(0); 874 while ( len' > 1 ) { 875 for ( i = 0; i < floor(len' / 2); i = i + 1 ) { 876 ADRS.setTreeIndex(i); 877 pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS); 878 } 879 if ( len' % 2 == 1 ) { 880 pk[floor(len' / 2)] = pk[len' - 1]; 881 } 882 len' = ceil(len' / 2); 883 ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 884 } 885 return pk[0]; 887 4.1.6. TreeHash 889 For the computation of the internal n-byte nodes of a Merkle tree, 890 the subroutine treeHash (Algorithm 9) accepts an XMSS secret key SK, 891 an unsigned integer s (the start index), an unsigned integer t (the 892 target node height), a seed SEED, and an address ADRS that encodes 893 the address of the containing tree. For the height of a node within 894 a tree counting starts with the leaves at height zero. The treeHash 895 algorithm returns the root node of a tree of height t with the 896 leftmost leaf being the hash of the WOTS+ pk with index s. It is 897 REQUIRED that s % 2^t = 0, i.e. that the leaf at index s is a left 898 most leaf of a sub-tree of height t. Otherwise the hash-addressing 899 scheme fails. The treeHash algorithm uses a stack holding up to 900 (t-1) n-byte strings, with the usual stack functions push() and 901 pop(). 903 Algorithm 9: treeHash 905 if( s % (1 << t) != 0 ) return -1; 906 for ( i = 0; i < 2^t; i = i + 1 ) { 907 ADRS.setOTSBit(1); 908 ADRS.setOTSAddress(s+i); 909 pk = WOTS_genPK (getWOTS_SK(SK, s+i), SEED, ADRS); 910 ADRS.setOTSBit(0); 911 ADRS.setLTreeBit(1); 912 ADRS.setLTreeAddress(s+i); 913 node = ltree(pk, SEED, ADRS); 914 ADRS.setLTreeBit(0); 915 ADRS.setTreeHeight(0); 916 ADRS.setTreeIndex(i+s); 917 while ( Top node on Stack has same height t' as node ) { 918 ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); 919 node = RAND_HASH(Stack.pop(), node, SEED, ADRS); 920 ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 921 } 922 Stack.push(node); 923 } 924 return Stack.pop(); 926 4.1.7. XMSS Public Key 928 The XMSS public key is computed as described in XMSS_genPK (Algorithm 929 10). The algorithm takes the XMSS secret key SK, and the tree height 930 h. The XMSS public key PK consists of the root of the binary hash 931 tree and the seed SEED. SEED is generated as a uniformly random 932 n-byte string. Although SEED is public, it is important that it is 933 generated using a good entropy source. The root is computed using 934 treeHash. For XMSS, there is only a single main tree. Hence, the 935 used address is set to the all-zero-string. 937 Algorithm 10: XMSS_genPK - Generate an XMSS public key from an XMSS 938 private key 940 set SEED to a uniformly random n-byte string; 941 ADRS = toByte(0, 16); 942 root = treeHash(SK, 0, h, SEED, ADRS); 943 PK = root || SEED; 944 return PK; 946 Public and private key generation MAY be interleaved to save space. 947 Especially, when a pseudorandom method is used to generate the secret 948 key, generation MAY be done when the respective WOTS+ key pair is 949 needed by treeHash. 951 The format of an XMSS public key is given below. 953 XMSS Public Key 955 +---------------------------------+ 956 | algorithm OID | 957 +---------------------------------+ 958 | | 959 | root node | n bytes 960 | | 961 +---------------------------------+ 962 | | 963 | SEED | n bytes 964 | | 965 +---------------------------------+ 967 4.1.8. XMSS Signature 969 An XMSS signature is a (4 + m + (len + h) * n)-byte string consisting 970 of 972 the index idx_sig of the used WOTS+ key pair (4 bytes), 974 a byte string r used for randomized message hashing (m bytes), 976 a WOTS+ signature sig_ots (len * n bytes), 978 the so-called authentication path 'auth' for the leaf associated 979 with the used WOTS+ key pair (h * n bytes). 981 The authentication path is an array of h n-byte strings. It contains 982 the siblings of the nodes on the path from the used leaf to the root. 983 It does not contain the nodes on the path itself. These nodes are 984 needed by a verifier to compute a root node for the tree from the 985 WOTS+ public key. A node Node is addressed by its position in the 986 tree. Node(x,y) denotes the x^th node on level y with x = 0 being 987 the leftmost node on a level. The leaves are on level 0, the root is 988 on level h. An authentication path contains exactly one node on 989 every layer 0 <= x <= h-1. For the i^th WOTS+ key pair, counting 990 from zero, the j^th authentication path node is 992 Node(j, floor(i / (2^j)) XOR 1) 994 Given an XMSS secret key SK and seed SEED, all nodes in a tree are 995 determined. Their value is defined in terms of treeHash (Algorithm 996 9). Hence, one can compute the authentication path: 998 buildAuth - Compute the authentication path for the i^th WOTS+ key 999 pair 1001 ADRS = toByte(0, 16); 1002 for (j = 0; j < h; j++) { 1003 k = floor(i / (2^j)) XOR 1; 1004 auth[j] = treeHash(SK, k * 2^j, j, SEED, ADRS); 1005 } 1007 The data format for a signature is given below. 1009 XMSS Signature 1011 +---------------------------------+ 1012 | | 1013 | index idx_sig | 4 bytes 1014 | | 1015 +---------------------------------+ 1016 | | 1017 | randomness r | m bytes 1018 | | 1019 +---------------------------------+ 1020 | | 1021 | WOTS+ signature sig_ots | len * n bytes 1022 | | 1023 +---------------------------------+ 1024 | | 1025 | auth[0] | n bytes 1026 | | 1027 +---------------------------------+ 1028 | | 1029 ~ .... ~ 1030 | | 1031 +---------------------------------+ 1032 | | 1033 | auth[h-1] | n bytes 1034 | | 1035 +---------------------------------+ 1037 4.1.9. XMSS Signature Generation 1039 To compute the XMSS signature of a message M with an XMSS private 1040 key, the signer first computes a randomized message digest using a 1041 random value r and idx_sig, the index of the WOTS+ keypair to be 1042 used, as key. Then a WOTS+ signature of the message digest is 1043 computed using the next unused WOTS+ private key. Next, the 1044 authentication path is computed. Finally, the secret key is updated, 1045 i.e. idx is incremented. An implementation MUST NOT output the 1046 signature before the updated private key. 1048 The node values of the authentication path MAY be computed in any 1049 way. This computation is assumed to be performed by the subroutine 1050 buildAuth for the function XMSS_sign, as below. The fastest 1051 alternative is to store all tree nodes and set the array in the 1052 signature by copying them, respectively. The least storage-intensive 1053 alternative is to recompute all nodes for each signature online. 1054 There exist several algorithms in between, with different time/ 1055 storage trade-offs. For an overview see [BDS09]. Note that the 1056 details of this procedure are not relevant to interoperability; it is 1057 not necessary to know any of these details in order to perform the 1058 signature verification operation. The version of buildAuth presented 1059 above is only one of several possible alternatives. 1061 The algorithm XMSS_sign (Algorithm 11) described below calculates an 1062 updated secret key SK and a signature on a message M. XMSS_sign 1063 takes as inputs a message M of an arbitrary length, an XMSS secret 1064 key SK and seed SEED. It returns the byte string containing the 1065 concatenation of the updated secret key SK and the signature Sig. 1067 Algorithm 11: XMSS_sign - Generate an XMSS signature and update the 1068 XMSS secret key 1070 idx_sig = getIdx(SK); 1071 ADRS = toByte(0, 16); 1072 auth = buildAuth(SK, idx_sig, SEED, ADRS); 1073 byte[m] r = PRF_m(getSK_PRF(SK), M); 1074 byte[m] M' = H_m( (toByte(idx_sig, m) || r), M); 1075 ADRS.setOTSBit(1); 1076 ADRS.setOTSAddress(idx_sig); 1077 sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), M', SEED, ADRS); 1078 Sig = (idx_sig || r || sig_ots || auth); 1079 setIdx(SK, idx_sig + 1); 1080 return (SK || Sig); 1082 4.1.10. XMSS Signature Verification 1084 An XMSS signature is verified by first computing the message digest 1085 using randomness r, index idx_sig, and a message M. Then the used 1086 WOTS+ public key pk_ots is computed from the WOTS+ signature using 1087 WOTS_pkFromSig. The WOTS+ public key in turn is used to compute the 1088 corresponding leaf using an L-tree. The leaf, together with index 1089 idx_sig and authentication path auth is used to compute an 1090 alternative root value for the tree. These first steps are done by 1091 XMSS_rootFromSig (Algorithm 12). The verification succeeds if and 1092 only if the computed root value matches the one in the XMSS public 1093 key. In any other case it MUST return fail. 1095 The main part of XMSS signature verification is done by the function 1096 XMSS_rootFromSig (Algorithm 12) described below. XMSS_rootFromSig 1097 takes as inputs an XMSS signature Sig, a message M, and seed SEED. 1098 XMSS_rootFromSig returns an n-byte string holding the value of the 1099 root of a tree defined by the input data. 1101 Algorithm 12: XMSS_rootFromSig - Compute a root node using an XMSS 1102 signature, a message, and seed SEED 1104 byte[m] M' = H_m((toByte(idx_sig, m) || r), M); 1105 ADRS = toByte(0, 16); 1106 ADRS.setOTSBit(1); 1107 ADRS.setOTSAddress(idx_sig); 1108 pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS); 1109 ADRS.setOTSBit(0); 1110 ADRS.setLTreeBit(1); 1111 ADRS.setLTreeAddress(idx_sig); 1112 byte[n][2] node; 1113 node[0] = ltree(pk_ots, SEED, ADRS); 1114 ADRS.setLTreeBit(0); 1115 ADRS.setTreeIndex(idx_sig); 1116 for ( k = 0; k < h; k = k + 1 ) { 1117 ADRS.setTreeHeight(k); 1118 if ( floor(idx_sig / (2^k)) % 2 is equal to 0 ) { 1119 ADRS.setTreeIndex(ADRS.getTreeIndex() / 2); 1120 node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS); 1121 } else { 1122 ADRS.setTreeIndex(ADRS.getTreeIndex() - 1 / 2); 1123 node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS); 1124 } 1125 node[0] = node[1]; 1126 } 1127 return node[0]; 1129 The full XMSS signature verification is depicted below. XMSS^MT uses 1130 only XMSS_rootFromSig and delegates the comparison to a later 1131 comparison of data depending on its output. 1133 Algorithm 13: XMSS_verify - Verify an XMSS signature using an XMSS 1134 signature, the corresponding XMSS public key and a message 1136 byte[n] node = XMSS_rootFromSig(Sig, M, getSEED(PK)); 1137 if ( node is equal to root in PK ) { 1138 return true; 1139 } else { 1140 return false; 1141 } 1143 4.1.11. Pseudorandom Key Generation 1145 An implementation MAY use a cryptographically secure pseudorandom 1146 method to generate the XMSS secret key from a single n-byte value. 1147 For example, the method suggested in [BDH11] and explained below MAY 1148 be used. Other methods MAY be used. The choice of a pseudorandom 1149 method does not affect interoperability, but the cryptographic 1150 strength MUST match that of the used XMSS parameters. 1152 For XMSS a similar method than the one used for WOTS+ can be used. 1153 The suggested method from [BDH11] can be described using G. During 1154 key generation a uniformly random n-byte string S is sampled from a 1155 secure source of randomness. This seed S MUST NOT be confused with 1156 the public seed SEED. The seed S MUST be independent of SEED and as 1157 it is the main secret, it MUST be kept secret. This seed S is used 1158 to generate an n-byte value S_ots for each WOTS+ key pair. The 1159 n-byte value S_ots can then be used to compute the respective WOTS+ 1160 secret key using the method described in Section 3.1.7. The seeds 1161 for the WOTS+ key pairs are computed as S_ots[i] = G(S,i). The 1162 second parameter of G is the index i of the WOTS+ key pair, 1163 represented as 16-byte string in the common way. An advantage of 1164 this method is that a WOTS+ key can be computed using only len + 1 1165 evaluations of G when S is given. 1167 4.1.12. Free Index Handling and Partial Secret Keys 1169 Some applications might require to work with partial secret keys or 1170 copies of secret keys. Examples include delegation of signing rights 1171 / proxy signatures, and load balancing. Such applications MAY use 1172 their own key format and MAY use a signing algorithm different from 1173 the one described above. The index in partial secret keys or copies 1174 of a secret key MAY be manipulated as required by the applications. 1175 However, applications MUST establish means that guarantee that each 1176 index and thereby each WOTS+ key pair is used to sign only a single 1177 message. 1179 4.2. XMSS^MT: Multi-Tree XMSS 1181 XMSS^MT is a method for signing a large but fixed number of messages. 1182 It was first described in [HRB13]. It builds on XMSS. XMSS^MT uses 1183 a tree of several layers of XMSS trees. The trees on top and 1184 intermediate layers are used to sign the root nodes of the trees on 1185 the respective layer below. Trees on the lowest layer are used to 1186 sign the actual messages. All XMSS trees have equal height. 1188 Consider an XMSS^MT tree of total height h that has d layers of XMSS 1189 trees of height h / d. Then layer d - 1 contains one XMSS tree, 1190 layer d - 2 contains 2^(h / d) XMSS trees, and so on. Finally, layer 1191 0 contains 2^(h - h / d) XMSS trees. 1193 4.2.1. XMSS^MT Parameters 1195 In addition to all XMSS parameters, an XMSS^MT system requires the 1196 number of tree layers d, specified as an integer value that divides h 1197 without remainder. The same tree height h / d and the same 1198 Winternitz parameter w are used for all tree layers. 1200 All the trees on higher layers sign root nodes of other trees which 1201 are n-byte strings. Hence, no message compression is needed and 1202 WOTS+ is used to sign the root nodes themselves instead of their hash 1203 values. Hence the WOTS+ message length for these layers is n not m. 1204 Accordingly, the values of len_1, len_2 and len change for these 1205 layers. The parameters len_1_n, len_2_n, and len_n denote the 1206 respective values computed using n as message length for WOTS+. 1208 4.2.2. XMSS Algorithms Without Message Hash 1210 As all XMSS trees besides those on layer 0 are used to sign short 1211 fixed length messages and even on layer 0 the message hash has to be 1212 handled separately, the initial message hash can be omitted. In the 1213 description below XMSS_sign_wo_hash and XMSS_rootFromSig_wo_hash are 1214 versions of XMSS_sign and XMSS_rootFromSig, respectively, that omit 1215 the initial message hash. They are obtained by setting M' = M in the 1216 above algorithms. Accordingly, the evaluations of H_m and PRF_m MUST 1217 be omitted. This also means that no randomization element r for the 1218 message hash is required. XMSS signatures generated by 1219 XMSS_sign_wo_hash and verified by XMSS_rootFromSig_wo_hash MUST NOT 1220 contain a value r. 1222 4.2.3. XMSS^MT Private Key 1224 An XMSS^MT private key SK_MT consists of one reduced XMSS private key 1225 for each XMSS tree. These reduced XMSS private keys contain no 1226 pseudorandom function key and no index. Instead, SK_MT contains a 1227 single m-byte pseudorandom function key SK_PRF and a single (ceil(h / 1228 8))-byte index idx_MT. The index is a global index over all WOTS+ 1229 key pairs of all XMSS trees on layer 0. It is initialized with 0. 1230 It stores the index of the last used WOTS+ key pair on the bottom 1231 layer, i.e. a number between 0 and 2^h - 1. 1233 The algorithm descriptions below uses a function getXMSS_SK(SK, x, y) 1234 that outputs the reduced secret key of the x^th XMSS tree on the y^th 1235 layer. 1237 4.2.4. XMSS^MT Public Key 1239 The XMSS^MT public key PK_MT contains the root of the single XMSS 1240 tree on layer d-1 and the seed SEED. The pseudorandom generator G is 1241 used with SEED to generate the bitmasks and keys for all XMSS trees. 1242 Algorithm 14 shows pseudocode to generate PK_MT. First, the n-byte 1243 SEED is chosen uniformly at random. The n-byte root node of the top 1244 layer tree is computed using treeHash. The algorithm XMSSMT_genPK 1245 takes the XMSS^MT secret key SK_MT as an input and outputs an XMSS^MT 1246 public key PK_MT. 1248 Algorithm 14: XMSSMT_genPK - Generate an XMSS^MT public key from an 1249 XMSS^MT private key 1251 set SEED to a uniformly random n-byte string; 1252 ADRS = toByte(0, 16); 1253 ADRS.setLayerAddress(d-1); 1254 root = treeHash(getXMSS_SK(SK_MT, 0, d - 1), 0, h / d, SEED, ADRS); 1255 PK_MT = root || SEED; 1256 return PK_MT; 1258 The format of an XMSS^MT public key is given below. 1260 XMSS^MT Public Key 1262 +---------------------------------+ 1263 | algorithm OID | 1264 +---------------------------------+ 1265 | | 1266 | root node | n bytes 1267 | | 1268 +---------------------------------+ 1269 | | 1270 | SEED | n bytes 1271 | | 1272 +---------------------------------+ 1274 4.2.5. XMSS^MT Signature 1276 An XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) + 1277 m + (h + len + (d - 1) * len_n) * n). It consists of 1279 the index idx_sig of the used WOTS+ key pair on the bottom layer 1280 (ceil(h / 8) bytes), 1282 a byte string r used for randomized message hashing (m bytes), 1284 one reduced XMSS signature ((h / d + len) * n bytes), 1286 d-1 reduced XMSS signatures with message length n ((h / d + len_n) 1287 * n bytes each). 1289 The reduced XMSS signatures contain no index idx and no byte string 1290 r. They only contain a WOTS+ signature sig_ots and an authentication 1291 path auth. The first reduced XMSS signature contains a WOTS+ 1292 signature that consists of len n-byte elements. The remaining 1293 reduced XMSS signatures contain a WOTS+ signature on an n-byte 1294 message that consists of len_n n-byte elements. 1296 The data format for a signature is given below. 1298 XMSS^MT signature 1300 +---------------------------------+ 1301 | | 1302 | index idx_sig | ceil(h / 8) bytes 1303 | | 1304 +---------------------------------+ 1305 | | 1306 | randomness r | m bytes 1307 | | 1308 +---------------------------------+ 1309 | | 1310 | (reduced) XMSS signature Sig | (h / d + len) * n bytes 1311 | (bottom layer 0) | 1312 | | 1313 +---------------------------------+ 1314 | | 1315 | (reduced) XMSS signature Sig | (h / d + len_n) * n bytes 1316 | (layer 1) | 1317 | | 1318 +---------------------------------+ 1319 | | 1320 ~ .... ~ 1321 | | 1322 +---------------------------------+ 1323 | | 1324 | (reduced) XMSS signature Sig | (h / d + len_n) * n bytes 1325 | (layer d-1) | 1326 | | 1327 +---------------------------------+ 1329 4.2.6. XMSS^MT Signature Generation 1331 To compute the XMSS^MT signature Sig_MT of a message M using an 1332 XMSS^MT private key SK_MT and seed SEED, XMSSMT_sign (Algorithm 15) 1333 described below uses XMSS_sign_wo_hash as defined in Section 4.2.2. 1334 First, the signature index is set to idx_sig. Next, PRF_m is used to 1335 compute a pseudorandom m-byte string r. This m-byte string and 1336 idx_sig are then used to compute a randomized message digest of 1337 length m. The message digest is signed using the WOTS+ key pair on 1338 the bottom layer with absolute index idx. The authentication path 1339 for the WOTS+ key pair is computed as well as the root of the 1340 containing XMSS tree. The root is signed by the parent XMSS tree. 1341 This is repeated until the top tree is reached. 1343 Algorithm 15: XMSSMT_sign - Generate an XMSS^MT signature and update 1344 the XMSS^MT secret key 1346 ADRS = toByte(0, 16); 1347 SK_PRF = getSK_PRF(SK_MT); 1348 idx_sig = getIdx(SK_MT); 1349 setIdx(SK_MT, idx_sig + 1); 1350 Sig_MT = idx_sig; 1351 unsigned int idx_tree = (h - h/d) most significant bits of idx_sig; 1352 unsigned int idx_leaf = (h / d) least significant bits of idx_sig; 1353 SK = idx_leaf || SK_PRF || getXMSS_SK(SK_MT, idx_tree, 0); 1354 ADRS.setLayerAddress(0); 1355 ADRS.setTreeAddress(idx_tree); 1356 byte[m] r = PRF_m(getSK_PRF(SK), M); 1357 byte[m] M' = H_m( (toByte(idx_sig, m) || r), M); 1358 Sig_tmp = XMSS_sign_wo_hash(M', SK, SEED, ADRS); 1359 Sig_tmp = Sig_tmp with idx removed; 1360 Sig_MT = Sig_MT || r || Sig_tmp; 1361 for ( j = 1; j < d; j = j + 1 ) { 1362 root = treeHash(SK, 0, h / d, SEED, ADRS); 1363 idx_leaf = (h / d) least significant bits of idx_tree; 1364 idx_tree = (h - j * (h / d)) most significant bits of idx_tree; 1365 SK = idx_leaf || SK_PRF || getXMSS_SK(SK_MT, idx_tree, j); 1366 ADRS.setLayerAddress(j); 1367 ADRS.setTreeAddress(idx_tree); 1368 Sig_tmp = XMSS_sign_wo_hash(root, SK, SEED, ADRS) 1369 with idx removed; 1370 Sig_MT = Sig_MT || Sig_tmp; 1371 } 1372 return SK_MT || Sig_MT; 1374 Algorithm 15 is only one method to compute XMSS^MT signatures. 1375 Especially, there exist time-memory trade-offs that allow to reduce 1376 the signing time to less than the signing time of an XMSS scheme with 1377 tree height h / d. These trade-offs prevent certain values from 1378 being recomputed several times by keeping a state and distribute all 1379 computations over all signature generations. Details can be found in 1380 [Huelsing13a]. 1382 4.2.7. XMSS^MT Signature Verification 1384 XMSS^MT signature verification (Algorithm 16) can be summarized as d 1385 XMSS signature verifications with small changes. First, only the 1386 message is hashed. The remaining XMSS signatures are on the root 1387 nodes of trees which have a fixed length. Second, instead of 1388 comparing the computed root node to a given value, a signature on the 1389 root is verified. Only the root node of the top tree is compared to 1390 the value in the XMSS^MT public key. XMSSMT_verify uses 1391 XMSS_rootFromSig and XMSS_rootFromSig_wo_hash. 1392 getXMSSSignature(Sig_MT, i) returns the ith reduced XMSS signature 1393 from the XMSS^MT signature Sig_MT. XMSSMT_verify takes as inputs an 1394 XMSS^MT signature Sig_MT, a message M and a public key PK_MT. It 1395 outputs a boolean. 1397 Algorithm 16: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a 1398 message M using an XMSS^MT public key PK_MT 1400 idx_sig = getIdx(Sig_MT); 1401 SEED = getSEED(PK_MT); 1402 ADRS = toByte(0, 16); 1403 unsigned int idx_leaf = (h / d) least significant bits of idx_sig; 1404 unsigned int idx_tree = (h - h / d) most significant bits of idx_sig; 1405 Sig' = idx_leaf || getR(Sig_MT) || getXMSSSignature(Sig_MT, 0); 1406 ADRS.setLayerAddress(0); 1407 ADRS.setTreeAddress(idx_tree); 1408 byte[m] M' = H_m( (toByte(idx_sig, m) || getR(Sig_MT)), M ); 1409 byte[n] node = XMSS_rootFromSig_wo_hash(Sig', M', SEED, ADRS); 1410 for ( j = 1; j < d; j = j + 1 ) { 1411 idx_leaf = (h / d) least significant bytes of idx_tree; 1412 idx_tree = (h - j * h / d) most significant bytes of idx_tree; 1413 Sig' = idx_leaf || getXMSSSignature(Sig_MT, j); 1414 ADRS.setLayerAddress(j); 1415 ADRS.setTreeAddress(idx_tree); 1416 node = XMSS_rootFromSig_wo_hash(Sig', node, SEED, ADRS); 1417 } 1418 if ( node is equal to getRoot(PK_MT) ) { 1419 return true; 1420 } else { 1421 return false; 1422 } 1424 4.2.8. Pseudorandom Key Generation 1426 Like for XMSS, an implementation MAY use a cryptographically secure 1427 pseudorandom method to generate the XMSS^MT secret key from a single 1428 n-byte value. For example, the method explained below MAY be used. 1429 Other methods MAY be used, too. The choice of a pseudorandom method 1430 does not affect interoperability, but the cryptographic strength MUST 1431 match that of the used XMSS parameters. 1433 For XMSS^MT a method similar to that for XMSS and WOTS+ can be used. 1434 The method uses a G as pseudorandom generator. During key generation 1435 a uniformly random n-byte string S_MT is sampled from a secure source 1436 of randomness. This seed S_MT is used to generate one n-byte value S 1437 for each XMSS key pair. This n-byte value can be used to compute the 1438 respective XMSS secret key using the method described in 1439 Section 4.1.11. Let S[x][y] be the seed for the x^th XMSS secret key 1440 on layer y. The seeds are computed as S[x][y] = G(G(S, y), x). The 1441 second parameter of G is the index x (resp. level y), represented as 1442 16-byte string in the common way. 1444 4.2.9. Free Index Handling and Partial Secret Keys 1446 The content of Section 4.1.12 also applies to XMSS^MT. 1448 5. Parameter Sets 1450 This note provides a first basic set of parameter sets which are 1451 assumed to cover most relevant applications. Parameter sets for two 1452 classical security levels are defined: 256 and 512 bits. Function 1453 output sizes are n = m = 32 and 64 bytes. Considering quantum- 1454 computer-aided attacks, these output sizes yield post-quantum 1455 security of 128 and 256 bits, respectively. 1457 For the n = m = 32 and n = m = 64 settings, we give parameters that 1458 use SHA2-256 and SHA2-512 as defined in [FIPS180], respectively, and 1459 ChaCha20 as defined in [RFC7539]. SHA2 does not provide a keyed-mode 1460 itself. To implement a keyed hash function, SHA2-256(toByte(0, 1461 32) || KEY || M) and SHA2-512(toByte(0, 64) || KEY || M) are used for 1462 the functions F, H. The "0" padding is necessary as KEY is m bytes 1463 but the internal compression function takes 2m-byte blocks. To 1464 implement H_m, SHA2-256(KEY || M) and SHA2-512(KEY || M) are used, as 1465 KEY in this case is a 2m-byte string. To implement PRF_m, HMAC- 1466 SHA2-256 and HMAC-SHA2-512 are used, respectively. The pseudorandom 1467 generator G for n = 32 is implemented as ChaCha20 using SEED as key, 1468 the most significant 12 bytes of the address input as nonce and the 1469 least significant 4 bytes as counter. The output consists of the 1470 first 32 bytes of the key stream. The pseudorandom generator G for n 1471 = 64 is implemented as HMAC-SHA2-512. 1473 5.1. WOTS+ Parameters 1475 To fully describe a WOTS+ signature method, the parameters m, n, and 1476 w, as well as the functions F and G MUST be specified. This section 1477 defines several WOTS+ signature systems, each of which is identified 1478 by a name. Values for len are provided for convenience. 1480 +------------------------+-------+----------+----+----+----+-----+ 1481 | Name | F | G | m | n | w | len | 1482 +------------------------+-------+----------+----+----+----+-----+ 1483 | WOTSP_SHA2-256_M32_W16 | SHA-2 | ChaCha20 | 32 | 32 | 16 | 67 | 1484 | | | | | | | | 1485 | WOTSP_SHA2-512_M64_W16 | SHA-2 | SHA-2 | 64 | 64 | 16 | 131 | 1486 +------------------------+-------+----------+----+----+----+-----+ 1488 Table 1 1490 The implementation of the single functions is done as described 1491 above. XDR formats for WOTS+ are listed in Appendix A. 1493 5.2. XMSS Parameters 1495 To fully describe an XMSS signature method, the parameters m, n, w, 1496 and h, as well as the functions F, H, H_m, PRF_m, and G MUST be 1497 specified. This section defines different XMSS signature systems, 1498 each of which is identified by a name. We define parameter sets that 1499 implement the functions using SHA2 and ChaCha20 for n = 32 and only 1500 SHA2 for n = 64 as described above. 1502 +---------------------------+----+----+----+-----+----+ 1503 | Name | m | n | w | len | h | 1504 +---------------------------+----+----+----+-----+----+ 1505 | XMSS_SHA2-256_M32_W16_H10 | 32 | 32 | 16 | 67 | 10 | 1506 | | | | | | | 1507 | XMSS_SHA2-256_M32_W16_H16 | 32 | 32 | 16 | 67 | 16 | 1508 | | | | | | | 1509 | XMSS_SHA2-256_M32_W16_H20 | 32 | 32 | 16 | 67 | 20 | 1510 | | | | | | | 1511 | XMSS_SHA2-512_M64_W16_H10 | 64 | 64 | 16 | 131 | 10 | 1512 | | | | | | | 1513 | XMSS_SHA2-512_M64_W16_H16 | 64 | 64 | 16 | 131 | 16 | 1514 | | | | | | | 1515 | XMSS_SHA2-512_M64_W16_H20 | 64 | 64 | 16 | 131 | 20 | 1516 +---------------------------+----+----+----+-----+----+ 1518 Table 2 1520 The XDR formats for XMSS are listed in Appendix B. 1522 5.3. XMSS^MT Parameters 1524 To fully describe an XMSS^MT signature method, the parameters m, n, 1525 w, h, and d, as well as the functions F, H, H_m, PRF_m, and G MUST be 1526 specified. This section defines several XMSS^MT signature systems, 1527 each of which is identified by a name. We define parameter sets that 1528 implement the functions using SHA2 and ChaCha20 for n = 32 and only 1529 SHA2 for n = 64 as described above. 1531 +---------------------------------+----+----+----+-----+----+----+ 1532 | Name | m | n | w | len | h | d | 1533 +---------------------------------+----+----+----+-----+----+----+ 1534 | XMSSMT_SHA2-256_M32_W16_H20_D2 | 32 | 32 | 16 | 67 | 20 | 2 | 1535 | | | | | | | | 1536 | XMSSMT_SHA2-256_M32_W16_H20_D4 | 32 | 32 | 16 | 67 | 20 | 4 | 1537 | | | | | | | | 1538 | XMSSMT_SHA2-256_M32_W16_H40_D2 | 32 | 32 | 16 | 67 | 40 | 2 | 1539 | | | | | | | | 1540 | XMSSMT_SHA2-256_M32_W16_H40_D4 | 32 | 32 | 16 | 67 | 40 | 4 | 1541 | | | | | | | | 1542 | XMSSMT_SHA2-256_M32_W16_H40_D8 | 32 | 32 | 16 | 67 | 40 | 8 | 1543 | | | | | | | | 1544 | XMSSMT_SHA2-256_M32_W16_H60_D3 | 32 | 32 | 16 | 67 | 60 | 3 | 1545 | | | | | | | | 1546 | XMSSMT_SHA2-256_M32_W16_H60_D6 | 32 | 32 | 16 | 67 | 60 | 6 | 1547 | | | | | | | | 1548 | XMSSMT_SHA2-256_M32_W16_H60_D12 | 32 | 32 | 16 | 67 | 60 | 12 | 1549 | | | | | | | | 1550 | XMSSMT_SHA2-512_M64_W16_H20_D2 | 64 | 64 | 16 | 131 | 20 | 2 | 1551 | | | | | | | | 1552 | XMSSMT_SHA2-512_M64_W16_H20_D4 | 64 | 64 | 16 | 131 | 20 | 4 | 1553 | | | | | | | | 1554 | XMSSMT_SHA2-512_M64_W16_H40_D2 | 64 | 64 | 16 | 131 | 40 | 2 | 1555 | | | | | | | | 1556 | XMSSMT_SHA2-512_M64_W16_H40_D4 | 64 | 64 | 16 | 131 | 40 | 4 | 1557 | | | | | | | | 1558 | XMSSMT_SHA2-512_M64_W16_H40_D8 | 64 | 64 | 16 | 131 | 40 | 8 | 1559 | | | | | | | | 1560 | XMSSMT_SHA2-512_M64_W16_H60_D3 | 64 | 64 | 16 | 131 | 60 | 3 | 1561 | | | | | | | | 1562 | XMSSMT_SHA2-512_M64_W16_H60_D6 | 64 | 64 | 16 | 131 | 60 | 6 | 1563 | | | | | | | | 1564 | XMSSMT_SHA2-512_M64_W16_H60_D12 | 64 | 64 | 16 | 131 | 60 | 12 | 1565 +---------------------------------+----+----+----+-----+----+----+ 1567 Table 3 1569 XDR formats for XMSS^MT are listed in Appendix C. 1571 6. Rationale 1573 The goal of this note is to describe the WOTS+, XMSS and XMSS^MT 1574 algorithms following the scientific literature. Other signature 1575 methods are out of scope and may be an interesting follow-on work. 1577 The description is done in a modular way that allows to base a 1578 description of stateless hash-based signature algorithms like SPHINCS 1579 [BHH15] on it. 1581 The draft slightly deviates from the scientific literature using a 1582 tweak that prevents multi-target attacks against the underlying hash- 1583 function. The security assumptions for this tweak are discussed in 1584 Section 8. The main difference to literature is that security now 1585 relies either on the random oracle model or some other seemingly 1586 natural heuristic assumptions. 1588 We suggest the value w = 16 for the Winternitz parameter. No bigger 1589 values are included since the decrease in signature size then becomes 1590 less significant. Furthermore, the value w = 16 considerably 1591 simplifies the implementations of some of the algorithms. Please 1592 note that we do allow w = 4, but limit the specified parameter sets 1593 to w = 16 for efficiency reasons. 1595 The signature and public key formats are designed so that they are 1596 easy to parse. Each format starts with a 32-bit enumeration value 1597 that indicates all of the details of the signature algorithm and 1598 hence defines all of the information that is needed in order to parse 1599 the format. 1601 The enumeration values used in this note are palindromes, which have 1602 the same byte representation in either host order or network order. 1603 This fact allows an implementation to omit the conversion between 1604 byte order for those enumerations. Note however that the idx field 1605 used in XMSS and XMSS^MT signatures and secret keys must be properly 1606 converted to and from network byte order; this is the only field that 1607 requires such conversion. There are 2^32 XDR enumeration values, 1608 2^16 of which are palindromes, which is adequate for the foreseeable 1609 future. If there is a need for more assignments, non-palindromes can 1610 be assigned. 1612 7. IANA Considerations 1614 The Internet Assigned Numbers Authority (IANA) is requested to create 1615 three registries: one for WOTS+ signatures as defined in Section 3, 1616 one for XMSS signatures and one for XMSS^MT signatures; the latter 1617 two being defined in Section 4. For the sake of clarity and 1618 convenience, the first sets of WOTS+, XMSS, and XMSS^MT parameter 1619 sets are defined in Section 5. Additions to these registries require 1620 that a specification be documented in an RFC or another permanent and 1621 readily available reference in sufficient details to make 1622 interoperability between independent implementations possible. Each 1623 entry in the registry contains the following elements: 1625 a short name, such as "XMSS_SHA2-512_M64_W16_H20", 1627 a positive number, and 1629 a reference to a specification that completely defines the 1630 signature method test cases that can be used to verify the 1631 correctness of an implementation. 1633 Requests to add an entry to the registry MUST include the name and 1634 the reference. The number is assigned by IANA. These number 1635 assignments SHOULD use the smallest available palindromic number. 1636 Submitters SHOULD have their requests reviewed by the IRTF Crypto 1637 Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants 1638 that are unfamiliar with IANA processes should visit 1639 http://www.iana.org. 1641 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1642 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1643 are reserved for private use; no attempt will be made to prevent 1644 multiple sites from using the same value in different (and 1645 incompatible) ways [RFC2434]. 1647 The WOTS+ registry is as follows. 1649 +-------------------------+-------------+--------------------+ 1650 | Name | Reference | Numeric Identifier | 1651 +-------------------------+-------------+--------------------+ 1652 | WOTSP_SHA2-256_M32_W16 | Section 5.1 | 0x01000001 | 1653 | | | | 1654 | WOTSP_SHA2-512_M64_W16 | Section 5.1 | 0x02000002 | 1655 +-------------------------+-------------+--------------------+ 1657 Table 4 1659 The XMSS registry is as follows. 1661 +----------------------------+-------------+--------------------+ 1662 | Name | Reference | Numeric Identifier | 1663 +----------------------------+-------------+--------------------+ 1664 | XMSS_SHA2-256_M32_W16_H10 | Section 5.2 | 0x01000001 | 1665 | | | | 1666 | XMSS_SHA2-256_M32_W16_H16 | Section 5.2 | 0x02000002 | 1667 | | | | 1668 | XMSS_SHA2-256_M32_W16_H20 | Section 5.2 | 0x03000003 | 1669 | | | | 1670 | XMSS_SHA2-512_M64_W16_H10 | Section 5.2 | 0x04000004 | 1671 | | | | 1672 | XMSS_SHA2-512_M64_W16_H16 | Section 5.2 | 0x05000005 | 1673 | | | | 1674 | XMSS_SHA2-512_M64_W16_H20 | Section 5.2 | 0x06000006 | 1675 +----------------------------+-------------+--------------------+ 1677 Table 5 1679 The XMSS^MT registry is as follows. 1681 +---------------------------------+-------------+-------------------+ 1682 | Name | Reference | Numeric | 1683 | | | Identifier | 1684 +---------------------------------+-------------+-------------------+ 1685 | XMSSMT_SHA2-256_M32_W16_H20_D2 | Section 5.3 | 0x01000001 | 1686 | | | | 1687 | XMSSMT_SHA2-256_M32_W16_H20_D4 | Section 5.3 | 0x02000002 | 1688 | | | | 1689 | XMSSMT_SHA2-256_M32_W16_H40_D2 | Section 5.3 | 0x03000003 | 1690 | | | | 1691 | XMSSMT_SHA2-256_M32_W16_H40_D4 | Section 5.3 | 0x04000004 | 1692 | | | | 1693 | XMSSMT_SHA2-256_M32_W16_H40_D8 | Section 5.3 | 0x05000005 | 1694 | | | | 1695 | XMSSMT_SHA2-256_M32_W16_H60_D3 | Section 5.3 | 0x06000006 | 1696 | | | | 1697 | XMSSMT_SHA2-256_M32_W16_H60_D6 | Section 5.3 | 0x07000007 | 1698 | | | | 1699 | XMSSMT_SHA2-256_M32_W16_H60_D12 | Section 5.3 | 0x08000008 | 1700 | | | | 1701 | XMSSMT_SHA2-512_M64_W16_H20_D2 | Section 5.3 | 0x09000009 | 1702 | | | | 1703 | XMSSMT_SHA2-512_M64_W16_H20_D4 | Section 5.3 | 0x0a00000a | 1704 | | | | 1705 | XMSSMT_SHA2-512_M64_W16_H40_D2 | Section 5.3 | 0x0b00000b | 1706 | | | | 1707 | XMSSMT_SHA2-512_M64_W16_H40_D4 | Section 5.3 | 0x0c00000c | 1708 | | | | 1709 | XMSSMT_SHA2-512_M64_W16_H40_D8 | Section 5.3 | 0x0d00000d | 1710 | | | | 1711 | XMSSMT_SHA2-512_M64_W16_H60_D3 | Section 5.3 | 0x0e00000e | 1712 | | | | 1713 | XMSSMT_SHA2-512_M64_W16_H60_D6 | Section 5.3 | 0x0f00000f | 1714 | | | | 1715 | XMSSMT_SHA2-512_M64_W16_H60_D12 | Section 5.3 | 0x01010101 | 1716 +---------------------------------+-------------+-------------------+ 1718 Table 6 1720 An IANA registration of a signature system does not constitute an 1721 endorsement of that system or its security. 1723 8. Security Considerations 1725 A signature system is considered secure if it prevents an attacker 1726 from forging a valid signature. More specifically, consider a 1727 setting in which an attacker gets a public key and can learn 1728 signatures on arbitrary messages of his choice. A signature system 1729 is secure if, even in this setting, the attacker can not produce a 1730 new message signature pair of his choosing such that the verification 1731 algorithm accepts. 1733 Preventing an attacker from mounting an attack means that the attack 1734 is computationally too expensive to be carried out. There exist 1735 various estimates when a computation is too expensive to be done. 1736 For that reason, this note only describes how expensive it is for an 1737 attacker to generate a forgery. Parameters are accompanied by a bit 1738 security value. The meaning of bit security is as follows. A 1739 parameter set grants b bits of security if the best attack takes at 1740 least 2^(b - 1) bit operations to achieve a success probability of 1741 1/2. Hence, to mount a successful attack, an attacker needs to 1742 perform 2^b bit operations on average. The given values for bit 1743 security were estimated according to [HRS16]. 1745 8.1. Security Proofs 1747 A full security proof for the scheme described here can be found in 1748 [HRS16]. This proof shows that an attacker has to break at least one 1749 out of certain security properties of the used hash functions and 1750 PRFs to forge a signature. The proof in [HRS16] considers a 1751 different initial message compression than the "indexed" randomized 1752 hashing used here. We comment on this below. For the original 1753 schemes, these proofs show that an attacker has to break certain 1754 minimal security properties. In particular, it is not sufficient to 1755 break the collision resistance of the hash functions to generate a 1756 forgery. 1758 The proof in [HRS16] considers classical randomized hashing for the 1759 initial message compression, i.e., H(r, M) instead of H(idx || r, M). 1760 While the classical randomized hashing used in [HRS16] allows to 1761 prove that it is not enough for an adversary to break the collision 1762 resistance of the underlying hash function, it turns out that an 1763 attacker could launch a multi-target attack. The reason is that the 1764 adversary learns 2^h randomized hashes H(r_i || M_i) with calling 1765 index i being an element of [0, 2^h - 1] and it suffices to find a 1766 pair (r*, M*) such that H(r* || M*) = H(r_i || M_i) for one out of 1767 the 2^h learned hashes. Hence, an attacker can do a brute force 1768 search in time 2^n / 2^h instead of 2^n. 1770 The indexed randomized hashing H(toByte(idx, m) || r, M) used here 1771 makes the hash function calls position-dependent. This thwarts the 1772 above attack because each hash function evaluation during an attack 1773 can only target one of the learned randomized hash values. More 1774 specifically, an attacker now has to decide which index idx to use 1775 for each query. This can also be shown formally in a black box 1776 model. 1778 The given bit security values were estimated based on the complexity 1779 of the best known generic attacks against the required security 1780 properties of the used hash functions and PRFs. 1782 8.2. Security Assumptions 1784 The security assumptions made to argue for the security of the 1785 described schemes are minimal. Any signature algorithm that allows 1786 arbitrary size messages relies on the security of a cryptographic 1787 hash function. For the schemes described here this is already 1788 sufficient to be secure. In contrast, common signature schemes like 1789 RSA, DSA, and ECDSA additionally rely on the conjectured hardness of 1790 certain mathematical problems. 1792 8.3. Post-Quantum Security 1794 A post-quantum cryptosystem is a system that is secure against 1795 attackers with access to a reasonably sized quantum computer. At the 1796 time of writing this note, whether or not it is feasible to build 1797 such machine is an open conjecture. However, significant progress 1798 was made over the last few years in this regard. 1800 In contrast to RSA, DSA, and ECDSA, the described signature systems 1801 are post-quantum-secure if they are used with an appropriate 1802 cryptographic hash function. In particular, for post-quantum 1803 security, the size of m and n must be twice the size required for 1804 classical security. This is in order to protect against quantum 1805 square root attacks due to Grover's algorithm. It has been shown in 1806 [HRS16] that variants of Grover's algorithm are optimal for attacking 1807 the security properties of hash functions required for the described 1808 scheme. 1810 9. Acknowledgements 1812 We would like to thank Scott Fluhrer, Burt Kaliski, Adam Langley, 1813 David McGrew, Sean Parkinson, and Joost Rijneveld for their help and 1814 comments. 1816 10. References 1818 10.1. Normative References 1820 [FIPS180] National Institute of Standards and Technology, "Secure 1821 Hash Standard (SHS)", FIPS 180-4, 2012. 1823 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1824 Requirement Levels", BCP 14, RFC 2119, 1825 DOI 10.17487/RFC2119, March 1997, 1826 . 1828 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1829 IANA Considerations Section in RFCs", RFC 2434, 1830 DOI 10.17487/RFC2434, October 1998, 1831 . 1833 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 1834 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 1835 2006, . 1837 [RFC7539] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF 1838 Protocols", RFC 7539, DOI 10.17487/RFC7539, May 2015, 1839 . 1841 10.2. Informative References 1843 [BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A 1844 Practical Forward Secure Signature Scheme Based on Minimal 1845 Security Assumptions", Lecture Notes in Computer Science 1846 volume 7071. Post-Quantum Cryptography, 2011. 1848 [BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based 1849 Digital Signature Schemes", Book chapter Post-Quantum 1850 Cryptography, Springer, 2009. 1852 [BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., 1853 Niederhagen, R., Papachristodoulou, L., Schneider, M., 1854 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical 1855 Stateless Hash-Based Signatures", Lecture Notes in 1856 Computer Science volume 9056. Advances in Cryptology - 1857 EUROCRYPT, 2015. 1859 [DC15] McGrew, D. and M. Curcio, "Hash-based signatures", draft- 1860 mcgrew-hash-sigs-03 (work in progress), October 2015. 1862 [HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal 1863 Parameters for XMSS^MT", Lecture Notes in Computer Science 1864 volume 8128. CD-ARES, 2013. 1866 [HRS16] Huelsing, A., Rijneveld, J., and F. Song, "Mitigating 1867 Multi-Target Attacks in Hash-based Signatures", Lecture 1868 Notes in Computer Science volume 9614. Public-Key 1869 Cryptography - PKC 2016, 2016. 1871 [Huelsing13] 1872 Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based 1873 Signature Schemes", Lecture Notes in Computer Science 1874 volume 7918. Progress in Cryptology - AFRICACRYPT, 2013. 1876 [Huelsing13a] 1877 Huelsing, A., "Practical Forward Secure Signatures using 1878 Minimal Security Assumptions", PhD thesis TU Darmstadt, 1879 2013. 1881 [Kaliski15] 1882 Kaliski, B., "Panel: Shoring up the Infrastructure: A 1883 Strategy for Standardizing Hash Signatures", NIST Workshop 1884 on Cybersecurity in a Post-Quantum World, 2015. 1886 [Merkle79] 1887 Merkle, R., "Secrecy, Authentication, and Public Key 1888 Systems", Stanford University Information Systems 1889 Laboratory Technical Report 1979-1, 1979. 1891 Appendix A. WOTS+ XDR Formats 1893 The WOTS+ signature and public key formats are formally defined using 1894 XDR [RFC4506] in order to provide an unambiguous, machine readable 1895 definition. Though XDR is used, these formats are simple and easy to 1896 parse without any special tools. To avoid the need to convert to and 1897 from network / host byte order, the enumeration values are all 1898 palindromes. 1900 WOTS+ parameter sets are defined using XDR syntax as follows: 1902 /* ots_algorithm_type identifies a particular 1903 signature algorithm */ 1905 enum ots_algorithm_type { 1906 wotsp_reserved = 0x00000000, 1907 wotsp_sha2-256_m32_w16 = 0x01000001, 1908 wotsp_sha2-512_m64_w16 = 0x02000002, 1909 }; 1911 WOTS+ signatures are defined using XDR syntax as follows: 1913 /* Byte strings */ 1915 typedef opaque bytestring32[32]; 1916 typedef opaque bytestring64[64]; 1918 union ots_signature switch (ots_algorithm_type type) { 1919 case wotsp_sha2-256_m32_w16: 1920 bytestring32 ots_sig_m32_len67[67]; 1922 case wotsp_sha2-512_m64_w16: 1923 bytestring64 ots_sig_m64_len18[131]; 1925 default: 1926 void; /* error condition */ 1927 }; 1929 WOTS+ public keys are defined using XDR syntax as follows: 1931 union ots_pubkey switch (ots_algorithm_type type) { 1932 case wotsp_sha2-256_m32_w16: 1933 bytestring32 ots_pubk_m32_len67[67]; 1935 case wotsp_sha2-512_m64_w16: 1936 bytestring64 ots_pubk_m64_len18[131]; 1938 default: 1939 void; /* error condition */ 1940 }; 1942 Appendix B. XMSS XDR Formats 1943 XMSS parameter sets are defined using XDR syntax as follows: 1945 /* Byte strings */ 1947 typedef opaque bytestring4[4]; 1949 /* Definition of parameter sets */ 1951 enum xmss_algorithm_type { 1952 xmss_reserved = 0x00000000, 1954 /* 256 bit classical security, 128 bit post-quantum security */ 1956 xmss_sha2-256_m32_w16_h10 = 0x01000001, 1957 xmss_sha2-256_m32_w16_h16 = 0x02000002, 1958 xmss_sha2-256_m32_w16_h20 = 0x03000003, 1960 /* 512 bit classical security, 256 bit post-quantum security */ 1962 xmss_sha2-512_m64_w16_h10 = 0x04000004, 1963 xmss_sha2-512_m64_w16_h16 = 0x05000005, 1964 xmss_sha2-512_m64_w16_h20 = 0x06000006, 1965 }; 1967 XMSS signatures are defined using XDR syntax as follows: 1969 /* Authentication path types */ 1971 union xmss_path switch (xmss_algorithm_type type) { 1972 case xmss_sha2-256_m32_w16_h10: 1973 bytestring32 path_n32_t10[10]; 1975 case xmss_sha2-256_m32_w16_h16: 1976 bytestring32 path_n32_t16[16]; 1978 case xmss_sha2-256_m32_w16_h20: 1979 bytestring32 path_n32_t20[20]; 1981 case xmss_sha2-512_m64_w16_h10: 1982 bytestring64 path_n64_t10[10]; 1984 case xmss_sha2-512_m64_w16_h16: 1985 bytestring64 path_n64_t16[16]; 1987 case xmss_sha2-512_m64_w16_h20: 1989 bytestring64 path_n64_t20[20]; 1991 default: 1992 void; /* error condition */ 1993 }; 1995 /* Types for XMSS random strings */ 1997 union random_string_xmss switch (xmss_algorithm_type type) { 1998 case xmss_sha2-256_m32_w16_h10: 1999 case xmss_sha2-256_m32_w16_h16: 2000 case xmss_sha2-256_m32_w16_h20: 2001 bytestring32 rand_m32; 2003 case xmss_sha2-512_m64_w16_h10: 2004 case xmss_sha2-512_m64_w16_h16: 2005 case xmss_sha2-512_m64_w16_h20: 2006 bytestring64 rand_m64; 2008 default: 2009 void; /* error condition */ 2010 }; 2012 /* Corresponding WOTS+ type for given XMSS type */ 2014 union xmss_ots_signature switch (xmss_algorithm_type type) { 2015 case xmss_sha2-256_m32_w16_h10: 2016 case xmss_sha2-256_m32_w16_h16: 2017 case xmss_sha2-256_m32_w16_h20: 2018 wotsp_sha2-256_m32_w16; 2020 case xmss_sha2-512_m64_w16_h10: 2021 case xmss_sha2-512_m64_w16_h16: 2022 case xmss_sha2-512_m64_w16_h20: 2023 wotsp_sha2-512_m64_w16; 2025 default: 2026 void; /* error condition */ 2027 }; 2029 /* XMSS signature structure */ 2031 struct xmss_signature { 2032 /* WOTS+ key pair index */ 2033 bytestring4 idx_sig; 2034 /* Random string for randomized hashing */ 2035 random_string_xmss rand_string; 2036 /* WOTS+ signature */ 2037 xmss_ots_signature sig_ots; 2038 /* authentication path */ 2039 xmss_path nodes; 2040 }; 2042 XMSS public keys are defined using XDR syntax as follows: 2044 /* Types for bitmask seed */ 2046 union seed switch (xmss_algorithm_type type) { 2047 case xmss_sha2-256_m32_w16_h10: 2048 case xmss_sha2-256_m32_w16_h16: 2049 case xmss_sha2-256_m32_w16_h20: 2050 bytestring32 seed_n32; 2052 case xmss_sha2-512_m64_w16_h10: 2053 case xmss_sha2-512_m64_w16_h16: 2054 case xmss_sha2-512_m64_w16_h20: 2055 bytestring64 seed_n64; 2057 default: 2058 void; /* error condition */ 2059 }; 2061 /* Types for XMSS root node */ 2063 union xmss_root switch (xmss_algorithm_type type) { 2064 case xmss_sha2-256_m32_w16_h10: 2065 case xmss_sha2-256_m32_w16_h16: 2066 case xmss_sha2-256_m32_w16_h20: 2067 bytestring32 root_n32; 2069 case xmss_sha2-512_m64_w16_h10: 2070 case xmss_sha2-512_m64_w16_h16: 2071 case xmss_sha2-512_m64_w16_h20: 2072 bytestring64 root_n64; 2074 default: 2075 void; /* error condition */ 2076 }; 2078 /* XMSS public key structure */ 2080 struct xmss_public_key { 2081 xmss_root root; /* Root node */ 2082 seed SEED; /* Seed for bitmasks */ 2083 }; 2085 Appendix C. XMSS^MT XDR Formats 2087 XMSS^MT parameter sets are defined using XDR syntax as follows: 2089 /* Byte strings */ 2091 typedef opaque bytestring3[3]; 2092 typedef opaque bytestring5[5]; 2093 typedef opaque bytestring8[8]; 2095 /* Definition of parameter sets */ 2097 enum xmssmt_algorithm_type { 2098 xmssmt_reserved = 0x00000000, 2100 /* 256 bit classical security, 128 bit post-quantum security */ 2102 xmssmt_sha2-256_m32_w16_h20_d2 = 0x01000001, 2103 xmssmt_sha2-256_m32_w16_h20_d4 = 0x02000002, 2104 xmssmt_sha2-256_m32_w16_h40_d2 = 0x03000003, 2105 xmssmt_sha2-256_m32_w16_h40_d4 = 0x04000004, 2106 xmssmt_sha2-256_m32_w16_h40_d8 = 0x05000005, 2107 xmssmt_sha2-256_m32_w16_h60_d3 = 0x06000006, 2108 xmssmt_sha2-256_m32_w16_h60_d6 = 0x07000007, 2109 xmssmt_sha2-256_m32_w16_h60_d12 = 0x08000008, 2111 /* 512 bit classical security, 256 bit post-quantum security */ 2113 xmssmt_sha2-512_m64_w16_h20_d2 = 0x09000009, 2114 xmssmt_sha2-512_m64_w16_h20_d4 = 0x0a00000a, 2115 xmssmt_sha2-512_m64_w16_h40_d2 = 0x0b00000b, 2116 xmssmt_sha2-512_m64_w16_h40_d4 = 0x0c00000c, 2117 xmssmt_sha2-512_m64_w16_h40_d8 = 0x0d00000d, 2118 xmssmt_sha2-512_m64_w16_h60_d3 = 0x0e00000e, 2119 xmssmt_sha2-512_m64_w16_h60_d6 = 0x0f00000f, 2120 xmssmt_sha2-512_m64_w16_h60_d12 = 0x01010101, 2121 }; 2123 XMSS^MT signatures are defined using XDR syntax as follows: 2125 /* Type for XMSS^MT key pair index */ 2126 /* Depends solely on h */ 2128 union idx_sig_xmssmt switch (xmss_algorithm_type type) { 2129 case xmssmt_sha2-256_m32_w16_h20_d2: 2131 case xmssmt_sha2-256_m32_w16_h20_d4: 2132 case xmssmt_sha2-512_m64_w16_h20_d2: 2133 case xmssmt_sha2-512_m64_w16_h20_d4: 2134 bytestring3 idx3; 2136 case xmssmt_sha2-256_m32_w16_h40_d2: 2137 case xmssmt_sha2-256_m32_w16_h40_d4: 2138 case xmssmt_sha2-256_m32_w16_h40_d8: 2139 case xmssmt_sha2-512_m64_w16_h40_d2: 2140 case xmssmt_sha2-512_m64_w16_h40_d4: 2141 case xmssmt_sha2-512_m64_w16_h40_d8: 2142 bytestring5 idx5; 2144 case xmssmt_sha2-256_m32_w16_h60_d3: 2145 case xmssmt_sha2-256_m32_w16_h60_d6: 2146 case xmssmt_sha2-256_m32_w16_h60_d12: 2147 case xmssmt_sha2-512_m64_w16_h60_d3: 2148 case xmssmt_sha2-512_m64_w16_h60_d6: 2149 case xmssmt_sha2-512_m64_w16_h60_d12: 2150 bytestring8 idx8; 2152 default: 2153 void; /* error condition */ 2154 }; 2156 union random_string_xmssmt switch (xmssmt_algorithm_type type) { 2157 case xmssmt_sha2-256_m32_w16_h20_d2: 2158 case xmssmt_sha2-256_m32_w16_h20_d4: 2159 case xmssmt_sha2-256_m32_w16_h40_d2: 2160 case xmssmt_sha2-256_m32_w16_h40_d4: 2161 case xmssmt_sha2-256_m32_w16_h40_d8: 2162 case xmssmt_sha2-256_m32_w16_h60_d3: 2163 case xmssmt_sha2-256_m32_w16_h60_d6: 2164 case xmssmt_sha2-256_m32_w16_h60_d12: 2165 bytestring32 rand_m32; 2167 case xmssmt_sha2-512_m64_w16_h20_d2: 2168 case xmssmt_sha2-512_m64_w16_h20_d4: 2169 case xmssmt_sha2-512_m64_w16_h40_d2: 2170 case xmssmt_sha2-512_m64_w16_h40_d4: 2171 case xmssmt_sha2-512_m64_w16_h40_d8: 2172 case xmssmt_sha2-512_m64_w16_h60_d3: 2173 case xmssmt_sha2-512_m64_w16_h60_d6: 2174 case xmssmt_sha2-512_m64_w16_h60_d12: 2175 bytestring64 rand_m64; 2177 default: 2178 void; /* error condition */ 2180 }; 2182 union xmss_reduced_bottom (xmss_algorithm_type type) { 2183 case xmssmt_sha2-256_m32_w16_h20_d2: 2184 case xmssmt_sha2-256_m32_w16_h40_d4: 2185 case xmssmt_sha2-256_m32_w16_h60_d6: 2186 bytestring32 xmss_reduced_n32_t77[77]; 2188 case xmssmt_sha2-256_m32_w16_h20_d4: 2189 case xmssmt_sha2-256_m32_w16_h40_d8: 2190 case xmssmt_sha2-256_m32_w16_h60_d12: 2191 bytestring32 xmss_reduced_n32_t72[72]; 2193 case xmssmt_sha2-256_m32_w16_h40_d2: 2194 case xmssmt_sha2-256_m32_w16_h60_d3: 2195 bytestring32 xmss_reduced_n32_t87[87]; 2197 case xmssmt_sha2-512_m64_w16_h20_d2: 2198 case xmssmt_sha2-512_m64_w16_h40_d4: 2199 case xmssmt_sha2-512_m64_w16_h60_d6: 2200 bytestring64 xmss_reduced_n32_t141[141]; 2202 case xmssmt_sha2-512_m64_w16_h20_d4: 2203 case xmssmt_sha2-512_m64_w16_h40_d8: 2204 case xmssmt_sha2-512_m64_w16_h60_d12: 2205 bytestring64 xmss_reduced_n32_t136[136]; 2207 case xmssmt_sha2-512_m64_w16_h40_d2: 2208 case xmssmt_sha2-512_m64_w16_h60_d3: 2209 bytestring64 xmss_reduced_n32_t151[151]; 2211 default: 2212 void; /* error condition */ 2213 }; 2215 /* Type for individual reduced XMSS signatures on higher layers */ 2217 union xmss_reduced_others (xmss_algorithm_type type) { 2218 case xmssmt_sha2-256_m32_w16_h20_d2: 2219 case xmssmt_sha2-256_m32_w16_h40_d4: 2220 case xmssmt_sha2-256_m32_w16_h60_d6: 2221 bytestring32 xmss_reduced_n32_t77[77]; 2223 case xmssmt_sha2-256_m32_w16_h20_d4: 2224 case xmssmt_sha2-256_m32_w16_h40_d8: 2225 case xmssmt_sha2-256_m32_w16_h60_d12: 2226 bytestring32 xmss_reduced_n32_t72[72]; 2228 case xmssmt_sha2-256_m32_w16_h40_d2: 2229 case xmssmt_sha2-256_m32_w16_h60_d3: 2230 bytestring32 xmss_reduced_n32_t87[87]; 2232 case xmssmt_sha2-512_m64_w16_h20_d2: 2233 case xmssmt_sha2-512_m64_w16_h40_d4: 2234 case xmssmt_sha2-512_m64_w16_h60_d6: 2235 bytestring64 xmss_reduced_n32_t141[141]; 2237 case xmssmt_sha2-512_m64_w16_h20_d4: 2238 case xmssmt_sha2-512_m64_w16_h40_d8: 2239 case xmssmt_sha2-512_m64_w16_h60_d12: 2240 bytestring64 xmss_reduced_n32_t136[136]; 2242 case xmssmt_sha2-512_m64_w16_h40_d2: 2243 case xmssmt_sha2-512_m64_w16_h60_d3: 2244 bytestring64 xmss_reduced_n32_t151[151]; 2246 default: 2247 void; /* error condition */ 2248 }; 2250 /* xmss_reduced_array depends on d */ 2252 union xmss_reduced_array (xmss_algorithm_type type) { 2253 case xmssmt_sha2-256_m32_w16_h20_d2: 2254 case xmssmt_sha2-512_m64_w16_h20_d2: 2255 case xmssmt_sha2-256_m32_w16_h40_d2: 2256 case xmssmt_sha2-512_m64_w16_h40_d2: 2257 xmss_reduced_others xmss_red_arr_d2[1]; 2259 case xmssmt_sha2-256_m32_w16_h60_d3: 2260 case xmssmt_sha2-512_m64_w16_h60_d3: 2261 xmss_reduced_others xmss_red_arr_d3[2]; 2263 case xmssmt_sha2-256_m32_w16_h20_d4: 2264 case xmssmt_sha2-512_m64_w16_h20_d4: 2265 case xmssmt_sha2-256_m32_w16_h40_d4: 2266 case xmssmt_sha2-512_m64_w16_h40_d4: 2267 xmss_reduced_others xmss_red_arr_d4[3]; 2269 case xmssmt_sha2-256_m32_w16_h60_d6: 2270 case xmssmt_sha2-512_m64_w16_h60_d6: 2271 xmss_reduced_others xmss_red_arr_d6[5]; 2273 case xmssmt_sha2-256_m32_w16_h40_d8: 2274 case xmssmt_sha2-512_m64_w16_h40_d8: 2275 xmss_reduced_others xmss_red_arr_d8[7]; 2277 case xmssmt_sha2-256_m32_w16_h60_d12: 2278 case xmssmt_sha2-512_m64_w16_h60_d12: 2279 xmss_reduced_others xmss_red_arr_d12[11]; 2281 default: 2282 void; /* error condition */ 2283 }; 2285 /* XMSS^MT signature structure */ 2287 struct xmssmt_signature { 2288 /* WOTS+ key pair index */ 2289 idx_sig_xmssmt idx_sig; 2290 /* Random string for randomized hashing */ 2291 random_string_xmssmt randomness; 2292 /* Reduced bottom layer XMSS signature */ 2293 xmss_reduced_bottom; 2294 /* Array of reduced XMSS signatures with message length n */ 2295 xmss_reduced_array; 2296 }; 2298 XMSS^MT public keys are defined using XDR syntax as follows: 2300 /* Types for bitmask seed */ 2302 union seed switch (xmssmt_algorithm_type type) { 2303 case xmssmt_sha2-256_m32_w16_h20_d2: 2304 case xmssmt_sha2-256_m32_w16_h40_d4: 2305 case xmssmt_sha2-256_m32_w16_h60_d6: 2306 case xmssmt_sha2-256_m32_w16_h20_d4: 2307 case xmssmt_sha2-256_m32_w16_h40_d8: 2308 case xmssmt_sha2-256_m32_w16_h60_d12: 2309 case xmssmt_sha2-256_m32_w16_h40_d2: 2310 case xmssmt_sha2-256_m32_w16_h60_d3: 2311 bytestring32 seed_n32; 2313 case xmssmt_sha2-512_m64_w16_h20_d2: 2314 case xmssmt_sha2-512_m64_w16_h40_d4: 2315 case xmssmt_sha2-512_m64_w16_h60_d6: 2316 case xmssmt_sha2-512_m64_w16_h20_d4: 2317 case xmssmt_sha2-512_m64_w16_h40_d8: 2318 case xmssmt_sha2-512_m64_w16_h60_d12: 2319 case xmssmt_sha2-512_m64_w16_h40_d2: 2320 case xmssmt_sha2-512_m64_w16_h60_d3: 2321 bytestring64 seed_n64; 2323 default: 2324 void; /* error condition */ 2325 }; 2327 /* Types for XMSS^MT root node */ 2329 union xmssmt_root switch (xmssmt_algorithm_type type) { 2330 case xmssmt_sha2-256_m32_w16_h20_d2: 2331 case xmssmt_sha2-256_m32_w16_h20_d4: 2332 case xmssmt_sha2-256_m32_w16_h40_d2: 2333 case xmssmt_sha2-256_m32_w16_h40_d4: 2334 case xmssmt_sha2-256_m32_w16_h40_d8: 2335 case xmssmt_sha2-256_m32_w16_h60_d3: 2336 case xmssmt_sha2-256_m32_w16_h60_d6: 2337 case xmssmt_sha2-256_m32_w16_h60_d12: 2338 bytestring32 root_n32; 2340 case xmssmt_sha2-512_m64_w16_h20_d2: 2341 case xmssmt_sha2-512_m64_w16_h20_d4: 2342 case xmssmt_sha2-512_m64_w16_h40_d2: 2343 case xmssmt_sha2-512_m64_w16_h40_d4: 2344 case xmssmt_sha2-512_m64_w16_h40_d8: 2345 case xmssmt_sha2-512_m64_w16_h60_d3: 2346 case xmssmt_sha2-512_m64_w16_h60_d6: 2347 case xmssmt_sha2-512_m64_w16_h60_d12: 2348 bytestring64 root_n64; 2350 default: 2351 void; /* error condition */ 2352 }; 2354 /* XMSS^MT public key structure */ 2356 struct xmssmt_public_key { 2357 xmssmt_root root; /* Root node */ 2358 seed SEED; /* Seed for bitmasks */ 2359 }; 2361 Appendix D. Changed since draft-irtf-cfrg-xmss-hash-based-signatures-02 2363 1: Changed comment for endianness of data types from "If not stated 2364 or handled otherwise, we assume big-endian representation for any 2365 data types." to "We assume big-endian representation for any data 2366 types or structures." as we don't use little-endian representation 2367 any more. 2369 2: Changed the addresses for the hash function address scheme. 2371 2.1: Rearranged address elements to comply with byte- and word-orders 2372 (but the tree address which is larger than a word). 2374 2.2: Tree height and tree index for the l-tree addresses were 2375 increased to match a hash tree address. 2377 3: Notation of member functions is now explained in more detail. 2379 4: Sizes for the reduced signatures as part of an XMSS^MT signature 2380 were corrected: 2382 Bottom layer: (h + len) * n bytes is now (h / d + len) * n bytes 2384 Other layers: (h + len_n) * n bytes is now (h / d + len_n) * n bytes 2386 5: For Algorithm 16, getXMSSSignature is now explained in the text. 2387 Sig was changed to Sig_MT. 2389 6: Some minor typo fixes. 2391 7: Randomized hashing for message compression now takes index as part 2392 of the key argument. 2394 8: Security considerations updated. Taking the new proofs in [HRS16] 2395 into account. 2397 9: XDR formats for reduced XMSS signatures inside the XMSS^MT 2398 signature format were corrected. 2400 Authors' Addresses 2402 Andreas Huelsing 2403 TU Eindhoven 2404 P.O. Box 513 2405 Eindhoven 5600 MB 2406 The Netherlands 2408 Email: ietf@huelsing.net 2410 Denis Butin 2411 TU Darmstadt 2412 Hochschulstrasse 10 2413 Darmstadt 64289 2414 Germany 2416 Email: dbutin@cdc.informatik.tu-darmstadt.de 2417 Stefan-Lukas Gazdag 2418 genua GmbH 2419 Domagkstrasse 7 2420 Kirchheim bei Muenchen 85551 2421 Germany 2423 Email: stefan-lukas_gazdag@genua.eu 2425 Aziz Mohaisen 2426 SUNY Buffalo 2427 323 Davis Hall 2428 Buffalo, NY 14260 2429 US 2431 Phone: +1 716 645-1592 2432 Email: mohaisen@buffalo.edu