idnits 2.17.1 draft-irtf-cfrg-xmss-hash-based-signatures-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 3, 2015) is 3214 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 1110 -- Looks like a reference, but probably isn't: '1' on line 2199 -- Looks like a reference, but probably isn't: '2' on line 2203 -- Looks like a reference, but probably isn't: '3' on line 2209 -- Looks like a reference, but probably isn't: '4' on line 1916 -- Looks like a reference, but probably isn't: '5' on line 2213 -- Looks like a reference, but probably isn't: '6' on line 465 -- Looks like a reference, but probably isn't: '7' on line 2217 == Missing Reference: '2i' is mentioned on line 863, but not defined -- Looks like a reference, but probably isn't: '32' on line 1884 -- Looks like a reference, but probably isn't: '64' on line 1885 -- Looks like a reference, but probably isn't: '67' on line 1902 -- Looks like a reference, but probably isn't: '131' on line 1905 -- Looks like a reference, but probably isn't: '10' on line 1951 -- Looks like a reference, but probably isn't: '16' on line 1954 -- Looks like a reference, but probably isn't: '20' on line 1958 -- Looks like a reference, but probably isn't: '8' on line 2062 -- Looks like a reference, but probably isn't: '87' on line 2161 -- Looks like a reference, but probably isn't: '107' on line 2166 -- Looks like a reference, but probably isn't: '127' on line 2171 -- Looks like a reference, but probably isn't: '151' on line 2175 -- Looks like a reference, but probably isn't: '171' on line 2180 -- Looks like a reference, but probably isn't: '191' on line 2185 -- Looks like a reference, but probably isn't: '11' on line 2221 ** 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-02 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 25 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: January 4, 2016 TU Darmstadt 6 S. Gazdag 7 genua GmbH 8 A. Mohaisen 9 Verisign Labs 10 July 3, 2015 12 XMSS: Extended Hash-Based Signatures 13 draft-irtf-cfrg-xmss-hash-based-signatures-01 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 January 4, 2016. 50 Copyright Notice 52 Copyright (c) 2015 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 . . . . . . . . . . . . . . . . 26 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 . . . . . . . . . . . . . . . . . . 28 107 4.2.6. XMSS^MT Signature Generation . . . . . . . . . . . . 29 108 4.2.7. XMSS^MT Signature Verification . . . . . . . . . . . 31 109 4.2.8. Pseudorandom Key Generation . . . . . . . . . . . . . 31 110 4.2.9. Free Index Handling and Partial Secret Keys . . . . . 32 111 5. Parameter Sets . . . . . . . . . . . . . . . . . . . . . . . 32 112 5.1. WOTS+ Parameters . . . . . . . . . . . . . . . . . . . . 32 113 5.2. XMSS Parameters . . . . . . . . . . . . . . . . . . . . . 33 114 5.3. XMSS^MT Parameters . . . . . . . . . . . . . . . . . . . 33 115 6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 34 116 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35 117 8. Security Considerations . . . . . . . . . . . . . . . . . . . 38 118 8.1. Security Proofs . . . . . . . . . . . . . . . . . . . . . 39 119 8.2. Security Assumptions . . . . . . . . . . . . . . . . . . 40 120 8.3. Post-Quantum Security . . . . . . . . . . . . . . . . . . 40 121 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 40 122 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 41 123 10.1. Normative References . . . . . . . . . . . . . . . . . . 41 124 10.2. Informative References . . . . . . . . . . . . . . . . . 41 125 Appendix A. WOTS+ XDR Formats . . . . . . . . . . . . . . . . . 42 126 Appendix B. XMSS XDR Formats . . . . . . . . . . . . . . . . . . 43 127 Appendix C. XMSS^MT XDR Formats . . . . . . . . . . . . . . . . 48 128 Appendix D. Changed since draft-irtf-cfrg-xmss-hash-based- 129 signatures-00 . . . . . . . . . . . . . . . . . . . 53 130 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 54 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 [DC14] specifying the "textbook" Lamport-Diffie- 158 Winternitz-Merkle (LDWM) scheme based on early publications. 159 Independently, Buchmann, Dahmen and Huelsing have proposed XMSS 160 [BDH11], the eXtended Merkle Signature Scheme, offering better 161 efficiency and a modern security proof. Very recently, the stateless 162 hash-based signature scheme SPHINCS was introduced [BHH15], with the 163 intent of being easier to deploy in current applications. A 164 reasonable next step toward introducing hash-based signatures would 165 be to complete the specifications of the basic algorithms - LDWM, 166 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. If not stated or handled otherwise, we assume 209 big-endian representation of data types. 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 a 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) the 268 y-byte representation of x as the y-byte string that contains the 269 binary representation of x padded with zeros in the most significant 270 bit positions in little endian byte-order. 272 2.5. Hash Function Address Scheme 274 The schemes described in this document randomize each hash function 275 call. This means that aside of the initial message digest, for each 276 hash function call a different key and different bitmask is used. 277 These values are pseudorandomly generated using a pseudorandom 278 generator that takes a seed S and a 16-byte address A. The latter is 279 used to select the A-th n-byte block from the PRG output where n is 280 the security parameter. Here we explain the structure of address A. 281 We explain the construction of the addresses in the following 282 sections where they are used. 284 The schemes in the next two sections use two kinds of hash functions 285 parameterized by security parameter n. For the hash tree 286 constructions a hash function that maps 2n-byte inputs and an n-byte 287 key to n-byte outputs is used. To randomize this function, 3n bytes 288 are needed - n bytes for the key and 2n bytes for a bitmask. For the 289 one-time signature scheme constructions a hash function that maps 290 n-byte inputs and n-byte keys to n-byte outputs is used. To 291 randomize this function, 2n bytes are needed - n bytes for the key 292 and n bytes for a bitmask. Consequently, three addresses are needed 293 for the first function and two addresses for the second one. 295 There are three different address formats for the different use 296 cases. One format for the hashes used in one-time signature schemes, 297 one for hashes used within the main Merkle-tree construction, and one 298 for hashes used in the L-trees. The latter being used to compress 299 one-time public keys. All these formats share as much format as 300 possible. In the following we describe these formats in detail. 302 An address is structured as follows. It always starts with 46 zero 303 bits in the most significant bits. These are followed by a layer 304 address of 8 bits, and a tree address of 24 bits. The next bit 305 decides whether it is an OTS construction or a hash tree address. 306 This OTS bit is set to zero for a tree hash address and it is set to 307 one for an OTS hash address. 309 We first describe the OTS address case as the hash tree case again 310 splits into two cases. In this case, the OTS bit is followed by a 311 24-bit OTS address that encodes the index of the OTS key pair within 312 a tree. The next 16 bits encode the chain address followed by 8 bits 313 that encode the address of the hash function call within a chain. 314 The key bit is used to generate two different addresses for one hash 315 function call. The bit is set to one to generate the key. To 316 generate the n-byte bitmask, the key bit is set to zero. 318 Index i for OTS hash 319 +------------------------+ 320 | Padding = 0 (46 bit)| 321 +------------------------+ 322 | layer address (8 bit)| 323 +------------------------+ 324 | tree address (24 bit)| 325 +------------------------+ 326 | OTS bit = 1 (1 bit)| 327 +------------------------+ 328 | OTS address (24 bit)| 329 +------------------------+ 330 | chain address (16 bit)| 331 +------------------------+ 332 | hash address (8 bit)| 333 +------------------------+ 334 | key bit (1 bit)| 335 +------------------------+ 337 Now we describe the hash tree address case. This case again splits 338 into two. The OTS bit is followed by an L-tree bit. This bit is set 339 to zero in case of an L-tree and set to one for main tree nodes. We 340 first discuss the L-tree case. In this case the L-tree bit is 341 followed by a 24 bit L-tree address, encoding the index of the leaf 342 computed with this L-tree. The next 6 bits encode the height of the 343 node inside the L-tree and the following 16 bit encode the index of 344 the node at that height, inside the L-tree. The last two bits are 345 used to generate three different addresses for one node. The first 346 of these bits is set to one to generate the key. In that case the 347 last bit is always zero. To generate the 2n-byte bitmask, the key 348 bit is set to zero. The most significant n bytes are generated using 349 the address with the last bit zero. The least significant bytes are 350 generated using the address with the last bit set to one. 352 An L-tree address 353 +------------------------+ 354 | Padding = 0 (46 bit)| 355 +------------------------+ 356 | layer address (8 bit)| 357 +------------------------+ 358 | tree address (24 bit)| 359 +------------------------+ 360 | OTS bit = 0 (1 bit)| 361 +------------------------+ 362 | L-tree bit = 1 (1 bit)| 363 +------------------------+ 364 | L-tree address (24 bit)| 365 +------------------------+ 366 | tree height (6 bit)| 367 +------------------------+ 368 | tree index (16 bit)| 369 +------------------------+ 370 | key bit (1 bit)| 371 +------------------------+ 372 | block bit (1 bit)| 373 +------------------------+ 375 We now describe the remaining format for the main tree hash 376 addresses. In this case the L-tree bit is set to zero and followed 377 by 14 zero bits padding as there are less hash tree addresses 378 required. The next 8 bits encode the height of the tree node to be 379 computed within the tree, followed by 24 bits that encode the index 380 of this node at that height. The last two bits are used to generate 381 three different addresses for one node as described for the L-tree 382 case. The first of these bits is set to one to generate the key. In 383 that case the last bit is always zero. To generate the 2n-byte 384 bitmask, the key bit is set to zero. The most significant n bytes 385 are generated using the address with the last bit zero. The least 386 significant bytes are generated using the address with the last bit 387 set to one. 389 A hash tree address 390 +------------------------+ 391 | Padding = 0 (46 bit)| 392 +------------------------+ 393 | layer address (8 bit)| 394 +------------------------+ 395 | tree address (24 bit)| 396 +------------------------+ 397 | OTS bit = 0 (1 bit)| 398 +------------------------+ 399 | L-tree bit = 0 (1 bit)| 400 +------------------------+ 401 | Padding = 0 (14 bit)| 402 +------------------------+ 403 | tree height (8 bit)| 404 +------------------------+ 405 | tree index (24 bit)| 406 +------------------------+ 407 | key bit (1 bit)| 408 +------------------------+ 409 | block bit (1 bit)| 410 +------------------------+ 412 All fields within these addresses encode unsigned integers. When 413 describing the generation of addresses we use setter-methods that 414 take positive integers and set the bits of a field to the binary 415 representation of that integer of the length of the field. We also 416 assume that setting the L-tree bit to zero, does also set the 417 (second) padding block to zero. 419 2.6. Strings of Base w Numbers 421 A byte string can be considered as a string of base w numbers, i.e. 422 integers in the set {0, ... , w - 1}. The correspondence is defined 423 by the function base_w(X, w) as follows. If X is an m-byte string, w 424 is a member of the set {4, 16}, then base_w(X, w) outputs a length 8 425 * m / lg(w) array of integers between 0 and w - 1. 427 Algorithm 1: base_w(X, w) 429 int in = 0; 430 int out = 0; 431 unsigned int total = 0; 432 int bits = 0; 433 int consumed; 435 for ( consumed = 0; consumed < 8 * m; consumed += lg(w) ) { 436 if ( bits == 0 ) { 437 total = X[m - 1 - in]; 438 in++; 439 bits += 8; 440 } 441 bits -= lg(w); 442 basew[out] = (total >> bits) AND (w - 1); 443 out++; 444 } 445 return basew; 447 For example, if X is the (big endian) byte string 0x1234, then 448 base_w(X, 4) returns the array a = {0, 3, 1, 0, 0, 1, 0, 2}. 450 X (represented as bits) 451 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 452 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 453 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 454 X[0] | X[1] 456 X (represented as base 4 numbers) 457 +-----+-----+-----+-----+-----+-----+-----+-----+ 458 | 0 | 1 | 0 | 2 | 0 | 3 | 1 | 0 | 459 +-----+-----+-----+-----+-----+-----+-----+-----+ 461 base_w(X, 4) 462 +-----+-----+-----+-----+-----+-----+-----+-----+ 463 | 0 | 3 | 1 | 0 | 0 | 1 | 0 | 2 | 464 +-----+-----+-----+-----+-----+-----+-----+-----+ 465 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 467 2.7. Member Functions 469 To simplify algorithm descriptions, we assume the existence of member 470 functions. If a complex data structure like a public key PK contains 471 a value X then getX(PK) returns the value of X for this public key. 472 Accordingly, setX(PK, X, Y) sets value X in PK to the value hold by 473 Y. 475 3. Primitives 477 3.1. WOTS+ One-Time Signatures 479 This section describes the WOTS+ one-time signature system, in a 480 version similar to [Huelsing13]. WOTS+ is a one-time signature 481 scheme; while a private key can be used to sign any message, each 482 private key MUST be used only once to sign a single message. In 483 particular, if a secret key is used to sign two different messages, 484 the scheme becomes insecure. 486 The section starts with an explanation of parameters. Afterwards, 487 the so-called chaining function, which forms the main building block 488 of the WOTS+ scheme, is explained. It follows a description of the 489 algorithms for key generation, signing and verification. Finally, 490 pseudorandom key generation is discussed. 492 3.1.1. WOTS+ Parameters 494 WOTS+ uses the parameters m, n, and w; they all take positive integer 495 values. These parameters are summarized as follows: 497 m : the message length in bytes 499 n : the length, in bytes, of a secret key, public key, or 500 signature element 502 w : the Winternitz parameter; it is a member of the set {4, 16} 504 The parameters are used to compute values len, len_1 and len_2: 506 len : the number of n-byte string elements in a WOTS+ secret key, 507 public key, and signature. It is computed as len = len_1 + len_2, 508 with len_1 = ceil(8m/lg(w)) and len_2 = 509 floor(lg(len_1*(w-1))/lg(w)) + 1 511 The value of n is determined by the cryptographic hash function used 512 for WOTS+. The hash function is chosen to ensure an appropriate 513 level of security. The value of m is the input length that can be 514 processed by the signing algorithm. It is often the length of a 515 message digest. The parameter w can be chosen from the set {4, 16}. 516 A larger value of w results in shorter signatures but slower overall 517 signing operations; it has little effect on security. Choices of w 518 are limited to the values 4 and 16 since these values yield optimal 519 trade-offs and easy implementation. 521 3.1.1.1. WOTS+ Functions 523 The WOTS+ algorithm uses a keyed cryptographic hash function F. F 524 accepts and returns byte strings of length n using keys of length n. 525 Security requirements on F are discussed in Section 8. In addition, 526 WOTS+ uses a pseudorandom generator G. G takes as input an n-byte 527 key and a 16-byte index and generates pseudorandom outputs of length 528 n. Security requirements on G are discussed in Section 8. 530 3.1.2. WOTS+ Chaining Function 532 The chaining function (Algorithm 2) computes an iteration of F on an 533 n-byte input using outputs of G. It takes a hash function address as 534 input. This address will have the first 119 bits set to encode the 535 address of this chain. In each iteration, one output of G is used as 536 key for F and a second output is XORed to the intermediate result 537 before it is processed by F. In the following, ADRS is a 16-byte 538 hash function address as specified in Section 2.5 and SEED is an 539 n-byte string, both used to generate the outputs of G. The chaining 540 function takes as input an n-byte string X, a start index i, a number 541 of steps s, as well as ADRS and SEED. The chaining function returns 542 as output the value obtained by iterating F for s times on input X, 543 using the outputs of G. 545 Algorithm 2: Chaining Function 547 if ( s is equal to 0 ) { 548 return X; 549 } 550 if ( (i+s) > w-1 ) { 551 return NULL; 552 } 553 byte[n] tmp = chain(X, i, s-1, SEED, ADRS); 554 ADRS.setHashAddress(i+s-1); 555 ADRS.setKeyBit(0); 556 BM = G(SEED, ADRS); 557 ADRS.setKeyBit(1); 558 KEY = G(SEED, ADRS); 559 tmp = F(KEY, tmp XOR BM); 560 return tmp; 562 3.1.3. WOTS+ Private Key 564 The private key in WOTS+, denoted by sk, is a length len array of 565 n-byte strings. This private key MUST be only used to sign exactly 566 one message. Each n-byte string MUST either be selected randomly 567 from the uniform distribution or using a cryptographically secure 568 pseudorandom procedure. In the latter case, the security of the used 569 procedure MUST at least match that of the WOTS+ parameters used. For 570 a further discussion on pseudorandom key generation see the end of 571 this section. The following pseudocode (Algorithm 3) describes an 572 algorithm for generating sk. 574 Algorithm 3: Generating a WOTS+ Private Key 576 for ( i = 0; i < len; i = i + 1 ) { 577 set sk[i] to a uniformly random n-byte string; 578 } 579 return sk; 581 3.1.4. WOTS+ Public Key 583 A WOTS+ key pair defines a virtual structure that consists of len 584 hash chains of length w. The len n-byte strings in the secret key 585 each define the start node for one hash chain. The public key 586 consists of the end nodes of these hash chains. Therefore, like the 587 secret key, the public key is also a length len array of n-byte 588 strings. To compute the hash chain, the chaining function (Algorithm 589 2) is used. A hash function address ADRS and a seed SEED has to be 590 provided by the calling algorithm. This address will encode the 591 address of the WOTS+ key pair within a greater structure. Hence, a 592 WOTS+ algorithm MUST NOT manipulate any other fields of ADRS than 593 chain address, hash address and key bit. Please note that the SEED 594 used here is public information also available to a verifier. The 595 following pseudocode (Algorithm 4) describes an algorithm for 596 generating the public key pk, where sk is the private key. 598 Algorithm 4 (WOTS_genPK): Generating a WOTS+ Public Key From a 599 Private Key 601 for ( i = 0; i < len; i = i + 1 ) { 602 ADRS.setChainAddress(i); 603 pk[i] = chain(sk[i], 0, w-1, SEED, ADRS); 604 } 605 return pk; 607 3.1.5. WOTS+ Signature Generation 609 A WOTS+ signature is a length len array of n-byte strings. The WOTS+ 610 signature is generated by mapping a message to len integers between 0 611 and w - 1. To this end, the message is transformed into base w 612 numbers using the base_w function defined in Section 2.6. Next, a 613 checksum is computed and appended to the transformed message as len_2 614 base w numbers using the base_w function. Each of the base w 615 integers is used to select a node from a different hash chain. The 616 signature is formed by concatenating the selected nodes. The 617 pseudocode for signature generation is shown below (Algorithm 5), 618 where M is the message and sig is the resulting signature. 620 Algorithm 5 (WOTS_sign): Generating a signature from a private key 621 and a message 623 csum = 0; 625 // convert message to base w 626 msg = base_w(M,w); 628 // compute checksum 629 for ( i = 0; i < len_1; i = i + 1 ) { 630 csum = csum + w - 1 - msg[i]; 631 } 633 // Convert csum to base w 634 csum = csum << ( 8 - ( len_2 % 8 )); 635 len_2_bytes = ceil( len_2 / 8 ); 636 msg = msg || base_w(toByte(csum, len_2_bytes), w); 637 for ( i = 0; i < len; i = i + 1 ) { 638 ADRS.setChainAddress(i); 639 sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS); 640 } 641 return sig; 643 The data format for a signature is given below. 645 WOTS+ Signature 647 +---------------------------------+ 648 | algorithm OID | 649 +---------------------------------+ 650 | | 651 | sig_ots[0] | n bytes 652 | | 653 +---------------------------------+ 654 | | 655 ~ .... ~ 656 | | 657 +---------------------------------+ 658 | | 659 | sig_ots[len-1] | n bytes 660 | | 661 +---------------------------------+ 663 3.1.6. WOTS+ Signature Verification 665 In order to verify a signature sig on a message M, the verifier 666 computes a WOTS+ public key value from the signature. This can be 667 done by "completing" the chain computations starting from the 668 signature values, using the base w values of the message hash and its 669 checksum. This step, called WOTS_pkFromSig, is described below in 670 Algorithm 6. The result of WOTS_pkFromSig is then compared to the 671 given public key. If the values are equal, the signature is 672 accepted. Otherwise, the signature is rejected. 674 Algorithm 6 (WOTS_pkFromSig): Computing a WOTS+ public key from a 675 message and its signature 677 csum = 0; 679 // convert message to base w 680 msg = base_w(M,w); 682 // compute checksum 683 for ( i = 0; i < len_1; i = i + 1 ) { 684 csum = csum + w - 1 - msg[i]; 685 } 687 // Convert csum to base w 688 csum = csum << ( 8 - ( len_2 % 8 )); 689 len_2_bytes = ceil( len_2 / 8 ); 690 msg = msg || base_w(toByte(csum, len_2_bytes), w); 691 for ( i = 0; i < len; i = i + 1 ) { 692 ADRS.setChainAddress(i); 693 tmp_pk[i] = chain(sig[i], msg[i], w-1-msg[i], SEED, ADRS); 694 } 695 return tmp_pk; 697 Note: XMSS uses WOTS_pkFromSig to compute a public key value and 698 delays the comparison to a later point. 700 3.1.7. Pseudorandom Key Generation 702 An implementation MAY use a cryptographically secure pseudorandom 703 method to generate the secret key from a single n-byte value. For 704 example, the method suggested in [BDH11] and explained below MAY be 705 used. Other methods MAY be used. The choice of a pseudorandom 706 method does not affect interoperability, but the cryptographic 707 strength MUST match that of the used WOTS+ parameters. 709 The advantage of generating the secret key elements from a random 710 n-byte string is that only this n-byte string needs to be stored 711 instead of the full secret key. The key can be regenerated when 712 needed. The suggested method from [BDH11] can be described using G. 713 During key generation a uniformly random n-byte string S is sampled 714 from a secure source of randomness. This string S is stored as 715 secret key. The secret key elements are computed as sk[i] = G'(S, 716 toByte(i,16)) whenever needed. Please note that this seed S MUST be 717 different from the seed SEED used to randomize the hash function 718 calls. Also, this seed S MUST be kept secret. 720 4. Schemes 722 In this section, the eXtended Merkle Signature Scheme (XMSS) is 723 described using WOTS+. XMSS comes in two flavors: First, a single- 724 tree variant (XMSS) and second a multi-tree variant (XMSS^MT). Both 725 allow combining a large number of WOTS+ key pairs under a single 726 small public key. The main ingredient added is a binary hash tree 727 construction. XMSS uses a single hash tree while XMSS^MT uses a tree 728 of XMSS key pairs. 730 4.1. XMSS: eXtended Merkle Signature Scheme 732 XMSS is a method for signing a potentially large but fixed number of 733 messages. It is based on the Merkle signature scheme. XMSS uses 734 five cryptographic components: WOTS+ as OTS method, two additional 735 cryptographic hash functions H and H_m, a pseudorandom function 736 PRF_m, and a pseudorandom generator G. One of the main advantages of 737 XMSS with WOTS+ is that it does not rely on the collision resistance 738 of the used hash functions but on weaker properties. Each XMSS 739 public/private key pair is associated with a perfect binary tree, 740 every node of which contains an n-byte value. Each tree leaf 741 contains a special tree hash of a WOTS+ public key value. Each non- 742 leaf tree node is computed by first concatenating the values of its 743 child nodes, computing the XOR with a bitmask, and applying the keyed 744 hash function H to the result. The bitmasks and the keys for the 745 hash function H are generated from a (public) seed that is part of 746 the public key using the pseudorandom generator G. The value 747 corresponding to the root of the XMSS tree forms the XMSS public key 748 together with the seed. 750 To generate a key pair that can be used to sign 2^h messages, a tree 751 of height h is used. XMSS is a stateful signature scheme, meaning 752 that the secret key changes after every signature. To prevent one- 753 time secret keys from being used twice, the WOTS+ key pairs are 754 numbered from 0 to (2^h)-1 according to the related leaf, starting 755 from index 0 for the leftmost leaf. The secret key contains an index 756 that is updated after every signature, such that it contains the 757 index of the next unused WOTS+ key pair. 759 A signature consists of the index of the used WOTS+ key pair, the 760 WOTS+ signature on the message and the so-called authentication path. 761 The latter is a vector of tree nodes that allow a verifier to compute 762 a value for the root of the tree starting from a WOTS+ signature. A 763 verifier computes the root value and compares it to the respective 764 value in the XMSS public key. If they match, the signature is valid. 765 The XMSS secret key consists of all WOTS+ secret keys and the actual 766 index. To reduce storage, a pseudorandom key generation procedure, 767 as described in [BDH11], MAY be used. The security of the used 768 method MUST at least match the security of the XMSS instance. 770 4.1.1. XMSS Parameters 772 XMSS has the following parameters: 774 h : the height (number of levels - 1) of the tree 776 n : the length in bytes of each node 778 m : the length of the message digest 780 w : the Winternitz parameter as defined for WOTS+ in Section 3.1 782 There are N = 2^h leaves in the tree. 784 For XMSS and XMSS^MT, secret and public keys are denoted by SK and 785 PK. For WOTS+, secret and public keys are denoted by sk and pk, 786 respectively. XMSS and XMSS^MT signatures are denoted by Sig. WOTS+ 787 signatures are denoted by sig. 789 4.1.2. XMSS Hash Functions 791 Besides the cryptographic hash function F required by WOTS+, XMSS 792 uses four more functions: 794 A cryptographic hash function H. H accepts n-byte keys and byte 795 strings of length (2 * n) and returns an n-byte string. 797 A cryptographic hash function H_m. H_m accepts m-byte keys and 798 byte strings of arbitrary length and returns an m-byte string. 800 A pseudorandom function PRF_m. PRF_m accepts byte strings of 801 arbitrary length and an m-byte key and returns an m-byte string. 803 A pseudorandom generator G. G takes as input an n-byte key and a 804 16-byte index and generates pseudorandom outputs of length n. 806 4.1.3. XMSS Private Key 808 An XMSS private key contains N = 2^h WOTS+ private keys, the leaf 809 index idx of the next WOTS+ private key that has not yet been used 810 and SK_PRF, an m-byte key for the PRF. The leaf index idx is 811 initialized to zero when the XMSS private key is created. The PRF 812 key SK_PRF MUST be sampled from a secure source of randomness that 813 follows the uniform distribution. The WOTS+ secret keys MUST be 814 generated as described in Section 3.1. To reduce the secret key 815 size, a cryptographic pseudorandom method MAY be used as discussed at 816 the end of this section. For the following algorithm descriptions, 817 the existence of a method getWOTS_SK(SK,i) is assumed. This method 818 takes as inputs an XMSS secret key SK and an integer i and outputs 819 the i^th WOTS+ secret key of SK. 821 4.1.4. Randomized Tree Hashing 823 To improve readability we introduce a function RAND_HASH(LEFT, RIGHT, 824 SEED, ADRS) that does the randomized hashing. It takes as input two 825 n-byte values LEFT and RIGHT that represent the left and the right 826 half of the hash function input, the seed SEED for G and the address 827 ADRS of this hash function call. RAND_HASH first uses G with SEED 828 and ADRS to generate a key KEY and n-byte bitmasks BM_0, BM_1. Then 829 it returns the randomized hash H(KEY, (LEFT XOR BM_0)||(RIGHT XOR 830 BM_1)). 832 Algorithm 7: RAND_HASH 834 ADRS.setKeyBit(0); 835 ADRS.setBlockBit(0); 836 BM_0 = G(SEED, ADRS); 837 ADRS.setBlockBit(1); 838 BM_1 = G(SEED, ADRS); 839 ADRS.setKeyBit(1); 840 ADRS.setBlockBit(0); 841 KEY = G(SEED, ADRS); 842 return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); 844 4.1.5. L-Trees 846 To compute the leaves of the binary hash tree, a so-called L-tree is 847 used. An L-tree is an unbalanced binary hash tree, distinct but 848 similar to the main XMSS binary hash tree. The algorithm ltree 849 (Algorithm 8) takes as input a WOTS+ public key pk and compresses it 850 to a single n-byte value pk[0]. Towards this end it also takes an 851 address ADRS as input that encodes the address of the L-tree. The 852 algorithm uses G and the seed SEED generated during public key 853 generation. 855 Algorithm 8: ltree 857 unsigned int len' = len; 858 unsigned int j = 0; 859 ADRS.setTreeHeight(0); 860 while ( len' > 1 ) { 861 for ( i = 0; i < floor(len' / 2); i = i + 1 ) { 862 ADRS.setTreeIndex(i); 863 pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS); 864 } 865 if ( len' % 2 == 1 ) { 866 pk[floor(len' / 2) + 1] = pk[len']; 867 } 868 len' = ceil(len' / 2); 869 ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 870 } 871 return pk[0]; 873 4.1.6. TreeHash 875 For the computation of the internal n-byte nodes of a Merkle tree, 876 the subroutine treeHash (Algorithm 9) accepts an XMSS secret key SK, 877 an unsigned integer s (the start index), an unsigned integer t (the 878 target node height), a seed SEED, and an address ADRS that encodes 879 the address of the containing tree. For the height of a node within 880 a tree counting starts with the leaves at height zero. The treeHash 881 algorithm returns the root node of a tree of height t with the 882 leftmost leaf being the hash of the WOTS+ pk with index s. It is 883 REQUIRED that s % 2^t = 0, i.e. that the leaf at index s is a left 884 most leaf of a sub-tree of height t. Otherwise the hash-addressing 885 scheme fails. The treeHash algorithm uses a stack holding up to 886 (t-1) n-byte strings, with the usual stack functions push() and 887 pop(). 889 Algorithm 9: treeHash 891 if( s % (1 << t) != 0 ) return -1; 892 for ( i = 0; i < 2^t; i = i + 1 ) { 893 ADRS.setOTSBit(1); 894 ADRS.setOTSAddress(s+i); 895 pk = WOTS_genPK (getWOTS_SK(SK, s+i), SEED, ADRS); 896 ADRS.setOTSBit(0); 897 ADRS.setLTreeBit(1); 898 ADRS.setLTreeAddress(s+i); 899 node = ltree(pk, SEED, ADRS); 900 ADRS.setLTreeBit(0); 901 ADRS.setTreeHeight(0); 902 ADRS.setTreeIndex(i+s); 903 while ( Top node on Stack has same height t' as node ) { 904 ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); 905 node = RAND_HASH(Stack.pop(), node, SEED, ADRS); 906 ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 907 } 908 Stack.push(node); 909 } 910 return Stack.pop(); 912 4.1.7. XMSS Public Key 914 The XMSS public key is computed as described in XMSS_genPK (Algorithm 915 10). The algorithm takes the XMSS secret key SK, and the tree height 916 h. The XMSS public key PK consists of the root of the binary hash 917 tree and the seed SEED. SEED is generated as a uniformly random 918 n-byte string. Although SEED is public, it is important that it is 919 generated using a good entropy source. The root is computed using 920 treeHash. For XMSS, there is only a single main tree. Hence, the 921 used address is set to the all-zero-string. 923 Algorithm 10: XMSS_genPK - Generate an XMSS public key from an XMSS 924 private key 926 set SEED to a uniformly random n-byte string; 927 ADRS = toByte(0,16); 928 root = treeHash(SK, 0, h, SEED, ADRS); 929 PK = root || SEED; 930 return PK; 932 Public and private key generation MAY be interleaved to save space. 933 Especially, when a pseudorandom method is used to generate the secret 934 key, generation MAY be done when the respective WOTS+ key pair is 935 needed by treeHash. 937 The format of an XMSS public key is given below. 939 XMSS Public Key 941 +---------------------------------+ 942 | algorithm OID | 943 +---------------------------------+ 944 | | 945 | root node | n bytes 946 | | 947 +---------------------------------+ 948 | | 949 | SEED | n bytes 950 | | 951 +---------------------------------+ 953 4.1.8. XMSS Signature 955 An XMSS signature is a (4 + m + (len + h) * n)-byte string consisting 956 of 958 the index idx_sig of the used WOTS+ key pair (4 bytes), 960 a byte string r used for randomized message hashing (m bytes), 962 a WOTS+ signature sig_ots (len * n bytes), 964 the so-called authentication path 'auth' for the leaf associated 965 with the used WOTS+ key pair (h * n bytes). 967 The authentication path is an array of h n-byte strings. It contains 968 the siblings of the nodes on the path from the used leaf to the root. 969 It does not contain the nodes on the path itself. These nodes are 970 needed by a verifier to compute a root node for the tree from the 971 WOTS+ public key. A node Node is addressed by its position in the 972 tree. Node(x,y) denotes the x^th node on level y with x = 0 being 973 the leftmost node on a level. The leaves are on level 0, the root is 974 on level h. An authentication path contains exactly one node on 975 every layer 0 <= x <= h-1. For the i^th WOTS+ key pair, counting 976 from zero, the j^th authentication path node is 978 Node(j, floor(i / (2^j)) XOR 1) 980 Given an XMSS secret key SK and seed SEED, all nodes in a tree are 981 determined. Their value is defined in terms of treeHash(Algorithm 982 9). Hence, one can compute the authentication path: 984 ADRS = toByte(0, 16); 985 for (j = 0; j < h; j++) { 986 k = floor(i / (2^j)) XOR 1; 987 auth[j] = treeHash(SK, k * 2^j, j, SEED, ADRS); 988 } 990 The data format for a signature is given below. 992 XMSS Signature 994 +---------------------------------+ 995 | | 996 | index idx_sig | 4 bytes 997 | | 998 +---------------------------------+ 999 | | 1000 | randomness r | m bytes 1001 | | 1002 +---------------------------------+ 1003 | | 1004 | WOTS+ signature sig_ots | len * n bytes 1005 | | 1006 +---------------------------------+ 1007 | | 1008 | auth[0] | n bytes 1009 | | 1010 +---------------------------------+ 1011 | | 1012 ~ .... ~ 1013 | | 1014 +---------------------------------+ 1015 | | 1016 | auth[h-1] | n bytes 1017 | | 1018 +---------------------------------+ 1020 4.1.9. XMSS Signature Generation 1022 To compute the XMSS signature of a message M with an XMSS private 1023 key, the signer first computes a randomized message digest. Then a 1024 WOTS+ signature of the message is computed using the next unused 1025 WOTS+ private key. Next, the authentication path is computed. 1026 Finally, the secret key is updated, i.e. idx is incremented. An 1027 implementation MUST NOT output the signature before the updated 1028 private key. 1030 The node values of the authentication path MAY be computed in any 1031 way. This computation is assumed to be performed by the subroutine 1032 buildAuth for the function XMSS_sign, as below. The fastest 1033 alternative is to store all tree nodes and set the array in the 1034 signature by copying them, respectively. The least storage-intensive 1035 alternative is to recompute all nodes for each signature online. 1036 There exist several algorithms in between, with different time/ 1037 storage trade-offs. For an overview see [BDS09]. Note that the 1038 details of this procedure are not relevant to interoperability; it is 1039 not necessary to know any of these details in order to perform the 1040 signature verification operation. As a consequence, buildAuth is not 1041 specified here. 1043 The algorithm XMSS_sign (Algorithm 11) described below calculates an 1044 updated secret key SK and a signature on a message M. XMSS_sign 1045 takes as inputs a message M of an arbitrary length, an XMSS secret 1046 key SK and seed SEED. It returns the byte string containing the 1047 concatenation of the updated secret key SK and the signature Sig. 1049 Algorithm 11: XMSS_sign - Generate an XMSS signature and update the 1050 XMSS secret key 1052 idx_sig = getIdx(SK); 1053 ADRS = toByte(0,16); 1054 auth = buildAuth(SK, idx_sig, SEED, ADRS); 1055 byte[m] r = PRF_m(getSK_PRF(SK), M); 1056 byte[m] M' = H_m(r, M); 1057 ADRS.setOTSBit(0); 1058 ADRS.setOTSAddress(idx_sig); 1059 sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), M', SEED, ADRS); 1060 Sig = (idx_sig || r || sig_ots || auth); 1061 setIdx(SK, idx_sig + 1); 1062 return (SK || Sig); 1064 4.1.10. XMSS Signature Verification 1066 An XMSS signature is verified by first computing the message digest 1067 using randomness r and a message M. Then the used WOTS+ public key 1068 pk_ots is computed from the WOTS+ signature using WOTS_pkFromSig. 1069 The WOTS+ public key in turn is used to compute the corresponding 1070 leaf using an L-tree. The leaf, together with index idx_sig and 1071 authentication path auth is used to compute an alternative root value 1072 for the tree. These first steps are done by XMSS_rootFromSig 1073 (Algorithm 12). The verification succeeds if and only if the 1074 computed root value matches the one in the XMSS public key. In any 1075 other case it MUST return fail. 1077 The main part of XMSS signature verification is done by the function 1078 XMSS_rootFromSig (Algorithm 12) described below. XMSS_rootFromSig 1079 takes as inputs an XMSS signature Sig, a message M, and seed SEED. 1081 XMSS_rootFromSig returns an n-byte string holding the value of the 1082 root of a tree defined by the input data. 1084 Algorithm 12: XMSS_rootFromSig - Compute a root node using an XMSS 1085 signature, a message, and seed SEED 1087 byte[m] M' = H_m(r, M); 1088 ADRS = toByte(0,16); 1089 ADRS.setOTSBit(1); 1090 ADRS.setOTSAddress(idx_sig); 1091 pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS); 1092 ADRS.setOTSBit(0); 1093 ADRS.setLTreeBit(1); 1094 ADRS.setLTreeAddress(idx_sig); 1095 byte[n][2] node; 1096 node[0] = ltree(pk_ots, SEED, ADRS); 1097 ADRS.setLTreeBit(0); 1098 ADRS.setTreeIndex(idx_sig); 1099 for ( k = 0; k < h; k = k + 1 ) { 1100 ADRS.setTreeHeight(k); 1101 if ( floor(idx_sig / (2^k)) % 2 is equal to 0 ) { 1102 ADRS.setTreeIndex(ADRS.getTreeIndex() / 2); 1103 node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS); 1104 } else { 1105 ADRS.setTreeIndex(ADRS.getTreeIndex() - 1 / 2); 1106 node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS); 1107 } 1108 node[0] = node[1]; 1109 } 1110 return node[0]; 1112 The full XMSS signature verification is depicted below. XMSS^MT uses 1113 only XMSS_rootFromSig and delegates the comparison to a later 1114 comparison of data depending on its output. 1116 Algorithm 13: XMSS_verify - Verify an XMSS signature using an XMSS 1117 signature, the corresponding XMSS public key and a message 1119 byte[n] node = XMSS_rootFromSig(Sig, M, getSEED(PK)); 1120 if ( node is equal to root in PK ) { 1121 return true; 1122 } else { 1123 return false; 1124 } 1126 4.1.11. Pseudorandom Key Generation 1128 An implementation MAY use a cryptographically secure pseudorandom 1129 method to generate the XMSS secret key from a single n-byte value. 1130 For example, the method suggested in [BDH11] and explained below MAY 1131 be used. Other methods MAY be used. The choice of a pseudorandom 1132 method does not affect interoperability, but the cryptographic 1133 strength MUST match that of the used XMSS parameters. 1135 For XMSS a similar method than the one used for WOTS+ can be used. 1136 The suggested method from [BDH11] can be described using G. During 1137 key generation a uniformly random n-byte string S is sampled from a 1138 secure source of randomness. This seed S MUST NOT be confused with 1139 the public seed SEED. The seed S MUST be independent of SEED and as 1140 it is the main secret, it MUST be kept secret. This seed S is used 1141 to generate an n-byte value S_ots for each WOTS+ key pair. The 1142 n-byte value S_ots can then be used to compute the respective WOTS+ 1143 secret key using the method described in Section 3.1.7. The seeds 1144 for the WOTS+ key pairs are computed as S_ots[i] = G(S,i). The 1145 second parameter of G is the index i of the WOTS+ key pair, 1146 represented as 16-byte string in the common way. An advantage of 1147 this method is that a WOTS+ key can be computed using only len + 1 1148 evaluations of G when S is given. 1150 4.1.12. Free Index Handling and Partial Secret Keys 1152 Some applications might require to work with partial secret keys or 1153 copies of secret keys. Examples include delegation of signing rights 1154 / proxy signatures, and load balancing. Such applications MAY use 1155 their own key format and MAY use a signing algorithm different from 1156 the one described above. The index in partial secret keys or copies 1157 of a secret key MAY be manipulated as required by the applications. 1158 However, applications MUST establish means that guarantee that each 1159 index and thereby each WOTS+ key pair is used to sign only a single 1160 message. 1162 4.2. XMSS^MT: Multi-Tree XMSS 1164 XMSS^MT is a method for signing a large but fixed number of messages. 1165 It was first described in [HRB13]. It builds on XMSS. XMSS^MT uses 1166 a tree of several layers of XMSS trees. The trees on top and 1167 intermediate layers are used to sign the root nodes of the trees on 1168 the respective layer below. Trees on the lowest layer are used to 1169 sign the actual messages. All XMSS trees have equal height. 1171 Consider an XMSS^MT tree of total height h that has d layers of XMSS 1172 trees of height h / d. Then layer d - 1 contains one XMSS tree, 1173 layer d - 2 contains 2^(h / d) XMSS trees, and so on. Finally, layer 1174 0 contains 2^(h - h / d) XMSS trees. 1176 4.2.1. XMSS^MT Parameters 1178 In addition to all XMSS parameters, an XMSS^MT system requires the 1179 number of tree layers d, specified as an integer value that divides h 1180 without remainder. The same tree height h / d and the same 1181 Winternitz parameter w are used for all tree layers. 1183 All the trees on higher layers sign root nodes of other trees which 1184 are n-byte strings. Hence, no message compression is needed and 1185 WOTS+ is used to sign the root nodes themselves instead of their hash 1186 values. Hence the WOTS+ message length for these layers is n not m. 1187 Accordingly, the values of len_1, len_2 and len change for these 1188 layers. The parameters len_1_n, len_2_n, and len_n denote the 1189 respective values computed using n as message length for WOTS+. 1191 4.2.2. XMSS Algorithms Without Message Hash 1193 As all XMSS trees besides those on layer 0 are used to sign short 1194 fixed length messages, the initial message hash can be omitted. In 1195 the description below XMSS_sign_wo_hash and XMSS_rootFromSig_wo_hash 1196 are versions of XMSS_sign and XMSS_rootFromSig, respectively, that 1197 omit the initial message hash. They are obtained by setting M' = M 1198 in the above algorithms. Accordingly, the evaluations of H_m and 1199 PRF_m MUST be omitted. This also means that no randomization element 1200 r for the message hash is required. XMSS signatures generated by 1201 XMSS_sign_wo_hash and verified by XMSS_rootFromSig_wo_hash MUST NOT 1202 contain a value r. 1204 4.2.3. XMSS^MT Private Key 1206 An XMSS^MT private key SK_MT consists of one reduced XMSS private key 1207 for each XMSS tree. These reduced XMSS private keys contain no 1208 pseudorandom function key and no index. Instead, SK_MT contains a 1209 single m-byte pseudorandom function key SK_PRF and a single (ceil(h / 1210 8))-byte index idx_MT. The index is a global index over all WOTS+ 1211 key pairs of all XMSS trees on layer 0. It is initialized with 0. 1212 It stores the index of the last used WOTS+ key pair on the bottom 1213 layer, i.e. a number between 0 and 2^h - 1. 1215 The algorithm descriptions below uses a function getXMSS_SK(SK, x, y) 1216 that outputs the reduced secret key of the x^th XMSS tree on the y^th 1217 layer. 1219 4.2.4. XMSS^MT Public Key 1221 The XMSS^MT public key PK_MT contains the root of the single XMSS 1222 tree on layer d-1 and the seed SEED. The pseudorandom generator G is 1223 used with SEED to generate the bitmasks and keys for all XMSS trees. 1224 Algorithm 14 shows pseudocode to generate PK_MT. First, the n-byte 1225 SEED is chosen uniformly at random. The n-byte root node of the top 1226 layer tree is computed using treeHash. The algorithm XMSSMT_genPK 1227 takes the XMSS^MT secret key SK_MT as an input and outputs an XMSS^MT 1228 public key PK_MT. 1230 Algorithm 14: XMSSMT_genPK - Generate an XMSS^MT public key from an 1231 XMSS^MT private key 1233 set SEED to a uniformly random n-byte string; 1234 ADRS = toByte(0,16); 1235 ADRS.setLayerAddress(d-1); 1236 root = treeHash(getXMSS_SK(SK_MT, 0, d - 1), 0, h / d, SEED, ADRS); 1237 PK_MT = root || SEED; 1238 return PK_MT; 1240 The format of an XMSS^MT public key is given below. 1242 XMSS^MT Public Key 1244 +---------------------------------+ 1245 | algorithm OID | 1246 +---------------------------------+ 1247 | | 1248 | root node | n bytes 1249 | | 1250 +---------------------------------+ 1251 | | 1252 | SEED | n bytes 1253 | | 1254 +---------------------------------+ 1256 4.2.5. XMSS^MT Signature 1258 An XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) + 1259 m + (h + len + (d - 1) * len_n) * n). It consists of 1261 the index idx_sig of the used WOTS+ key pair on the bottom layer 1262 (ceil(h / 8) bytes), 1264 a byte string r used for randomized message hashing (m bytes), 1266 one reduced XMSS signature ((h + len) * n bytes), 1267 d-1 reduced XMSS signatures with message length n ((h + len_n) * n 1268 bytes). 1270 The reduced XMSS signatures contain no index idx and no byte string 1271 r. They only contain a WOTS+ signature sig_ots and an authentication 1272 path auth. The first reduced XMSS signature contains a WOTS+ 1273 signature that consists of len n-byte elements. The remaining 1274 reduced XMSS signatures contain a WOTS+ signature on an n-byte 1275 message that consists of len_n n-byte elements. 1277 The data format for a signature is given below. 1279 XMSS^MT signature 1281 +---------------------------------+ 1282 | | 1283 | index idx_sig | ceil(h / 8) bytes 1284 | | 1285 +---------------------------------+ 1286 | | 1287 | randomness r | m bytes 1288 | | 1289 +---------------------------------+ 1290 | | 1291 | (reduced) XMSS signature Sig | (h + len) * n bytes 1292 | (bottom layer 0) | 1293 | | 1294 +---------------------------------+ 1295 | | 1296 | (reduced) XMSS signature Sig | (h + len_n) * n bytes 1297 | (layer 1) | 1298 | | 1299 +---------------------------------+ 1300 | | 1301 ~ .... ~ 1302 | | 1303 +---------------------------------+ 1304 | | 1305 | (reduced) XMSS signature Sig | (h + len_n) * n bytes 1306 | (layer d-1) | 1307 | | 1308 +---------------------------------+ 1310 4.2.6. XMSS^MT Signature Generation 1312 To compute the XMSS^MT signature Sig_MT of a message M using an 1313 XMSS^MT private key SK_MT and seed SEED, XMSSMT_sign (Algorithm 15) 1314 described below uses XMSS_sign and XMSS_sign_wo_hash as defined in 1315 Section 4.2.2. First, the signature index is set to idx. Next, 1316 PRF_m is used to compute a pseudorandom m-byte string r. This m-byte 1317 string is then used to compute a randomized message digest of length 1318 m. The message digest is signed using the WOTS+ key pair on the 1319 bottom layer with absolute index idx. The authentication path for 1320 the WOTS+ key pair is computed as well as the root of the containing 1321 XMSS tree. The root is signed by the parent XMSS tree. This is 1322 repeated until the top tree is reached. 1324 Algorithm 15: XMSSMT_sign - Generate an XMSS^MT signature and update 1325 the XMSS^MT secret key 1327 ADRS = toByte(0,16); 1328 SK_PRF = getSK_PRF(SK_MT); 1329 idx_sig = getIdx(SK_MT); 1330 setIdx(SK_MT, idx_sig + 1); 1331 Sig_MT = idx_sig; 1332 unsigned int idx_tree = (h - h / d) most significant bits of idx_sig; 1333 unsigned int idx_leaf = (h / d) least significant bits of idx_sig; 1334 SK = idx_leaf || SK_PRF || getXMSS_SK(SK_MT, idx_tree, 0); 1335 ADRS.setLayerAddress(0); 1336 ADRS.setTreeAddress(idx_tree); 1337 Sig_tmp = XMSS_sign(M, SK, SEED, ADRS); 1338 Sig_tmp = Sig_tmp without idx; 1339 Sig_MT = Sig_MT || Sig_tmp; 1340 for ( j = 1; j < d; j = j + 1 ) { 1341 root = treeHash(SK, 0, h / d, SEED, ADRS); 1342 idx_leaf = (h / d) least significant bits of idx_tree; 1343 idx_tree = (h - j * (h / d)) most significant bits of idx_tree; 1344 SK = idx_leaf || SK_PRF || getXMSS_SK(SK_MT, idx_tree, j); 1345 ADRS.setLayerAddress(j); 1346 ADRS.setTreeAddress(idx_tree); 1347 Sig_tmp = XMSS_sign_wo_hash(root, SK, SEED, ADRS) 1348 with idx removed; 1349 Sig_MT = Sig_MT || Sig_tmp; 1350 } 1351 return SK_MT || Sig_MT; 1353 Algorithm 15 is only one method to compute XMSS^MT signatures. 1354 Especially, there exist time-memory trade-offs that allow to reduce 1355 the signing time to less than the signing time of an XMSS scheme with 1356 tree height h / d. These trade-offs prevent certain values from 1357 being recomputed several times by keeping a state and distribute all 1358 computations over all signature generations. Details can be found in 1359 [Huelsing13a]. 1361 4.2.7. XMSS^MT Signature Verification 1363 XMSS^MT signature verification (Algorithm 16) can be summarized as d 1364 XMSS signature verifications with small changes. First, only the 1365 message is hashed. The remaining XMSS signatures are on the root 1366 nodes of trees which have a fixed length. Second, instead of 1367 comparing the computed root node to a given value, a signature on the 1368 root is verified. Only the root node of the top tree is compared to 1369 the value in the XMSS^MT public key. XMSSMT_verify uses 1370 XMSS_rootFromSig and XMSS_rootFromSig_wo_hash. XMSSMT_verify takes 1371 as inputs an XMSS^MT signature Sig^MT, a message M and a public key 1372 PK_MT. It outputs a boolean. 1374 Algorithm 16: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a 1375 message M using an XMSS^MT public key PK_MT 1377 idx = getIdx(Sig_MT); 1378 SEED = getSEED(PK_MT); 1379 ADRS = toByte(0,16); 1380 unsigned int idx_leaf = (h / d) least significant bits of idx; 1381 unsigned int idx_tree = (h - h / d) most significant bits of idx; 1382 Sig' = leaf || setR(Sig_MT) || getXMSSSignature(Sig, 0); 1383 ADRS.setLayerAddress(0); 1384 ADRS.setTreeAddress(idx_tree); 1385 byte[n] node = XMSS_rootFromSig(Sig', M, SEED, ADRS); 1386 for ( j = 1; j < d; j = j + 1 ) { 1387 idx_leaf = (h / d) least significant bytes of idx_tree; 1388 idx_tree = (h - j * h / d) most significant bytes of idx_tree; 1389 Sig' = idx_leaf || getXMSSSignature(Sig, j); 1390 ADRS.setLayerAddress(j); 1391 ADRS.setTreeAddress(idx_tree); 1392 node = XMSS_rootFromSig_wo_hash(Sig', node, SEED, ADRS); 1393 } 1394 if ( node is equal to getRoot(PK_MT) ) { 1395 return true; 1396 } else { 1397 return false; 1398 } 1400 4.2.8. Pseudorandom Key Generation 1402 Like for XMSS, an implementation MAY use a cryptographically secure 1403 pseudorandom method to generate the XMSS^MT secret key from a single 1404 n-byte value. For example, the method explained below MAY be used. 1405 Other methods MAY be used, too. The choice of a pseudorandom method 1406 does not affect interoperability, but the cryptographic strength MUST 1407 match that of the used XMSS parameters. 1409 For XMSS^MT a method similar to that for XMSS and WOTS+ can be used. 1410 The method uses a G as pseudorandom generator. During key generation 1411 a uniformly random n-byte string S_MT is sampled from a secure source 1412 of randomness. This seed S_MT is used to generate one n-byte value S 1413 for each XMSS key pair. This n-byte value can be used to compute the 1414 respective XMSS secret key using the method described in 1415 Section 4.1.11. Let S[x][y] be the seed for the x^th XMSS secret key 1416 on layer y. The seeds are computed as S[x][y] = G(G(S, y), x). The 1417 second parameter of G is the index x (resp. level y), represented as 1418 16-byte string in the common way. 1420 4.2.9. Free Index Handling and Partial Secret Keys 1422 The content of Section 4.1.12 also applies to XMSS^MT. 1424 5. Parameter Sets 1426 This note provides a first basic set of parameter sets which are 1427 assumed to cover most relevant applicants. Parameter sets for two 1428 classical security levels are defined: 256 and 512 bits. Function 1429 output sizes are n = m = 32 and 64 bytes. Considering quantum- 1430 computer-aided attacks, these output sizes yield post-quantum 1431 security of 128 and 256 bits, respectively. 1433 For the n = m = 32 and n = m = 64 settings, we give parameters that 1434 use SHA2-256 and SHA2-512 as defined in [FIPS180], respectively, and 1435 ChaCha20 as defined in [RFC7539]. SHA2 does not provide a keyed-mode 1436 itself. To implement a keyed hash-function, SHA2-256(toByte(0,32) || 1437 KEY || M) and SHA2-512(toByte(0,64) || KEY || M) are used. This 1438 construction is used for the functions F, H, and H_m. To implement 1439 PRF_m, HMAC-SHA2-256 and HMAC-SHA2-512 are used, respectively. The 1440 pseudorandom generator G for n=32 is implemented as ChaCha20 using 1441 SEED as key, the most significant 12 bytes of the address input as 1442 nonce and the least significant 4 bytes as counter. The output 1443 consists of the first 32 bytes of the key stream. The pseudorandom 1444 generator G for n=64 is implemented as HMAC-SHA2-512. 1446 5.1. WOTS+ Parameters 1448 To fully describe a WOTS+ signature method, the parameters m, n, and 1449 w, as well as the functions F and G MUST be specified. This section 1450 defines several WOTS+ signature systems, each of which is identified 1451 by a name. Values for len are provided for convenience. 1453 +------------------------+-------+----------+----+----+----+-----+ 1454 | Name | F | G | m | n | w | len | 1455 +------------------------+-------+----------+----+----+----+-----+ 1456 | WOTSP_SHA2-256_M32_W16 | SHA-2 | ChaCha20 | 32 | 32 | 16 | 67 | 1457 | | | | | | | | 1458 | WOTSP_SHA2-512_M64_W16 | SHA-2 | SHA-2 | 64 | 64 | 16 | 131 | 1459 +------------------------+-------+----------+----+----+----+-----+ 1461 Table 1 1463 The implementation of the single functions is done as described 1464 above. XDR formats for WOTS+ are listed in Appendix A. 1466 5.2. XMSS Parameters 1468 To fully describe an XMSS signature method, the parameters m, n, w, 1469 and h, as well as the functions F, H, H_m, PRF_m, and G MUST be 1470 specified. This section defines different XMSS signature systems, 1471 each of which is identified by a name. We define parameter sets that 1472 implement the functions using SHA2 and ChaCha20 for n = 32 and only 1473 SHA2 for n=64 as described above. 1475 +---------------------------+----+----+----+-----+----+ 1476 | Name | m | n | w | len | h | 1477 +---------------------------+----+----+----+-----+----+ 1478 | XMSS_SHA2-256_M32_W16_H10 | 32 | 32 | 16 | 67 | 10 | 1479 | | | | | | | 1480 | XMSS_SHA2-256_M32_W16_H16 | 32 | 32 | 16 | 67 | 16 | 1481 | | | | | | | 1482 | XMSS_SHA2-256_M32_W16_H20 | 32 | 32 | 16 | 67 | 20 | 1483 | | | | | | | 1484 | XMSS_SHA2-512_M64_W16_H10 | 64 | 64 | 16 | 131 | 10 | 1485 | | | | | | | 1486 | XMSS_SHA2-512_M64_W16_H16 | 64 | 64 | 16 | 131 | 16 | 1487 | | | | | | | 1488 | XMSS_SHA2-512_M64_W16_H20 | 64 | 64 | 16 | 131 | 20 | 1489 +---------------------------+----+----+----+-----+----+ 1491 Table 2 1493 The XDR formats for XMSS are listed in Appendix B. 1495 5.3. XMSS^MT Parameters 1497 To fully describe an XMSS^MT signature method, the parameters m, n, 1498 w, h, and d, as well as the functions F, H, H_m, PRF_m, and G MUST be 1499 specified. This section defines several XMSS^MT signature systems, 1500 each of which is identified by a name. We define parameter sets that 1501 implement the functions using SHA2 and ChaCha20 for n = 32 and only 1502 SHA2 for n=64 as described above. 1504 +---------------------------------+----+----+----+-----+----+----+ 1505 | Name | m | n | w | len | h | d | 1506 +---------------------------------+----+----+----+-----+----+----+ 1507 | XMSSMT_SHA2-256_M32_W16_H20_D2 | 32 | 32 | 16 | 67 | 20 | 2 | 1508 | | | | | | | | 1509 | XMSSMT_SHA2-256_M32_W16_H20_D4 | 32 | 32 | 16 | 67 | 20 | 4 | 1510 | | | | | | | | 1511 | XMSSMT_SHA2-256_M32_W16_H40_D2 | 32 | 32 | 16 | 67 | 40 | 2 | 1512 | | | | | | | | 1513 | XMSSMT_SHA2-256_M32_W16_H40_D4 | 32 | 32 | 16 | 67 | 40 | 4 | 1514 | | | | | | | | 1515 | XMSSMT_SHA2-256_M32_W16_H40_D8 | 32 | 32 | 16 | 67 | 40 | 8 | 1516 | | | | | | | | 1517 | XMSSMT_SHA2-256_M32_W16_H60_D3 | 32 | 32 | 16 | 67 | 60 | 3 | 1518 | | | | | | | | 1519 | XMSSMT_SHA2-256_M32_W16_H60_D6 | 32 | 32 | 16 | 67 | 60 | 6 | 1520 | | | | | | | | 1521 | XMSSMT_SHA2-256_M32_W16_H60_D12 | 32 | 32 | 16 | 67 | 60 | 12 | 1522 | | | | | | | | 1523 | XMSSMT_SHA2-512_M64_W16_H20_D2 | 64 | 64 | 16 | 131 | 20 | 2 | 1524 | | | | | | | | 1525 | XMSSMT_SHA2-512_M64_W16_H20_D4 | 64 | 64 | 16 | 131 | 20 | 4 | 1526 | | | | | | | | 1527 | XMSSMT_SHA2-512_M64_W16_H40_D2 | 64 | 64 | 16 | 131 | 40 | 2 | 1528 | | | | | | | | 1529 | XMSSMT_SHA2-512_M64_W16_H40_D4 | 64 | 64 | 16 | 131 | 40 | 4 | 1530 | | | | | | | | 1531 | XMSSMT_SHA2-512_M64_W16_H40_D8 | 64 | 64 | 16 | 131 | 40 | 8 | 1532 | | | | | | | | 1533 | XMSSMT_SHA2-512_M64_W16_H60_D3 | 64 | 64 | 16 | 131 | 60 | 3 | 1534 | | | | | | | | 1535 | XMSSMT_SHA2-512_M64_W16_H60_D6 | 64 | 64 | 16 | 131 | 60 | 6 | 1536 | | | | | | | | 1537 | XMSSMT_SHA2-512_M64_W16_H60_D12 | 64 | 64 | 16 | 131 | 60 | 12 | 1538 +---------------------------------+----+----+----+-----+----+----+ 1540 Table 3 1542 XDR formats for XMSS^MT are listed in Appendix C. 1544 6. Rationale 1546 The goal of this note is to describe the WOTS+, XMSS and XMSS^MT 1547 algorithms following the scientific literature. Other signature 1548 methods are out of scope and may be an interesting follow-on work. 1550 The description is done in a modular way that allows to base a 1551 description of stateless hash-based signature algorithms like SPHINCS 1552 [BHH15] on it. 1554 The draft slightly deviates from the scientific literature using a 1555 tweak that prevents multi-target attacks against the underlying hash- 1556 function. The security assumptions for this tweak are discussed in 1557 Section 8. The main difference to literature is that security now 1558 relies either on the random oracle model or some other seemingly 1559 natural heuristic assumptions. 1561 We suggest the value w = 16 for the Winternitz parameter. No bigger 1562 values are included since the decrease in signature size then becomes 1563 less significant. Furthermore, the value w = 16 considerably 1564 simplifies the implementations of some of the algorithms. Please 1565 note that we do allow w = 4, but limit the specified parameter sets 1566 to w = 16 for efficiency reasons. 1568 The signature and public key formats are designed so that they are 1569 easy to parse. Each format starts with a 32-bit enumeration value 1570 that indicates all of the details of the signature algorithm and 1571 hence defines all of the information that is needed in order to parse 1572 the format. 1574 The enumeration values used in this note are palindromes, which have 1575 the same byte representation in either host order or network order. 1576 This fact allows an implementation to omit the conversion between 1577 byte order for those enumerations. Note however that the idx field 1578 used in XMSS and XMSS^MT signatures and secret keys must be properly 1579 converted to and from network byte order; this is the only field that 1580 requires such conversion. There are 2^32 XDR enumeration values, 1581 2^16 of which are palindromes, which is adequate for the foreseeable 1582 future. If there is a need for more assignments, non-palindromes can 1583 be assigned. 1585 7. IANA Considerations 1587 The Internet Assigned Numbers Authority (IANA) is requested to create 1588 three registries: one for WOTS+ signatures as defined in Section 3, 1589 one for XMSS signatures and one for XMSS^MT signatures; the latter 1590 two being defined in Section 4. For the sake of clarity and 1591 convenience, the first sets of WOTS+, XMSS, and XMSS^MT parameter 1592 sets are defined in Section 5. Additions to these registries require 1593 that a specification be documented in an RFC or another permanent and 1594 readily available reference in sufficient details to make 1595 interoperability between independent implementations possible. Each 1596 entry in the registry contains the following elements: 1598 a short name, such as "XMSS_SHA2-512_M64_W16_H20", 1600 a positive number, and 1602 a reference to a specification that completely defines the 1603 signature method test cases that can be used to verify the 1604 correctness of an implementation. 1606 Requests to add an entry to the registry MUST include the name and 1607 the reference. The number is assigned by IANA. These number 1608 assignments SHOULD use the smallest available palindromic number. 1609 Submitters SHOULD have their requests reviewed by the IRTF Crypto 1610 Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants 1611 that are unfamiliar with IANA processes should visit 1612 http://www.iana.org. 1614 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1615 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1616 are reserved for private use; no attempt will be made to prevent 1617 multiple sites from using the same value in different (and 1618 incompatible) ways [RFC2434]. 1620 The WOTS+ registry is as follows. 1622 +-------------------------+-------------+--------------------+ 1623 | Name | Reference | Numeric Identifier | 1624 +-------------------------+-------------+--------------------+ 1625 | WOTSP_SHA2-256_M32_W16 | Section 5.1 | 0x01000001 | 1626 | | | | 1627 | WOTSP_SHA2-512_M64_W16 | Section 5.1 | 0x02000002 | 1628 +-------------------------+-------------+--------------------+ 1630 Table 4 1632 The XMSS registry is as follows. 1634 +----------------------------+-------------+--------------------+ 1635 | Name | Reference | Numeric Identifier | 1636 +----------------------------+-------------+--------------------+ 1637 | XMSS_SHA2-256_M32_W16_H10 | Section 5.2 | 0x01000001 | 1638 | | | | 1639 | XMSS_SHA2-256_M32_W16_H16 | Section 5.2 | 0x02000002 | 1640 | | | | 1641 | XMSS_SHA2-256_M32_W16_H20 | Section 5.2 | 0x03000003 | 1642 | | | | 1643 | XMSS_SHA2-512_M64_W16_H10 | Section 5.2 | 0x04000004 | 1644 | | | | 1645 | XMSS_SHA2-512_M64_W16_H16 | Section 5.2 | 0x05000005 | 1646 | | | | 1647 | XMSS_SHA2-512_M64_W16_H20 | Section 5.2 | 0x06000006 | 1648 +----------------------------+-------------+--------------------+ 1650 Table 5 1652 The XMSS^MT registry is as follows. 1654 +---------------------------------+-------------+-------------------+ 1655 | Name | Reference | Numeric | 1656 | | | Identifier | 1657 +---------------------------------+-------------+-------------------+ 1658 | XMSSMT_SHA2-256_M32_W16_H20_D2 | Section 5.3 | 0x01000001 | 1659 | | | | 1660 | XMSSMT_SHA2-256_M32_W16_H20_D4 | Section 5.3 | 0x02000002 | 1661 | | | | 1662 | XMSSMT_SHA2-256_M32_W16_H40_D2 | Section 5.3 | 0x03000003 | 1663 | | | | 1664 | XMSSMT_SHA2-256_M32_W16_H40_D4 | Section 5.3 | 0x04000004 | 1665 | | | | 1666 | XMSSMT_SHA2-256_M32_W16_H40_D8 | Section 5.3 | 0x05000005 | 1667 | | | | 1668 | XMSSMT_SHA2-256_M32_W16_H60_D3 | Section 5.3 | 0x06000006 | 1669 | | | | 1670 | XMSSMT_SHA2-256_M32_W16_H60_D6 | Section 5.3 | 0x07000007 | 1671 | | | | 1672 | XMSSMT_SHA2-256_M32_W16_H60_D12 | Section 5.3 | 0x08000008 | 1673 | | | | 1674 | XMSSMT_SHA2-512_M64_W16_H20_D2 | Section 5.3 | 0x09000009 | 1675 | | | | 1676 | XMSSMT_SHA2-512_M64_W16_H20_D4 | Section 5.3 | 0x0a00000a | 1677 | | | | 1678 | XMSSMT_SHA2-512_M64_W16_H40_D2 | Section 5.3 | 0x0b00000b | 1679 | | | | 1680 | XMSSMT_SHA2-512_M64_W16_H40_D4 | Section 5.3 | 0x0c00000c | 1681 | | | | 1682 | XMSSMT_SHA2-512_M64_W16_H40_D8 | Section 5.3 | 0x0d00000d | 1683 | | | | 1684 | XMSSMT_SHA2-512_M64_W16_H60_D3 | Section 5.3 | 0x0e00000e | 1685 | | | | 1686 | XMSSMT_SHA2-512_M64_W16_H60_D6 | Section 5.3 | 0x0f00000f | 1687 | | | | 1688 | XMSSMT_SHA2-512_M64_W16_H60_D12 | Section 5.3 | 0x01010101 | 1689 +---------------------------------+-------------+-------------------+ 1691 Table 6 1693 An IANA registration of a signature system does not constitute an 1694 endorsement of that system or its security. 1696 8. Security Considerations 1698 A signature system is considered secure if it prevents an attacker 1699 from forging a valid signature. More specifically, consider a 1700 setting in which an attacker gets a public key and can learn 1701 signatures on arbitrary messages of his choice. A signature system 1702 is secure if, even in this setting, the attacker can not produce a 1703 message signature pair of his choosing such that the verification 1704 algorithm accepts. 1706 Preventing an attacker from mounting an attack means that the attack 1707 is computationally too expensive to be carried out. There exist 1708 various estimates when a computation is too expensive to be done. 1709 For that reason, this note only describes how expensive it is for an 1710 attacker to generate a forgery. Parameters are accompanied by a bit 1711 security value. The meaning of bit security is as follows. A 1712 parameter set grants b bits of security if the best attack takes at 1713 least 2^(b-1) bit operations to achieve a success probability of 1/2. 1714 Hence, to mount a successful attack, an attacker needs to perform 2^b 1715 bit operations on average. How the given values for bit security 1716 were estimated is described below. 1718 8.1. Security Proofs 1720 There exist formal security proofs for schemes very similar to those 1721 described here in the literature [Huelsing13a]. These proofs show 1722 that an attacker has to break at least one out of certain security 1723 properties of the used hash functions and PRFs to forge a signature. 1724 The proofs in [Huelsing13a] do not consider the initial message 1725 compression and the extended randomized hashing used here. For the 1726 original schemes, these proofs show that an attacker has to break 1727 certain minimal security properties. In particular, it is not 1728 sufficient to break the collision resistance of the hash functions to 1729 generate a forgery. 1731 It is folklore that one can securely combine a secure signature 1732 scheme for fixed length messages with an initial message digest. It 1733 is easy to prove that an attacker either must break the security of 1734 the fixed-input-length signature scheme or the collision resistance 1735 of the used hash function. The descriptions of XMSS and XMSS^MT in 1736 this note use a known trick to prevent the applicability of collision 1737 attacks. Namely, the schemes use a randomized message hash. For 1738 technical reasons, it is not possible to formally prove in the 1739 standard model that the resulting scheme is secure if the hash 1740 function is not collision-resistant but fulfills some weaker security 1741 properties. However, in the random oracle model such a proof is 1742 trivial. 1744 While the basic randomized hashing used in the original descriptions 1745 of the schemes allows to prove that it is not enough for an adversary 1746 to break the collision resistance of the underlying hash function. 1747 However, it turns out that an attacker could launch a multi-target 1748 second-preimage attack. The (simplified) reason is that the 1749 adversary learns in the order of 2^h hash function input-output pairs 1750 and it suffices to find a second-preimage for one out of those. 1751 Hence, an attacker can do a brute force search until he finds an 1752 input that matches one of the given outputs. 1754 The extended randomized hashing used here makes the hash function 1755 calls position dependent. Hence, the above attack does not work 1756 anymore because each hash function evaluation during an attack can 1757 only target one output value. This can also be shown formally. 1759 The given bit security values were estimated based on the complexity 1760 of the best known generic attacks against the required security 1761 properties of the used hash functions and PRFs. 1763 8.2. Security Assumptions 1765 The security assumptions made to argue for the security of the 1766 described schemes are minimal. Any signature algorithm that allows 1767 arbitrary size messages relies on the security of a cryptographic 1768 hash function. For the schemes described here this is already 1769 sufficient to be secure. In contrast, common signature schemes like 1770 RSA, DSA, and ECDSA additionally rely on the conjectured hardness of 1771 certain mathematical problems. 1773 8.3. Post-Quantum Security 1775 A post-quantum cryptosystem is a system that is secure against 1776 attackers with access to a reasonably sized quantum computer. At the 1777 time of writing this note, whether or not it is feasible to build 1778 such machine is an open conjecture. However, significant progress 1779 was made over the last few years in this regard. 1781 In contrast to RSA, DSA, and ECDSA, the described signature systems 1782 are post-quantum-secure if they are used with an appropriate 1783 cryptographic hash function. In particular, for post-quantum 1784 security, the size of m and n must be twice the size required for 1785 classical security. This is in order to protect against quantum 1786 square root attacks due to Grover's algorithm. It has been shown 1787 that Grover's algorithm is optimal for finding preimages and 1788 collisions. 1790 9. Acknowledgements 1792 We would like to thank Scott Fluhrer, Burt Kaliski, Adam Langley, 1793 David McGrew, and Sean Parkinson for their help and comments. 1795 10. References 1797 10.1. Normative References 1799 [FIPS180] National Institute of Standards and Technology, "Secure 1800 Hash Standard (SHS)", FIPS 180-4, 2012. 1802 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1803 Requirement Levels", BCP 14, RFC 2119, March 1997. 1805 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1806 IANA Considerations Section in RFCs", BCP 26, RFC 2434, 1807 October 1998. 1809 [RFC4506] Eisler, M., "XDR: External Data Representation Standard", 1810 STD 67, RFC 4506, May 2006. 1812 [RFC7539] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF 1813 Protocols", RFC 7539, May 2015. 1815 10.2. Informative References 1817 [BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A 1818 Practical Forward Secure Signature Scheme Based on Minimal 1819 Security Assumptions", Lecture Notes in Computer Science 1820 volume 7071. Post-Quantum Cryptography, 2011. 1822 [BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based 1823 Digital Signature Schemes", Book chapter Post-Quantum 1824 Cryptography, Springer, 2009. 1826 [BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., 1827 Niederhagen, R., Papachristodoulou, L., Schneider, M., 1828 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical 1829 Stateless Hash-Based Signatures", Lecture Notes in 1830 Computer Science volume 9056. Advances in Cryptology - 1831 EUROCRYPT, 2015. 1833 [DC14] McGrew, D. and M. Curcio, "Hash-based signatures", draft- 1834 mcgrew-hash-sigs-02 (work in progress), July 2014. 1836 [HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal 1837 Parameters for XMSS^MT", Lecture Notes in Computer Science 1838 volume 8128. CD-ARES, 2013. 1840 [Huelsing13] 1841 Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based 1842 Signature Schemes", Lecture Notes in Computer Science 1843 volume 7918. Progress in Cryptology - AFRICACRYPT, 2013. 1845 [Huelsing13a] 1846 Huelsing, A., "Practical Forward Secure Signatures using 1847 Minimal Security Assumptions", PhD thesis TU Darmstadt, 1848 2013. 1850 [Kaliski15] 1851 Kaliski, B., "Panel: Shoring up the Infrastructure: A 1852 Strategy for Standardizing Hash Signatures", NIST Workshop 1853 on Cybersecurity in a Post-Quantum World, 2015. 1855 [Merkle79] 1856 Merkle, R., "Secrecy, Authentication, and Public Key 1857 Systems", Stanford University Information Systems 1858 Laboratory Technical Report 1979-1, 1979. 1860 Appendix A. WOTS+ XDR Formats 1862 The WOTS+ signature and public key formats are formally defined using 1863 XDR [RFC4506] in order to provide an unambiguous, machine readable 1864 definition. Though XDR is used, these formats are simple and easy to 1865 parse without any special tools. To avoid the need to convert to and 1866 from network / host byte order, the enumeration values are all 1867 palindromes. 1869 WOTS+ parameter sets are defined using XDR syntax as follows: 1871 /* ots_algorithm_type identifies a particular 1872 signature algorithm */ 1874 enum ots_algorithm_type { 1875 wotsp_reserved = 0x00000000, 1876 wotsp_sha2-256_m32_w16 = 0x01000001, 1877 wotsp_sha2-512_m64_w16 = 0x02000002, 1878 }; 1880 WOTS+ signatures are defined using XDR syntax as follows: 1882 /* Byte strings */ 1884 typedef opaque bytestring32[32]; 1885 typedef opaque bytestring64[64]; 1887 union ots_signature switch (ots_algorithm_type type) { 1888 case wotsp_sha2-256_m32_w16: 1889 bytestring32 ots_sig_m32_len67[67]; 1891 case wotsp_sha2-512_m64_w16: 1892 bytestring64 ots_sig_m64_len18[131]; 1894 default: 1895 void; /* error condition */ 1896 }; 1898 WOTS+ public keys are defined using XDR syntax as follows: 1900 union ots_pubkey switch (ots_algorithm_type type) { 1901 case wotsp_sha2-256_m32_w16: 1902 bytestring32 ots_pubk_m32_len67[67]; 1904 case wotsp_sha2-512_m64_w16: 1905 bytestring64 ots_pubk_m64_len18[131]; 1907 default: 1908 void; /* error condition */ 1909 }; 1911 Appendix B. XMSS XDR Formats 1912 XMSS parameter sets are defined using XDR syntax as follows: 1914 /* Byte strings */ 1916 typedef opaque bytestring4[4]; 1918 /* Definition of parameter sets */ 1920 enum xmss_algorithm_type { 1921 xmss_reserved = 0x00000000, 1923 /* 256 bit classical security, 128 bit post-quantum security */ 1925 xmss_sha2-256_m32_w16_h10 = 0x01000001, 1926 xmss_sha2-256_m32_w16_h16 = 0x02000002, 1927 xmss_sha2-256_m32_w16_h20 = 0x03000003, 1929 /* 512 bit classical security, 256 bit post-quantum security */ 1931 xmss_sha2-512_m64_w16_h10 = 0x04000004, 1932 xmss_sha2-512_m64_w16_h16 = 0x05000005, 1933 xmss_sha2-512_m64_w16_h20 = 0x06000006, 1934 }; 1936 XMSS signatures are defined using XDR syntax as follows: 1938 /* Authentication path types */ 1940 union xmss_path switch (xmss_algorithm_type type) { 1941 case xmss_sha2-256_m32_w16_h10: 1942 bytestring32 path_n32_t10[10]; 1944 case xmss_sha2-256_m32_w16_h16: 1945 bytestring32 path_n32_t16[16]; 1947 case xmss_sha2-256_m32_w16_h20: 1948 bytestring32 path_n32_t20[20]; 1950 case xmss_sha2-512_m64_w16_h10: 1951 bytestring64 path_n64_t10[10]; 1953 case xmss_sha2-512_m64_w16_h16: 1954 bytestring64 path_n64_t16[16]; 1956 case xmss_sha2-512_m64_w16_h20: 1958 bytestring64 path_n64_t20[20]; 1960 default: 1961 void; /* error condition */ 1962 }; 1964 /* Types for XMSS random strings */ 1966 union random_string_xmss switch (xmss_algorithm_type type) { 1967 case xmss_sha2-256_m32_w16_h10: 1968 case xmss_sha2-256_m32_w16_h16: 1969 case xmss_sha2-256_m32_w16_h20: 1970 bytestring32 rand_m32; 1972 case xmss_sha2-512_m64_w16_h10: 1973 case xmss_sha2-512_m64_w16_h16: 1974 case xmss_sha2-512_m64_w16_h20: 1975 bytestring64 rand_m64; 1977 default: 1978 void; /* error condition */ 1979 }; 1981 /* Corresponding WOTS+ type for given XMSS type */ 1983 union xmss_ots_signature switch (xmss_algorithm_type type) { 1984 case xmss_sha2-256_m32_w16_h10: 1985 case xmss_sha2-256_m32_w16_h16: 1986 case xmss_sha2-256_m32_w16_h20: 1987 wotsp_sha2-256_m32_w16; 1989 case xmss_sha2-512_m64_w16_h10: 1990 case xmss_sha2-512_m64_w16_h16: 1991 case xmss_sha2-512_m64_w16_h20: 1992 wotsp_sha2-512_m64_w16; 1994 default: 1995 void; /* error condition */ 1996 }; 1998 /* XMSS signature structure */ 2000 struct xmss_signature { 2001 /* WOTS+ key pair index */ 2002 bytestring4 idx_sig; 2003 /* Random string for randomized hashing */ 2004 random_string_xmss rand_string; 2005 /* WOTS+ signature */ 2006 xmss_ots_signature sig_ots; 2007 /* authentication path */ 2008 xmss_path nodes; 2009 }; 2011 XMSS public keys are defined using XDR syntax as follows: 2013 /* Types for bitmask seed */ 2015 union seed switch (xmss_algorithm_type type) { 2016 case xmss_sha2-256_m32_w16_h10: 2017 case xmss_sha2-256_m32_w16_h16: 2018 case xmss_sha2-256_m32_w16_h20: 2019 bytestring32 seed_n32; 2021 case xmss_sha2-512_m64_w16_h10: 2022 case xmss_sha2-512_m64_w16_h16: 2023 case xmss_sha2-512_m64_w16_h20: 2024 bytestring64 seed_n64; 2026 default: 2027 void; /* error condition */ 2028 }; 2030 /* Types for XMSS root node */ 2032 union xmss_root switch (xmss_algorithm_type type) { 2033 case xmss_sha2-256_m32_w16_h10: 2034 case xmss_sha2-256_m32_w16_h16: 2035 case xmss_sha2-256_m32_w16_h20: 2036 bytestring32 root_n32; 2038 case xmss_sha2-512_m64_w16_h10: 2039 case xmss_sha2-512_m64_w16_h16: 2040 case xmss_sha2-512_m64_w16_h20: 2041 bytestring64 root_n64; 2043 default: 2044 void; /* error condition */ 2045 }; 2047 /* XMSS public key structure */ 2049 struct xmss_public_key { 2050 xmss_root root; /* Root node */ 2051 seed SEED; /* Seed for bitmasks */ 2052 }; 2054 Appendix C. XMSS^MT XDR Formats 2056 XMSS^MT parameter sets are defined using XDR syntax as follows: 2058 /* Byte strings */ 2060 typedef opaque bytestring3[3]; 2061 typedef opaque bytestring5[5]; 2062 typedef opaque bytestring8[8]; 2064 /* Definition of parameter sets */ 2066 enum xmssmt_algorithm_type { 2067 xmssmt_reserved = 0x00000000, 2069 /* 256 bit classical security, 128 bit post-quantum security */ 2071 xmssmt_sha2-256_m32_w16_h20_d2 = 0x01000001, 2072 xmssmt_sha2-256_m32_w16_h20_d4 = 0x02000002, 2073 xmssmt_sha2-256_m32_w16_h40_d2 = 0x03000003, 2074 xmssmt_sha2-256_m32_w16_h40_d4 = 0x04000004, 2075 xmssmt_sha2-256_m32_w16_h40_d8 = 0x05000005, 2076 xmssmt_sha2-256_m32_w16_h60_d3 = 0x06000006, 2077 xmssmt_sha2-256_m32_w16_h60_d6 = 0x07000007, 2078 xmssmt_sha2-256_m32_w16_h60_d12 = 0x08000008, 2080 /* 512 bit classical security, 256 bit post-quantum security */ 2082 xmssmt_sha2-512_m64_w16_h20_d2 = 0x09000009, 2083 xmssmt_sha2-512_m64_w16_h20_d4 = 0x0a00000a, 2084 xmssmt_sha2-512_m64_w16_h40_d2 = 0x0b00000b, 2085 xmssmt_sha2-512_m64_w16_h40_d4 = 0x0c00000c, 2086 xmssmt_sha2-512_m64_w16_h40_d8 = 0x0d00000d, 2087 xmssmt_sha2-512_m64_w16_h60_d3 = 0x0e00000e, 2088 xmssmt_sha2-512_m64_w16_h60_d6 = 0x0f00000f, 2089 xmssmt_sha2-512_m64_w16_h60_d12 = 0x01010101, 2090 }; 2092 XMSS^MT signatures are defined using XDR syntax as follows: 2094 /* Type for XMSS^MT key pair index */ 2095 /* Depends solely on h */ 2097 union idx_sig_xmssmt switch (xmss_algorithm_type type) { 2098 case xmssmt_sha2-256_m32_w16_h20_d2: 2100 case xmssmt_sha2-256_m32_w16_h20_d4: 2101 case xmssmt_sha2-512_m64_w16_h20_d2: 2102 case xmssmt_sha2-512_m64_w16_h20_d4: 2103 bytestring3 idx3; 2105 case xmssmt_sha2-256_m32_w16_h40_d2: 2106 case xmssmt_sha2-256_m32_w16_h40_d4: 2107 case xmssmt_sha2-256_m32_w16_h40_d8: 2108 case xmssmt_sha2-512_m64_w16_h40_d2: 2109 case xmssmt_sha2-512_m64_w16_h40_d4: 2110 case xmssmt_sha2-512_m64_w16_h40_d8: 2111 bytestring5 idx5; 2113 case xmssmt_sha2-256_m32_w16_h60_d3: 2114 case xmssmt_sha2-256_m32_w16_h60_d6: 2115 case xmssmt_sha2-256_m32_w16_h60_d12: 2116 case xmssmt_sha2-512_m64_w16_h60_d3: 2117 case xmssmt_sha2-512_m64_w16_h60_d6: 2118 case xmssmt_sha2-512_m64_w16_h60_d12: 2119 bytestring8 idx8; 2121 default: 2122 void; /* error condition */ 2123 }; 2125 union random_string_xmssmt switch (xmssmt_algorithm_type type) { 2126 case xmssmt_sha2-256_m32_w16_h20_d2: 2127 case xmssmt_sha2-256_m32_w16_h20_d4: 2128 case xmssmt_sha2-256_m32_w16_h40_d2: 2129 case xmssmt_sha2-256_m32_w16_h40_d4: 2130 case xmssmt_sha2-256_m32_w16_h40_d8: 2131 case xmssmt_sha2-256_m32_w16_h60_d3: 2132 case xmssmt_sha2-256_m32_w16_h60_d6: 2133 case xmssmt_sha2-256_m32_w16_h60_d12: 2134 bytestring32 rand_m32; 2136 case xmssmt_sha2-512_m64_w16_h20_d2: 2137 case xmssmt_sha2-512_m64_w16_h20_d4: 2138 case xmssmt_sha2-512_m64_w16_h40_d2: 2139 case xmssmt_sha2-512_m64_w16_h40_d4: 2140 case xmssmt_sha2-512_m64_w16_h40_d8: 2141 case xmssmt_sha2-512_m64_w16_h60_d3: 2142 case xmssmt_sha2-512_m64_w16_h60_d6: 2143 case xmssmt_sha2-512_m64_w16_h60_d12: 2144 bytestring64 rand_m64; 2146 default: 2147 void; /* error condition */ 2149 }; 2151 struct xmss_reduced_bottom { 2152 xmss_ots_signature sig_ots; /* WOTS+ signature */ 2153 xmss_path nodes; /* authentication path */ 2154 }; 2156 /* Type for individual reduced XMSS signatures on higher layers */ 2158 union xmss_reduced_others (xmss_algorithm_type type) { 2159 case xmssmt_sha2-256_m32_w16_h20_d2: 2160 case xmssmt_sha2-256_m32_w16_h20_d4: 2161 bytestring32 xmss_reduced_n32_t87[87]; 2163 case xmssmt_sha2-256_m32_w16_h40_d2: 2164 case xmssmt_sha2-256_m32_w16_h40_d4: 2165 case xmssmt_sha2-256_m32_w16_h40_d8: 2166 bytestring32 xmss_reduced_n32_t107[107]; 2168 case xmssmt_sha2-256_m32_w16_h60_d3: 2169 case xmssmt_sha2-256_m32_w16_h60_d6: 2170 case xmssmt_sha2-256_m32_w16_h60_d12: 2171 bytestring32 xmss_reduced_n32_t127[127]; 2173 case xmssmt_sha2-512_m64_w16_h20_d2: 2174 case xmssmt_sha2-512_m64_w16_h20_d4: 2175 bytestring64 xmss_reduced_n64_t151[151]; 2177 case xmssmt_sha2-512_m64_w16_h40_d2: 2178 case xmssmt_sha2-512_m64_w16_h40_d4: 2179 case xmssmt_sha2-512_m64_w16_h40_d8: 2180 bytestring64 xmss_reduced_n64_t171[171]; 2182 case xmssmt_sha2-512_m64_w16_h60_d3: 2183 case xmssmt_sha2-512_m64_w16_h60_d6: 2184 case xmssmt_sha2-512_m64_w16_h60_d12: 2185 bytestring64 xmss_reduced_n64_t191[191]; 2187 default: 2188 void; /* error condition */ 2189 }; 2191 /* xmss_reduced_array depends on d */ 2193 union xmss_reduced_array (xmss_algorithm_type type) { 2194 case xmssmt_sha2-256_m32_w16_h20_d2: 2195 case xmssmt_sha2-512_m64_w16_h20_d2: 2196 case xmssmt_sha2-256_m32_w16_h40_d2: 2198 case xmssmt_sha2-512_m64_w16_h40_d2: 2199 xmss_reduced_others xmss_red_arr_d2[1]; 2201 case xmssmt_sha2-256_m32_w16_h60_d3: 2202 case xmssmt_sha2-512_m64_w16_h60_d3: 2203 xmss_reduced_others xmss_red_arr_d3[2]; 2205 case xmssmt_sha2-256_m32_w16_h20_d4: 2206 case xmssmt_sha2-512_m64_w16_h20_d4: 2207 case xmssmt_sha2-256_m32_w16_h40_d4: 2208 case xmssmt_sha2-512_m64_w16_h40_d4: 2209 xmss_reduced_others xmss_red_arr_d4[3]; 2211 case xmssmt_sha2-256_m32_w16_h60_d6: 2212 case xmssmt_sha2-512_m64_w16_h60_d6: 2213 xmss_reduced_others xmss_red_arr_d6[5]; 2215 case xmssmt_sha2-256_m32_w16_h40_d8: 2216 case xmssmt_sha2-512_m64_w16_h40_d8: 2217 xmss_reduced_others xmss_red_arr_d8[7]; 2219 case xmssmt_sha2-256_m32_w16_h60_d12: 2220 case xmssmt_sha2-512_m64_w16_h60_d12: 2221 xmss_reduced_others xmss_red_arr_d12[11]; 2223 default: 2224 void; /* error condition */ 2225 }; 2227 /* XMSS^MT signature structure */ 2229 struct xmssmt_signature { 2230 /* WOTS+ key pair index */ 2231 idx_sig_xmssmt idx_sig; 2232 /* Random string for randomized hashing */ 2233 random_string_xmssmt randomness; 2234 /* Reduced bottom layer XMSS signature */ 2235 xmss_reduced_bottom; 2236 /* Array of reduced XMSS signatures with message length n */ 2237 xmss_reduced_array; 2238 }; 2240 XMSS^MT public keys are defined using XDR syntax as follows: 2242 /* Types for bitmask seed */ 2243 union seed switch (xmssmt_algorithm_type type) { 2244 case xmssmt_sha2-256_m32_w16_h20_d2: 2245 case xmssmt_sha2-256_m32_w16_h40_d4: 2246 case xmssmt_sha2-256_m32_w16_h60_d6: 2247 case xmssmt_sha2-256_m32_w16_h20_d4: 2248 case xmssmt_sha2-256_m32_w16_h40_d8: 2249 case xmssmt_sha2-256_m32_w16_h60_d12: 2250 case xmssmt_sha2-256_m32_w16_h40_d2: 2251 case xmssmt_sha2-256_m32_w16_h60_d3: 2252 bytestring32 seed_n32; 2254 case xmssmt_sha2-512_m64_w16_h20_d2: 2255 case xmssmt_sha2-512_m64_w16_h40_d4: 2256 case xmssmt_sha2-512_m64_w16_h60_d6: 2257 case xmssmt_sha2-512_m64_w16_h20_d4: 2258 case xmssmt_sha2-512_m64_w16_h40_d8: 2259 case xmssmt_sha2-512_m64_w16_h60_d12: 2260 case xmssmt_sha2-512_m64_w16_h40_d2: 2261 case xmssmt_sha2-512_m64_w16_h60_d3: 2262 bytestring64 seed_n64; 2264 default: 2265 void; /* error condition */ 2266 }; 2268 /* Types for XMSS^MT root node */ 2270 union xmssmt_root switch (xmssmt_algorithm_type type) { 2271 case xmssmt_sha2-256_m32_w16_h20_d2: 2272 case xmssmt_sha2-256_m32_w16_h20_d4: 2273 case xmssmt_sha2-256_m32_w16_h40_d2: 2274 case xmssmt_sha2-256_m32_w16_h40_d4: 2275 case xmssmt_sha2-256_m32_w16_h40_d8: 2276 case xmssmt_sha2-256_m32_w16_h60_d3: 2277 case xmssmt_sha2-256_m32_w16_h60_d6: 2278 case xmssmt_sha2-256_m32_w16_h60_d12: 2279 bytestring32 root_n32; 2281 case xmssmt_sha2-512_m64_w16_h20_d2: 2282 case xmssmt_sha2-512_m64_w16_h20_d4: 2283 case xmssmt_sha2-512_m64_w16_h40_d2: 2284 case xmssmt_sha2-512_m64_w16_h40_d4: 2285 case xmssmt_sha2-512_m64_w16_h40_d8: 2286 case xmssmt_sha2-512_m64_w16_h60_d3: 2287 case xmssmt_sha2-512_m64_w16_h60_d6: 2288 case xmssmt_sha2-512_m64_w16_h60_d12: 2289 bytestring64 root_n64; 2291 default: 2292 void; /* error condition */ 2293 }; 2295 /* XMSS^MT public key structure */ 2297 struct xmssmt_public_key { 2298 xmssmt_root root; /* Root node */ 2299 seed SEED; /* Seed for bitmasks */ 2300 }; 2302 Appendix D. Changed since draft-irtf-cfrg-xmss-hash-based-signatures-00 2304 Added keying of hash functions with pseudorandomly generated keys 2305 for all hashes but the message hash. A Hash Function Address 2306 Scheme is introduced that for. For further information please 2307 take a look at sections Section 2.5 and Section 8. 2309 Replaced bitmasks by pseudorandomly generated values. 2311 Removed zero bitmasks, as we now only store a small seed (n bytes) 2312 for bitmask generation, which is pretty small compared to the 2313 bitmask solution before. 2315 Removed w = 8 to reduce huge number of parameter sets. Simplified 2316 algorithms (like base_w) as we don't need to support the w = 8 2317 case now. 2319 Removed w = 4 from the suggested parameter sets. 2321 Changed 'l' to 'len, 'l_1' to 'len_1' and 'l_2' to 'len_2' to 2322 avoid confusion between the characters 'l' and '1'. 2324 Changed appearances of "is equal" or "mod" to % operator for 2325 better readability. 2327 Removed the OID in the XMSS and XMSS^MT signatures. This was 2328 redundant, since the OID is already part of the public key in both 2329 cases. 2331 Replaced SHA-3 by SHA-2 in light of more widespread usage and 2332 faster implementations for SHA-2. 2334 Fixed the log notation in the Schemes section. 2336 Removed AES-based parameter sets. 2338 Adapted XDR according to the changes. 2340 Removed definitions like max() from notation, when no longer 2341 needed in this document. 2343 Authors' Addresses 2345 Andreas Huelsing 2346 TU Eindhoven 2347 P.O. Box 513 2348 Eindhoven 5600 MB 2349 The Netherlands 2351 Email: a.t.huelsing@tue.nl 2353 Denis Butin 2354 TU Darmstadt 2355 Hochschulstrasse 10 2356 Darmstadt 64289 2357 Germany 2359 Email: dbutin@cdc.informatik.tu-darmstadt.de 2361 Stefan-Lukas Gazdag 2362 genua GmbH 2363 Domagkstrasse 7 2364 Kirchheim bei Muenchen 85551 2365 Germany 2367 Email: stefan-lukas_gazdag@genua.eu 2369 Aziz Mohaisen 2370 Verisign Labs 2371 12061 Bluemont Way 2372 Reston, VA 20190 2374 Phone: +1 703 948-3200 2375 Email: amohaisen@verisign.com