idnits 2.17.1 draft-irtf-cfrg-xmss-hash-based-signatures-12.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 (January 10, 2018) is 2291 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 1300 -- Looks like a reference, but probably isn't: '1' on line 1298 -- Looks like a reference, but probably isn't: '2' on line 2949 -- Looks like a reference, but probably isn't: '3' on line 2955 == Missing Reference: '2i' is mentioned on line 982, but not defined -- Looks like a reference, but probably isn't: '32' on line 2518 -- Looks like a reference, but probably isn't: '64' on line 2519 -- Looks like a reference, but probably isn't: '67' on line 2539 -- Looks like a reference, but probably isn't: '131' on line 2543 -- Looks like a reference, but probably isn't: '4' on line 2965 -- Looks like a reference, but probably isn't: '10' on line 2605 -- Looks like a reference, but probably isn't: '16' on line 2609 -- Looks like a reference, but probably isn't: '20' on line 2613 -- Looks like a reference, but probably isn't: '5' on line 2744 -- Looks like a reference, but probably isn't: '8' on line 2978 -- Looks like a reference, but probably isn't: '77' on line 2896 -- Looks like a reference, but probably isn't: '72' on line 2904 -- Looks like a reference, but probably isn't: '87' on line 2910 -- Looks like a reference, but probably isn't: '141' on line 2918 -- Looks like a reference, but probably isn't: '136' on line 2926 -- Looks like a reference, but probably isn't: '151' on line 2932 -- Looks like a reference, but probably isn't: '6' on line 2971 -- Looks like a reference, but probably isn't: '12' on line 2984 == Outdated reference: A later version (-15) exists of draft-mcgrew-hash-sigs-08 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 24 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group A. Huelsing 3 Internet-Draft TU Eindhoven 4 Intended status: Informational D. Butin 5 Expires: July 14, 2018 TU Darmstadt 6 S. Gazdag 7 genua GmbH 8 J. Rijneveld 9 Radboud University 10 A. Mohaisen 11 University of Central Florida 12 January 10, 2018 14 XMSS: Extended Hash-Based Signatures 15 draft-irtf-cfrg-xmss-hash-based-signatures-12 17 Abstract 19 This note describes the eXtended Merkle Signature Scheme (XMSS), a 20 hash-based digital signature system. It follows existing 21 descriptions in scientific literature. The note specifies the WOTS+ 22 one-time signature scheme, a single-tree (XMSS) and a multi-tree 23 variant (XMSS^MT) of XMSS. Both variants use WOTS+ as a main 24 building block. XMSS provides cryptographic digital signatures 25 without relying on the conjectured hardness of mathematical problems. 26 Instead, it is proven that it only relies on the properties of 27 cryptographic hash functions. XMSS provides strong security 28 guarantees and is even secure when the collision resistance of the 29 underlying hash function is broken. It is suitable for compact 30 implementations, relatively simple to implement, and naturally 31 resists side-channel attacks. Unlike most other signature systems, 32 hash-based signatures can withstand so far known attacks using 33 quantum computers. 35 Status of This Memo 37 This Internet-Draft is submitted in full conformance with the 38 provisions of BCP 78 and BCP 79. 40 Internet-Drafts are working documents of the Internet Engineering 41 Task Force (IETF). Note that other groups may also distribute 42 working documents as Internet-Drafts. The list of current Internet- 43 Drafts is at https://datatracker.ietf.org/drafts/current/. 45 Internet-Drafts are draft documents valid for a maximum of six months 46 and may be updated, replaced, or obsoleted by other documents at any 47 time. It is inappropriate to use Internet-Drafts as reference 48 material or to cite them other than as "work in progress." 49 This Internet-Draft will expire on July 14, 2018. 51 Copyright Notice 53 Copyright (c) 2018 IETF Trust and the persons identified as the 54 document authors. All rights reserved. 56 This document is subject to BCP 78 and the IETF Trust's Legal 57 Provisions Relating to IETF Documents 58 (https://trustee.ietf.org/license-info) in effect on the date of 59 publication of this document. Please review these documents 60 carefully, as they describe your rights and restrictions with respect 61 to this document. Code Components extracted from this document must 62 include Simplified BSD License text as described in Section 4.e of 63 the Trust Legal Provisions and are provided without warranty as 64 described in the Simplified BSD License. 66 Table of Contents 68 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 69 1.1. CFRG Note on Post-Quantum Cryptography . . . . . . . . . 5 70 1.2. Conventions Used In This Document . . . . . . . . . . . . 6 71 2. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 6 72 2.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 6 73 2.2. Functions . . . . . . . . . . . . . . . . . . . . . . . . 6 74 2.3. Operators . . . . . . . . . . . . . . . . . . . . . . . . 6 75 2.4. Integer to Byte Conversion . . . . . . . . . . . . . . . 7 76 2.5. Hash Function Address Scheme . . . . . . . . . . . . . . 7 77 2.6. Strings of Base w Numbers . . . . . . . . . . . . . . . . 10 78 2.7. Member Functions . . . . . . . . . . . . . . . . . . . . 12 79 3. Primitives . . . . . . . . . . . . . . . . . . . . . . . . . 12 80 3.1. WOTS+ One-Time Signatures . . . . . . . . . . . . . . . . 12 81 3.1.1. WOTS+ Parameters . . . . . . . . . . . . . . . . . . 13 82 3.1.1.1. WOTS+ Functions . . . . . . . . . . . . . . . . . 13 83 3.1.2. WOTS+ Chaining Function . . . . . . . . . . . . . . . 14 84 3.1.3. WOTS+ Private Key . . . . . . . . . . . . . . . . . . 14 85 3.1.4. WOTS+ Public Key . . . . . . . . . . . . . . . . . . 15 86 3.1.5. WOTS+ Signature Generation . . . . . . . . . . . . . 16 87 3.1.6. WOTS+ Signature Verification . . . . . . . . . . . . 18 88 3.1.7. Pseudorandom Key Generation . . . . . . . . . . . . . 19 89 4. Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 90 4.1. XMSS: eXtended Merkle Signature Scheme . . . . . . . . . 19 91 4.1.1. XMSS Parameters . . . . . . . . . . . . . . . . . . . 20 92 4.1.2. XMSS Hash Functions . . . . . . . . . . . . . . . . . 21 93 4.1.3. XMSS Private Key . . . . . . . . . . . . . . . . . . 21 94 4.1.4. Randomized Tree Hashing . . . . . . . . . . . . . . . 21 95 4.1.5. L-Trees . . . . . . . . . . . . . . . . . . . . . . . 22 96 4.1.6. TreeHash . . . . . . . . . . . . . . . . . . . . . . 23 97 4.1.7. XMSS Key Generation . . . . . . . . . . . . . . . . . 24 98 4.1.8. XMSS Signature . . . . . . . . . . . . . . . . . . . 26 99 4.1.9. XMSS Signature Generation . . . . . . . . . . . . . . 27 100 4.1.10. XMSS Signature Verification . . . . . . . . . . . . . 29 101 4.1.11. Pseudorandom Key Generation . . . . . . . . . . . . . 31 102 4.1.12. Free Index Handling and Partial Private Keys . . . . 32 103 4.2. XMSS^MT: Multi-Tree XMSS . . . . . . . . . . . . . . . . 32 104 4.2.1. XMSS^MT Parameters . . . . . . . . . . . . . . . . . 32 105 4.2.2. XMSS^MT Key generation . . . . . . . . . . . . . . . 32 106 4.2.3. XMSS^MT Signature . . . . . . . . . . . . . . . . . . 35 107 4.2.4. XMSS^MT Signature Generation . . . . . . . . . . . . 36 108 4.2.5. XMSS^MT Signature Verification . . . . . . . . . . . 38 109 4.2.6. Pseudorandom Key Generation . . . . . . . . . . . . . 39 110 4.2.7. Free Index Handling and Partial Private Keys . . . . 40 111 5. Parameter Sets . . . . . . . . . . . . . . . . . . . . . . . 40 112 5.1. Implementing the functions . . . . . . . . . . . . . . . 40 113 5.2. WOTS+ Parameters . . . . . . . . . . . . . . . . . . . . 42 114 5.3. XMSS Parameters . . . . . . . . . . . . . . . . . . . . . 42 115 5.3.1. Parameter guide . . . . . . . . . . . . . . . . . . . 43 116 5.4. XMSS^MT Parameters . . . . . . . . . . . . . . . . . . . 44 117 5.4.1. Parameter guide . . . . . . . . . . . . . . . . . . . 46 118 6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 48 119 7. Reference Code . . . . . . . . . . . . . . . . . . . . . . . 49 120 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 49 121 9. Security Considerations . . . . . . . . . . . . . . . . . . . 53 122 9.1. Security Proofs . . . . . . . . . . . . . . . . . . . . . 53 123 9.2. Minimal Security Assumptions . . . . . . . . . . . . . . 55 124 9.3. Post-Quantum Security . . . . . . . . . . . . . . . . . . 55 125 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 56 126 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 56 127 11.1. Normative References . . . . . . . . . . . . . . . . . . 56 128 11.2. Informative References . . . . . . . . . . . . . . . . . 56 129 Appendix A. WOTS+ XDR Formats . . . . . . . . . . . . . . . . . 58 130 Appendix B. XMSS XDR Formats . . . . . . . . . . . . . . . . . . 59 131 Appendix C. XMSS^MT XDR Formats . . . . . . . . . . . . . . . . 64 132 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 71 134 1. Introduction 136 A (cryptographic) digital signature scheme provides asymmetric 137 message authentication. The key generation algorithm produces a key 138 pair consisting of a private and a public key. A message is signed 139 using a private key to produce a signature. A message/signature pair 140 can be verified using a public key. A One-Time Signature (OTS) 141 scheme allows using a key pair to sign exactly one message securely. 142 A Many-Time Signature (MTS) system can be used to sign multiple 143 messages. 145 OTS schemes, and MTS schemes composed from them, were proposed by 146 Merkle in 1979 [Merkle79]. They were well-studied in the 1990s and 147 have regained interest from the mid 2000s onwards because of their 148 resistance against quantum-computer-aided attacks. These kinds of 149 signature schemes are called hash-based signature schemes as they are 150 built out of a cryptographic hash function. Hash-based signature 151 schemes generally feature small private and public keys as well as 152 fast signature generation and verification but large signatures and 153 relatively slow key generation. In addition, they are suitable for 154 compact implementations that benefit various applications and are 155 naturally resistant to most kinds of side-channel attacks. 157 Some progress has already been made toward introducing and 158 standardizing hash-based signatures. McGrew, Curcio, and Fluhrer 159 have published an Internet-Draft [MCF17] specifying the Lamport- 160 Diffie-Winternitz-Merkle (LDWM) scheme, also taking into account 161 subsequent adaptations by Leighton and Micali. Independently, 162 Buchmann, Dahmen and Huelsing have proposed XMSS [BDH11], the 163 eXtended Merkle Signature Scheme, offering better efficiency and a 164 modern security proof. Very recently, the stateless hash-based 165 signature scheme SPHINCS was introduced [BHH15], with the intent of 166 being easier to deploy in current applications. A reasonable next 167 step toward introducing hash-based signatures is to complete the 168 specifications of the basic algorithms - LDWM, XMSS, SPHINCS and/or 169 variants [Kaliski15]. 171 The eXtended Merkle Signature Scheme (XMSS) [BDH11] is the latest 172 stateful hash-based signature scheme. It has the smallest signatures 173 out of such schemes and comes with a multi-tree variant that solves 174 the problem of slow key generation. Moreover, it can be shown that 175 XMSS is secure, making only mild assumptions on the underlying hash 176 function. Especially, it is not required that the cryptographic hash 177 function is collision-resistant for the security of XMSS. 178 Improvements upon XMSS, as described in [HRS16], are part of this 179 note. 181 This document describes a single-tree and a multi-tree variant of 182 XMSS. It also describes WOTS+, a variant of the Winternitz OTS 183 scheme introduced in [Huelsing13] that is used by XMSS. The schemes 184 are described with enough specificity to ensure interoperability 185 between implementations. 187 This document is structured as follows. Notation is introduced in 188 Section 2. Section 3 describes the WOTS+ signature system. MTS 189 schemes are defined in Section 4: the eXtended Merkle Signature 190 Scheme (XMSS) in Section 4.1, and its Multi-Tree variant (XMSS^MT) in 191 Section 4.2. Parameter sets are described in Section 5. Section 6 192 describes the rationale behind choices in this note. The IANA 193 registry for these signature systems is described in Section 8. 194 Finally, security considerations are presented in Section 9. 196 1.1. CFRG Note on Post-Quantum Cryptography 198 All post-quantum algorithms documented by CFRG are today considered 199 ready for experimentation and further engineering development (e.g. 200 to establish the impact of performance and sizes on IETF protocols). 201 However, at the time of writing, we do not have significant 202 deployment experience with such algorithms. 204 Many of these algorithms come with specific restrictions, e.g. 205 change of classical interface or less cryptanalysis of proposed 206 parameters than established schemes. CFRG has consensus that all 207 documents describing post-quantum technologies include the above 208 paragraph and a clear additional warning about any specific 209 restrictions, especially as those might affect use or deployment of 210 the specific scheme. That guidance may be changed over time via 211 document updates. 213 Additionally, for XMSS: 215 CFRG consensus is that we are confident in the cryptographic security 216 of the signature schemes described in this document against quantum 217 computers, given the current state of the research community's 218 knowledge about quantum algorithms. Indeed, we are confident that 219 the security of a significant part of the Internet could be made 220 dependent on the signature schemes defined in this document, if 221 developers take care of the following. 223 In contrast to traditional signature schemes, the signature schemes 224 described in this document are stateful, meaning the secret key 225 changes over time. If a secret key state is used twice, no 226 cryptographic security guarantees remain. In consequence, it becomes 227 feasible to forge a signature on a new message. This is a new 228 property that most developers will not be familiar with and requires 229 careful handling of secret keys. Developers should not use the 230 schemes described here except in systems that prevent the reuse of 231 secret key states. 233 Note that the fact that the schemes described in this document are 234 stateful also implies that classical APIs for digital signature 235 cannot be used without modification. The API MUST be able to handle 236 a secret key state. This especially means that the API HAS TO allow 237 to return an updated secret key state. 239 1.2. Conventions Used In This Document 241 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 242 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 243 document are to be interpreted as described in [RFC2119]. 245 2. Notation 247 2.1. Data Types 249 Bytes and byte strings are the fundamental data types. A byte is a 250 sequence of eight bits. A single byte is denoted as a pair of 251 hexadecimal digits with a leading "0x". A byte string is an ordered 252 sequence of zero or more bytes and is denoted as an ordered sequence 253 of hexadecimal characters with a leading "0x". For example, 0xe534f0 254 is a byte string of length 3. An array of byte strings is an 255 ordered, indexed set starting with index 0 in which all byte strings 256 have identical length. We assume big-endian representation for any 257 data types or structures. 259 2.2. Functions 261 If x is a non-negative real number, then we define the following 262 functions: 264 ceil(x) : returns the smallest integer greater than or equal to x. 266 floor(x) : returns the largest integer less than or equal to x. 268 lg(x) : returns the logarithm to base 2 of x. 270 2.3. Operators 272 When a and b are integers, mathematical operators are defined as 273 follows: 275 ^ : a ^ b denotes the result of a raised to the power of b. 277 * : a * b denotes the product of a and b. This operator is 278 sometimes omitted in the absence of ambiguity, as in usual 279 mathematical notation. 281 / : a / b denotes the quotient of a by non-zero b. 283 % : a % b denotes the non-negative remainder of the integer 284 division of a by b. 286 + : a + b denotes the sum of a and b. 288 - : a - b denotes the difference of a and b. 290 ++ : a++ denotes incrementing a by 1, i.e., a = a + 1. 292 << : a << b denotes a logical left shift with b being non- 293 negative, i.e., a * 2^b. 295 >> : a >> b denotes a logical right shift with b being non- 296 negative, i.e. floor(a / 2^b). 298 The standard order of operations is used when evaluating arithmetic 299 expressions. 301 Arrays are used in the common way, where the i^th element of an array 302 A is denoted A[i]. Byte strings are treated as arrays of bytes where 303 necessary: If X is a byte string, then X[i] denotes its i^th byte, 304 where X[0] is the leftmost byte. 306 If A and B are byte strings of equal length, then: 308 A AND B denotes the bitwise logical conjunction operation. 310 A XOR B denotes the bitwise logical exclusive disjunction 311 operation. 313 When B is a byte and i is an integer, then B >> i denotes the logical 314 right-shift operation. 316 If X is an x-byte string and Y a y-byte string, then X || Y denotes 317 the concatenation of X and Y, with X || Y = X[0] ... X[x-1] Y[0] ... 318 Y[y-1]. 320 2.4. Integer to Byte Conversion 322 If x and y are non-negative integers, we define Z = toByte(x, y) to 323 be the y-byte string containing the binary representation of x in 324 big-endian byte-order. 326 2.5. Hash Function Address Scheme 328 The schemes described in this document randomize each hash function 329 call. This means that aside from the initial message digest, for 330 each hash function call a different key and different bitmask is 331 used. These values are pseudorandomly generated using a pseudorandom 332 function that takes a key SEED and a 32-byte address ADRS as input 333 and outputs an n-byte value, where n is the security parameter. Here 334 we explain the structure of address ADRS and propose setter methods 335 to manipulate the address. We explain the generation of the 336 addresses in the following sections where they are used. 338 The schemes in the next two sections use two kinds of hash functions 339 parameterized by security parameter n. For the hash tree 340 constructions, a hash function that maps an n-byte key and 2n-byte 341 inputs to n-byte outputs is used. To randomize this function, 3n 342 bytes are needed - n bytes for the key and 2n bytes for a bitmask. 343 For the OTS scheme constructions, a hash function that maps n-byte 344 keys and n-byte inputs to n-byte outputs is used. To randomize this 345 function, 2n bytes are needed - n bytes for the key and n bytes for a 346 bitmask. Consequently, three addresses are needed for the first 347 function and two addresses for the second one. 349 There are three different types of addresses for the different use 350 cases. One type is used for the hashes in OTS schemes, one is used 351 for hashes within the main Merkle tree construction, and one is used 352 for hashes in the L-trees. The latter is used to compress one-time 353 public keys. All these types share as much format as possible. In 354 the following we describe these types in detail. 356 The structure of an address complies with word borders, with a word 357 being 32 bits long in this context. Only the tree address is too 358 long to fit a single word but matches a double word. An address is 359 structured as follows. It always starts with a layer address of one 360 word in the most significant bits, followed by a tree address of two 361 words. Both addresses are needed for the multi-tree variant (see 362 Section 4.2) and describe the position of a tree within a multi-tree. 363 They are therefore set to zero in case of single-tree applications. 364 For multi-tree hash-based signatures the layer address describes the 365 height of a tree within the multi-tree starting from height zero for 366 trees at the bottom layer. The tree address describes the position 367 of a tree within a layer of a multi-tree starting with index zero for 368 the leftmost tree. The next word defines the type of the address. 369 It is set to 0 for an OTS address, to 1 for an L-tree address, and to 370 2 for a hash tree address. Whenever the type word of an address is 371 changed, all following words should be initialized with 0 to prevent 372 non-zero values in unused padding words. 374 We first describe the OTS address case. In this case, the type word 375 is followed by an OTS address word that encodes the index of the OTS 376 key pair within the tree. The next word encodes the chain address 377 followed by a word that encodes the address of the hash function call 378 within the chain. The last word, called keyAndMask, is used to 379 generate two different addresses for one hash function call. The 380 word is set to zero to generate the key. To generate the n-byte 381 bitmask, the word is set to one. 383 An OTS hash address 384 +------------------------+ 385 | layer address (32 bit)| 386 +------------------------+ 387 | tree address (64 bit)| 388 +------------------------+ 389 | type = 0 (32 bit)| 390 +------------------------+ 391 | OTS address (32 bit)| 392 +------------------------+ 393 | chain address (32 bit)| 394 +------------------------+ 395 | hash address (32 bit)| 396 +------------------------+ 397 | keyAndMask (32 bit)| 398 +------------------------+ 400 We now discuss the L-tree case, which means that the type word is set 401 to one. In that case the type word is followed by an L-tree address 402 word that encodes the index of the leaf computed with this L-tree. 403 The next word encodes the height of the node being input for the next 404 computation inside the L-tree. The following word encodes the index 405 of the node at that height, inside the L-tree. This time, the last 406 word, keyAndMask, is used to generate three different addresses for 407 one function call. The word is set to zero to generate the key. To 408 generate the most significant n bytes of the 2n-byte bitmask, the 409 word is set to one. The least significant bytes are generated using 410 the address with the word set to two. 412 An L-tree address 413 +------------------------+ 414 | layer address (32 bit)| 415 +------------------------+ 416 | tree address (64 bit)| 417 +------------------------+ 418 | type = 1 (32 bit)| 419 +------------------------+ 420 | L-tree address (32 bit)| 421 +------------------------+ 422 | tree height (32 bit)| 423 +------------------------+ 424 | tree index (32 bit)| 425 +------------------------+ 426 | keyAndMask (32 bit)| 427 +------------------------+ 429 We now describe the remaining type for the main tree hash addresses. 430 In this case the type word is set to two, followed by a zero padding 431 of one word. The next word encodes the height of the tree node being 432 input for the next computation, followed by a word that encodes the 433 index of this node at that height. As for the L-tree addresses, the 434 last word, keyAndMask, is used to generate three different addresses 435 for one function call. The word is set to zero to generate the key. 436 To generate the most significant n bytes of the 2n-byte bitmask, the 437 word is set to one. The least significant bytes are generated using 438 the address with the word set to two. 440 A hash tree address 441 +------------------------+ 442 | layer address (32 bit)| 443 +------------------------+ 444 | tree address (64 bit)| 445 +------------------------+ 446 | type = 2 (32 bit)| 447 +------------------------+ 448 | Padding = 0 (32 bit)| 449 +------------------------+ 450 | tree height (32 bit)| 451 +------------------------+ 452 | tree index (32 bit)| 453 +------------------------+ 454 | keyAndMask (32 bit)| 455 +------------------------+ 457 All fields within these addresses encode unsigned integers. When 458 describing the generation of addresses we use setter methods that 459 take positive integers and set the bits of a field to the binary 460 representation of that integer of the length of the field. We 461 furthermore assume that the setType() method sets the four words 462 following the type word to zero. 464 2.6. Strings of Base w Numbers 466 A byte string can be considered as a string of base w numbers, i.e. 467 integers in the set {0, ... , w - 1}. The correspondence is defined 468 by the function base_w(X, w, out_len) as follows. If X is a len_X- 469 byte string, and w is a member of the set {4, 16}, then base_w(X, w, 470 out_len) outputs an array of out_len integers between 0 and w - 1. 471 The length out_len is REQUIRED to be less than or equal to 8 * len_X 472 / lg(w). 474 Algorithm 1: base_w 476 Input: len_X-byte string X, int w, output length out_len 477 Output: out_len int array basew 479 int in = 0; 480 int out = 0; 481 unsigned int total = 0; 482 int bits = 0; 483 int consumed; 485 for ( consumed = 0; consumed < out_len; consumed++ ) { 486 if ( bits == 0 ) { 487 total = X[in]; 488 in++; 489 bits += 8; 490 } 491 bits -= lg(w); 492 basew[out] = (total >> bits) AND (w - 1); 493 out++; 494 } 495 return basew; 497 For example, if X is the (big-endian) byte string 0x1234, then 498 base_w(X, 16, 4) returns the array a = {1, 2, 3, 4}. 500 X (represented as bits) 501 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 502 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 503 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 504 X[0] | X[1] 506 X (represented as base 16 numbers) 507 +-----------+-----------+-----------+-----------+ 508 | 1 | 2 | 3 | 4 | 509 +-----------+-----------+-----------+-----------+ 511 base_w(X, 16, 4) 512 +-----------+-----------+-----------+-----------+ 513 | 1 | 2 | 3 | 4 | 514 +-----------+-----------+-----------+-----------+ 515 a[0] a[1] a[2] a[3] 517 base_w(X, 16, 3) 518 +-----------+-----------+-----------+ 519 | 1 | 2 | 3 | 520 +-----------+-----------+-----------+ 521 a[0] a[1] a[2] 523 base_w(X, 16, 2) 524 +-----------+-----------+ 525 | 1 | 2 | 526 +-----------+-----------+ 527 a[0] a[1] 529 2.7. Member Functions 531 To simplify algorithm descriptions, we assume the existence of member 532 functions. If a complex data structure like a public key PK contains 533 a value X then getX(PK) returns the value of X for this public key. 534 Accordingly, setX(PK, X, Y) sets value X in PK to the value held by 535 Y. Since camelCase is used for member function names, a value z may 536 be referred to as Z in the function name, e.g. getZ. 538 3. Primitives 540 3.1. WOTS+ One-Time Signatures 542 This section describes the WOTS+ OTS system, in a version similar to 543 [Huelsing13]. WOTS+ is a OTS scheme; while a private key can be used 544 to sign any message, each private key MUST be used only once to sign 545 a single message. In particular, if a private key is used to sign 546 two different messages, the scheme becomes insecure. 548 The section starts with an explanation of parameters. Afterwards, 549 the so-called chaining function, which forms the main building block 550 of the WOTS+ scheme, is explained. A description of the algorithms 551 for key generation, signing and verification follows. Finally, 552 pseudorandom key generation is discussed. 554 3.1.1. WOTS+ Parameters 556 WOTS+ uses the parameters n, and w; they all take positive integer 557 values. These parameters are summarized as follows: 559 n : the message length as well as the length of a private key, 560 public key, or signature element in bytes. 562 w : the Winternitz parameter; it is a member of the set {4, 16}. 564 The parameters are used to compute values len, len_1 and len_2: 566 len : the number of n-byte string elements in a WOTS+ private key, 567 public key, and signature. It is computed as len = len_1 + len_2, 568 with len_1 = ceil(8n / lg(w)) and len_2 = floor(lg(len_1 * (w - 569 1)) / lg(w)) + 1. 571 The value of n is determined by the cryptographic hash function used 572 for WOTS+. The hash function is chosen to ensure an appropriate level 573 of security. The value of n is the input length that can be 574 processed by the signing algorithm. It is often the length of a 575 message digest. The parameter w can be chosen from the set {4, 16}. 576 A larger value of w results in shorter signatures but slower overall 577 signing operations; it has little effect on security. Choices of w 578 are limited to the values 4 and 16 since these values yield optimal 579 trade-offs and easy implementation. 581 WOTS+ parameters are implicitly included in algorithm inputs as 582 needed. 584 3.1.1.1. WOTS+ Functions 586 The WOTS+ algorithm uses a keyed cryptographic hash function F. F 587 accepts and returns byte strings of length n using keys of length n. 588 More detail on specific instantiations can be found in Section 5. 589 Security requirements on F are discussed in Section 9. In addition, 590 WOTS+ uses a pseudorandom function PRF. PRF takes as input an n-byte 591 key and a 32-byte index and generates pseudorandom outputs of length 592 n. More detail on specific instantiations can be found in Section 5. 593 Security requirements on PRF are discussed in Section 9. 595 3.1.2. WOTS+ Chaining Function 597 The chaining function (Algorithm 2) computes an iteration of F on an 598 n-byte input using outputs of PRF. It takes an OTS hash address as 599 input. This address will have the first six 32-bit words set to 600 encode the address of this chain. In each iteration, PRF is used to 601 generate a key for F and a bitmask that is XORed to the intermediate 602 result before it is processed by F. In the following, ADRS is a 603 32-byte OTS hash address as specified in Section 2.5 and SEED is an 604 n-byte string. To generate the keys and bitmasks, PRF is called with 605 SEED as key and ADRS as input. The chaining function takes as input 606 an n-byte string X, a start index i, a number of steps s, as well as 607 ADRS and SEED. The chaining function returns as output the value 608 obtained by iterating F for s times on input X, using the outputs of 609 PRF. 611 Algorithm 2: chain - Chaining Function 613 Input: Input string X, start index i, number of steps s, 614 seed SEED, address ADRS 615 Output: value of F iterated s times on X 617 if ( s == 0 ) { 618 return X; 619 } 620 if ( (i + s) > (w - 1) ) { 621 return NULL; 622 } 623 byte[n] tmp = chain(X, i, s - 1, SEED, ADRS); 625 ADRS.setHashAddress(i + s - 1); 626 ADRS.setKeyAndMask(0); 627 KEY = PRF(SEED, ADRS); 628 ADRS.setKeyAndMask(1); 629 BM = PRF(SEED, ADRS); 631 tmp = F(KEY, tmp XOR BM); 632 return tmp; 634 3.1.3. WOTS+ Private Key 636 The private key in WOTS+, denoted by sk (s for secret), is a length 637 len array of n-byte strings. This private key MUST be only used to 638 sign at most one message. Each n-byte string MUST either be selected 639 randomly from the uniform distribution or using a cryptographically 640 secure pseudorandom procedure. In the latter case, the security of 641 the used procedure MUST at least match that of the WOTS+ parameters 642 used. For a further discussion on pseudorandom key generation, see 643 Section 3.1.7. The following pseudocode (Algorithm 3) describes an 644 algorithm for generating sk. 646 Algorithm 3: WOTS_genSK - Generating a WOTS+ Private Key 648 Input: No input 649 Output: WOTS+ private key sk 651 for ( i = 0; i < len; i++ ) { 652 initialize sk[i] with a uniformly random n-byte string; 653 } 654 return sk; 656 3.1.4. WOTS+ Public Key 658 A WOTS+ key pair defines a virtual structure that consists of len 659 hash chains of length w. The len n-byte strings in the private key 660 each define the start node for one hash chain. The public key 661 consists of the end nodes of these hash chains. Therefore, like the 662 private key, the public key is also a length len array of n-byte 663 strings. To compute the hash chain, the chaining function (Algorithm 664 2) is used. An OTS hash address ADRS and a seed SEED have to be 665 provided by the calling algorithm. This address will encode the 666 address of the WOTS+ key pair within a greater structure. Hence, a 667 WOTS+ algorithm MUST NOT manipulate any other parts of ADRS than the 668 last three 32-bit words. Please note that the SEED used here is 669 public information also available to a verifier. The following 670 pseudocode (Algorithm 4) describes an algorithm for generating the 671 public key pk, where sk is the private key. 673 Algorithm 4: WOTS_genPK - Generating a WOTS+ Public Key From a 674 Private Key 676 Input: WOTS+ private key sk, address ADRS, seed SEED 677 Output: WOTS+ public key pk 679 for ( i = 0; i < len; i++ ) { 680 ADRS.setChainAddress(i); 681 pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS); 682 } 683 return pk; 685 3.1.5. WOTS+ Signature Generation 687 A WOTS+ signature is a length len array of n-byte strings. The WOTS+ 688 signature is generated by mapping a message to len integers between 0 689 and w - 1. To this end, the message is transformed into len_1 base w 690 numbers using the base_w function defined in Section 2.6. Next, a 691 checksum is computed and appended to the transformed message as len_2 692 base w numbers using the base_w function. Note that the checksum may 693 reach a maximum integer value of len_1 * (w - 1) * 2^8 and therefore 694 depends on the parameters n and w. For the parameter sets given in 695 Section 5 a 32-bit unsigned integer is sufficient to hold the 696 checksum. If other parameter settings are used the size of the 697 variable holding the integer value of the checksum MUST be 698 sufficiently large. Each of the base w integers is used to select a 699 node from a different hash chain. The signature is formed by 700 concatenating the selected nodes. An OTS hash address ADRS and a 701 seed SEED have to be provided by the calling algorithm. This address 702 will encode the address of the WOTS+ key pair within a greater 703 structure. Hence, a WOTS+ algorithm MUST NOT manipulate any other 704 parts of ADRS than the last three 32-bit words. Please note that the 705 SEED used here is public information also available to a verifier. 706 The pseudocode for signature generation is shown below (Algorithm 5), 707 where M is the message and sig is the resulting signature. 709 Algorithm 5: WOTS_sign - Generating a signature from a private key 710 and a message 712 Input: Message M, WOTS+ private key sk, address ADRS, seed SEED 713 Output: WOTS+ signature sig 715 csum = 0; 717 // Convert message to base w 718 msg = base_w(M, w, len_1); 720 // Compute checksum 721 for ( i = 0; i < len_1; i++ ) { 722 csum = csum + w - 1 - msg[i]; 723 } 725 // Convert csum to base w 726 csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); 727 len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); 728 msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2); 729 for ( i = 0; i < len; i++ ) { 730 ADRS.setChainAddress(i); 731 sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS); 732 } 733 return sig; 735 The data format for a signature is given below. 737 WOTS+ Signature 739 +---------------------------------+ 740 | | 741 | sig_ots[0] | n bytes 742 | | 743 +---------------------------------+ 744 | | 745 ~ .... ~ 746 | | 747 +---------------------------------+ 748 | | 749 | sig_ots[len - 1] | n bytes 750 | | 751 +---------------------------------+ 753 3.1.6. WOTS+ Signature Verification 755 In order to verify a signature sig on a message M, the verifier 756 computes a WOTS+ public key value from the signature. This can be 757 done by "completing" the chain computations starting from the 758 signature values, using the base w values of the message hash and its 759 checksum. This step, called WOTS_pkFromSig, is described below in 760 Algorithm 6. The result of WOTS_pkFromSig is then compared to the 761 given public key. If the values are equal, the signature is 762 accepted. Otherwise, the signature MUST be rejected. An OTS hash 763 address ADRS and a seed SEED have to be provided by the calling 764 algorithm. This address will encode the address of the WOTS+ key 765 pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT 766 manipulate any other parts of ADRS than the last three 32-bit words. 767 Please note that the SEED used here is public information also 768 available to a verifier. 770 Algorithm 6: WOTS_pkFromSig - Computing a WOTS+ public key from a 771 message and its signature 773 Input: Message M, WOTS+ signature sig, address ADRS, seed SEED 774 Output: 'Temporary' WOTS+ public key tmp_pk 776 csum = 0; 778 // Convert message to base w 779 msg = base_w(M, w, len_1); 781 // Compute checksum 782 for ( i = 0; i < len_1; i++ ) { 783 csum = csum + w - 1 - msg[i]; 784 } 786 // Convert csum to base w 787 csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); 788 len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); 789 msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2); 790 for ( i = 0; i < len; i++ ) { 791 ADRS.setChainAddress(i); 792 tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS); 793 } 794 return tmp_pk; 796 Note: XMSS uses WOTS_pkFromSig to compute a public key value and 797 delays the comparison to a later point. 799 3.1.7. Pseudorandom Key Generation 801 An implementation MAY use a cryptographically secure pseudorandom 802 method to generate the private key from a single n-byte value. For 803 example, the method suggested in [BDH11] and explained below MAY be 804 used. Other methods MAY be used. The choice of a pseudorandom 805 method does not affect interoperability, but the cryptographic 806 strength MUST match that of the used WOTS+ parameters. 808 The advantage of generating the private key elements from a random 809 n-byte string is that only this n-byte string needs to be stored 810 instead of the full private key. The key can be regenerated when 811 needed. The suggested method from [BDH11] can be described using 812 PRF. During key generation a uniformly random n-byte string S is 813 sampled from a secure source of randomness. This string S is stored 814 as private key. The private key elements are computed as sk[i] = 815 PRF(S, toByte(i, 32)) whenever needed. Please note that this seed S 816 MUST be different from the seed SEED used to randomize the hash 817 function calls. Also, this seed S MUST be kept secret. The seed S 818 MUST NOT be a low entropy, human-memorable value since private key 819 elements are derived from S deterministically and their 820 confidentiality is security-critical. 822 4. Schemes 824 In this section, the eXtended Merkle Signature Scheme (XMSS) is 825 described using WOTS+. XMSS comes in two flavors: First, a single- 826 tree variant (XMSS) and second a multi-tree variant (XMSS^MT). Both 827 allow combining a large number of WOTS+ key pairs under a single 828 small public key. The main ingredient added is a binary hash tree 829 construction. XMSS uses a single hash tree while XMSS^MT uses a tree 830 of XMSS key pairs. 832 4.1. XMSS: eXtended Merkle Signature Scheme 834 XMSS is a method for signing a potentially large but fixed number of 835 messages. It is based on the Merkle signature scheme. XMSS uses 836 four cryptographic components: WOTS+ as OTS method, two additional 837 cryptographic hash functions H and H_msg, and a pseudorandom function 838 PRF. One of the main advantages of XMSS with WOTS+ is that it does 839 not rely on the collision resistance of the used hash functions but 840 on weaker properties. Each XMSS public/private key pair is 841 associated with a perfect binary tree, every node of which contains 842 an n-byte value. Each tree leaf contains a special tree hash of a 843 WOTS+ public key value. Each non-leaf tree node is computed by first 844 concatenating the values of its child nodes, computing the XOR with a 845 bitmask, and applying the keyed hash function H to the result. The 846 bitmasks and the keys for the hash function H are generated from a 847 (public) seed that is part of the public key using the pseudorandom 848 function PRF. The value corresponding to the root of the XMSS tree 849 forms the XMSS public key together with the seed. 851 To generate a key pair that can be used to sign 2^h messages, a tree 852 of height h is used. XMSS is a stateful signature scheme, meaning 853 that the private key changes with every signature generation. To 854 prevent one-time private keys from being used twice, the WOTS+ key 855 pairs are numbered from 0 to (2^h) - 1 according to the related leaf, 856 starting from index 0 for the leftmost leaf. The private key 857 contains an index that is updated with every signature generation, 858 such that it contains the index of the next unused WOTS+ key pair. 860 A signature consists of the index of the used WOTS+ key pair, the 861 WOTS+ signature on the message and the so-called authentication path. 862 The latter is a vector of tree nodes that allow a verifier to compute 863 a value for the root of the tree starting from a WOTS+ signature. A 864 verifier computes the root value and compares it to the respective 865 value in the XMSS public key. If they match, the signature is 866 declared valid. The XMSS private key consists of all WOTS+ private 867 keys and the current index. To reduce storage, a pseudorandom key 868 generation procedure, as described in [BDH11], MAY be used. The 869 security of the used method MUST at least match the security of the 870 XMSS instance. 872 4.1.1. XMSS Parameters 874 XMSS has the following parameters: 876 h : the height (number of levels - 1) of the tree 878 n : the length in bytes of the message digest as well as of each 879 node 881 w : the Winternitz parameter as defined for WOTS+ in Section 3.1 883 There are 2^h leaves in the tree. 885 For XMSS and XMSS^MT, private and public keys are denoted by SK (S 886 for secret) and PK. For WOTS+, private and public keys are denoted 887 by sk (s for secret) and pk, respectively. XMSS and XMSS^MT 888 signatures are denoted by Sig. WOTS+ signatures are denoted by sig. 890 XMSS and XMSS^MT parameters are implicitly included in algorithm 891 inputs as needed. 893 4.1.2. XMSS Hash Functions 895 Besides the cryptographic hash function F and the pseudorandom 896 function PRF required by WOTS+, XMSS uses two more functions: 898 A cryptographic hash function H. H accepts n-byte keys and byte 899 strings of length 2n and returns an n-byte string. 901 A cryptographic hash function H_msg. H_msg accepts 3n-byte keys 902 and byte strings of arbitrary length and returns an n-byte string. 904 More detail on specific instantiations can be found in Section 5. 905 Security requirements on H and H_msg are discussed in Section 9. 907 4.1.3. XMSS Private Key 909 An XMSS private key SK contains 2^h WOTS+ private keys, the leaf 910 index idx of the next WOTS+ private key that has not yet been used, 911 SK_PRF, an n-byte key to generate pseudorandom values for randomized 912 message hashing, the n-byte value root, which is the root node of the 913 tree and SEED, the n-byte public seed used to pseudorandomly generate 914 bitmasks and hash function keys. Although root and SEED formally 915 would be considered only part of the public key, they are needed e.g. 916 for signature generation and hence are also required for functions 917 that do not take the public key as input. 919 The leaf index idx is initialized to zero when the XMSS private key 920 is created. The key SK_PRF MUST be sampled from a secure source of 921 randomness that follows the uniform distribution. The WOTS+ private 922 keys MUST either be generated as described in Section 3.1 or, to 923 reduce the private key size, a cryptographic pseudorandom method MUST 924 be used as discussed in Section 4.1.11. SEED is generated as a 925 uniformly random n-byte string. Although SEED is public, it is 926 critical for security that it is generated using a good entropy 927 source. The root node is generated as described below in the section 928 on key generation (Section 4.1.7). That section also contains an 929 example algorithm for combined private and public key generation. 931 For the following algorithm descriptions, the existence of a method 932 getWOTS_SK(SK, i) is assumed. This method takes as inputs an XMSS 933 private key SK and an integer i and outputs the i^th WOTS+ private 934 key of SK. 936 4.1.4. Randomized Tree Hashing 938 To improve readability we introduce a function RAND_HASH(LEFT, RIGHT, 939 SEED, ADRS) that does the randomized hashing in the tree. It takes 940 as input two n-byte values LEFT and RIGHT that represent the left and 941 the right half of the hash function input, the seed SEED used as key 942 for PRF and the address ADRS of this hash function call. RAND_HASH 943 first uses PRF with SEED and ADRS to generate a key KEY and n-byte 944 bitmasks BM_0, BM_1. Then it returns the randomized hash H(KEY, 945 (LEFT XOR BM_0) || (RIGHT XOR BM_1)). 947 Algorithm 7: RAND_HASH 949 Input: n-byte value LEFT, n-byte value RIGHT, seed SEED, 950 address ADRS 951 Output: n-byte randomized hash 953 ADRS.setKeyAndMask(0); 954 KEY = PRF(SEED, ADRS); 955 ADRS.setKeyAndMask(1); 956 BM_0 = PRF(SEED, ADRS); 957 ADRS.setKeyAndMask(2); 958 BM_1 = PRF(SEED, ADRS); 960 return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); 962 4.1.5. L-Trees 964 To compute the leaves of the binary hash tree, a so-called L-tree is 965 used. An L-tree is an unbalanced binary hash tree, distinct but 966 similar to the main XMSS binary hash tree. The algorithm ltree 967 (Algorithm 8) takes as input a WOTS+ public key pk and compresses it 968 to a single n-byte value pk[0]. Towards this end it also takes an 969 L-tree address ADRS as input that encodes the address of the L-tree, 970 and the seed SEED. 972 Algorithm 8: ltree 974 Input: WOTS+ public key pk, address ADRS, seed SEED 975 Output: n-byte compressed public key value pk[0] 977 unsigned int len' = len; 978 ADRS.setTreeHeight(0); 979 while ( len' > 1 ) { 980 for ( i = 0; i < floor(len' / 2); i++ ) { 981 ADRS.setTreeIndex(i); 982 pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS); 983 } 984 if ( len' % 2 == 1 ) { 985 pk[floor(len' / 2)] = pk[len' - 1]; 986 } 987 len' = ceil(len' / 2); 988 ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 989 } 990 return pk[0]; 992 4.1.6. TreeHash 994 For the computation of the internal n-byte nodes of a Merkle tree, 995 the subroutine treeHash (Algorithm 9) accepts an XMSS private key SK 996 (including seed SEED), an unsigned integer s (the start index), an 997 unsigned integer t (the target node height), and an address ADRS that 998 encodes the address of the containing tree. For the height of a node 999 within a tree counting starts with the leaves at height zero. The 1000 treeHash algorithm returns the root node of a tree of height t with 1001 the leftmost leaf being the hash of the WOTS+ pk with index s. It is 1002 REQUIRED that s % 2^t = 0, i.e. that the leaf at index s is a 1003 leftmost leaf of a sub-tree of height t. Otherwise the hash- 1004 addressing scheme fails. The treeHash algorithm described here uses 1005 a stack holding up to (t - 1) nodes, with the usual stack functions 1006 push() and pop(). We furthermore assume that the height of a node 1007 (an unsigned integer) is stored alongside a node's value (an n-byte 1008 string) on the stack. 1010 Algorithm 9: treeHash 1012 Input: XMSS private key SK, start index s, target node height t, 1013 address ADRS 1014 Output: n-byte root node - top node on Stack 1016 if( s % (1 << t) != 0 ) return -1; 1017 for ( i = 0; i < 2^t; i++ ) { 1018 SEED = getSEED(SK); 1019 ADRS.setType(0); // Type = OTS hash address 1020 ADRS.setOTSAddress(s + i); 1021 pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); 1022 ADRS.setType(1); // Type = L-tree address 1023 ADRS.setLTreeAddress(s + i); 1024 node = ltree(pk, SEED, ADRS); 1025 ADRS.setType(2); // Type = hash tree address 1026 ADRS.setTreeHeight(0); 1027 ADRS.setTreeIndex(i + s); 1028 while ( Top node on Stack has same height t' as node ) { 1029 ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); 1030 node = RAND_HASH(Stack.pop(), node, SEED, ADRS); 1031 ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 1032 } 1033 Stack.push(node); 1034 } 1035 return Stack.pop(); 1037 4.1.7. XMSS Key Generation 1039 The XMSS key pair is computed as described in XMSS_keyGen (Algorithm 1040 10). The XMSS public key PK consists of the root of the binary hash 1041 tree and the seed SEED, both also stored in SK. The root is computed 1042 using treeHash. For XMSS, there is only a single main tree. Hence, 1043 the used address is set to the all-zero string in the beginning. 1044 Note that we do not define any specific format or handling for the 1045 XMSS private key SK by introducing this algorithm. It relates to 1046 requirements described earlier and simply shows a basic but very 1047 inefficient example to initialize a private key. 1049 Algorithm 10: XMSS_keyGen - Generate an XMSS key pair 1051 Input: No input 1052 Output: XMSS private key SK, XMSS public key PK 1054 // Example initialization for SK-specific contents 1055 idx = 0; 1056 for ( i = 0; i < 2^h; i++ ) { 1057 wots_sk[i] = WOTS_genSK(); 1058 } 1059 initialize SK_PRF with a uniformly random n-byte string; 1060 setSK_PRF(SK, SK_PRF); 1062 // Initialization for common contents 1063 initialize SEED with a uniformly random n-byte string; 1064 setSEED(SK, SEED); 1065 setWOTS_SK(SK, wots_sk)); 1066 ADRS = toByte(0, 32); 1067 root = treeHash(SK, 0, h, ADRS); 1069 SK = idx || wots_sk || SK_PRF || root || SEED; 1070 PK = OID || root || SEED; 1071 return (SK || PK); 1073 The above is just an example algorithm. It is strongly RECOMMENDED 1074 to use pseudorandom key generation to reduce the private key size. 1075 Public and private key generation MAY be interleaved to save space. 1076 Especially, when a pseudorandom method is used to generate the 1077 private key, generation MAY be done when the respective WOTS+ key 1078 pair is needed by treeHash. 1080 The format of an XMSS public key is given below. 1082 XMSS Public Key 1084 +---------------------------------+ 1085 | algorithm OID | 1086 +---------------------------------+ 1087 | | 1088 | root node | n bytes 1089 | | 1090 +---------------------------------+ 1091 | | 1092 | SEED | n bytes 1093 | | 1094 +---------------------------------+ 1096 4.1.8. XMSS Signature 1098 An XMSS signature is a (4 + n + (len + h) * n)-byte string consisting 1099 of 1101 the index idx_sig of the used WOTS+ key pair (4 bytes), 1103 a byte string r used for randomized message hashing (n bytes), 1105 a WOTS+ signature sig_ots (len * n bytes), 1107 the so-called authentication path 'auth' for the leaf associated 1108 with the used WOTS+ key pair (h * n bytes). 1110 The authentication path is an array of h n-byte strings. It contains 1111 the siblings of the nodes on the path from the used leaf to the root. 1112 It does not contain the nodes on the path itself. These nodes are 1113 needed by a verifier to compute a root node for the tree from the 1114 WOTS+ public key. A node Node is addressed by its position in the 1115 tree. Node(x, y) denotes the y^th node on level x with y = 0 being 1116 the leftmost node on a level. The leaves are on level 0, the root is 1117 on level h. An authentication path contains exactly one node on 1118 every layer 0 <= x <= (h - 1). For the i^th WOTS+ key pair, counting 1119 from zero, the j^th authentication path node is 1121 Node(j, floor(i / (2^j)) XOR 1) 1123 The computation of the authentication path is discussed in 1124 Section 4.1.9. 1126 The data format for a signature is given below. 1128 XMSS Signature 1130 +---------------------------------+ 1131 | | 1132 | index idx_sig | 4 bytes 1133 | | 1134 +---------------------------------+ 1135 | | 1136 | randomness r | n bytes 1137 | | 1138 +---------------------------------+ 1139 | | 1140 | WOTS+ signature sig_ots | len * n bytes 1141 | | 1142 +---------------------------------+ 1143 | | 1144 | auth[0] | n bytes 1145 | | 1146 +---------------------------------+ 1147 | | 1148 ~ .... ~ 1149 | | 1150 +---------------------------------+ 1151 | | 1152 | auth[h - 1] | n bytes 1153 | | 1154 +---------------------------------+ 1156 4.1.9. XMSS Signature Generation 1158 To compute the XMSS signature of a message M with an XMSS private 1159 key, the signer first computes a randomized message digest using a 1160 random value r, idx_sig, the index of the WOTS+ key pair to be used, 1161 and the root value from the public key as key. Then a WOTS+ 1162 signature of the message digest is computed using the next unused 1163 WOTS+ private key. Next, the authentication path is computed. 1164 Finally, the private key is updated, i.e. idx is incremented. An 1165 implementation MUST NOT output the signature before the private key 1166 is updated. 1168 The node values of the authentication path MAY be computed in any 1169 way. This computation is assumed to be performed by the subroutine 1170 buildAuth for the function XMSS_sign, as below. The fastest 1171 alternative is to store all tree nodes and set the array in the 1172 signature by copying the respective nodes. The least storage- 1173 intensive alternative is to recompute all nodes for each signature 1174 online using the treeHash algorithm (Algorithm 9). There exist 1175 several algorithms in between, with different time/storage trade- 1176 offs. For an overview, see [BDS09]. A further approach can be found 1177 in [KMN14]. Note that the details of this procedure are not relevant 1178 to interoperability; it is not necessary to know any of these details 1179 in order to perform the signature verification operation. The 1180 following version of buildAuth is given for completeness. It is a 1181 simple example for understanding, but extremely inefficient. The use 1182 of one of the alternative algorithms is strongly RECOMMENDED. 1184 Given an XMSS private key SK, all nodes in a tree are determined. 1185 Their value is defined in terms of treeHash (Algorithm 9). Hence, 1186 one can compute the authentication path as follows: 1188 (Example) buildAuth - Compute the authentication path for the i^th 1189 WOTS+ key pair 1191 Input: XMSS private key SK, WOTS+ key pair index i, ADRS 1192 Output: Authentication path auth 1194 for ( j = 0; j < h; j++ ) { 1195 k = floor(i / (2^j)) XOR 1; 1196 auth[j] = treeHash(SK, k * 2^j, j, ADRS); 1197 } 1199 We split the description of the signature generation into two main 1200 algorithms. The first one, treeSig (Algorithm 11), generates the 1201 main part of an XMSS signature and is also used by the multi-tree 1202 version XMSS^MT. XMSS_sign (Algorithm 12) calls treeSig but handles 1203 message compression before and the private key update afterwards. 1205 The algorithm treeSig (Algorithm 11) described below calculates the 1206 WOTS+ signature on an n-byte message and the corresponding 1207 authentication path. treeSig takes as inputs an n-byte message M', 1208 an XMSS private key SK, a signature index idx_sig, and an address 1209 ADRS. It returns the concatenation of the WOTS+ signature sig_ots 1210 and authentication path auth. 1212 Algorithm 11: treeSig - Generate a WOTS+ signature on a message with 1213 corresponding authentication path 1215 Input: n-byte message M', XMSS private key SK, 1216 signature index idx_sig, ADRS 1217 Output: Concatenation of WOTS+ signature sig_ots and 1218 authentication path auth 1220 auth = buildAuth(SK, idx_sig, ADRS); 1221 ADRS.setType(0); // Type = OTS hash address 1222 ADRS.setOTSAddress(idx_sig); 1223 sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), 1224 M', getSEED(SK), ADRS); 1225 Sig = sig_ots || auth; 1226 return Sig; 1228 The algorithm XMSS_sign (Algorithm 12) described below calculates an 1229 updated private key SK and a signature on a message M. XMSS_sign 1230 takes as inputs a message M of arbitrary length, and an XMSS private 1231 key SK. It returns the byte string containing the concatenation of 1232 the updated private key SK and the signature Sig. 1234 Algorithm 12: XMSS_sign - Generate an XMSS signature and update the 1235 XMSS private key 1237 Input: Message M, XMSS private key SK 1238 Output: Updated SK, XMSS signature Sig 1240 idx_sig = getIdx(SK); 1241 setIdx(SK, idx_sig + 1); 1242 ADRS = toByte(0, 32); 1243 byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32)); 1244 byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M); 1245 Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS); 1246 return (SK || Sig); 1248 4.1.10. XMSS Signature Verification 1250 An XMSS signature is verified by first computing the message digest 1251 using randomness r, index idx_sig, the root from PK and message M. 1252 Then the used WOTS+ public key pk_ots is computed from the WOTS+ 1253 signature using WOTS_pkFromSig. The WOTS+ public key in turn is used 1254 to compute the corresponding leaf using an L-tree. The leaf, 1255 together with index idx_sig and authentication path auth is used to 1256 compute an alternative root value for the tree. The verification 1257 succeeds if and only if the computed root value matches the one in 1258 the XMSS public key. In any other case it MUST return fail. 1260 As for signature generation, we split verification into two parts to 1261 allow for reuse in the XMSS^MT description. The steps also needed 1262 for XMSS^MT are done by the function XMSS_rootFromSig (Algorithm 13). 1263 XMSS_verify (Algorithm 14) calls XMSS_rootFromSig as a subroutine and 1264 handles the XMSS-specific steps. 1266 The main part of XMSS signature verification is done by the function 1267 XMSS_rootFromSig (Algorithm 13) described below. XMSS_rootFromSig 1268 takes as inputs an index idx_sig, a WOTS+ signature sig_ots, an 1269 authentication path auth, an n-byte message M', seed SEED, and 1270 address ADRS. XMSS_rootFromSig returns an n-byte string holding the 1271 value of the root of a tree defined by the input data. 1273 Algorithm 13: XMSS_rootFromSig - Compute a root node from a tree 1274 signature 1276 Input: index idx_sig, WOTS+ signature sig_ots, authentication path 1277 auth, n-byte message M', seed SEED, address ADRS 1278 Output: n-byte root value node[0] 1280 ADRS.setType(0); // Type = OTS hash address 1281 ADRS.setOTSAddress(idx_sig); 1282 pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS); 1283 ADRS.setType(1); // Type = L-tree address 1284 ADRS.setLTreeAddress(idx_sig); 1285 byte[n][2] node; 1286 node[0] = ltree(pk_ots, SEED, ADRS); 1287 ADRS.setType(2); // Type = hash tree address 1288 ADRS.setTreeIndex(idx_sig); 1289 for ( k = 0; k < h; k++ ) { 1290 ADRS.setTreeHeight(k); 1291 if ( (floor(idx_sig / (2^k)) % 2) == 0 ) { 1292 ADRS.setTreeIndex(ADRS.getTreeIndex() / 2); 1293 node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS); 1294 } else { 1295 ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); 1296 node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS); 1297 } 1298 node[0] = node[1]; 1299 } 1300 return node[0]; 1302 The full XMSS signature verification is depicted below (Algorithm 1303 14). It handles message compression, delegates the root computation 1304 to XMSS_rootFromSig, and compares the result to the value in the 1305 public key. XMSS_verify takes an XMSS signature Sig, a message M, 1306 and an XMSS public key PK. XMSS_verify returns true if and only if 1307 Sig is a valid signature on M under public key PK. Otherwise, it 1308 returns false. 1310 Algorithm 14: XMSS_verify - Verify an XMSS signature using the 1311 corresponding XMSS public key and a message 1313 Input: XMSS signature Sig, message M, XMSS public key PK 1314 Output: Boolean 1316 ADRS = toByte(0, 32); 1317 byte[n] M' = H_msg(r || getRoot(PK) || (toByte(idx_sig, n)), M); 1319 byte[n] node = XMSS_rootFromSig(idx_sig, sig_ots, auth, M', 1320 getSEED(PK), ADRS); 1321 if ( node == getRoot(PK) ) { 1322 return true; 1323 } else { 1324 return false; 1325 } 1327 4.1.11. Pseudorandom Key Generation 1329 An implementation MAY use a cryptographically secure pseudorandom 1330 method to generate the XMSS private key from a single n-byte value. 1331 For example, the method suggested in [BDH11] and explained below MAY 1332 be used. Other methods, such as the one in [HRS16], MAY be used. 1333 The choice of a pseudorandom method does not affect interoperability, 1334 but the cryptographic strength MUST match that of the used XMSS 1335 parameters. 1337 For XMSS a similar method than the one used for WOTS+ can be used. 1338 The suggested method from [BDH11] can be described using PRF. During 1339 key generation a uniformly random n-byte string S is sampled from a 1340 secure source of randomness. This seed S MUST NOT be confused with 1341 the public seed SEED. The seed S MUST be independent of SEED and as 1342 it is the main secret, it MUST be kept secret. This seed S is used 1343 to generate an n-byte value S_ots for each WOTS+ key pair. The 1344 n-byte value S_ots can then be used to compute the respective WOTS+ 1345 private key using the method described in Section 3.1.7. The seeds 1346 for the WOTS+ key pairs are computed as S_ots[i] = PRF(S, toByte(i, 1347 32)) where i is the index of the WOTS+ key pair. An advantage of 1348 this method is that a WOTS+ key can be computed using only len + 1 1349 evaluations of PRF when S is given. 1351 4.1.12. Free Index Handling and Partial Private Keys 1353 Some applications might require to work with partial private keys or 1354 copies of private keys. Examples include delegation of signing 1355 rights / proxy signatures, and load balancing. Such applications MAY 1356 use their own key format and MAY use a signing algorithm different 1357 from the one described above. The index in partial private keys or 1358 copies of a private key MAY be manipulated as required by the 1359 applications. However, applications MUST establish means that 1360 guarantee that each index and thereby each WOTS+ key pair is used to 1361 sign only a single message. 1363 4.2. XMSS^MT: Multi-Tree XMSS 1365 XMSS^MT is a method for signing a large but fixed number of messages. 1366 It was first described in [HRB13]. It builds on XMSS. XMSS^MT uses 1367 a tree of several layers of XMSS trees, a so-called hypertree. The 1368 trees on top and intermediate layers are used to sign the root nodes 1369 of the trees on the respective layer below. Trees on the lowest 1370 layer are used to sign the actual messages. All XMSS trees have 1371 equal height. 1373 Consider an XMSS^MT tree of total height h that has d layers of XMSS 1374 trees of height h / d. Then layer d - 1 contains one XMSS tree, 1375 layer d - 2 contains 2^(h / d) XMSS trees, and so on. Finally, layer 1376 0 contains 2^(h - h / d) XMSS trees. 1378 4.2.1. XMSS^MT Parameters 1380 In addition to all XMSS parameters, an XMSS^MT system requires the 1381 number of tree layers d, specified as an integer value that divides h 1382 without remainder. The same tree height h / d and the same 1383 Winternitz parameter w are used for all tree layers. 1385 All the trees on higher layers sign root nodes of other trees which 1386 are n-byte strings. Hence, no message compression is needed and 1387 WOTS+ is used to sign the root nodes themselves instead of their hash 1388 values. 1390 4.2.2. XMSS^MT Key generation 1392 An XMSS^MT private key SK_MT (S for secret) consists of one reduced 1393 XMSS private key for each XMSS tree. These reduced XMSS private keys 1394 just contain the WOTS+ private keys corresponding to that XMSS key 1395 pair and no pseudorandom function key, no index, no public seed, no 1396 root node. Instead, SK_MT contains a single n-byte pseudorandom 1397 function key SK_PRF, a single (ceil(h / 8))-byte index idx_MT, a 1398 single n-byte seed SEED, and a single root value root which is the 1399 root of the single tree on the top layer. The index is a global 1400 index over all WOTS+ key pairs of all XMSS trees on layer 0. It is 1401 initialized with 0. It stores the index of the last used WOTS+ key 1402 pair on the bottom layer, i.e. a number between 0 and 2^h - 1. 1404 The reduced XMSS private keys MUST either be generated as described 1405 in Section 4.1.3 or using a cryptographic pseudorandom method as 1406 discussed in Section 4.2.6. As for XMSS, the PRF key SK_PRF MUST be 1407 sampled from a secure source of randomness that follows the uniform 1408 distribution. SEED is generated as a uniformly random n-byte string. 1409 Although SEED is public, it is critical for security that it is 1410 generated using a good entropy source. The root is the root node of 1411 the single XMSS tree on the top layer. Its computation is explained 1412 below. As for XMSS, root and SEED are public information and would 1413 classically be considered part of the public key. However, as both 1414 are needed for signing, which only takes the private key, they are 1415 also part of SK_MT. 1417 This document does not define any specific format for the XMSS^MT 1418 private key SK_MT as it is not required for interoperability. The 1419 algorithm descriptions below use a function getXMSS_SK(SK, x, y) that 1420 outputs the reduced private key of the x^th XMSS tree on the y^th 1421 layer. 1423 The XMSS^MT public key PK_MT contains the root of the single XMSS 1424 tree on layer d - 1 and the seed SEED. These are the same values as 1425 in the private key SK_MT. The pseudorandom function PRF keyed with 1426 SEED is used to generate the bitmasks and keys for all XMSS trees. 1427 XMSSMT_keyGen (Algorithm 15) shows example pseudocode to generate 1428 SK_MT and PK_MT. The n-byte root node of the top layer tree is 1429 computed using treeHash. The algorithm XMSSMT_keyGen outputs an 1430 XMSS^MT private key SK_MT and an XMSS^MT public key PK_MT. The 1431 algorithm below gives an example of how the reduced XMSS private keys 1432 can be generated. However, any of the above mentioned ways is 1433 acceptable as long as the cryptographic strength of the used method 1434 matches or supersedes that of the used XMSS^MT parameter set. 1436 Algorithm 15: XMSSMT_keyGen - Generate an XMSS^MT key pair 1438 Input: No input 1439 Output: XMSS^MT private key SK_MT, XMSS^MT public key PK_MT 1441 // Example initialization 1442 idx_MT = 0; 1443 setIdx(SK_MT, idx_MT); 1444 initialize SK_PRF with a uniformly random n-byte string; 1445 setSK_PRF(SK_MT, SK_PRF); 1446 initialize SEED with a uniformly random n-byte string; 1447 setSEED(SK_MT, SEED); 1449 // Generate reduced XMSS private keys 1450 ADRS = toByte(0, 32); 1451 for ( layer = 0; layer < d; layer++ ) { 1452 ADRS.setLayerAddress(layer); 1453 for ( tree = 0; tree < 1454 (1 << ((d - 1 - layer) * (h / d))); 1455 tree++ ) { 1456 ADRS.setTreeAddress(tree); 1457 for ( i = 0; i < 2^(h / d); i++ ) { 1458 wots_sk[i] = WOTS_genSK(); 1459 } 1460 setXMSS_SK(SK_MT, wots_sk, tree, layer); 1461 } 1462 } 1464 SK = getXMSS_SK(SK_MT, 0, d - 1); 1465 setSEED(SK, SEED); 1466 root = treeHash(SK, 0, h / d, ADRS); 1467 setRoot(SK_MT, root); 1469 PK_MT = OID || root || SEED; 1470 return (SK_MT || PK_MT); 1472 The above is just an example algorithm. It is strongly RECOMMENDED 1473 to use pseudorandom key generation to reduce the private key size. 1474 Public and private key generation MAY be interleaved to save space. 1475 Especially, when a pseudorandom method is used to generate the 1476 private key, generation MAY be delayed to the point when the 1477 respective WOTS+ key pair is needed by another algorithm. 1479 The format of an XMSS^MT public key is given below. 1481 XMSS^MT Public Key 1483 +---------------------------------+ 1484 | algorithm OID | 1485 +---------------------------------+ 1486 | | 1487 | root node | n bytes 1488 | | 1489 +---------------------------------+ 1490 | | 1491 | SEED | n bytes 1492 | | 1493 +---------------------------------+ 1495 4.2.3. XMSS^MT Signature 1497 An XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) + 1498 n + (h + d * len) * n). It consists of 1500 the index idx_sig of the used WOTS+ key pair on the bottom layer 1501 (ceil(h / 8) bytes), 1503 a byte string r used for randomized message hashing (n bytes), 1505 d reduced XMSS signatures ((h / d + len) * n bytes each). 1507 The reduced XMSS signatures only contain a WOTS+ signature sig_ots 1508 and an authentication path auth. They contain no index idx and no 1509 byte string r. 1511 The data format for a signature is given below. 1513 XMSS^MT signature 1515 +---------------------------------+ 1516 | | 1517 | index idx_sig | ceil(h / 8) bytes 1518 | | 1519 +---------------------------------+ 1520 | | 1521 | randomness r | n bytes 1522 | | 1523 +---------------------------------+ 1524 | | 1525 | (reduced) XMSS signature Sig | (h / d + len) * n bytes 1526 | (bottom layer 0) | 1527 | | 1528 +---------------------------------+ 1529 | | 1530 | (reduced) XMSS signature Sig | (h / d + len) * n bytes 1531 | (layer 1) | 1532 | | 1533 +---------------------------------+ 1534 | | 1535 ~ .... ~ 1536 | | 1537 +---------------------------------+ 1538 | | 1539 | (reduced) XMSS signature Sig | (h / d + len) * n bytes 1540 | (layer d - 1) | 1541 | | 1542 +---------------------------------+ 1544 4.2.4. XMSS^MT Signature Generation 1546 To compute the XMSS^MT signature Sig_MT of a message M using an 1547 XMSS^MT private key SK_MT, XMSSMT_sign (Algorithm 16) described below 1548 uses treeSig as defined in Section 4.1.9. First, the signature index 1549 is set to idx_sig. Next, PRF is used to compute a pseudorandom 1550 n-byte string r. This n-byte string, idx_sig, and the root node from 1551 PK_MT are then used to compute a randomized message digest of length 1552 n. The message digest is signed using the WOTS+ key pair on the 1553 bottom layer with absolute index idx. The authentication path for 1554 the WOTS+ key pair is computed as well as the root of the containing 1555 XMSS tree. The root is signed by the parent XMSS tree. This is 1556 repeated until the top tree is reached. 1558 Algorithm 16: XMSSMT_sign - Generate an XMSS^MT signature and update 1559 the XMSS^MT private key 1561 Input: Message M, XMSS^MT private key SK_MT 1562 Output: Updated SK_MT, signature Sig_MT 1564 // Init 1565 ADRS = toByte(0, 32); 1566 SEED = getSEED(SK_MT); 1567 SK_PRF = getSK_PRF(SK_MT); 1568 idx_sig = getIdx(SK_MT); 1570 // Update SK_MT 1571 setIdx(SK_MT, idx_sig + 1); 1573 // Message compression 1574 byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); 1575 byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M); 1577 // Sign 1578 Sig_MT = idx_sig; 1579 unsigned int idx_tree 1580 = (h - h / d) most significant bits of idx_sig; 1581 unsigned int idx_leaf = (h / d) least significant bits of idx_sig; 1582 SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF 1583 || toByte(0, n) || SEED; 1584 ADRS.setLayerAddress(0); 1585 ADRS.setTreeAddress(idx_tree); 1586 Sig_tmp = treeSig(M', SK, idx_leaf, ADRS); 1587 Sig_MT = Sig_MT || r || Sig_tmp; 1588 for ( j = 1; j < d; j++ ) { 1589 root = treeHash(SK, 0, h / d, ADRS); 1590 idx_leaf = (h / d) least significant bits of idx_tree; 1591 idx_tree = (h - j * (h / d)) most significant bits of idx_tree; 1592 SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF 1593 || toByte(0, n) || SEED; 1594 ADRS.setLayerAddress(j); 1595 ADRS.setTreeAddress(idx_tree); 1596 Sig_tmp = treeSig(root, SK, idx_leaf, ADRS); 1597 Sig_MT = Sig_MT || Sig_tmp; 1598 } 1599 return SK_MT || Sig_MT; 1601 Algorithm 16 is only one method to compute XMSS^MT signatures. 1602 Especially, there exist time-memory trade-offs that allow to reduce 1603 the signing time to less than the signing time of an XMSS scheme with 1604 tree height h / d. These trade-offs prevent certain values from 1605 being recomputed several times by keeping a state and distribute all 1606 computations over all signature generations. Details can be found in 1607 [Huelsing13a]. 1609 4.2.5. XMSS^MT Signature Verification 1611 XMSS^MT signature verification (Algorithm 17) can be summarized as d 1612 XMSS signature verifications with small changes. First, the message 1613 is hashed. The XMSS signatures are then all on n-byte values. 1614 Second, instead of comparing the computed root node to a given value, 1615 a signature on this root node is verified. Only the root node of the 1616 top tree is compared to the value in the XMSS^MT public key. 1617 XMSSMT_verify uses XMSS_rootFromSig. The function 1618 getXMSSSignature(Sig_MT, i) returns the ith reduced XMSS signature 1619 from the XMSS^MT signature Sig_MT. XMSSMT_verify takes as inputs an 1620 XMSS^MT signature Sig_MT, a message M and a public key PK_MT. 1621 XMSSMT_verify returns true if and only if Sig_MT is a valid signature 1622 on M under public key PK_MT. Otherwise, it returns false. 1624 Algorithm 17: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a 1625 message M using an XMSS^MT public key PK_MT 1627 Input: XMSS^MT signature Sig_MT, message M, 1628 XMSS^MT public key PK_MT 1629 Output: Boolean 1631 idx_sig = getIdx(Sig_MT); 1632 SEED = getSEED(PK_MT); 1633 ADRS = toByte(0, 32); 1635 byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT) 1636 || (toByte(idx_sig, n)), M); 1638 unsigned int idx_leaf 1639 = (h / d) least significant bits of idx_sig; 1640 unsigned int idx_tree 1641 = (h - h / d) most significant bits of idx_sig; 1642 Sig' = getXMSSSignature(Sig_MT, 0); 1643 ADRS.setLayerAddress(0); 1644 ADRS.setTreeAddress(idx_tree); 1645 byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'), 1646 getAuth(Sig'), M', SEED, ADRS); 1647 for ( j = 1; j < d; j++ ) { 1648 idx_leaf = (h / d) least significant bits of idx_tree; 1649 idx_tree = (h - j * h / d) most significant bits of idx_tree; 1650 Sig' = getXMSSSignature(Sig_MT, j); 1651 ADRS.setLayerAddress(j); 1652 ADRS.setTreeAddress(idx_tree); 1653 node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'), 1654 getAuth(Sig'), node, SEED, ADRS); 1655 } 1656 if ( node == getRoot(PK_MT) ) { 1657 return true; 1658 } else { 1659 return false; 1660 } 1662 4.2.6. Pseudorandom Key Generation 1664 Like for XMSS, an implementation MAY use a cryptographically secure 1665 pseudorandom method to generate the XMSS^MT private key from a single 1666 n-byte value. For example, the method explained below MAY be used. 1667 Other methods, such as the one in [HRS16], MAY be used. The choice 1668 of a pseudorandom method does not affect interoperability, but the 1669 cryptographic strength MUST match that of the used XMSS^MT 1670 parameters. 1672 For XMSS^MT a method similar to that for XMSS and WOTS+ can be used. 1673 The method uses PRF. During key generation a uniformly random n-byte 1674 string S_MT is sampled from a secure source of randomness. This seed 1675 S_MT is used to generate one n-byte value S for each XMSS key pair. 1676 This n-byte value can be used to compute the respective XMSS private 1677 key using the method described in Section 4.1.11. Let S[x][y] be the 1678 seed for the x^th XMSS private key on layer y. The seeds are 1679 computed as S[x][y] = PRF(PRF(S, toByte(y, 32)), toByte(x, 32)). 1681 4.2.7. Free Index Handling and Partial Private Keys 1683 The content of Section 4.1.12 also applies to XMSS^MT. 1685 5. Parameter Sets 1687 This section provides a basic set of parameter sets which are assumed 1688 to cover most relevant applications. Parameter sets for two 1689 classical security levels are defined. Parameters with n = 32 1690 provide a classical security level of 256 bits. Parameters with n = 1691 64 provide a classical security level of 512 bits. Considering 1692 quantum-computer-aided attacks, these output sizes yield post-quantum 1693 security of 128 and 256 bits, respectively. 1695 While this document specifies several parameter sets, an 1696 implementation is only REQUIRED to provide support for verification 1697 of all REQUIRED parameter sets. The REQUIRED parameter sets all use 1698 SHA2-256 to instantiate all functions. The REQUIRED parameter sets 1699 are only distinguished by the tree height parameter h which 1700 determines the number of signatures that can be done with a single 1701 key pair and the number of layers d which defines a trade-off between 1702 speed and signature size. An implementation MAY provide support for 1703 signature generation using any of the proposed parameter sets. For 1704 convenience this document defines a default option for XMSS 1705 (XMSS_SHA2_20_256) and XMSS^MT (XMSSMT-SHA2_60/3_256). These are 1706 supposed to match the most generic requirements. 1708 5.1. Implementing the functions 1710 For the n = 32 and n = 64 settings, we give parameters that use 1711 SHA2-256, SHA2-512 as defined in [FIPS180], and the SHA3/Keccak-based 1712 extendable-output functions SHAKE-128, SHAKE-256 as defined in 1713 [FIPS202]. The parameter sets using SHA2-256 are mandatory for 1714 deployment and therefore MUST be provided by any implementation. The 1715 remaining parameter sets specified in this document are OPTIONAL. 1717 SHA2 does not provide a keyed-mode itself. To implement the keyed 1718 hash functions the following is used for SHA2 with n = 32: 1720 F: SHA2-256(toByte(0, 32) || KEY || M), 1722 H: SHA2-256(toByte(1, 32) || KEY || M), 1724 H_msg: SHA2-256(toByte(2, 32) || KEY || M), 1726 PRF: SHA2-256(toByte(3, 32) || KEY || M). 1728 Accordingly, for SHA2 with n = 64 we use: 1730 F: SHA2-512(toByte(0, 64) || KEY || M), 1732 H: SHA2-512(toByte(1, 64) || KEY || M), 1734 H_msg: SHA2-512(toByte(2, 64) || KEY || M), 1736 PRF: SHA2-512(toByte(3, 64) || KEY || M). 1738 The n-byte padding is used for two reasons. First, it is necessary 1739 that the internal compression function takes 2n-byte blocks but keys 1740 are n and 3n bytes long. Second, the padding is used to achieve 1741 independence of the different function families. Finally, for the 1742 PRF no full-fledged HMAC is needed as the message length is fixed, 1743 meaning that standard length extension attacks are not a concern 1744 here. For that reason, the simpler construction above suffices. 1746 Similar constructions are used with SHA3. To implement the keyed 1747 hash functions the following is used for SHA3 with n = 32: 1749 F: SHAKE128(toByte(0, 32) || KEY || M, 256), 1751 H: SHAKE128(toByte(1, 32) || KEY || M, 256), 1753 H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256), 1755 PRF: SHAKE128(toByte(3, 32) || KEY || M, 256). 1757 Accordingly, for SHA3 with n = 64 we use: 1759 F: SHAKE256(toByte(0, 64) || KEY || M, 512), 1761 H: SHAKE256(toByte(1, 64) || KEY || M, 512), 1763 H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512), 1765 PRF: SHAKE256(toByte(3, 64) || KEY || M, 512). 1767 As for SHA2, an initial n-byte identifier is used to achieve 1768 independence of the different function families. While a shorter 1769 identifier could be used in case of SHA3, we use n bytes for 1770 consistency with the SHA2 implementations. 1772 5.2. WOTS+ Parameters 1774 To fully describe a WOTS+ signature method, the parameters n, and w, 1775 as well as the functions F and PRF MUST be specified. This section 1776 defines several WOTS+ signature systems, each of which is identified 1777 by a name. Naming follows the convention: WOTSP-[Hashfamily]_[n in 1778 bits]. Naming does not include w as all parameter sets in this 1779 document use w=16. Values for len are provided for convenience. 1781 +-----------------+----------+----+----+-----+ 1782 | Name | F / PRF | n | w | len | 1783 +-----------------+----------+----+----+-----+ 1784 | REQUIRED: | | | | | 1785 | | | | | | 1786 | WOTSP-SHA2_256 | SHA2-256 | 32 | 16 | 67 | 1787 | | | | | | 1788 | OPTIONAL: | | | | | 1789 | | | | | | 1790 | WOTSP-SHA2_512 | SHA2-512 | 64 | 16 | 131 | 1791 | | | | | | 1792 | WOTSP-SHAKE_256 | SHAKE128 | 32 | 16 | 67 | 1793 | | | | | | 1794 | WOTSP-SHAKE_512 | SHAKE256 | 64 | 16 | 131 | 1795 +-----------------+----------+----+----+-----+ 1797 Table 1 1799 The implementation of the single functions is done as described 1800 above. XDR formats for WOTS+ are listed in Appendix A. 1802 5.3. XMSS Parameters 1804 To fully describe an XMSS signature method, the parameters n, w, and 1805 h, as well as the functions F, H, H_msg, and PRF MUST be specified. 1806 This section defines different XMSS signature systems, each of which 1807 is identified by a name. Naming follows the convention: 1808 XMSS-[Hashfamily]_[h]_[n in bits]. Naming does not include w as all 1809 parameter sets in this document use w=16. 1811 +-------------------+-----------+----+----+-----+----+ 1812 | Name | Functions | n | w | len | h | 1813 +-------------------+-----------+----+----+-----+----+ 1814 | REQUIRED: | | | | | | 1815 | | | | | | | 1816 | XMSS-SHA2_10_256 | SHA2-256 | 32 | 16 | 67 | 10 | 1817 | | | | | | | 1818 | XMSS-SHA2_16_256 | SHA2-256 | 32 | 16 | 67 | 16 | 1819 | | | | | | | 1820 | XMSS-SHA2_20_256 | SHA2-256 | 32 | 16 | 67 | 20 | 1821 | | | | | | | 1822 | OPTIONAL: | | | | | | 1823 | | | | | | | 1824 | XMSS-SHA2_10_512 | SHA2-512 | 64 | 16 | 131 | 10 | 1825 | | | | | | | 1826 | XMSS-SHA2_16_512 | SHA2-512 | 64 | 16 | 131 | 16 | 1827 | | | | | | | 1828 | XMSS-SHA2_20_512 | SHA2-512 | 64 | 16 | 131 | 20 | 1829 | | | | | | | 1830 | XMSS-SHAKE_10_256 | SHAKE128 | 32 | 16 | 67 | 10 | 1831 | | | | | | | 1832 | XMSS-SHAKE_16_256 | SHAKE128 | 32 | 16 | 67 | 16 | 1833 | | | | | | | 1834 | XMSS-SHAKE_20_256 | SHAKE128 | 32 | 16 | 67 | 20 | 1835 | | | | | | | 1836 | XMSS-SHAKE_10_512 | SHAKE256 | 64 | 16 | 131 | 10 | 1837 | | | | | | | 1838 | XMSS-SHAKE_16_512 | SHAKE256 | 64 | 16 | 131 | 16 | 1839 | | | | | | | 1840 | XMSS-SHAKE_20_512 | SHAKE256 | 64 | 16 | 131 | 20 | 1841 +-------------------+-----------+----+----+-----+----+ 1843 Table 2 1845 The XDR formats for XMSS are listed in Appendix B. 1847 5.3.1. Parameter guide 1849 In contrast to traditional signature schemes like RSA or DSA, XMSS 1850 has a tree height parameter h which determines the number of messages 1851 that can be signed with one key pair. Increasing the height allows 1852 to use a key pair for more signatures but it also increases the 1853 signature size and slows down key generation, signing, and 1854 verification. To demonstrate the impact of different values of h the 1855 following table shows signature size and runtimes. Runtimes are 1856 given as the number of calls to F and H when the BDS algorithm is 1857 used to compute authentication paths for the worst case. The last 1858 column shows the number of messages that can be signed with one key 1859 pair. The numbers are the same for the XMSS-SHAKE instances with 1860 same parameters h and n. 1862 +------------------+-------+------------+--------+--------+-------+ 1863 | Name | |Sig| | KeyGen | Sign | Verify | #Sigs | 1864 +------------------+-------+------------+--------+--------+-------+ 1865 | REQUIRED: | | | | | | 1866 | | | | | | | 1867 | XMSS-SHA2_10_256 | 2,500 | 1,238,016 | 5,725 | 1,149 | 2^10 | 1868 | | | | | | | 1869 | XMSS-SHA2_16_256 | 2,692 | 79*10^6 | 9,163 | 1,155 | 2^16 | 1870 | | | | | | | 1871 | XMSS-SHA2_20_256 | 2,820 | 1,268*10^6 | 11,455 | 1,159 | 2^20 | 1872 | | | | | | | 1873 | OPTIONAL: | | | | | | 1874 | | | | | | | 1875 | XMSS-SHA2_10_512 | 9,092 | 2,417,664 | 11,165 | 2,237 | 2^10 | 1876 | | | | | | | 1877 | XMSS-SHA2_16_512 | 9,476 | 155*10^6 | 17,867 | 2,243 | 2^16 | 1878 | | | | | | | 1879 | XMSS-SHA2_20_512 | 9,732 | 2,476*10^6 | 22,335 | 2,247 | 2^20 | 1880 +------------------+-------+------------+--------+--------+-------+ 1882 Table 3 1884 Users without special requirements should use as default option XMSS- 1885 SHA2_20_256 which allows to sign 2^20 messages with one key pair and 1886 provides reasonable speed and signature size. Users that require 1887 more signatures per key pair or faster key generation should consider 1888 XMSS^MT. 1890 5.4. XMSS^MT Parameters 1892 To fully describe an XMSS^MT signature method, the parameters n, w, 1893 h, and d, as well as the functions F, H, H_msg, and PRF MUST be 1894 specified. This section defines different XMSS^MT signature systems, 1895 each of which is identified by a name. Naming follows the 1896 convention: XMSSMT-[Hashfamily]_[h]/[d]_[n in bits]. Naming does not 1897 include w as all parameter sets in this document use w=16. 1899 +------------------------+-----------+----+----+-----+----+----+ 1900 | Name | Functions | n | w | len | h | d | 1901 +------------------------+-----------+----+----+-----+----+----+ 1902 | REQUIRED: | | | | | | | 1903 | | | | | | | | 1904 | XMSSMT-SHA2_20/2_256 | SHA2-256 | 32 | 16 | 67 | 20 | 2 | 1905 | | | | | | | | 1906 | XMSSMT-SHA2_20/4_256 | SHA2-256 | 32 | 16 | 67 | 20 | 4 | 1907 | | | | | | | | 1908 | XMSSMT-SHA2_40/2_256 | SHA2-256 | 32 | 16 | 67 | 40 | 2 | 1909 | | | | | | | | 1910 | XMSSMT-SHA2_40/4_256 | SHA2-256 | 32 | 16 | 67 | 40 | 4 | 1911 | | | | | | | | 1912 | XMSSMT-SHA2_40/8_256 | SHA2-256 | 32 | 16 | 67 | 40 | 8 | 1913 | | | | | | | | 1914 | XMSSMT-SHA2_60/3_256 | SHA2-256 | 32 | 16 | 67 | 60 | 3 | 1915 | | | | | | | | 1916 | XMSSMT-SHA2_60/6_256 | SHA2-256 | 32 | 16 | 67 | 60 | 6 | 1917 | | | | | | | | 1918 | XMSSMT-SHA2_60/12_256 | SHA2-256 | 32 | 16 | 67 | 60 | 12 | 1919 | | | | | | | | 1920 | OPTIONAL: | | | | | | | 1921 | | | | | | | | 1922 | XMSSMT-SHA2_20/2_512 | SHA2-512 | 64 | 16 | 131 | 20 | 2 | 1923 | | | | | | | | 1924 | XMSSMT-SHA2_20/4_512 | SHA2-512 | 64 | 16 | 131 | 20 | 4 | 1925 | | | | | | | | 1926 | XMSSMT-SHA2_40/2_512 | SHA2-512 | 64 | 16 | 131 | 40 | 2 | 1927 | | | | | | | | 1928 | XMSSMT-SHA2_40/4_512 | SHA2-512 | 64 | 16 | 131 | 40 | 4 | 1929 | | | | | | | | 1930 | XMSSMT-SHA2_40/8_512 | SHA2-512 | 64 | 16 | 131 | 40 | 8 | 1931 | | | | | | | | 1932 | XMSSMT-SHA2_60/3_512 | SHA2-512 | 64 | 16 | 131 | 60 | 3 | 1933 | | | | | | | | 1934 | XMSSMT-SHA2_60/6_512 | SHA2-512 | 64 | 16 | 131 | 60 | 6 | 1935 | | | | | | | | 1936 | XMSSMT-SHA2_60/12_512 | SHA2-512 | 64 | 16 | 131 | 60 | 12 | 1937 | | | | | | | | 1938 | XMSSMT-SHAKE_20/2_256 | SHAKE128 | 32 | 16 | 67 | 20 | 2 | 1939 | | | | | | | | 1940 | XMSSMT-SHAKE_20/4_256 | SHAKE128 | 32 | 16 | 67 | 20 | 4 | 1941 | | | | | | | | 1942 | XMSSMT-SHAKE_40/2_256 | SHAKE128 | 32 | 16 | 67 | 40 | 2 | 1943 | | | | | | | | 1944 | XMSSMT-SHAKE_40/4_256 | SHAKE128 | 32 | 16 | 67 | 40 | 4 | 1945 | | | | | | | | 1946 | XMSSMT-SHAKE_40/8_256 | SHAKE128 | 32 | 16 | 67 | 40 | 8 | 1947 | | | | | | | | 1948 | XMSSMT-SHAKE_60/3_256 | SHAKE128 | 32 | 16 | 67 | 60 | 3 | 1949 | | | | | | | | 1950 | XMSSMT-SHAKE_60/6_256 | SHAKE128 | 32 | 16 | 67 | 60 | 6 | 1951 | | | | | | | | 1952 | XMSSMT-SHAKE_60/12_256 | SHAKE128 | 32 | 16 | 67 | 60 | 12 | 1953 | | | | | | | | 1954 | XMSSMT-SHAKE_20/2_512 | SHAKE256 | 64 | 16 | 131 | 20 | 2 | 1955 | | | | | | | | 1956 | XMSSMT-SHAKE_20/4_512 | SHAKE256 | 64 | 16 | 131 | 20 | 4 | 1957 | | | | | | | | 1958 | XMSSMT-SHAKE_40/2_512 | SHAKE256 | 64 | 16 | 131 | 40 | 2 | 1959 | | | | | | | | 1960 | XMSSMT-SHAKE_40/4_512 | SHAKE256 | 64 | 16 | 131 | 40 | 4 | 1961 | | | | | | | | 1962 | XMSSMT-SHAKE_40/8_512 | SHAKE256 | 64 | 16 | 131 | 40 | 8 | 1963 | | | | | | | | 1964 | XMSSMT-SHAKE_60/3_512 | SHAKE256 | 64 | 16 | 131 | 60 | 3 | 1965 | | | | | | | | 1966 | XMSSMT-SHAKE_60/6_512 | SHAKE256 | 64 | 16 | 131 | 60 | 6 | 1967 | | | | | | | | 1968 | XMSSMT-SHAKE_60/12_512 | SHAKE256 | 64 | 16 | 131 | 60 | 12 | 1969 +------------------------+-----------+----+----+-----+----+----+ 1971 Table 4 1973 XDR formats for XMSS^MT are listed in Appendix C. 1975 5.4.1. Parameter guide 1977 In addition to the tree height parameter already used for XMSS, 1978 XMSS^MT has the parameter d which determines the number of tree 1979 layers. XMSS can be understood as XMSS^MT with a single layer, i.e., 1980 d=1. Hence, the choice of h has the same effect as for XMSS. The 1981 number of tree layers provides a trade-off between signature size on 1982 the one side and key generation and signing speed on the other side. 1983 Increasing the number of layers reduces key generation time 1984 exponentially and signing time linearly at the cost of increasing the 1985 signature size linearly. Essentially, an XMSS^MT signature contains 1986 one WOTSP signature per layer. Speed roughly corresponds to d-times 1987 the speed for XMSS with trees of height h/d. 1989 To demonstrate the impact of different values of h and d the 1990 following table shows signature size and runtimes. Runtimes are 1991 given as the number of calls to F and H when the BDS algorithm and 1992 distributed signature generation are used. Timings are worst-case 1993 times. The last column shows the number of messages that can be 1994 signed with one key pair. The numbers are the same for the XMSS- 1995 SHAKE instances with same parameters h and n. Due to formatting 1996 limitations, only the parameter part of the parameter set names are 1997 given, omitting the name XMSSMT. 1999 +----------------+---------+------------+--------+--------+-------+ 2000 | Name | |Sig| | KeyGen | Sign | Verify | #Sigs | 2001 +----------------+---------+------------+--------+--------+-------+ 2002 | REQUIRED: | | | | | | 2003 | | | | | | | 2004 | SHA2_20/2_256 | 4,963 | 2,476,032 | 7,227 | 2,298 | 2^20 | 2005 | | | | | | | 2006 | SHA2_20/4_256 | 9,251 | 154,752 | 4,170 | 4,576 | 2^20 | 2007 | | | | | | | 2008 | SHA2_40/2_256 | 5,605 | 2,535*10^6 | 13,417 | 2,318 | 2^40 | 2009 | | | | | | | 2010 | SHA2_40/4_256 | 9,893 | 4,952,064 | 7,227 | 4,596 | 2^40 | 2011 | | | | | | | 2012 | SHA2_40/8_256 | 18,469 | 309,504 | 4,170 | 9,152 | 2^40 | 2013 | | | | | | | 2014 | SHA2_60/3_256 | 8,392 | 3,803*10^6 | 13,417 | 3,477 | 2^60 | 2015 | | | | | | | 2016 | SHA2_60/6_256 | 14,824 | 7,428,096 | 7,227 | 6,894 | 2^60 | 2017 | | | | | | | 2018 | SHA2_60/12_256 | 27,688 | 464,256 | 4,170 | 13,728 | 2^60 | 2019 | | | | | | | 2020 | OPTIONAL: | | | | | | 2021 | | | | | | | 2022 | SHA2_20/2_512 | 18,115 | 4,835,328 | 14,075 | 4,474 | 2^20 | 2023 | | | | | | | 2024 | SHA2_20/4_512 | 34,883 | 302,208 | 8,138 | 8,928 | 2^20 | 2025 | | | | | | | 2026 | SHA2_40/2_512 | 19,397 | 4,951*10^6 | 26,025 | 4,494 | 2^40 | 2027 | | | | | | | 2028 | SHA2_40/4_512 | 36,165 | 9,670,656 | 14,075 | 8,948 | 2^40 | 2029 | | | | | | | 2030 | SHA2_40/8_512 | 69,701 | 604,416 | 8,138 | 17,856 | 2^40 | 2031 | | | | | | | 2032 | SHA2_60/3_512 | 29,064 | 7,427*10^6 | 26,025 | 6,741 | 2^60 | 2033 | | | | | | | 2034 | SHA2_60/6_512 | 54,216 | 14,505,984 | 14,075 | 13,422 | 2^60 | 2035 | | | | | | | 2036 | SHA2_60/12_512 | 104,520 | 906,624 | 8,138 | 26,784 | 2^60 | 2037 +----------------+---------+------------+--------+--------+-------+ 2039 Table 5 2041 Users without special requirements should use as default option 2042 XMSSMT-SHA2_60/3_256 which allows to sign 2^60 messages with one key 2043 pair, which is a virtually unbounded number of signatures. At the 2044 same time, signature size and speed are well balanced. 2046 6. Rationale 2048 The goal of this note is to describe the WOTS+, XMSS and XMSS^MT 2049 algorithms following the scientific literature. The description is 2050 done in a modular way that allows to base a description of stateless 2051 hash-based signature algorithms like SPHINCS [BHH15] on it. 2053 This note slightly deviates from the scientific literature using a 2054 tweak that prevents multi-user / multi-target attacks against H_msg. 2055 To this end, the public key as well as the index of the used one-time 2056 key pair become part of the hash function key. Thereby we achieve a 2057 domain separation that forces an attacker to decide which hash value 2058 to attack. 2060 For the generation of the randomness used for randomized message 2061 hashing, we apply a PRF, keyed with a secret value, to the index of 2062 the used one-time key pair instead of the message. The reason is 2063 that this requires to process the message only once instead of twice. 2064 For long messages this improves speed and simplifies implementations 2065 on resource constrained devices that cannot hold the entire message 2066 in storage. 2068 We give one mandatory set of parameters using SHA2-256. The reasons 2069 are twofold. On the one hand, SHA2-256 is part of most cryptographic 2070 libraries. On the other hand, a 256-bit hash function leads to 2071 parameters that provide 128 bit of security even against quantum- 2072 computer-aided attacks. A post-quantum security level of 256 bit 2073 seems overly conservative. However, to prepare for possible 2074 cryptanalytic breakthroughs, we also provide OPTIONAL parameter sets 2075 using the less widely supported SHA2-512, SHAKE-256, and SHAKE-512 2076 functions. 2078 We suggest the value w = 16 for the Winternitz parameter. No bigger 2079 values are included since the decrease in signature size then becomes 2080 less significant. Furthermore, the value w = 16 considerably 2081 simplifies the implementations of some of the algorithms. Please 2082 note that we do allow w = 4, but limit the specified parameter sets 2083 to w = 16 for efficiency reasons. 2085 The signature and public key formats are designed so that they are 2086 easy to parse. Each format starts with a 32-bit enumeration value 2087 that indicates all of the details of the signature algorithm and 2088 hence defines all of the information that is needed in order to parse 2089 the format. 2091 7. Reference Code 2093 For testing purposes, a reference implementation in C is available. 2094 The code contains a basic implementation that closely follows the 2095 pseudocode in this document and an optimized implementation which 2096 uses the BDS algorithm [BDS08] to compute authentication paths and 2097 distributed signature generation as described in [HRB13] for XMSS^MT. 2099 The code is permanently available at 2100 https://github.com/joostrijneveld/xmss-reference 2102 8. IANA Considerations 2104 The Internet Assigned Numbers Authority (IANA) is requested to create 2105 three registries: one for WOTS+ signatures as defined in Section 3, 2106 one for XMSS signatures and one for XMSS^MT signatures; the latter 2107 two being defined in Section 4. For the sake of clarity and 2108 convenience, the first sets of WOTS+, XMSS, and XMSS^MT parameter 2109 sets are defined in Section 5. Additions to these registries require 2110 that a specification be documented in an RFC or another permanent and 2111 readily available reference in sufficient detail as defined by the 2112 "Specification Required" policy described in [RFC8126] to make 2113 interoperability between independent implementations possible. Each 2114 entry in the registry contains the following elements: 2116 a short name, such as "XMSS_SHA2_20_256", 2118 a positive number, and 2120 a reference to a specification that completely defines the 2121 signature method test cases or provides (a reference to) a 2122 reference implementation that can be used to verify the 2123 correctness of an implementation. 2125 Requests to add an entry to the registry MUST include the name and 2126 the reference. The number is assigned by IANA. These number 2127 assignments SHOULD use the smallest available positive number. 2128 Submitters MUST have their requests reviewed and approved. 2129 Designated Experts for this task as requested by the the 2130 "Specification Required" policy defined by [RFC8126] will be assigned 2131 by the Internet Engineering Steering Group (IESG). The IESG can be 2132 contacted via iesg@ietf.org. Interested applicants that are 2133 unfamiliar with IANA processes should visit http://www.iana.org. 2135 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 2136 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 2137 are reserved for private use; no attempt will be made to prevent 2138 multiple sites from using the same value in different (and 2139 incompatible) ways [RFC8126]. 2141 The WOTS+ registry is as follows. 2143 +-----------------+-------------+--------------------+ 2144 | Name | Reference | Numeric Identifier | 2145 +-----------------+-------------+--------------------+ 2146 | WOTSP-SHA2_256 | Section 5.2 | 0x00000001 | 2147 | | | | 2148 | WOTSP-SHA2_512 | Section 5.2 | 0x00000002 | 2149 | | | | 2150 | WOTSP-SHAKE_256 | Section 5.2 | 0x00000003 | 2151 | | | | 2152 | WOTSP-SHAKE_512 | Section 5.2 | 0x00000004 | 2153 +-----------------+-------------+--------------------+ 2155 Table 6 2157 The XMSS registry is as follows. 2159 +-------------------+-------------+--------------------+ 2160 | Name | Reference | Numeric Identifier | 2161 +-------------------+-------------+--------------------+ 2162 | XMSS-SHA2_10_256 | Section 5.3 | 0x00000001 | 2163 | | | | 2164 | XMSS-SHA2_16_256 | Section 5.3 | 0x00000002 | 2165 | | | | 2166 | XMSS-SHA2_20_256 | Section 5.3 | 0x00000003 | 2167 | | | | 2168 | XMSS-SHA2_10_512 | Section 5.3 | 0x00000004 | 2169 | | | | 2170 | XMSS-SHA2_16_512 | Section 5.3 | 0x00000005 | 2171 | | | | 2172 | XMSS-SHA2_20_512 | Section 5.3 | 0x00000006 | 2173 | | | | 2174 | XMSS-SHAKE_10_256 | Section 5.3 | 0x00000007 | 2175 | | | | 2176 | XMSS-SHAKE_16_256 | Section 5.3 | 0x00000008 | 2177 | | | | 2178 | XMSS-SHAKE_20_256 | Section 5.3 | 0x00000009 | 2179 | | | | 2180 | XMSS-SHAKE_10_512 | Section 5.3 | 0x0000000a | 2181 | | | | 2182 | XMSS-SHAKE_16_512 | Section 5.3 | 0x0000000b | 2183 | | | | 2184 | XMSS-SHAKE_20_512 | Section 5.3 | 0x0000000c | 2185 +-------------------+-------------+--------------------+ 2187 Table 7 2189 The XMSS^MT registry is as follows. 2191 +------------------------+-------------+--------------------+ 2192 | Name | Reference | Numeric Identifier | 2193 +------------------------+-------------+--------------------+ 2194 | XMSSMT-SHA2_20/2_256 | Section 5.4 | 0x00000001 | 2195 | | | | 2196 | XMSSMT-SHA2_20/4_256 | Section 5.4 | 0x00000002 | 2197 | | | | 2198 | XMSSMT-SHA2_40/2_256 | Section 5.4 | 0x00000003 | 2199 | | | | 2200 | XMSSMT-SHA2_40/4_256 | Section 5.4 | 0x00000004 | 2201 | | | | 2202 | XMSSMT-SHA2_40/8_256 | Section 5.4 | 0x00000005 | 2203 | | | | 2204 | XMSSMT-SHA2_60/3_256 | Section 5.4 | 0x00000006 | 2205 | | | | 2206 | XMSSMT-SHA2_60/6_256 | Section 5.4 | 0x00000007 | 2207 | | | | 2208 | XMSSMT-SHA2_60/12_256 | Section 5.4 | 0x00000008 | 2209 | | | | 2210 | XMSSMT-SHA2_20/2_512 | Section 5.4 | 0x00000009 | 2211 | | | | 2212 | XMSSMT-SHA2_20/4_512 | Section 5.4 | 0x0000000a | 2213 | | | | 2214 | XMSSMT-SHA2_40/2_512 | Section 5.4 | 0x0000000b | 2215 | | | | 2216 | XMSSMT-SHA2_40/4_512 | Section 5.4 | 0x0000000c | 2217 | | | | 2218 | XMSSMT-SHA2_40/8_512 | Section 5.4 | 0x0000000d | 2219 | | | | 2220 | XMSSMT-SHA2_60/3_512 | Section 5.4 | 0x0000000e | 2221 | | | | 2222 | XMSSMT-SHA2_60/6_512 | Section 5.4 | 0x0000000f | 2223 | | | | 2224 | XMSSMT-SHA2_60/12_512 | Section 5.4 | 0x00000010 | 2225 | | | | 2226 | XMSSMT-SHAKE_20/2_256 | Section 5.4 | 0x00000011 | 2227 | | | | 2228 | XMSSMT-SHAKE_20/4_256 | Section 5.4 | 0x00000012 | 2229 | | | | 2230 | XMSSMT-SHAKE_40/2_256 | Section 5.4 | 0x00000013 | 2231 | | | | 2232 | XMSSMT-SHAKE_40/4_256 | Section 5.4 | 0x00000014 | 2233 | | | | 2234 | XMSSMT-SHAKE_40/8_256 | Section 5.4 | 0x00000015 | 2235 | | | | 2236 | XMSSMT-SHAKE_60/3_256 | Section 5.4 | 0x00000016 | 2237 | | | | 2238 | XMSSMT-SHAKE_60/6_256 | Section 5.4 | 0x00000017 | 2239 | | | | 2240 | XMSSMT-SHAKE_60/12_256 | Section 5.4 | 0x00000018 | 2241 | | | | 2242 | XMSSMT-SHAKE_20/2_512 | Section 5.4 | 0x00000019 | 2243 | | | | 2244 | XMSSMT-SHAKE_20/4_512 | Section 5.4 | 0x0000001a | 2245 | | | | 2246 | XMSSMT-SHAKE_40/2_512 | Section 5.4 | 0x0000001b | 2247 | | | | 2248 | XMSSMT-SHAKE_40/4_512 | Section 5.4 | 0x0000001c | 2249 | | | | 2250 | XMSSMT-SHAKE_40/8_512 | Section 5.4 | 0x0000001d | 2251 | | | | 2252 | XMSSMT-SHAKE_60/3_512 | Section 5.4 | 0x0000001e | 2253 | | | | 2254 | XMSSMT-SHAKE_60/6_512 | Section 5.4 | 0x0000001f | 2255 | | | | 2256 | XMSSMT-SHAKE_60/12_512 | Section 5.4 | 0x00000020 | 2257 +------------------------+-------------+--------------------+ 2259 Table 8 2261 An IANA registration of a signature system does not constitute an 2262 endorsement of that system or its security. 2264 9. Security Considerations 2266 A signature system is considered secure if it prevents an attacker 2267 from forging a valid signature. More specifically, consider a 2268 setting in which an attacker gets a public key and can learn 2269 signatures on arbitrary messages of his choice. A signature system 2270 is secure if, even in this setting, the attacker can not produce a 2271 new message, signature pair of his choosing such that the 2272 verification algorithm accepts. 2274 Preventing an attacker from mounting an attack means that the attack 2275 is computationally too expensive to be carried out. There exist 2276 various estimates for when a computation is too expensive to be done. 2277 For that reason, this note only describes how expensive it is for an 2278 attacker to generate a forgery. Parameters are accompanied by a bit 2279 security value. The meaning of bit security is as follows. A 2280 parameter set grants b bits of security if the best attack takes at 2281 least 2^(b - 1) bit operations to achieve a success probability of 2282 1/2. Hence, to mount a successful attack, an attacker needs to 2283 perform 2^b bit operations on average. The given values for bit 2284 security were estimated according to [HRS16]. 2286 9.1. Security Proofs 2288 A full security proof for all schemes described in this document can 2289 be found in [HRS16]. This proof shows that an attacker has to break 2290 at least one out of certain security properties of the used hash 2291 functions and PRFs to forge a signature in any of the described 2292 schemes. The proof in [HRS16] considers a different initial message 2293 compression than the randomized hashing used here. We comment on 2294 this below. For the original schemes, these proofs show that an 2295 attacker has to break certain minimal security properties. In 2296 particular, it is not sufficient to break the collision resistance of 2297 the hash functions to generate a forgery. 2299 More specifically, the requirements on the used functions are that F 2300 and H are post-quantum multi-function multi-target second-preimage 2301 resistant keyed functions, F fulfills an additional statistical 2302 requirement that roughly says that most images have at least two 2303 preimages, PRF is a post-quantum pseudorandom function, H_msg is a 2304 post-quantum multi-target extended target collision resistant keyed 2305 hash function. For detailed definitions of these properties see 2306 [HRS16]. To give some intuition: Multi-function multi-target second 2307 preimage resistance is an extension of second preimage resistance to 2308 keyed hash functions, covering the case where an adversary succeeds 2309 if it finds a second preimage for one out of many values. The same 2310 holds for multi-target extended target collision resistance which 2311 just lacks the multi-function identifier as target collision 2312 resistance already considers keyed hash functions. The proof in 2313 [HRS16] splits PRF into two functions. When PRF is used for 2314 pseudorandom key generation or generation of randomness for 2315 randomized message hashing it is still considered a pseudorandom 2316 function. Whenever PRF is used to generate bitmasks and hash 2317 function keys it is modeled as a random oracle. This is due to 2318 technical reasons in the proof and an implementation using a 2319 pseudorandom function is secure. 2321 The proof in [HRS16] considers classical randomized hashing for the 2322 initial message compression, i.e., H(r, M) instead of H(r || 2323 getRoot(PK) || index, M). This classical randomized hashing allows 2324 to get a security reduction from extended target collision resistance 2325 [HRS16], a property that is conjectured to be strictly weaker than 2326 collision resistance. However, it turns out that in this case, an 2327 attacker could still launch a multi-target attack even against 2328 multiple users at the same time. The reason is that the adversary 2329 attacking u users at the same time learns u * 2^h randomized hashes 2330 H(r_i_j || M_i_j) with signature index i in [0, 2^h - 1] and user 2331 index j in [0, u]. It suffices to find a single pair (r*, M*) such 2332 that H(r* || M*) = H(r_i_u || M_i_u) for one out of the u * 2^h 2333 learned hashes. Hence, an attacker can do a brute force search in 2334 time 2^n / u * 2^h instead of 2^n. 2336 The indexed randomized hashing H(r || getRoot(PK) || toByte(idx, n), 2337 M) used in this work makes the hash function calls position- and 2338 user-dependent. This thwarts the above attack because each hash 2339 function evaluation during an attack can only target one of the 2340 learned randomized hash values. More specifically, an attacker now 2341 has to decide which index idx and which root value to use for each 2342 query. If one assumes that the used hash function is a random 2343 function it can be shown that a multi-user existential forgery attack 2344 that targets this message compression has a complexity of 2^n hash 2345 function calls. 2347 The given bit security values were estimated based on the complexity 2348 of the best known generic attacks against the required security 2349 properties of the used hash and pseudorandom functions assuming 2350 conventional and quantum adversaries. At the time of writing, 2351 generic attacks are the best known attacks for the parameters 2352 suggested in the classical setting. Also in the quantum setting 2353 there are no dedicated attacks known that perform better than generic 2354 attacks. Nevertheless, the topic of quantum cryptanalysis of hash 2355 functions is not as well understood as in the classical setting. 2357 9.2. Minimal Security Assumptions 2359 The security assumptions made to argue for the security of the 2360 described schemes are minimal. Any signature algorithm that allows 2361 arbitrary size messages relies on the security of a cryptographic 2362 hash function, either on collision resistance or on extended target 2363 collision resistance if randomized hashing is used for message 2364 compression. For the schemes described here this is already 2365 sufficient to be secure. In contrast, common signature schemes like 2366 RSA, DSA, and ECDSA additionally rely on the conjectured hardness of 2367 certain mathematical problems. 2369 9.3. Post-Quantum Security 2371 A post-quantum cryptosystem is a system that is secure against 2372 attackers with access to a reasonably sized quantum computer. At the 2373 time of writing this note, whether or not it is feasible to build 2374 such a machine is an open conjecture. However, significant progress 2375 was made over the last few years in this regard. Hence, we consider 2376 it a matter of risk assessment to prepare for this case. 2378 In contrast to RSA, DSA, and ECDSA, the described signature systems 2379 are post-quantum-secure if they are used with an appropriate 2380 cryptographic hash function. In particular, for post-quantum 2381 security, the size of n must be twice the size required for classical 2382 security. This is in order to protect against quantum square root 2383 attacks due to Grover's algorithm. It has been shown in [HRS16] that 2384 variants of Grover's algorithm are the optimal generic attacks 2385 against the security properties of hash functions required for the 2386 described scheme. 2388 As stated above, we only consider generic attacks here, as 2389 cryptographic hash functions should be deprecated as soon as there 2390 exist dedicated attacks that perform significantly better. This also 2391 applies for the quantum setting. As soon as there exist dedicated 2392 quantum attacks against the used hash function that perform 2393 significantly better than the described generic attacks these hash 2394 functions should not be used anymore for the described schemes or the 2395 computation of the security level has to be redone. 2397 10. Acknowledgements 2399 We would like to thank Johannes Braun, Peter Campbell, Florian 2400 Caullery, Stephen Farrell, Scott Fluhrer, Burt Kaliski, Adam Langley, 2401 Marcos Manzano, David McGrew, Rafael Misoczki, Sean Parkinson, 2402 Sebastian Roland, and the Keccak team for their help and comments. 2404 11. References 2406 11.1. Normative References 2408 [FIPS180] National Institute of Standards and Technology, "Secure 2409 Hash Standard (SHS)", FIPS 180-4, 2012. 2411 [FIPS202] National Institute of Standards and Technology, "SHA-3 2412 Standard: Permutation-Based Hash and Extendable-Output 2413 Functions", FIPS 202, 2015. 2415 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2416 Requirement Levels", BCP 14, RFC 2119, 2417 DOI 10.17487/RFC2119, March 1997, 2418 . 2420 [RFC4506] Eisler, M., Ed., "XDR: External Data Representation 2421 Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2422 2006, . 2424 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2425 Writing an IANA Considerations Section in RFCs", BCP 26, 2426 RFC 8126, DOI 10.17487/RFC8126, June 2017, 2427 . 2429 11.2. Informative References 2431 [BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A 2432 Practical Forward Secure Signature Scheme Based on Minimal 2433 Security Assumptions", Lecture Notes in Computer Science 2434 volume 7071. Post-Quantum Cryptography, 2011. 2436 [BDS08] Buchmann, J., Dahmen, E., and M. Schneider, "Merkle Tree 2437 Traversal Revisited", Lecture Notes in Computer Science 2438 volume 5299. Post-Quantum Cryptography, 2008. 2440 [BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based 2441 Digital Signature Schemes", Book chapter Post-Quantum 2442 Cryptography, Springer, 2009. 2444 [BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., 2445 Niederhagen, R., Papachristodoulou, L., Schneider, M., 2446 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical 2447 Stateless Hash-Based Signatures", Lecture Notes in 2448 Computer Science volume 9056. Advances in Cryptology - 2449 EUROCRYPT, 2015. 2451 [HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal 2452 Parameters for XMSS^MT", Lecture Notes in Computer Science 2453 volume 8128. CD-ARES, 2013. 2455 [HRS16] Huelsing, A., Rijneveld, J., and F. Song, "Mitigating 2456 Multi-Target Attacks in Hash-based Signatures", Lecture 2457 Notes in Computer Science volume 9614. Public-Key 2458 Cryptography - PKC 2016, 2016. 2460 [Huelsing13] 2461 Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based 2462 Signature Schemes", Lecture Notes in Computer Science 2463 volume 7918. Progress in Cryptology - AFRICACRYPT, 2013. 2465 [Huelsing13a] 2466 Huelsing, A., "Practical Forward Secure Signatures using 2467 Minimal Security Assumptions", PhD thesis TU Darmstadt, 2468 2013, 2469 . 2471 [Kaliski15] 2472 Kaliski, B., "Panel: Shoring up the Infrastructure: A 2473 Strategy for Standardizing Hash Signatures", NIST Workshop 2474 on Cybersecurity in a Post-Quantum World, 2015. 2476 [KMN14] Knecht, M., Meier, W., and C. Nicola, "A space- and time- 2477 efficient Implementation of the Merkle Tree Traversal 2478 Algorithm", Computing Research Repository 2479 (CoRR). arXiv:1409.4081, 2014. 2481 [MCF17] McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based 2482 Signatures", Work in Progress, draft-mcgrew-hash-sigs-08, 2483 October 2017, . 2486 [Merkle79] 2487 Merkle, R., "Secrecy, Authentication, and Public Key 2488 Systems", Stanford University Information Systems 2489 Laboratory Technical Report 1979-1, 1979, 2490 . 2492 Appendix A. WOTS+ XDR Formats 2494 The WOTS+ signature and public key formats are formally defined using 2495 XDR [RFC4506] in order to provide an unambiguous, machine readable 2496 definition. Though XDR is used, these formats are simple and easy to 2497 parse without any special tools. Note that this representation 2498 includes all optional parameter sets. The same applies for the XMSS 2499 and XMSS^MT formats below. 2501 WOTS+ parameter sets are defined using XDR syntax as follows: 2503 /* ots_algorithm_type identifies a particular 2504 signature algorithm */ 2506 enum ots_algorithm_type { 2507 wotsp_reserved = 0x00000000, 2508 wotsp-sha2_256 = 0x00000001, 2509 wotsp-sha2_512 = 0x00000002, 2510 wotsp-shake_256 = 0x00000003, 2511 wotsp-shake_512 = 0x00000004, 2512 }; 2514 WOTS+ signatures are defined using XDR syntax as follows: 2516 /* Byte strings */ 2518 typedef opaque bytestring32[32]; 2519 typedef opaque bytestring64[64]; 2521 union ots_signature switch (ots_algorithm_type type) { 2522 case wotsp-sha2_256: 2523 case wotsp-shake_256: 2524 bytestring32 ots_sig_n32_len67[67]; 2526 case wotsp-sha2_512: 2527 case wotsp-shake_512: 2528 bytestring64 ots_sig_n64_len18[131]; 2530 default: 2531 void; /* error condition */ 2532 }; 2534 WOTS+ public keys are defined using XDR syntax as follows: 2536 union ots_pubkey switch (ots_algorithm_type type) { 2537 case wotsp-sha2_256: 2538 case wotsp-shake_256: 2539 bytestring32 ots_pubk_n32_len67[67]; 2541 case wotsp-sha2_512: 2542 case wotsp-shake_512: 2543 bytestring64 ots_pubk_n64_len18[131]; 2545 default: 2546 void; /* error condition */ 2547 }; 2549 Appendix B. XMSS XDR Formats 2550 XMSS parameter sets are defined using XDR syntax as follows: 2552 /* Byte strings */ 2554 typedef opaque bytestring4[4]; 2556 /* Definition of parameter sets */ 2558 enum xmss_algorithm_type { 2559 xmss_reserved = 0x00000000, 2561 /* 256 bit classical security, 128 bit post-quantum security */ 2563 xmss-sha2_10_256 = 0x00000001, 2564 xmss-sha2_16_256 = 0x00000002, 2565 xmss-sha2_20_256 = 0x00000003, 2567 /* 512 bit classical security, 256 bit post-quantum security */ 2569 xmss-sha2_10_512 = 0x00000004, 2570 xmss-sha2_16_512 = 0x00000005, 2571 xmss-sha2_20_512 = 0x00000006, 2573 /* 256 bit classical security, 128 bit post-quantum security */ 2575 xmss-shake_10_256 = 0x00000007, 2576 xmss-shake_16_256 = 0x00000008, 2577 xmss-shake_20_256 = 0x00000009, 2579 /* 512 bit classical security, 256 bit post-quantum security */ 2581 xmss-shake_10_512 = 0x0a00000a, 2582 xmss-shake_16_512 = 0x0b00000b, 2583 xmss-shake_20_512 = 0x0c00000c, 2584 }; 2586 XMSS signatures are defined using XDR syntax as follows: 2588 /* Authentication path types */ 2590 union xmss_path switch (xmss_algorithm_type type) { 2591 case xmss-sha2_10_256: 2592 case xmss-shake_10_256: 2593 bytestring32 path_n32_t10[10]; 2595 case xmss-sha2_16_256: 2596 case xmss-shake_16_256: 2597 bytestring32 path_n32_t16[16]; 2599 case xmss-sha2_20_256: 2600 case xmss-shake_20_256: 2601 bytestring32 path_n32_t20[20]; 2603 case xmss-sha2_10_512: 2604 case xmss-shake_10_512: 2605 bytestring64 path_n64_t10[10]; 2607 case xmss-sha2_16_512: 2608 case xmss-shake_16_512: 2609 bytestring64 path_n64_t16[16]; 2611 case xmss-sha2_20_512: 2612 case xmss-shake_20_512: 2613 bytestring64 path_n64_t20[20]; 2615 default: 2616 void; /* error condition */ 2617 }; 2619 /* Types for XMSS random strings */ 2621 union random_string_xmss switch (xmss_algorithm_type type) { 2622 case xmss-sha2_10_256: 2623 case xmss-sha2_16_256: 2624 case xmss-sha2_20_256: 2625 case xmss-shake_10_256: 2626 case xmss-shake_16_256: 2627 case xmss-shake_20_256: 2628 bytestring32 rand_n32; 2630 case xmss-sha2_10_512: 2631 case xmss-sha2_16_512: 2632 case xmss-sha2_20_512: 2633 case xmss-shake_10_512: 2634 case xmss-shake_16_512: 2635 case xmss-shake_20_512: 2636 bytestring64 rand_n64; 2638 default: 2639 void; /* error condition */ 2640 }; 2642 /* Corresponding WOTS+ type for given XMSS type */ 2643 union xmss_ots_signature switch (xmss_algorithm_type type) { 2644 case xmss-sha2_10_256: 2645 case xmss-sha2_16_256: 2646 case xmss-sha2_20_256: 2647 wotsp-sha2_256; 2649 case xmss-sha2_10_512: 2650 case xmss-sha2_16_512: 2651 case xmss-sha2_20_512: 2652 wotsp-sha2_512; 2654 case xmss-shake_10_256: 2655 case xmss-shake_16_256: 2656 case xmss-shake_20_256: 2657 wotsp-shake_256; 2659 case xmss-shake_10_512: 2660 case xmss-shake_16_512: 2661 case xmss-shake_20_512: 2662 wotsp-shake_512; 2664 default: 2665 void; /* error condition */ 2666 }; 2668 /* XMSS signature structure */ 2670 struct xmss_signature { 2671 /* WOTS+ key pair index */ 2672 bytestring4 idx_sig; 2673 /* Random string for randomized hashing */ 2674 random_string_xmss rand_string; 2675 /* WOTS+ signature */ 2676 xmss_ots_signature sig_ots; 2677 /* authentication path */ 2678 xmss_path nodes; 2679 }; 2681 XMSS public keys are defined using XDR syntax as follows: 2683 /* Types for bitmask seed */ 2685 union seed switch (xmss_algorithm_type type) { 2686 case xmss-sha2_10_256: 2687 case xmss-sha2_16_256: 2688 case xmss-sha2_20_256: 2690 case xmss-shake_10_256: 2691 case xmss-shake_16_256: 2692 case xmss-shake_20_256: 2693 bytestring32 seed_n32; 2695 case xmss-sha2_10_512: 2696 case xmss-sha2_16_512: 2697 case xmss-sha2_20_512: 2698 case xmss-shake_10_512: 2699 case xmss-shake_16_512: 2700 case xmss-shake_20_512: 2701 bytestring64 seed_n64; 2703 default: 2704 void; /* error condition */ 2705 }; 2707 /* Types for XMSS root node */ 2709 union xmss_root switch (xmss_algorithm_type type) { 2710 case xmss-sha2_10_256: 2711 case xmss-sha2_16_256: 2712 case xmss-sha2_20_256: 2713 case xmss-shake_10_256: 2714 case xmss-shake_16_256: 2715 case xmss-shake_20_256: 2716 bytestring32 root_n32; 2718 case xmss-sha2_10_512: 2719 case xmss-sha2_16_512: 2720 case xmss-sha2_20_512: 2721 case xmss-shake_10_512: 2722 case xmss-shake_16_512: 2723 case xmss-shake_20_512: 2724 bytestring64 root_n64; 2726 default: 2727 void; /* error condition */ 2728 }; 2730 /* XMSS public key structure */ 2732 struct xmss_public_key { 2733 xmss_root root; /* Root node */ 2734 seed SEED; /* Seed for bitmasks */ 2735 }; 2737 Appendix C. XMSS^MT XDR Formats 2739 XMSS^MT parameter sets are defined using XDR syntax as follows: 2741 /* Byte strings */ 2743 typedef opaque bytestring3[3]; 2744 typedef opaque bytestring5[5]; 2745 typedef opaque bytestring8[8]; 2747 /* Definition of parameter sets */ 2749 enum xmssmt_algorithm_type { 2750 xmssmt_reserved = 0x00000000, 2752 /* 256 bit classical security, 128 bit post-quantum security */ 2754 xmssmt-sha2_20/2_256 = 0x00000001, 2755 xmssmt-sha2_20/4_256 = 0x00000002, 2756 xmssmt-sha2_40/2_256 = 0x00000003, 2757 xmssmt-sha2_40/4_256 = 0x00000004, 2758 xmssmt-sha2_40/8_256 = 0x00000005, 2759 xmssmt-sha2_60/3_256 = 0x00000006, 2760 xmssmt-sha2_60/6_256 = 0x00000007, 2761 xmssmt-sha2_60/12_256 = 0x00000008, 2763 /* 512 bit classical security, 256 bit post-quantum security */ 2765 xmssmt-sha2_20/2_512 = 0x00000009, 2766 xmssmt-sha2_20/4_512 = 0x0000000a, 2767 xmssmt-sha2_40/2_512 = 0x0000000b, 2768 xmssmt-sha2_40/4_512 = 0x0000000c, 2769 xmssmt-sha2_40/8_512 = 0x0000000d, 2770 xmssmt-sha2_60/3_512 = 0x0000000e, 2771 xmssmt-sha2_60/6_512 = 0x0000000f, 2772 xmssmt-sha2_60/12_512 = 0x00000010, 2774 /* 256 bit classical security, 128 bit post-quantum security */ 2776 xmssmt-shake_20/2_256 = 0x00000011, 2777 xmssmt-shake_20/4_256 = 0x00000012, 2778 xmssmt-shake_40/2_256 = 0x00000013, 2779 xmssmt-shake_40/4_256 = 0x00000014, 2780 xmssmt-shake_40/8_256 = 0x00000015, 2781 xmssmt-shake_60/3_256 = 0x00000016, 2782 xmssmt-shake_60/6_256 = 0x00000017, 2783 xmssmt-shake_60/12_256 = 0x00000018, 2784 /* 512 bit classical security, 256 bit post-quantum security */ 2786 xmssmt-shake_20/2_512 = 0x00000019, 2787 xmssmt-shake_20/4_512 = 0x0000001a, 2788 xmssmt-shake_40/2_512 = 0x0000001b, 2789 xmssmt-shake_40/4_512 = 0x0000001c, 2790 xmssmt-shake_40/8_512 = 0x0000001d, 2791 xmssmt-shake_60/3_512 = 0x0000001e, 2792 xmssmt-shake_60/6_512 = 0x0000001f, 2793 xmssmt-shake_60/12_512 = 0x00000020, 2794 }; 2796 XMSS^MT signatures are defined using XDR syntax as follows: 2798 /* Type for XMSS^MT key pair index */ 2799 /* Depends solely on h */ 2801 union idx_sig_xmssmt switch (xmss_algorithm_type type) { 2802 case xmssmt-sha2_20/2_256: 2803 case xmssmt-sha2_20/4_256: 2804 case xmssmt-sha2_20/2_512: 2805 case xmssmt-sha2_20/4_512: 2806 case xmssmt-shake_20/2_256: 2807 case xmssmt-shake_20/4_256: 2808 case xmssmt-shake_20/2_512: 2809 case xmssmt-shake_20/4_512: 2810 bytestring3 idx3; 2812 case xmssmt-sha2_40/2_256: 2813 case xmssmt-sha2_40/4_256: 2814 case xmssmt-sha2_40/8_256: 2815 case xmssmt-sha2_40/2_512: 2816 case xmssmt-sha2_40/4_512: 2817 case xmssmt-sha2_40/8_512: 2818 case xmssmt-shake_40/2_256: 2819 case xmssmt-shake_40/4_256: 2820 case xmssmt-shake_40/8_256: 2821 case xmssmt-shake_40/2_512: 2822 case xmssmt-shake_40/4_512: 2823 case xmssmt-shake_40/8_512: 2824 bytestring5 idx5; 2826 case xmssmt-sha2_60/3_256: 2827 case xmssmt-sha2_60/6_256: 2828 case xmssmt-sha2_60/12_256: 2829 case xmssmt-sha2_60/3_512: 2831 case xmssmt-sha2_60/6_512: 2832 case xmssmt-sha2_60/12_512: 2833 case xmssmt-shake_60/3_256: 2834 case xmssmt-shake_60/6_256: 2835 case xmssmt-shake_60/12_256: 2836 case xmssmt-shake_60/3_512: 2837 case xmssmt-shake_60/6_512: 2838 case xmssmt-shake_60/12_512: 2839 bytestring8 idx8; 2841 default: 2842 void; /* error condition */ 2843 }; 2845 union random_string_xmssmt switch (xmssmt_algorithm_type type) { 2846 case xmssmt-sha2_20/2_256: 2847 case xmssmt-sha2_20/4_256: 2848 case xmssmt-sha2_40/2_256: 2849 case xmssmt-sha2_40/4_256: 2850 case xmssmt-sha2_40/8_256: 2851 case xmssmt-sha2_60/3_256: 2852 case xmssmt-sha2_60/6_256: 2853 case xmssmt-sha2_60/12_256: 2854 case xmssmt-shake_20/2_256: 2855 case xmssmt-shake_20/4_256: 2856 case xmssmt-shake_40/2_256: 2857 case xmssmt-shake_40/4_256: 2858 case xmssmt-shake_40/8_256: 2859 case xmssmt-shake_60/3_256: 2860 case xmssmt-shake_60/6_256: 2861 case xmssmt-shake_60/12_256: 2862 bytestring32 rand_n32; 2864 case xmssmt-sha2_20/2_512: 2865 case xmssmt-sha2_20/4_512: 2866 case xmssmt-sha2_40/2_512: 2867 case xmssmt-sha2_40/4_512: 2868 case xmssmt-sha2_40/8_512: 2869 case xmssmt-sha2_60/3_512: 2870 case xmssmt-sha2_60/6_512: 2871 case xmssmt-sha2_60/12_512: 2872 case xmssmt-shake_20/2_512: 2873 case xmssmt-shake_20/4_512: 2874 case xmssmt-shake_40/2_512: 2875 case xmssmt-shake_40/4_512: 2876 case xmssmt-shake_40/8_512: 2877 case xmssmt-shake_60/3_512: 2878 case xmssmt-shake_60/6_512: 2880 case xmssmt-shake_60/12_512: 2881 bytestring64 rand_n64; 2883 default: 2884 void; /* error condition */ 2885 }; 2887 /* Type for reduced XMSS signatures */ 2889 union xmss_reduced (xmss_algorithm_type type) { 2890 case xmssmt-sha2_20/2_256: 2891 case xmssmt-sha2_40/4_256: 2892 case xmssmt-sha2_60/6_256: 2893 case xmssmt-shake_20/2_256: 2894 case xmssmt-shake_40/4_256: 2895 case xmssmt-shake_60/6_256: 2896 bytestring32 xmss_reduced_n32_t77[77]; 2898 case xmssmt-sha2_20/4_256: 2899 case xmssmt-sha2_40/8_256: 2900 case xmssmt-sha2_60/12_256: 2901 case xmssmt-shake_20/4_256: 2902 case xmssmt-shake_40/8_256: 2903 case xmssmt-shake_60/12_256: 2904 bytestring32 xmss_reduced_n32_t72[72]; 2906 case xmssmt-sha2_40/2_256: 2907 case xmssmt-sha2_60/3_256: 2908 case xmssmt-shake_40/2_256: 2909 case xmssmt-shake_60/3_256: 2910 bytestring32 xmss_reduced_n32_t87[87]; 2912 case xmssmt-sha2_20/2_512: 2913 case xmssmt-sha2_40/4_512: 2914 case xmssmt-sha2_60/6_512: 2915 case xmssmt-shake_20/2_512: 2916 case xmssmt-shake_40/4_512: 2917 case xmssmt-shake_60/6_512: 2918 bytestring64 xmss_reduced_n32_t141[141]; 2920 case xmssmt-sha2_20/4_512: 2921 case xmssmt-sha2_40/8_512: 2922 case xmssmt-sha2_60/12_512: 2923 case xmssmt-shake_20/4_512: 2924 case xmssmt-shake_40/8_512: 2925 case xmssmt-shake_60/12_512: 2926 bytestring64 xmss_reduced_n32_t136[136]; 2928 case xmssmt-sha2_40/2_512: 2929 case xmssmt-sha2_60/3_512: 2930 case xmssmt-shake_40/2_512: 2931 case xmssmt-shake_60/3_512: 2932 bytestring64 xmss_reduced_n32_t151[151]; 2934 default: 2935 void; /* error condition */ 2936 }; 2938 /* xmss_reduced_array depends on d */ 2940 union xmss_reduced_array (xmss_algorithm_type type) { 2941 case xmssmt-sha2_20/2_256: 2942 case xmssmt-sha2_20/2_512: 2943 case xmssmt-sha2_40/2_256: 2944 case xmssmt-sha2_40/2_512: 2945 case xmssmt-shake_20/2_256: 2946 case xmssmt-shake_20/2_512: 2947 case xmssmt-shake_40/2_256: 2948 case xmssmt-shake_40/2_512: 2949 xmss_reduced xmss_red_arr_d2[2]; 2951 case xmssmt-sha2_60/3_256: 2952 case xmssmt-sha2_60/3_512: 2953 case xmssmt-shake_60/3_256: 2954 case xmssmt-shake_60/3_512: 2955 xmss_reduced xmss_red_arr_d3[3]; 2957 case xmssmt-sha2_20/4_256: 2958 case xmssmt-sha2_20/4_512: 2959 case xmssmt-sha2_40/4_256: 2960 case xmssmt-sha2_40/4_512: 2961 case xmssmt-shake_20/4_256: 2962 case xmssmt-shake_20/4_512: 2963 case xmssmt-shake_40/4_256: 2964 case xmssmt-shake_40/4_512: 2965 xmss_reduced xmss_red_arr_d4[4]; 2967 case xmssmt-sha2_60/6_256: 2968 case xmssmt-sha2_60/6_512: 2969 case xmssmt-shake_60/6_256: 2970 case xmssmt-shake_60/6_512: 2971 xmss_reduced xmss_red_arr_d6[6]; 2973 case xmssmt-sha2_40/8_256: 2974 case xmssmt-sha2_40/8_512: 2975 case xmssmt-shake_40/8_256: 2977 case xmssmt-shake_40/8_512: 2978 xmss_reduced xmss_red_arr_d8[8]; 2980 case xmssmt-sha2_60/12_256: 2981 case xmssmt-sha2_60/12_512: 2982 case xmssmt-shake_60/12_256: 2983 case xmssmt-shake_60/12_512: 2984 xmss_reduced xmss_red_arr_d12[12]; 2986 default: 2987 void; /* error condition */ 2988 }; 2990 /* XMSS^MT signature structure */ 2992 struct xmssmt_signature { 2993 /* WOTS+ key pair index */ 2994 idx_sig_xmssmt idx_sig; 2995 /* Random string for randomized hashing */ 2996 random_string_xmssmt randomness; 2997 /* Array of d reduced XMSS signatures */ 2998 xmss_reduced_array; 2999 }; 3001 XMSS^MT public keys are defined using XDR syntax as follows: 3003 /* Types for bitmask seed */ 3005 union seed switch (xmssmt_algorithm_type type) { 3006 case xmssmt-sha2_20/2_256: 3007 case xmssmt-sha2_40/4_256: 3008 case xmssmt-sha2_60/6_256: 3009 case xmssmt-sha2_20/4_256: 3010 case xmssmt-sha2_40/8_256: 3011 case xmssmt-sha2_60/12_256: 3012 case xmssmt-sha2_40/2_256: 3013 case xmssmt-sha2_60/3_256: 3014 case xmssmt-shake_20/2_256: 3015 case xmssmt-shake_40/4_256: 3016 case xmssmt-shake_60/6_256: 3017 case xmssmt-shake_20/4_256: 3018 case xmssmt-shake_40/8_256: 3019 case xmssmt-shake_60/12_256: 3020 case xmssmt-shake_40/2_256: 3021 case xmssmt-shake_60/3_256: 3022 bytestring32 seed_n32; 3024 case xmssmt-sha2_20/2_512: 3025 case xmssmt-sha2_40/4_512: 3026 case xmssmt-sha2_60/6_512: 3027 case xmssmt-sha2_20/4_512: 3028 case xmssmt-sha2_40/8_512: 3029 case xmssmt-sha2_60/12_512: 3030 case xmssmt-sha2_40/2_512: 3031 case xmssmt-sha2_60/3_512: 3032 case xmssmt-shake_20/2_512: 3033 case xmssmt-shake_40/4_512: 3034 case xmssmt-shake_60/6_512: 3035 case xmssmt-shake_20/4_512: 3036 case xmssmt-shake_40/8_512: 3037 case xmssmt-shake_60/12_512: 3038 case xmssmt-shake_40/2_512: 3039 case xmssmt-shake_60/3_512: 3040 bytestring64 seed_n64; 3042 default: 3043 void; /* error condition */ 3044 }; 3046 /* Types for XMSS^MT root node */ 3048 union xmssmt_root switch (xmssmt_algorithm_type type) { 3049 case xmssmt-sha2_20/2_256: 3050 case xmssmt-sha2_20/4_256: 3051 case xmssmt-sha2_40/2_256: 3052 case xmssmt-sha2_40/4_256: 3053 case xmssmt-sha2_40/8_256: 3054 case xmssmt-sha2_60/3_256: 3055 case xmssmt-sha2_60/6_256: 3056 case xmssmt-sha2_60/12_256: 3057 case xmssmt-shake_20/2_256: 3058 case xmssmt-shake_20/4_256: 3059 case xmssmt-shake_40/2_256: 3060 case xmssmt-shake_40/4_256: 3061 case xmssmt-shake_40/8_256: 3062 case xmssmt-shake_60/3_256: 3063 case xmssmt-shake_60/6_256: 3064 case xmssmt-shake_60/12_256: 3065 bytestring32 root_n32; 3067 case xmssmt-sha2_20/2_512: 3068 case xmssmt-sha2_20/4_512: 3069 case xmssmt-sha2_40/2_512: 3070 case xmssmt-sha2_40/4_512: 3071 case xmssmt-sha2_40/8_512: 3073 case xmssmt-sha2_60/3_512: 3074 case xmssmt-sha2_60/6_512: 3075 case xmssmt-sha2_60/12_512: 3076 case xmssmt-shake_20/2_512: 3077 case xmssmt-shake_20/4_512: 3078 case xmssmt-shake_40/2_512: 3079 case xmssmt-shake_40/4_512: 3080 case xmssmt-shake_40/8_512: 3081 case xmssmt-shake_60/3_512: 3082 case xmssmt-shake_60/6_512: 3083 case xmssmt-shake_60/12_512: 3084 bytestring64 root_n64; 3086 default: 3087 void; /* error condition */ 3088 }; 3090 /* XMSS^MT public key structure */ 3092 struct xmssmt_public_key { 3093 xmssmt_root root; /* Root node */ 3094 seed SEED; /* Seed for bitmasks */ 3095 }; 3097 Authors' Addresses 3099 Andreas Huelsing 3100 TU Eindhoven 3101 P.O. Box 513 3102 Eindhoven 5600 MB 3103 NL 3105 Email: ietf@huelsing.net 3107 Denis Butin 3108 TU Darmstadt 3109 Hochschulstrasse 10 3110 Darmstadt 64289 3111 DE 3113 Email: dbutin@cdc.informatik.tu-darmstadt.de 3114 Stefan-Lukas Gazdag 3115 genua GmbH 3116 Domagkstrasse 7 3117 Kirchheim bei Muenchen 85551 3118 DE 3120 Email: ietf@gazdag.de 3122 Joost Rijneveld 3123 Radboud University 3124 Toernooiveld 212 3125 Nijmegen 6525 EC 3126 NL 3128 Email: ietf@joostrijneveld.nl 3130 Aziz Mohaisen 3131 University of Central Florida 3132 4000 Central Florida Blvd 3133 Orlando, FL 32816 3134 US 3136 Phone: +1 407 823-1294 3137 Email: mohaisen@ieee.org