idnits 2.17.1 draft-huelsing-cfrg-hash-sig-xmss-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 23, 2015) is 3315 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 1023 == Missing Reference: '2i' is mentioned on line 662, but not defined -- Looks like a reference, but probably isn't: '2' on line 3648 -- Looks like a reference, but probably isn't: '1' on line 3631 -- Looks like a reference, but probably isn't: '32' on line 2448 -- Looks like a reference, but probably isn't: '64' on line 2449 -- Looks like a reference, but probably isn't: '133' on line 2482 -- Looks like a reference, but probably isn't: '90' on line 2486 -- Looks like a reference, but probably isn't: '67' on line 2490 -- Looks like a reference, but probably isn't: '261' on line 2493 -- Looks like a reference, but probably isn't: '175' on line 2496 -- Looks like a reference, but probably isn't: '131' on line 2499 -- Looks like a reference, but probably isn't: '4' on line 2511 -- Looks like a reference, but probably isn't: '16' on line 2656 -- Looks like a reference, but probably isn't: '10' on line 2651 -- Looks like a reference, but probably isn't: '20' on line 2661 -- Looks like a reference, but probably isn't: '36' on line 3918 -- Looks like a reference, but probably isn't: '48' on line 2919 -- Looks like a reference, but probably isn't: '56' on line 3933 -- Looks like a reference, but probably isn't: '34' on line 3882 -- Looks like a reference, but probably isn't: '46' on line 2898 -- Looks like a reference, but probably isn't: '54' on line 3896 -- Looks like a reference, but probably isn't: '38' on line 3901 -- Looks like a reference, but probably isn't: '50' on line 2908 -- Looks like a reference, but probably isn't: '58' on line 3910 -- Looks like a reference, but probably isn't: '3' on line 3680 -- Looks like a reference, but probably isn't: '5' on line 3697 -- Looks like a reference, but probably isn't: '8' on line 2985 -- Looks like a reference, but probably isn't: '88' on line 3422 -- Looks like a reference, but probably isn't: '108' on line 3427 -- Looks like a reference, but probably isn't: '128' on line 3432 -- Looks like a reference, but probably isn't: '66' on line 3436 -- Looks like a reference, but probably isn't: '86' on line 3441 -- Looks like a reference, but probably isn't: '106' on line 3446 -- Looks like a reference, but probably isn't: '55' on line 3450 -- Looks like a reference, but probably isn't: '75' on line 3455 -- Looks like a reference, but probably isn't: '95' on line 3460 -- Looks like a reference, but probably isn't: '153' on line 3466 -- Looks like a reference, but probably isn't: '173' on line 3474 -- Looks like a reference, but probably isn't: '193' on line 3482 -- Looks like a reference, but probably isn't: '110' on line 3489 -- Looks like a reference, but probably isn't: '130' on line 3497 -- Looks like a reference, but probably isn't: '150' on line 3505 -- Looks like a reference, but probably isn't: '87' on line 3511 -- Looks like a reference, but probably isn't: '107' on line 3519 -- Looks like a reference, but probably isn't: '127' on line 3527 -- Looks like a reference, but probably isn't: '281' on line 3533 -- Looks like a reference, but probably isn't: '301' on line 3541 -- Looks like a reference, but probably isn't: '321' on line 3549 -- Looks like a reference, but probably isn't: '195' on line 3553 -- Looks like a reference, but probably isn't: '215' on line 3561 -- Looks like a reference, but probably isn't: '235' on line 3569 -- Looks like a reference, but probably isn't: '151' on line 3575 -- Looks like a reference, but probably isn't: '171' on line 3584 -- Looks like a reference, but probably isn't: '191' on line 3592 -- Looks like a reference, but probably isn't: '7' on line 3714 -- Looks like a reference, but probably isn't: '11' on line 3732 -- Looks like a reference, but probably isn't: '26' on line 3927 -- Looks like a reference, but probably isn't: '24' on line 3890 -- Looks like a reference, but probably isn't: '28' on line 3906 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) == Outdated reference: A later version (-15) exists of draft-mcgrew-hash-sigs-02 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 61 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: September 24, 2015 TU Darmstadt 6 S. Gazdag 7 genua mbH 8 A. Mohaisen 9 Verisign Labs 10 March 23, 2015 12 XMSS: Extended Hash-Based Signatures 13 draft-huelsing-cfrg-hash-sig-xmss-00 15 Abstract 17 This note describes the eXtended Merkle Signature Scheme (XMSS), a 18 hash-based digital signature system. It follows existing 19 descriptions in scientific literature. The note specifies the WOTS+ 20 one-time signature scheme, a single-tree (XMSS) and a multi-tree 21 variant (XMSS^MT) of XMSS. Both variants use WOTS+ as a main 22 building block. XMSS provides cryptographic digital signatures 23 without relying on the conjectured hardness of mathematical problems. 24 Instead, it is proven that it only relies on the properties of 25 cryptographic hash functions. XMSS provides strong security 26 guarantees and, besides some special instantiations, is even secure 27 when the collision resistance of the underlying hash function is 28 broken. It is suitable for compact implementations, relatively 29 simple to implement, and naturally resists side-channel attacks. 30 Unlike most other signature systems, hash-based signatures withstand 31 attacks using quantum computers. 33 Status of This Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at http://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on September 24, 2015. 50 Copyright Notice 52 Copyright (c) 2015 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 1.1. Conventions Used In This Document . . . . . . . . . . . . 5 69 2. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 5 70 2.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 5 71 2.2. Operators . . . . . . . . . . . . . . . . . . . . . . . . 5 72 2.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 6 73 2.4. Strings of Base-w Numbers . . . . . . . . . . . . . . . . 6 74 2.5. Member Functions . . . . . . . . . . . . . . . . . . . . 7 75 3. Primitives . . . . . . . . . . . . . . . . . . . . . . . . . 8 76 3.1. WOTS+ One-Time Signatures . . . . . . . . . . . . . . . . 8 77 3.1.1. WOTS+ Parameters . . . . . . . . . . . . . . . . . . 8 78 3.1.1.1. WOTS+ Hashing Functions . . . . . . . . . . . . . 9 79 3.1.2. WOTS+ Chaining Function . . . . . . . . . . . . . . . 9 80 3.1.3. WOTS+ Private Key . . . . . . . . . . . . . . . . . . 9 81 3.1.4. WOTS+ Public Key . . . . . . . . . . . . . . . . . . 10 82 3.1.5. WOTS+ Signature Generation . . . . . . . . . . . . . 10 83 3.1.6. WOTS+ Signature Verification . . . . . . . . . . . . 11 84 3.1.7. Pseudorandom Key Generation . . . . . . . . . . . . . 12 85 4. Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 86 4.1. XMSS: eXtended Merkle Signature Scheme . . . . . . . . . 13 87 4.1.1. XMSS Parameters . . . . . . . . . . . . . . . . . . . 13 88 4.1.2. XMSS Hash Functions . . . . . . . . . . . . . . . . . 14 89 4.1.3. XMSS Private Key . . . . . . . . . . . . . . . . . . 14 90 4.1.4. L-Trees . . . . . . . . . . . . . . . . . . . . . . . 14 91 4.1.5. TreeHash . . . . . . . . . . . . . . . . . . . . . . 15 92 4.1.6. XMSS Public Key . . . . . . . . . . . . . . . . . . . 15 93 4.1.7. XMSS Signature . . . . . . . . . . . . . . . . . . . 16 94 4.1.8. XMSS Signature Generation . . . . . . . . . . . . . . 18 95 4.1.9. XMSS Signature Verification . . . . . . . . . . . . . 19 96 4.1.10. Pseudorandom Key Generation . . . . . . . . . . . . . 20 97 4.1.11. Free Index Handling and Partial Secret Keys . . . . . 21 99 4.2. XMSS^MT: Multi-Tree XMSS . . . . . . . . . . . . . . . . 21 100 4.2.1. XMSS^MT Parameters . . . . . . . . . . . . . . . . . 21 101 4.2.2. XMSS Algorithms Without Message Hash . . . . . . . . 22 102 4.2.3. XMSS^MT Private Key . . . . . . . . . . . . . . . . . 22 103 4.2.4. XMSS^MT Public Key . . . . . . . . . . . . . . . . . 22 104 4.2.5. XMSS^MT Signature . . . . . . . . . . . . . . . . . . 23 105 4.2.6. XMSS^MT Signature Generation . . . . . . . . . . . . 24 106 4.2.7. XMSS^MT Signature Verification . . . . . . . . . . . 25 107 4.2.8. Pseudorandom Key Generation . . . . . . . . . . . . . 26 108 4.2.9. Free Index Handling and Partial Secret Keys . . . . . 26 109 5. Parameter Sets . . . . . . . . . . . . . . . . . . . . . . . 27 110 5.1. Zero Bitmasks . . . . . . . . . . . . . . . . . . . . . . 27 111 5.2. WOTS+ Parameters . . . . . . . . . . . . . . . . . . . . 28 112 5.3. XMSS Parameters . . . . . . . . . . . . . . . . . . . . . 29 113 5.3.1. XMSS Parameters . . . . . . . . . . . . . . . . . . . 29 114 5.3.1.1. XMSS Parameters with AES and SHA3 . . . . . . . . 29 115 5.3.1.2. XMSS Parameters with SHA3 . . . . . . . . . . . . 30 116 5.3.2. XMSS Parameters With Empty Bitmasks . . . . . . . . . 31 117 5.4. XMSS^MT Parameters . . . . . . . . . . . . . . . . . . . 32 118 5.4.1. XMSS^MT Parameters . . . . . . . . . . . . . . . . . 32 119 5.4.1.1. XMSS^MT Parameters with AES and SHA3 . . . . . . 32 120 5.4.1.2. XMSS^MT Parameters with SHA3 . . . . . . . . . . 33 121 5.4.2. XMSS^MT Parameters With Empty Bitmasks . . . . . . . 35 122 6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 38 123 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 124 8. Security Considerations . . . . . . . . . . . . . . . . . . . 49 125 8.1. Security Proofs . . . . . . . . . . . . . . . . . . . . . 50 126 8.2. Security Assumptions . . . . . . . . . . . . . . . . . . 51 127 8.3. Post-Quantum Security . . . . . . . . . . . . . . . . . . 51 128 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51 129 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 130 10.1. Normative References . . . . . . . . . . . . . . . . . . 51 131 10.2. Informative References . . . . . . . . . . . . . . . . . 52 132 Appendix A. WOTS+ XDR Formats . . . . . . . . . . . . . . . . . 53 133 Appendix B. XMSS XDR Formats . . . . . . . . . . . . . . . . . . 55 134 Appendix C. XMSS^MT XDR Formats . . . . . . . . . . . . . . . . 65 135 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 87 137 1. Introduction 139 A (cryptographic) digital signature scheme provides asymmetric 140 message authentication. The key generation algorithm produces a key 141 pair consisting of a private and a public key. A message is signed 142 using a private key to produce a signature. A message/signature pair 143 can be verified using a public key. A One-Time Signature (OTS) 144 scheme allows us to use a key pair to sign exactly one message 145 securely. A many-time signature system can be used to sign multiple 146 messages. 148 One-Time Signature schemes, and Many-Time Signature (MTS) schemes 149 composed of them, were proposed by Merkle in 1979 [Merkle79]. They 150 were well-studied in the 1990s and have regained interest from 2006 151 onwards because of their resistance against quantum-computer-aided 152 attacks. These kinds of signature schemes are called hash-based 153 signature schemes as they are built out of a cryptographic hash 154 function. Hash-based signature schemes generally feature small 155 private and public keys as well as fast signature generation and 156 verification but large signatures and a relatively slow key 157 generation. In addition, they are suitable for compact 158 implementations that benefit various applications and are naturally 159 resistant to most kinds of side-channel attacks. 161 Some progress has already been made toward standardizing and 162 introducing hash signatures. McGrew and Curcio have published an 163 Internet-Draft [DC14] specifying the "textbook" Lamport-Diffie- 164 Winternitz-Merkle (LDWM) scheme based on early publications. 165 Independently, Buchmann, Dahmen and Huelsing have proposed XMSS 166 [BDH11], the "eXtended Merkle Signature Scheme," offering better 167 efficiency and a modern security proof. Very recently, SPHINCS, a 168 stateless hash-based signature scheme was introduced [BHH15], with 169 the intent of being easier to deploy in current applications. A 170 reasonable next step toward introducing hash signatures would seem to 171 complete the specifications of the basic algorithms - LDWM, XMSS, 172 SPHINCS and/or variants [Kaliski15]. 174 The eXtended Merkle Signature Scheme (XMSS) [BDH11] is the latest 175 hash-based signature scheme. It has the smallest signatures out of 176 such schemes and comes with a multi-tree variant that solves the 177 problem of slow key generation. Moreover, it can be shown that XMSS 178 is secure, making only mild assumptions on the underlying hash 179 function. Especially, it is not required that the cryptographic hash 180 function is collision-resistant for the security of XMSS. 182 This note describes a single-tree and a multi-tree variant of the 183 eXtended Merkle Signature Scheme (XMSS) [BDH11]. It also describes 184 WOTS+, a variant of the Winternitz OTS scheme introduced in 185 [Huelsing13] that is used by XMSS. The schemes are described with 186 enough specificity to ensure interoperability between 187 implementations. 189 This note is structured as follows. Notation is introduced in 190 Section 2. Section 3 describes the WOTS+ signature system. Many 191 time signature schemes are defined in Section 4: the eXtended Merkle 192 Signature Scheme (XMSS) in Section 4.1, and its Multi-Tree variant 193 (XMSS^MT) in Section 4.2. Parameter sets are described in Section 5. 194 Section 6 describes the rationale behind choices in this note. The 195 IANA registry for these signature systems is described in Section 7. 196 Finally, security considerations are presented in Section 8. 198 1.1. Conventions Used In This Document 200 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 201 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 202 document are to be interpreted as described in [RFC2119]. 204 2. Notation 206 2.1. Data Types 208 Bytes and byte strings are the fundamental data types. A byte is a 209 sequence of eight bits. A single byte is denoted as a pair of 210 hexadecimal digits with a leading "0x". A byte string is an ordered 211 sequence of zero or more bytes and is denoted as an ordered sequence 212 of hexadecimal characters with a leading "0x". For example, 0xe534f0 213 is a byte string of length 3. An array of byte strings is an 214 ordered, indexed set starting with index 0 in which all byte strings 215 have identical length. 217 2.2. Operators 219 When a and b are integers, mathematical operators are defined as 220 follows: 222 ^ : a ^ b denotes the result of a raised to the power of b. 224 * : a * b denotes the product of a and b. This operator is 225 sometimes used implicitly in the absence of ambiguity, as in usual 226 mathematical notation. 228 / : a / b denotes the quotient of a by b. 230 % : a % b denotes the non-negative remainder of the integer 231 division of a by b. 233 + : a + b denotes the sum of a and b. 235 - : a - b denotes the difference of a and b. 237 The standard order of operations is used when evaluating arithmetic 238 expressions. 240 Arrays are used in the common way, where the i^th element of an array 241 A is denoted A[i]. Byte strings are treated as arrays of bytes where 242 necessary: If X is a byte string, then X[i] denotes its i^th byte, 243 where X[0] is the leftmost byte. In addition, bytes(X, i, j) with i 244 < j denotes the range of bytes from the i^th to the j^th byte in X, 245 inclusively. For example, if X = 0x01020304, then X[0] is 0x01 and 246 bytes(X, 1, 2) is 0x0203. 248 If A and B are byte strings of equal length, then: 250 A AND B denotes the bitwise logical conjunction operation. 252 A XOR B denotes the bitwise logical exclusive disjunction 253 operation. 255 When B is a byte and i is an integer, then B >> i denotes the logical 256 right-shift operation. Similarly, B << i denotes the logical left- 257 shift operation. 259 If X is a x-byte string and Y a y-byte string, then X || Y denotes 260 the concatenation of X and Y, with X || Y = 261 X[0]...X[x-1]Y[0]...Y[y-1]. 263 2.3. Functions 265 If x is a non-negative real number, then we define the following 266 functions: 268 ceil(x) : returns the smallest integer greater or equal than x. 270 floor(x) : returns the largest integer less or equal than x. 272 lg(x) : returns the base-2 logarithm of x. 274 If x, y, and z are real numbers, then we define the functions max(x, 275 y) and max(x, y, z) which return the maximum value of the set {x, y} 276 and {x, y, z}, respectively. 278 2.4. Strings of Base-w Numbers 280 A byte string can be considered as a string of base-w numbers, i.e. 281 integers in the set {0, ... , w - 1}. The correspondence is defined 282 by the function base_w(X, w) as follows. If X is a m-byte string, w 283 is a member of the set {4, 8, 16}, then base_w(X, w) outputs a length 284 ceil(8m/lg(w)) array of integers between 0 and w - 1. In case lg(w) 285 does not divide 8 * m without a remainder, X is virtually padded with 286 a sufficient amount of zero bits. 288 Algorithm 1: base_w(X, w) 290 i_byte = 0; 291 i_bit = 0; 292 for ( i=0; i < ceil(8m/lg(w)); i++ ){ 293 if( i_bit + lg(w) <= 8 ){ 294 basew[i] = ((X[i_byte] << i_bit) >> (8-lg(w))) AND (w-1); 295 i_bit += lg(w); 296 if ( i_bit == 8 ){ 297 i_bit = 0; 298 i_byte = i_byte + 1; 299 } 300 } else { 301 basew[i] = ((X[i_byte] << i_bit) >> (8-lg(w))) AND (w-1); 302 i_byte = i_byte + 1; 303 if ( i_byte < m ){ 304 basew[i] += (X[i_byte] >> (8-(i_bit + lg(w)-8))) AND (w-1); 305 i_bit = i_bit + lg(w)-8; 306 } 307 } 308 } 309 return basew; 311 For example, if X is 0x1234, then base_w(X, 8) returns the array {0, 312 4, 4, 3, 2, 0}. 314 X (represented as bits) 315 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 316 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 317 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 319 X (padded with zeros) 320 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 321 | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| 0| 0| 322 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 324 X (represented as base-w numbers) 325 +--------+--------+--------+--------+--------+--------+ 326 | 0 | 4 | 4 | 3 | 2 | 0 | 327 +--------+--------+--------+--------+--------+--------+ 329 2.5. Member Functions 331 To simplify algorithm descriptions, we assume the existence of member 332 functions. If a complex data structure like a public key PK contains 333 a value X then getX(PK) returns the value of X for this public key. 334 Accordingly, setX(PK, X, Y) sets value X in PK to the value hold by 335 Y. 337 3. Primitives 339 3.1. WOTS+ One-Time Signatures 341 This section describes the WOTS+ one-time signature system, as 342 defined in [Huelsing13]. WOTS+ is a one-time signature scheme; while 343 a private key can be used to sign any message, each private key MUST 344 be used only once to sign a single message. In particular, if a 345 secret key is used to sign two different messages, the scheme becomes 346 insecure. 348 The section starts with an explanation of parameters. Afterwards, 349 the so-called chaining function, which forms the main building block 350 of the WOTS+ scheme, is explained. It follows a description of the 351 algorithms for key generation, signing and verification. Finally, 352 pseudorandom key generation is discussed. 354 3.1.1. WOTS+ Parameters 356 WOTS+ uses the parameters m, n, and w; they all take positive integer 357 values. These parameters are summarized as follows: 359 m : the message length in bytes 361 n : the length, in bytes, of a secret key, public key, or 362 signature element 364 w : the Winternitz parameter; it is a member of the set {4, 8, 16} 366 The parameters are used to compute values l, l_1 and l_2: 368 l : the number of n-byte string elements in a WOTS+ secret key, 369 public key, and signature. It is computed as l = l_1 + l_2, with 370 l_1 = ceil(8m/lg(w)) and l_2 = floor(lg(l_1*(w-1))/lg(w)) + 1 372 The value of n is determined by the cryptographic hash function used 373 for WOTS+. The hash function is chosen to ensure an appropriate 374 level of security. The value of m is often the length of a message 375 digest. The parameter w can be chosen from the set {4,8,16}. A 376 larger value of w results in shorter signatures but slower overall 377 signing operations; it has little effect on security. Choices of w 378 are limited to the values 4, 8 and 16 since these values yield 379 optimal trade-offs. 381 3.1.1.1. WOTS+ Hashing Functions 383 The WOTS+ algorithm uses a cryptographic hash function F. F accepts 384 and returns byte strings of length n. Security requirements on F are 385 discussed in Section 8. 387 3.1.2. WOTS+ Chaining Function 389 The chaining function (Algorithm 2) computes an iteration of F on an 390 n-byte input using a vector of n-byte strings called bitmasks. In 391 each iteration, a bitmask is first XORed to an intermediate result 392 before it is processed by F. In the following, bm is an array of at 393 least w-2 n-byte strings (that contains the bitmasks). The chaining 394 function takes as input an n-byte string X, a start index i, a number 395 of steps s, and the bitmasks bm. The chaining function returns as 396 output the value obtained by iterating F for s times on input X, 397 using the bitmasks from bm starting at index i. 399 Algorithm 2: Chaining Function 401 if s is equal to 0 then 402 return X; 403 end 404 if (i+s) > w-1 then 405 return NULL; 406 end 407 byte[n] tmp = chain(X, i, s-1, bm); 408 tmp = F(tmp XOR bm[i+s-1]); 409 return tmp; 411 3.1.3. WOTS+ Private Key 413 The private key in WOTS+, denoted by sk, is a length l array of 414 n-byte strings. This private key MUST be only used to sign exactly 415 one message. Each n-byte string MUST either be selected randomly 416 from the uniform distribution or using a cryptographically secure 417 pseudorandom procedure. In the latter case, the security of the used 418 procedure MUST at least match that of the WOTS+ parameters used. For 419 a further discussion on pseudorandom key generation see the end of 420 this section. The following pseudocode (Algorithm 3) describes an 421 algorithm for generating sk. 423 Algorithm 3: Generating a WOTS+ Private Key 425 for ( i = 0; i < l; i = i + 1 ) { 426 set sk[i] to a uniformly random n-byte string 427 } 428 return sk 430 3.1.4. WOTS+ Public Key 432 A WOTS+ key pair defines a virtual structure that consists of l hash 433 chains of length w. The l n-byte strings in the secret key each 434 define the start node for one hash chain. The public key consists of 435 the end nodes of these hash chains. Therefore, like the secret key, 436 the public key is also a length l array of n-byte strings. To 437 compute the hash chain, the chaining function (Algorithm 2) is used. 438 The bitmasks have to be provided by the calling algorithm. The same 439 bitmasks are used for all chains. The following pseudocode 440 (Algorithm 4) describes an algorithm for generating the public key 441 pk, where sk is the private key. 443 Algorithm 4 (WOTS_genPK): Generating a WOTS+ Public Key From a 444 Private Key 446 for ( i = 0; i < l; i = i + 1 ) { 447 pk[i] = chain(sk[i], 0, w-1, bm); 448 } 449 return pk; 451 3.1.5. WOTS+ Signature Generation 453 A WOTS+ signature is a length l array of n-byte strings. The WOTS+ 454 signature is generated by mapping a message to l integers between 0 455 and w - 1. To this end, the message is transformed into base w 456 numbers using the base_w function defined in Section 2.4. Next, a 457 checksum is computed and appended to the transformed message as base 458 w numbers using base_w(). Each of the base w integers is used to 459 select a node from a different hash chain. The signature is formed 460 by concatenating the selected nodes. The pseudocode for signature 461 generation is shown below (Algorithm 5), where M is the message and 462 sig is the resulting signature. 464 Algorithm 5 (WOTS_sign): Generating a signature from a private key 465 and a message 466 csum = 0; 467 // convert message to base w 468 msg = base_w(M,w) 469 // compute checksum 470 for ( i = 0; i < l_1; i = i + 1 ) { 471 csum = csum + w - 1 - msg[i] 472 } 473 // Convert csum to base w 474 msg = msg || base_w(csum, w); 475 for ( i = 0; i < l; i = i + 1 ) { 476 sig[i] = chain(sk[i], 0, msg[i], bm) 477 } 478 return sig 480 The data format for a signature is given below. 482 WOTS+ Signature 484 +---------------------------------+ 485 | algorithm OID | 486 +---------------------------------+ 487 | | 488 | sig_ots[0] | n bytes 489 | | 490 +---------------------------------+ 491 | | 492 ~ .... ~ 493 | | 494 +---------------------------------+ 495 | | 496 | sig_ots[l-1] | n bytes 497 | | 498 +---------------------------------+ 500 3.1.6. WOTS+ Signature Verification 502 In order to verify a signature sig on a message M, the verifier 503 computes a WOTS+ public key value from the signature. This can be 504 done by "completing" the chain computations starting from the 505 signature values, using the base-w values of the message hash and its 506 checksum. This step, called WOTS_pkFromSig, is described below in 507 Algorithm 6. The result of WOTS_pkFromSig is then compared to the 508 given public key. If the values are equal, the signature is 509 accepted. Otherwise, the signature is rejected. 511 Algorithm 6 (WOTS_pkFromSig): Computing a WOTS+ public key from a 512 message and its signature 513 csum = 0; 514 // convert message to base w 515 msg = base_w(M,w) 516 // compute checksum 517 for ( i = 0; i < l_1; i = i + 1 ) { 518 csum = csum + w - 1 - msg[i] 519 } 520 // Convert csum to base w 521 msg = msg || base_w(csum, w); 522 for ( i = 0; i < l; i = i + 1 ) { 523 tmp_pk[i] = chain(sig[i], msg[i], w-1-msg[i], bm) 524 } 525 return tmp_pk 527 Note: XMSS uses WOTS_pkFromSig to compute a public key value and 528 delays the comparison to a later point. 530 3.1.7. Pseudorandom Key Generation 532 An implementation MAY use a cryptographically secure pseudorandom 533 method to generate the secret key from a single n-byte value. For 534 example, the method suggested in [BDH11] and explained below MAY be 535 used. Other methods MAY be used. The choice of a pseudorandom 536 method does not affect interoperability, but the cryptographic 537 strength MUST match that of the used WOTS+ parameters. 539 The advantage of generating the secret key elements from a random 540 n-byte string is that only this n-byte string needs to be stored 541 instead of the full secret key. The key can be regenerated when 542 needed. The suggested method from [BDH11] uses a pseudorandom 543 function G(K,M) that takes an n-byte key and an n-byte message. 544 During key generation a uniformly random n-byte string S is sampled 545 from a secure source of randomness. The secret key elements are 546 computed as sk[i] = G(S,i) whenever needed. The second parameter of 547 G is i, represented as n-byte string in the common way. To implement 548 G, an implementation MAY use the hash function F in PRF mode. When 549 WOTS+ is used within XMSS or XMSS^MT, an implementation SHOULD use 550 PRF_m, taking the first n bytes from the output. 552 4. Schemes 554 In this section, the extended Merkle signature scheme (XMSS) is 555 described using WOTS+. XMSS comes in two flavours: First, a single- 556 tree variant (XMSS) and second a multi-tree variant (XMSS^MT). Both 557 allow combining a large number of WOTS+ key pairs under a single 558 small public key. The main ingredient added is a binary hash tree 559 construction. XMSS uses a single hash tree while XMSS^MT uses a tree 560 of XMSS key pairs. 562 4.1. XMSS: eXtended Merkle Signature Scheme 564 XMSS is a method for signing a potentially large but fixed number of 565 messages. It is based on the Merkle signature scheme. XMSS uses 566 four cryptographic components: WOTS+ as OTS method, two additional 567 cryptographic hash functions H and H_m, and a pseudorandom function 568 PRF_m. One of the main advantages of XMSS with WOTS+ is that it does 569 not rely on the collision resistance of the used hash functions but 570 on weaker properties. Each XMSS public/private key pair is 571 associated with a perfect binary tree, every node of which contains 572 an n-byte value. Each tree leaf contains a special tree hash of a 573 WOTS+ public key value. Each non-leaf tree node is computed by first 574 concatenating the values of its child nodes, computing the XOR with a 575 bitmask, and applying the hash function H to the result. The value 576 corresponding to the root of the XMSS tree forms the XMSS public key 577 together with the bitmasks. 579 To generate a key pair that can be used to sign 2^h messages, a tree 580 of height h is used. XMSS is a stateful signature scheme, meaning 581 that the secret key changes after every signature. To prevent one- 582 time secret keys from being used twice, the WOTS+ key pairs are 583 numbered from 0 to (2^h)-1 according to the related leaf, starting 584 from index 0 for the leftmost leaf. The secret key contains an index 585 that is updated after every signature, such that it contains the 586 index of the next unused WOTS+ key pair. 588 A signature consists of the index of the used WOTS+ key pair, the 589 WOTS+ signature on the message and the so-called authentication path. 590 The latter is a vector of tree nodes that allow a verifier to compute 591 a value for the root of the tree. A verifier computes the root value 592 and compares it to the respective value in the XMSS public key. If 593 they match, the signature is valid. The XMSS secret key consists of 594 all WOTS+ secret keys and the actual index. To reduce storage, a 595 pseudorandom key generation procedure, as described in [BDH11], MAY 596 be used. The security of the used method MUST at least match the 597 security of the XMSS instance. 599 4.1.1. XMSS Parameters 601 XMSS has the following parameters: 603 h : the height (number of levels - 1) of the tree 605 n : the length in bytes of each node 607 m : the length of the message digest 609 w : the Winternitz parameter as defined for WOTS+ in Section 3.1 611 There are N = 2^h leaves in the tree. XMSS uses num_bm = max{2 * (h 612 + ceil(lg(l))), w - 2} bitmasks produced during key generation. 614 For XMSS and XMSS^MT, secret and public keys are denoted by SK and 615 PK. For WOTS+, secret and public keys are denoted by sk and pk, 616 respectively. XMSS and XMSS^MT signatures are denoted by Sig. WOTS+ 617 signatures are denoted by sig. 619 4.1.2. XMSS Hash Functions 621 Besides the cryptographic hash function F required by WOTS+, XMSS 622 uses three more functions: 624 A cryptographic hash function H. H accepts byte strings of length 625 (2 * n) and returns an n-byte string. 627 A cryptographic hash function H_m. H_m accepts byte strings of 628 arbitrary length and returns an m-byte string. 630 A pseudorandom function PRF_m. PRF_m accepts byte strings of 631 arbitrary length and an m-byte key and returns an m-byte string. 633 4.1.3. XMSS Private Key 635 An XMSS private key contains N = 2^h WOTS+ private keys, the leaf 636 index idx of the next WOTS+ private key that has not yet been used 637 and SK_PRF, an m-byte key for the PRF. The leaf index idx is 638 initialized to zero when the XMSS private key is created. The PRF 639 key SK_PRF MUST be sampled from a secure source of randomness that 640 follows the uniform distribution. The WOTS+ secret keys MUST be 641 generated as described in Section 3.1. To reduce the secret key 642 size, a cryptographic pseudorandom method MAY be used as discussed at 643 the end of this section. For the following algorithm descriptions, 644 the existence of a method getWOTS_SK(SK,i) is assumed. This method 645 takes as inputs an XMSS secret key SK and an integer i and outputs 646 the i^th WOTS+ secret key of SK. 648 4.1.4. L-Trees 650 To compute the leaves of the binary hash tree, a so-called L-tree is 651 used. An L-tree is an unbalanced binary hash tree, distinct but 652 similar to the main XMSS binary hash tree. The algorithm ltree 653 (Algorithm 7) takes as input a WOTS+ public key pk and compresses it 654 to a single n-byte value pk[0]. The algorithm uses the first (2 * 655 ceil( log(l) )) of the num_bm n-byte bitmasks bm. 657 Algorithm 7: ltree 658 unsigned int l' = l 659 unsigned int j = 0 660 while ( l' > 1 ) { 661 for ( i = 0; i < floor(l' / 2); i = i + 1 ) { 662 pk[i] = H((pk[2i] XOR bm[j]) || (pk[2i + 1] XOR bm[j + 1])) 663 } 664 if ( l' is equal to 1 % 2 ) { 665 pk[floor(l' / 2) + 1] = pk[l'] 666 } 667 l' = ceil(l' / 2) 668 j = j + 2 669 } 670 return pk[0] 672 4.1.5. TreeHash 674 For the computation of the internal n-byte nodes of a Merkle tree, 675 the subroutine treeHash (Algorithm 8) accepts an XMSS secret key SK, 676 an unsigned integer s (the start index), an unsigned integer h (the 677 target node height) and the bitmasks bm. The treeHash algorithm 678 returns the root node of a tree of height h with the leftmost leaf 679 being the hash of the WOTS+ pk with index s. The treeHash algorithm 680 uses a stack holding up to (h-1) n-byte strings, with the usual stack 681 functions push() and pop(). 683 Algorithm 8: treeHash 685 for ( i = 0; i < 2^h; i = i + 1 ) { 686 pk = WOTS_genPK (getWOTS_SK(SK, s+i), bm) 687 node = ltree(pk, bm) 688 while ( Top node on Stack has same height h' as node ) { 689 node = H((Stack.pop() XOR bm[2l + 2h']) || 690 (node XOR bm[2l + 2h' + 1])) 691 } 692 Stack.push(node) 693 } 694 return Stack.pop() 696 4.1.6. XMSS Public Key 698 The XMSS public key is computed as described in XMSS_genPK (Algorithm 699 9). The algorithm takes the num_bm n-byte bitmasks bm, the XMSS 700 secret key SK, and the tree height h. The XMSS public key PK 701 consists of the root of the binary hash tree and the bitmasks bm. 703 Algorithm 9: XMSS_genPK - Generate an XMSS public key from an XMSS 704 private key 705 for ( i = 0; i < num_bm; i = i + 1 ) { 706 set bm[i] to a uniformly random n-byte string 707 } 708 root = treeHash(SK, 0, h, bm) 709 PK = root || bm 710 return PK 712 Public and private key generation MAY be interleaved to save space. 713 Especially, when a pseudorandom method is used to generate the secret 714 key, generation MAY be done when the respective WOTS+ key pair is 715 needed by treeHash. 717 The format of an XMSS public key is given below. 719 XMSS Public Key 721 +---------------------------------+ 722 | algorithm OID | 723 +---------------------------------+ 724 | | 725 | root node | n bytes 726 | | 727 +---------------------------------+ 728 | | 729 | bm[0] | n bytes 730 | | 731 +---------------------------------+ 732 | | 733 ~ .... ~ 734 | | 735 +---------------------------------+ 736 | | 737 | bm[num_bm-1] | n bytes 738 | | 739 +---------------------------------+ 741 4.1.7. XMSS Signature 743 An XMSS signature is a (4 + m + (l + h) * n)-byte string consisting 744 of 746 the index idx_sig of the used WOTS+ key pair (4 bytes), 748 a byte string r used for randomized hashing (m bytes), 750 a WOTS+ signature sig_ots (l * n bytes), 751 the so called authentication path 'auth' for the leaf associated 752 with the used WOTS+ key pair (h * n bytes). 754 The authentication path is an array of h n-byte strings. It contains 755 the siblings of the nodes on the path from the used leaf to the root. 756 It does not contain the nodes on the path itself. These nodes are 757 needed by a verifier to compute a root node for the tree from the 758 WOTS+ public key. A node Node is addressed by its position in the 759 tree. Node(x,y) denotes the x^th node on level y with x = 0 being 760 the leftmost node on a level. The leaves are on level 0, the root is 761 on level h. An authentication path contains exactly one node on 762 every layer 0 <= x <= h-1. For the i^th WOTS+ key pair, counting 763 from zero, the j^th authentication path node is 765 Node(j, floor(i / (2^j)) + 1) if floor(i / (2^j)) is even or 767 Node(j, floor(i / (2^j)) - 1) if floor(i / (2^j)) is odd. 769 Given an XMSS secret key SK and bitmasks bm, all nodes in a tree are 770 determined. Their value is defined in terms of treeHash (Algorithm 771 8): 773 Node(x,y) = treeHash(SK, x * 2^y, y, bm). 775 The data format for a signature is given below. 777 XMSS Signature 778 +---------------------------------+ 779 | algorithm OID | 780 +---------------------------------+ 781 | | 782 | index idx_sig | 4 bytes 783 | | 784 +---------------------------------+ 785 | | 786 | randomness r | m bytes 787 | | 788 +---------------------------------+ 789 | | 790 | WOTS+ signature sig_ots | l * n bytes 791 | | 792 +---------------------------------+ 793 | | 794 | auth[0] | n bytes 795 | | 796 +---------------------------------+ 797 | | 798 ~ .... ~ 799 | | 800 +---------------------------------+ 801 | | 802 | auth[h-1] | n bytes 803 | | 804 +---------------------------------+ 806 4.1.8. XMSS Signature Generation 808 To compute the XMSS signature of a message M with an XMSS private 809 key, the signer first computes a randomized message digest. Then a 810 WOTS+ signature of the message is computed using the next unused 811 WOTS+ private key. Next, the authentication path is computed. 812 Finally, the secret key is updated, i.e. idx is incremented. An 813 implementation MUST NOT output the signature before the updated 814 private key. 816 The node values of the authentication path MAY be computed in any 817 way. This computation is assumed to be performed by the subroutine 818 buildAuth for the function XMSS_sign, as below. The fastest 819 alternative is to store all tree nodes and set the array in the 820 signature by copying them, respectively. The least storage-intensive 821 alternative is to recompute all nodes for each signature online. 822 There exist several algorithms in between, with different time/ 823 storage trade-offs. For an overview see [BDS09]. Note that the 824 details of this procedure are not relevant to interoperability; it is 825 not necessary to know any of these details in order to perform the 826 signature verification operation. As a consequence, buildAuth is not 827 specified here. 829 The algorithm XMSS_sign (Algorithm 10) described below calculates an 830 updated secret key SK and a signature on a message M. XMSS_sign 831 takes as inputs a message M of an arbitrary length, an XMSS secret 832 key SK and bitmasks bm. It returns the byte string containing the 833 concatenation of the updated secret key SK and the signature Sig. 835 Algorithm 10: XMSS_sign - Generate an XMSS signature and update the 836 XMSS secret key 838 idx_sig = getIdx(SK) 839 auth = buildAuth(SK, bm, idx_sig) 840 byte[m] r = PRF_m(getSK_PRF(SK), M) 841 byte[m] M' = H_m(r || M) 842 sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), M', bm) 843 Sig = (idx_sig || r || sig_ots || auth) 844 setIdx(SK, idx_sig + 1) 845 return (SK || Sig) 847 4.1.9. XMSS Signature Verification 849 An XMSS signature is verified by first computing the message digest 850 using randomness r and a message M. Then the used WOTS+ public key 851 pk_ots is computed from the WOTS+ signature using WOTS_pkFromSig. 852 The WOTS+ public key in turn is used to compute the corresponding 853 leaf using an L-tree. The leaf, together with index idx_sig, 854 authentication path auth and bitmasks bm is used to compute an 855 alternative root value for the tree. These first steps are done by 856 XMSS_rootFromSig (Algorithm 11). The verification succeeds if and 857 only if the computed root value matches the one in the XMSS public 858 key. In any other case it MUST return fail. 860 The main part of XMSS signature verification is done by the function 861 XMSS_rootFromSig (Algorithm 11) described below. XMSS_rootFromSig 862 takes as inputs an XMSS signature Sig, a message M, and the bitmasks 863 bm. XMSS_rootFromSig returns an n-byte string holding the value of 864 the root of a tree defined by the input data. 866 Algorithm 11: XMSS_rootFromSig - Compute a root node using an XMSS 867 signature, a message, and bitmasks bm 868 byte[m] M' = H_m(r || M) 869 pk_ots = WOTS_pkFromSig(sig_ots, M', bm) 870 byte[n][2] node 871 node[0] = ltree(pk_ots, bm) 872 for ( k = 1; k < h; k = k + 1 ) { 873 if ( floor(i / (2^k)) % 2 is equal to 0 ) { 874 node[1] = H((node[0] XOR bm[2l + 2k]) || 875 (auth[k - 1] XOR bm[2l + 2k + 1])) 876 } else { 877 node[1] = H((auth[k - 1] XOR bm[2l + 2k]) || 878 (node[0] XOR bm[2l + 2k + 1])) 879 } 880 node[0] = node[1] 881 } 882 return node[0] 884 The full XMSS signature verification is depicted below for 885 completeness. XMSS^MT uses only XMSS_rootFromSig and delegates the 886 comparison to a later comparison of data depending on its output. 888 Algorithm 12: XMSS_verify - Verify an XMSS signature using an XMSS 889 signature, the corresponding XMSS public key and a message 891 byte[n] node = XMSS_rootFromSig(Sig, M, getBM(PK)) 892 if ( node is equal to root in PK ) { 893 return true 894 } else { 895 return false 896 } 898 4.1.10. Pseudorandom Key Generation 900 An implementation MAY use a cryptographically secure pseudorandom 901 method to generate the XMSS secret key from a single n-byte value. 902 For example, the method suggested in [BDH11] and explained below MAY 903 be used. Other methods MAY be used. The choice of a pseudorandom 904 method does not affect interoperability, but the cryptographic 905 strength MUST match that of the used XMSS parameters. 907 For XMSS a similar method than the one used for WOTS+ can be used. 908 The suggested method from [BDH11] uses a pseudorandom function G(K,M) 909 that takes an n-byte key and an n-byte message. During key 910 generation a uniformly random n-byte string S is sampled from a 911 secure source of randomness. This seed S is used to generate an 912 n-byte value S_ots for each WOTS+ key pair. This n-byte value can 913 then be used to compute the respective WOTS+ secret key using the 914 method described in Section 3.1.7. The seeds for the WOTS+ key pairs 915 are computed as S_ots[i] = G(S,i). The second parameter of G is the 916 index i of the WOTS+ key pair, represented as n-byte string in the 917 common way. To implement G an implementation SHOULD use PRF_m, 918 taking the first n bytes from the output. An advantage of this 919 method is that a WOTS+ key can be computed using only l+1 evaluations 920 of G when S is given. 922 4.1.11. Free Index Handling and Partial Secret Keys 924 Some applications might require to work with partial secret keys or 925 copies of secret keys. Examples include delegation of signing rights 926 / proxy signatures, and load balancing. Such applications MAY use 927 their own key format and MAY use a signing algorithm different from 928 the one described above. The index in partial secret keys or copies 929 of a secret key MAY be manipulated as required by the applications. 930 However, applications MUST establish means that guarantee that each 931 index and thereby each WOTS+ key pair is used to sign only a single 932 message. 934 4.2. XMSS^MT: Multi-Tree XMSS 936 XMSS^MT is a method for signing a large but fixed number of messages. 937 It was first described in [HRB13]. It builds on XMSS. XMSS^MT uses 938 a tree of several layers of XMSS trees. The trees on top and 939 intermediate layers are used to sign the root nodes of the trees on 940 the respective layer below. Trees on the lowest layer are used to 941 sign the actual messages. All XMSS trees have equal height. 943 Consider an XMSS^MT tree of total height h that has d layers of XMSS 944 trees of height h / d. Then layer d - 1 contains one XMSS tree, 945 layer d - 2 contains 2^(h / d) XMSS trees, and so on. Finally, layer 946 0 contains 2^(h - h / d) XMSS trees. 948 4.2.1. XMSS^MT Parameters 950 In addition to all XMSS parameters, an XMSS^MT system requires the 951 number of tree layers d, specified as an integer value that divides h 952 without remainder. The same tree height h / d and the same 953 Winternitz parameter w are used for all tree layers. 955 All the trees on higher layers sign root nodes of other trees which 956 are n-byte strings. Hence, no message compression is needed and 957 WOTS+ is used to sign the root nodes themselves instead of their hash 958 values. Hence the WOTS+ message length for these layers is n not m. 959 Accordingly, the values of l_1, l_2 and l change for these layers. 960 The parameters l_1_n, l_2_n, and l_n denote the respective values 961 computed using n as message length for WOTS+. 963 4.2.2. XMSS Algorithms Without Message Hash 965 As all XMSS trees besides those on layer 0 are used to sign short 966 fixed length messages, the initial message hash can be omitted. In 967 the description below XMSS_sign_wo_hash and XMSS_rootFromSig_wo_hash 968 are versions of XMSS_sign and XMSS_rootFromSig, respectively, that 969 omit the initial message hash. They are obtained by setting M' = M 970 in the above algorithms. Accordingly, the evaluations of H_m and 971 PRF_m SHOULD be omitted. This also means that no randomization 972 element r for the message hash is required. XMSS signatures 973 generated by XMSS_sign_wo_hash and verified by 974 XMSS_rootFromSig_wo_hash MUST NOT contain a value r. 976 4.2.3. XMSS^MT Private Key 978 An XMSS^MT private key SK_MT consists of one reduced XMSS private key 979 for each XMSS tree. These reduced XMSS private keys contain no 980 pseudorandom function key and no index. Instead, SK_MT contains a 981 single m-byte pseudorandom function key SK_PRF and a single (ceil(h / 982 8))-byte index idx_MT. The index is a global index over all WOTS+ 983 key pairs of all XMSS trees on layer 0. It is initialized with 0. 984 It stores the index of the last used WOTS+ key pair on the bottom 985 layer, i.e. a number between 0 and 2^h - 1. 987 The algorithm descriptions below uses a function getXMSS_SK(SK, x, y) 988 that outputs the reduced secret key of the x^th XMSS tree on the y^th 989 layer. 991 4.2.4. XMSS^MT Public Key 993 The XMSS^MT public key PK_MT contains the root of the single XMSS 994 tree on layer d-1 and the bitmasks. The same bitmasks are used for 995 all XMSS tress. Algorithm 13 shows pseudocode to generate PK_MT. 996 First, num_bm = max{ 2 * (h / d + ceil(lg(l))), 2 * (h / d + 997 ceil(lg(l_n))), w - 2 } n-byte bitmasks bm are chosen uniformly at 998 random. The n-byte root node of the top layer tree is computed using 999 treeHash. The algorithm XMSSMT_genPK takes the XMSS^MT secret key 1000 SK_MT as an input and outputs an XMSS^MT public key PK_MT. 1002 Algorithm 13: XMSSMT_genPK - Generate an XMSS^MT public key from an 1003 XMSS^MT private key 1005 for ( i = 0; i < num_bm; i = i + 1 ) { 1006 set bm[i] to a uniformly random n-byte string 1007 } 1008 root = treeHash(getXMSS_SK(SK_MT, 0, d - 1), 0, h / d, bm) 1009 PK_MT = root || bm 1010 return PK_MT 1011 The format of an XMSS^MT public key is given below. 1013 XMSS^MT Public Key 1015 +---------------------------------+ 1016 | algorithm OID | 1017 +---------------------------------+ 1018 | | 1019 | root node | n bytes 1020 | | 1021 +---------------------------------+ 1022 | | 1023 | bm[0] | n bytes 1024 | | 1025 +---------------------------------+ 1026 | | 1027 ~ .... ~ 1028 | | 1029 +---------------------------------+ 1030 | | 1031 | bm[num_bm-1] | n bytes 1032 | | 1033 +---------------------------------+ 1035 4.2.5. XMSS^MT Signature 1037 An XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) + 1038 m + (h + l + (d - 1) * l_n) * n). It consists of 1040 the index idx_sig of the used WOTS+ key pair on the bottom layer 1041 (ceil(h / 8) bytes), 1043 a byte string r used for randomized hashing (m bytes), 1045 one reduced XMSS signature ((h + l) * n bytes), 1047 d-1 reduced XMSS signatures with message length n ((h + l_n) * n 1048 bytes). 1050 The reduced XMSS signatures contain no index idx and no byte string 1051 r. They only contain a WOTS+ signature sig_ots and an authentication 1052 path auth. The first reduced XMSS signature contains a WOTS+ 1053 signature that consists of l n-byte elements. The remaining reduced 1054 XMSS signatures contain a WOTS+ signature on an n-byte message and 1055 hence consist of l_n n-byte elements. 1057 The data format for a signature is given below. 1059 XMSS^MT signature 1061 +---------------------------------+ 1062 | algorithm OID | 1063 +---------------------------------+ 1064 | | 1065 | index idx_sig | ceil(h / 8) bytes 1066 | | 1067 +---------------------------------+ 1068 | | 1069 | randomness r | m bytes 1070 | | 1071 +---------------------------------+ 1072 | | 1073 | (reduced) XMSS signature Sig | (h + l) * n bytes 1074 | (bottom layer 0) | 1075 | | 1076 +---------------------------------+ 1077 | | 1078 | (reduced) XMSS signature Sig | (h + l_n) * n bytes 1079 | (layer 1) | 1080 | | 1081 +---------------------------------+ 1082 | | 1083 ~ .... ~ 1084 | | 1085 +---------------------------------+ 1086 | | 1087 | (reduced) XMSS signature Sig | (h + l_n) * n bytes 1088 | (layer d-1) | 1089 | | 1090 +---------------------------------+ 1092 4.2.6. XMSS^MT Signature Generation 1094 To compute the XMSS^MT signature Sig_MT of a message M using an 1095 XMSS^MT private key SK_MT and bitmasks bm, XMSSMT_sign (Algorithm 14) 1096 described below uses XMSS_sign and XMSS_sign_wo_hash as defined in 1097 Section 4.2.2. First, the signature index is set to idx. Next, 1098 PRF_m is used to compute a pseudorandom m-byte string r. This m-byte 1099 string is then used to compute a randomized message digest of length 1100 m. The message digest is signed using the WOTS+ key pair on the 1101 bottom layer with absolute index idx. The authentication path for 1102 the WOTS+ key pair is computed as well as the root of the containing 1103 XMSS tree. The root is signed by the parent XMSS tree. This is 1104 repeated until the top tree is reached. 1106 Algorithm 14: XMSSMT_sign - Generate an XMSS^MT signature and update 1107 the XMSS^MT secret key 1109 SK_PRF = getSK_PRF(SK_MT) 1110 idx_sig = getIdx(SK_MT) 1111 setIdx(SK_MT, idx_sig + 1) 1112 Sig_MT = idx_sig 1113 unsigned int idx_tree = (h - h / d) most significant bits of idx_sig 1114 unsigned int idx_leaf = (h / d) least significant bits of idx_sig 1115 SK = idx_leaf || SK_PRF || getXMSS_SK(SK_MT, idx_tree, 0) 1116 Sig_tmp = XMSS_sign(M, SK, bm) 1117 Sig_tmp = Sig_tmp without idx 1118 Sig_MT = Sig_MT || Sig_tmp 1119 for ( j = 1; j < d; j = j + 1 ) { 1120 root = treeHash(SK, 0, h / d, bm) 1121 idx_leaf = (h / d) least significant bits of idx_tree 1122 idx_tree = (h - j * (h / d)) most significant bytes of idx_tree 1123 SK = idx_leaf || SK_PRF || getXMSS_SK(SK_MT, idx_tree, j) 1124 Sig_tmp = XMSS_sign_wo_hash(root, SK, bm) with idx removed 1125 Sig_MT = Sig_MT || Sig_tmp 1126 } 1127 return SK_MT || Sig_MT 1129 Algorithm 14 is only one method to compute XMSS^MT signatures. 1130 Especially, there exist time-memory trade-offs that allow to reduce 1131 the signing time to less than the signing time of an XMSS scheme with 1132 tree height h / d. These trade-offs prevent certain values from being 1133 recomputed several times by keeping a state and distribute all 1134 computations over all signature generations. Details can be found in 1135 [Huelsing13a]. 1137 4.2.7. XMSS^MT Signature Verification 1139 XMSS^MT signature verification (Algorithm 15) can be summarized as d 1140 XMSS signature verifications with small changes. First, only the 1141 message is hashed. The remaining XMSS signatures are on the root 1142 nodes of trees which have a fixed length. Second, instead of 1143 comparing the computed root node to a given value, a signature on the 1144 root is verified. Only the root node of the top tree is compared to 1145 the value in the XMSS^MT public key. XMSSMT_verify uses 1146 XMSS_rootFromSig and XMSS_rootFromSig_wo_hash. XMSSMT_verify takes 1147 as inputs an XMSS^MT signature Sig^MT, a message M and a public key 1148 PK_MT. It outputs a boolean. 1150 Algorithm 15: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a 1151 message M using an XMSS^MT public key PK_MT 1152 idx = getIdx(Sig_MT) 1153 unsigned int idx_leaf = (h / d) least significant bits of idx 1154 unsigned int idx_tree = (h - h / d) most significant bits of idx 1155 Sig' = leaf || setR(Sig_MT) || getXMSSSignature(Sig, 0) 1156 byte[n] node = XMSS_rootFromSig(Sig', M, getBm(PK_MT)) 1157 for ( j = 1; j < d; j = j + 1 ) { 1158 idx_leaf = (h / d) least significant bytes of idx_tree 1159 idx_tree = (h - j * h / d) most significant bytes of idx_tree 1160 Sig' = idx_leaf || getXMSSSignature(Sig, j) 1161 node = XMSS_rootFromSig_wo_hash(Sig', node, getBm(PK_MT)) 1162 } 1163 if ( node is equal to getRoot(PK_MT) ) { 1164 return true 1165 } else { 1166 return false 1167 } 1169 4.2.8. Pseudorandom Key Generation 1171 Like for XMSS, an implementation MAY use a cryptographically secure 1172 pseudorandom method to generate the XMSS^MT secret key from a single 1173 n-byte value. For example, the method explained below MAY be used. 1174 Other methods MAY be used. The choice of a pseudorandom method does 1175 not affect interoperability, but the cryptographic strength MUST 1176 match that of the used XMSS parameters. 1178 For XMSS^MT a method similar to that for XMSS and WOTS+ can be used. 1179 The method uses a pseudorandom function G(K,M) that takes an n-byte 1180 key and an n-byte message. During key generation a uniformly random 1181 n-byte string S_MT is sampled from a secure source of randomness. 1182 This seed S_MT is used to generate one n-byte value S for each XMSS 1183 key pair. This n-byte value can be used to compute the respective 1184 XMSS secret key using the method described in Section 4.1.10. Let 1185 S[x][y] be the seed for the x^th XMSS secret key on layer y. The 1186 seeds are computed as S[x][y] = G(G(S, y), x). The second parameter 1187 of G is the index x (resp. level y), represented as n-byte string in 1188 the common way. To implement G an implementation SHOULD use PRF_m, 1189 taking the first n bytes from the output. 1191 4.2.9. Free Index Handling and Partial Secret Keys 1193 The content of Section 4.1.11 also applies to XMSS^MT. 1195 5. Parameter Sets 1197 This note provides a first basic set of parameter sets which are 1198 assumed to cover most relevant applicants. Parameter sets for three 1199 classical security levels are defined: 128, 256 and 512 bits. 1200 Function output sizes are n = 16, 32 and 64 bytes and m = 32, 64, 1201 respectively. While m = n is used for n = 32 and n = 64, m = 32 is 1202 used for the n = 16 case. Considering quantum-computer-aided 1203 attacks, these output sizes yield post-quantum security of 64, 128 1204 and 256 bits, respectively. The n = 16 parameter sets are included 1205 to encourage adoption in the pre-quantum era as they lead to smaller 1206 signatures and faster runtimes than other parameter sets. The n = 64 1207 parameter sets are provided to support post-quantum scenarios. 1209 For the n = 16 setting, this note only defines parameter sets with 1210 AES-based hash functions. The reason is that they benefit from 1211 hardware acceleration on many modern platforms. Let AES(K,M) denote 1212 evaluation of AES-128 with 128 bit key K and 128 bit message M. 1213 Define the 16-byte string IV = 0x0001020304050607080910111213141516. 1214 Then F and H are implemented as 1216 F(X) = AES(IV,X) XOR X 1218 H(X) = AES( AES(IV, X1) XOR X1, X2) XOR X2 1220 where X = X1 || X2, i.e. X1 denotes the most significant 16 bytes of 1221 X and X2 the least significant 16 bytes. For these parameter sets 1222 H_m is implemented as SHA3-256 and PRF_m as SHA3-256 in PRF/MAC mode. 1224 For the n = m = 32 and n = m = 64 settings, all functions are 1225 implemented using SHA3-256 and SHA3-512, respectively. 1227 5.1. Zero Bitmasks 1228 For applications that require a very small public key this note 1229 additionally defines zero bitmasks parameter sets. For these 1230 parameter sets the bitmasks are set to an all-zero string. The XMSS 1231 and XMSS^MT public keys for these parameter sets contain no bitmasks. 1232 Instead, they only contain the single n-byte value holding the root 1233 node. When handling zero bitmasks parameter sets, implementations 1234 MAY internally use an all-zero string as bitmasks and stick to the 1235 same algorithms as for the other parameter sets. Implementations MAY 1236 omit the XOR with an all-zero bitmask. Zero bitmasks parameter sets 1237 are only defined for n = 32 and n = 64, as formal security reductions 1238 require the used hash functions to be collision-resistant in this 1239 case. Hence, the estimated classical security levels are 128 and 256 1240 bits for n = 32 and n = 64 with zero bitmasks, respectively. The 1241 corresponding post-quantum security levels are approximately 85 and 1242 170 bits, respectively. 1244 5.2. WOTS+ Parameters 1246 To fully describe a WOTS+ signature method, the parameters m, n, and 1247 w, as well as the function F MUST be specified. This section defines 1248 several WOTS+ signature systems, each of which is identified by a 1249 name. Values for l are provided for convenience. 1251 +------------------------+--------+----+----+----+-----+ 1252 | Name | F | m | n | w | l | 1253 +------------------------+--------+----+----+----+-----+ 1254 | WOTSP_AES128_M32_W4 | AES128 | 32 | 16 | 4 | 133 | 1255 | | | | | | | 1256 | WOTSP_AES128_M32_W8 | AES128 | 32 | 16 | 8 | 90 | 1257 | | | | | | | 1258 | WOTSP_AES128_M32_W16 | AES128 | 32 | 16 | 16 | 67 | 1259 | | | | | | | 1260 | WOTSP_SHA3-256_M32_W4 | SHA3 | 32 | 32 | 4 | 133 | 1261 | | | | | | | 1262 | WOTSP_SHA3-256_M32_W8 | SHA3 | 32 | 32 | 8 | 90 | 1263 | | | | | | | 1264 | WOTSP_SHA3-256_M32_W16 | SHA3 | 32 | 32 | 16 | 67 | 1265 | | | | | | | 1266 | WOTSP_SHA3-512_M64_W4 | SHA3 | 64 | 64 | 4 | 261 | 1267 | | | | | | | 1268 | WOTSP_SHA3-512_M64_W8 | SHA3 | 64 | 64 | 8 | 175 | 1269 | | | | | | | 1270 | WOTSP_SHA3-512_M64_W16 | SHA3 | 64 | 64 | 16 | 131 | 1271 +------------------------+--------+----+----+----+-----+ 1273 Table 1 1275 Here SHA3 denotes the NIST standard hash function, also known as 1276 Keccak [DRAFTFIPS202]. XDR formats for WOTS+ are listed in 1277 Appendix A. 1279 5.3. XMSS Parameters 1281 To fully describe an XMSS signature method, the parameters m, n, w, 1282 and h, as well as the functions F, H, H_m and PRF_m MUST be 1283 specified. This section defines several XMSS signature systems, each 1284 of which is identified by a name. 1286 The XDR formats for XMSS are listed in Appendix B. 1288 5.3.1. XMSS Parameters 1290 We first define XMSS signature methods as described in Section 4.1. 1291 We define parameter sets that implement the functions using AES and 1292 SHA3 as described above as well as pure SHA3 parameter sets. 1294 5.3.1.1. XMSS Parameters with AES and SHA3 1296 The following XMSS signature methods implement the functions F, H, 1297 H_m and PRF_m using AES and SHA3 as described above. 1299 +--------------------------+----+----+----+-----+----+ 1300 | Name | m | n | w | l | h | 1301 +--------------------------+----+----+----+-----+----+ 1302 | XMSS_AES128_M32_W4_H10 | 32 | 16 | 4 | 133 | 10 | 1303 | | | | | | | 1304 | XMSS_AES128_M32_W4_H16 | 32 | 16 | 4 | 133 | 16 | 1305 | | | | | | | 1306 | XMSS_AES128_M32_W4_H20 | 32 | 16 | 4 | 133 | 20 | 1307 | | | | | | | 1308 | XMSS_AES128_M32_W8_H10 | 32 | 16 | 8 | 90 | 10 | 1309 | | | | | | | 1310 | XMSS_AES128_M32_W8_H16 | 32 | 16 | 8 | 90 | 16 | 1311 | | | | | | | 1312 | XMSS_AES128_M32_W8_H20 | 32 | 16 | 8 | 90 | 20 | 1313 | | | | | | | 1314 | XMSS_AES128_M32_W16_H10 | 32 | 16 | 16 | 67 | 10 | 1315 | | | | | | | 1316 | XMSS_AES128_M32_W16_H16 | 32 | 16 | 16 | 67 | 16 | 1317 | | | | | | | 1318 | XMSS_AES128_M32_W16_H20 | 32 | 16 | 16 | 67 | 20 | 1319 +--------------------------+----+----+----+-----+----+ 1321 Table 2 1323 5.3.1.2. XMSS Parameters with SHA3 1325 The following XMSS signature methods implement the functions F, H, 1326 H_m and PRF_m solely using SHA3 as described above. 1328 +----------------------------+----+----+----+-----+----+ 1329 | Name | m | n | w | l | h | 1330 +----------------------------+----+----+----+-----+----+ 1331 | XMSS_SHA3-256_M32_W4_H10 | 32 | 32 | 4 | 133 | 10 | 1332 | | | | | | | 1333 | XMSS_SHA3-256_M32_W4_H16 | 32 | 32 | 4 | 133 | 16 | 1334 | | | | | | | 1335 | XMSS_SHA3-256_M32_W4_H20 | 32 | 32 | 4 | 133 | 20 | 1336 | | | | | | | 1337 | XMSS_SHA3-256_M32_W8_H10 | 32 | 32 | 8 | 90 | 10 | 1338 | | | | | | | 1339 | XMSS_SHA3-256_M32_W8_H16 | 32 | 32 | 8 | 90 | 16 | 1340 | | | | | | | 1341 | XMSS_SHA3-256_M32_W8_H20 | 32 | 32 | 8 | 90 | 20 | 1342 | | | | | | | 1343 | XMSS_SHA3-256_M32_W16_H10 | 32 | 32 | 16 | 67 | 10 | 1344 | | | | | | | 1345 | XMSS_SHA3-256_M32_W16_H16 | 32 | 32 | 16 | 67 | 16 | 1346 | | | | | | | 1347 | XMSS_SHA3-256_M32_W16_H20 | 32 | 32 | 16 | 67 | 20 | 1348 | | | | | | | 1349 | XMSS_SHA3-512_M64_W4_H10 | 64 | 64 | 4 | 261 | 10 | 1350 | | | | | | | 1351 | XMSS_SHA3-512_M64_W4_H16 | 64 | 64 | 4 | 261 | 16 | 1352 | | | | | | | 1353 | XMSS_SHA3-512_M64_W4_H20 | 64 | 64 | 4 | 261 | 20 | 1354 | | | | | | | 1355 | XMSS_SHA3-512_M64_W8_H10 | 64 | 64 | 8 | 175 | 10 | 1356 | | | | | | | 1357 | XMSS_SHA3-512_M64_W8_H16 | 64 | 64 | 8 | 175 | 16 | 1358 | | | | | | | 1359 | XMSS_SHA3-512_M64_W8_H20 | 64 | 64 | 8 | 175 | 20 | 1360 | | | | | | | 1361 | XMSS_SHA3-512_M64_W16_H10 | 64 | 64 | 16 | 131 | 10 | 1362 | | | | | | | 1363 | XMSS_SHA3-512_M64_W16_H16 | 64 | 64 | 16 | 131 | 16 | 1364 | | | | | | | 1365 | XMSS_SHA3-512_M64_W16_H20 | 64 | 64 | 16 | 131 | 20 | 1366 +----------------------------+----+----+----+-----+----+ 1368 Table 3 1370 5.3.2. XMSS Parameters With Empty Bitmasks 1372 We now define XMSS signature methods for the zero bitmasks special 1373 case described in Section 5.1. For this setting all signature 1374 methods implement the functions F, H, H_m and PRF_m solely using SHA3 1375 as described above. 1377 +------------------------------+----+----+----+-----+----+ 1378 | Name | m | n | w | l | h | 1379 +------------------------------+----+----+----+-----+----+ 1380 | XMSS_SHA3-256_M32_W4_H10_z | 32 | 32 | 4 | 133 | 10 | 1381 | | | | | | | 1382 | XMSS_SHA3-256_M32_W4_H16_z | 32 | 32 | 4 | 133 | 16 | 1383 | | | | | | | 1384 | XMSS_SHA3-256_M32_W4_H20_z | 32 | 32 | 4 | 133 | 20 | 1385 | | | | | | | 1386 | XMSS_SHA3-256_M32_W8_H10_z | 32 | 32 | 8 | 90 | 10 | 1387 | | | | | | | 1388 | XMSS_SHA3-256_M32_W8_H16_z | 32 | 32 | 8 | 90 | 16 | 1389 | | | | | | | 1390 | XMSS_SHA3-256_M32_W8_H20_z | 32 | 32 | 8 | 90 | 20 | 1391 | | | | | | | 1392 | XMSS_SHA3-256_M32_W16_H10_z | 32 | 32 | 16 | 67 | 10 | 1393 | | | | | | | 1394 | XMSS_SHA3-256_M32_W16_H16_z | 32 | 32 | 16 | 67 | 16 | 1395 | | | | | | | 1396 | XMSS_SHA3-256_M32_W16_H20_z | 32 | 32 | 16 | 67 | 20 | 1397 | | | | | | | 1398 | XMSS_SHA3-512_M64_W4_H10_z | 64 | 64 | 4 | 261 | 10 | 1399 | | | | | | | 1400 | XMSS_SHA3-512_M64_W4_H16_z | 64 | 64 | 4 | 261 | 16 | 1401 | | | | | | | 1402 | XMSS_SHA3-512_M64_W4_H20_z | 64 | 64 | 4 | 261 | 20 | 1403 | | | | | | | 1404 | XMSS_SHA3-512_M64_W8_H10_z | 64 | 64 | 8 | 175 | 10 | 1405 | | | | | | | 1406 | XMSS_SHA3-512_M64_W8_H16_z | 64 | 64 | 8 | 175 | 16 | 1407 | | | | | | | 1408 | XMSS_SHA3-512_M64_W8_H20_z | 64 | 64 | 8 | 175 | 20 | 1409 | | | | | | | 1410 | XMSS_SHA3-512_M64_W16_H10_z | 64 | 64 | 16 | 131 | 10 | 1411 | | | | | | | 1412 | XMSS_SHA3-512_M64_W16_H16_z | 64 | 64 | 16 | 131 | 16 | 1413 | | | | | | | 1414 | XMSS_SHA3-512_M64_W16_H20_z | 64 | 64 | 16 | 131 | 20 | 1415 +------------------------------+----+----+----+-----+----+ 1417 Table 4 1419 5.4. XMSS^MT Parameters 1421 To fully describe an XMSS^MT signature method, the parameters m, n, 1422 w, h, and d, as well as the functions F, H, H_m and PRF_m MUST be 1423 specified. This section defines several XMSS^MT signature systems, 1424 each of which is identified by a name. 1426 XDR formats for XMSS^MT are listed in Appendix C. 1428 5.4.1. XMSS^MT Parameters 1430 We first define XMSS^MT signature methods as described in 1431 Section 4.2. We define parameter sets that implement the functions 1432 using AES and SHA3 as described above as well as pure SHA3 parameter 1433 sets. 1435 5.4.1.1. XMSS^MT Parameters with AES and SHA3 1437 The following XMSS^MT signature methods implement the functions F, H, 1438 H_m and PRF_m using AES and SHA3 as described above. 1440 +-------------------------------+----+----+----+-----+----+----+ 1441 | Name | m | n | w | l | h | d | 1442 +-------------------------------+----+----+----+-----+----+----+ 1443 | XMSSMT_AES128_M32_W4_H20_D2 | 32 | 16 | 4 | 133 | 20 | 2 | 1444 | | | | | | | | 1445 | XMSSMT_AES128_M32_W4_H20_D4 | 32 | 16 | 4 | 133 | 20 | 4 | 1446 | | | | | | | | 1447 | XMSSMT_AES128_M32_W4_H40_D2 | 32 | 16 | 4 | 133 | 40 | 2 | 1448 | | | | | | | | 1449 | XMSSMT_AES128_M32_W4_H40_D4 | 32 | 16 | 4 | 133 | 40 | 4 | 1450 | | | | | | | | 1451 | XMSSMT_AES128_M32_W4_H40_D8 | 32 | 16 | 4 | 133 | 40 | 8 | 1452 | | | | | | | | 1453 | XMSSMT_AES128_M32_W4_H60_D3 | 32 | 16 | 4 | 133 | 60 | 3 | 1454 | | | | | | | | 1455 | XMSSMT_AES128_M32_W4_H60_D6 | 32 | 16 | 4 | 133 | 60 | 6 | 1456 | | | | | | | | 1457 | XMSSMT_AES128_M32_W4_H60_D12 | 32 | 16 | 4 | 133 | 60 | 12 | 1458 | | | | | | | | 1459 | XMSSMT_AES128_M32_W8_H20_D2 | 32 | 16 | 8 | 90 | 20 | 2 | 1460 | | | | | | | | 1461 | XMSSMT_AES128_M32_W8_H20_D4 | 32 | 16 | 8 | 90 | 20 | 4 | 1462 | | | | | | | | 1463 | XMSSMT_AES128_M32_W8_H40_D2 | 32 | 16 | 8 | 90 | 40 | 2 | 1464 | | | | | | | | 1465 | XMSSMT_AES128_M32_W8_H40_D4 | 32 | 16 | 8 | 90 | 40 | 4 | 1466 | | | | | | | | 1467 | XMSSMT_AES128_M32_W8_H40_D8 | 32 | 16 | 8 | 90 | 40 | 8 | 1468 | | | | | | | | 1469 | XMSSMT_AES128_M32_W8_H60_D3 | 32 | 16 | 8 | 90 | 60 | 3 | 1470 | | | | | | | | 1471 | XMSSMT_AES128_M32_W8_H60_D6 | 32 | 16 | 8 | 90 | 60 | 6 | 1472 | | | | | | | | 1473 | XMSSMT_AES128_M32_W8_H60_D12 | 32 | 16 | 8 | 90 | 60 | 12 | 1474 | | | | | | | | 1475 | XMSSMT_AES128_M32_W16_H20_D2 | 32 | 16 | 16 | 67 | 20 | 2 | 1476 | | | | | | | | 1477 | XMSSMT_AES128_M32_W16_H20_D4 | 32 | 16 | 16 | 67 | 20 | 4 | 1478 | | | | | | | | 1479 | XMSSMT_AES128_M32_W16_H40_D2 | 32 | 16 | 16 | 67 | 40 | 2 | 1480 | | | | | | | | 1481 | XMSSMT_AES128_M32_W16_H40_D4 | 32 | 16 | 16 | 67 | 40 | 4 | 1482 | | | | | | | | 1483 | XMSSMT_AES128_M32_W16_H40_D8 | 32 | 16 | 16 | 67 | 40 | 8 | 1484 | | | | | | | | 1485 | XMSSMT_AES128_M32_W16_H60_D3 | 32 | 16 | 16 | 67 | 60 | 3 | 1486 | | | | | | | | 1487 | XMSSMT_AES128_M32_W16_H60_D6 | 32 | 16 | 16 | 67 | 60 | 6 | 1488 | | | | | | | | 1489 | XMSSMT_AES128_M32_W16_H60_D12 | 32 | 16 | 16 | 67 | 60 | 12 | 1490 +-------------------------------+----+----+----+-----+----+----+ 1492 Table 5 1494 5.4.1.2. XMSS^MT Parameters with SHA3 1496 The following XMSS^MT signature methods implement the functions F, H, 1497 H_m and PRF_m solely using SHA3 as described above. 1499 +----------------------------------+----+----+----+-----+----+----+ 1500 | Name | m | n | w | l | h | d | 1501 +----------------------------------+----+----+----+-----+----+----+ 1502 | XMSSMT_SHA3-256_M32_W4_H20_D2 | 32 | 32 | 4 | 133 | 20 | 2 | 1503 | | | | | | | | 1504 | XMSSMT_SHA3-256_M32_W4_H20_D4 | 32 | 32 | 4 | 133 | 20 | 4 | 1505 | | | | | | | | 1506 | XMSSMT_SHA3-256_M32_W4_H40_D2 | 32 | 32 | 4 | 133 | 40 | 2 | 1507 | | | | | | | | 1508 | XMSSMT_SHA3-256_M32_W4_H40_D4 | 32 | 32 | 4 | 133 | 40 | 4 | 1509 | | | | | | | | 1510 | XMSSMT_SHA3-256_M32_W4_H40_D8 | 32 | 32 | 4 | 133 | 40 | 8 | 1511 | | | | | | | | 1512 | XMSSMT_SHA3-256_M32_W4_H60_D3 | 32 | 32 | 4 | 133 | 60 | 3 | 1513 | | | | | | | | 1514 | XMSSMT_SHA3-256_M32_W4_H60_D6 | 32 | 32 | 4 | 133 | 60 | 6 | 1515 | | | | | | | | 1516 | XMSSMT_SHA3-256_M32_W4_H60_D12 | 32 | 32 | 4 | 133 | 60 | 12 | 1517 | | | | | | | | 1518 | XMSSMT_SHA3-256_M32_W8_H20_D2 | 32 | 32 | 8 | 90 | 20 | 2 | 1519 | | | | | | | | 1520 | XMSSMT_SHA3-256_M32_W8_H20_D4 | 32 | 32 | 8 | 90 | 20 | 4 | 1521 | | | | | | | | 1522 | XMSSMT_SHA3-256_M32_W8_H40_D2 | 32 | 32 | 8 | 90 | 40 | 2 | 1523 | | | | | | | | 1524 | XMSSMT_SHA3-256_M32_W8_H40_D4 | 32 | 32 | 8 | 90 | 40 | 4 | 1525 | | | | | | | | 1526 | XMSSMT_SHA3-256_M32_W8_H40_D8 | 32 | 32 | 8 | 90 | 40 | 8 | 1527 | | | | | | | | 1528 | XMSSMT_SHA3-256_M32_W8_H60_D3 | 32 | 32 | 8 | 90 | 60 | 3 | 1529 | | | | | | | | 1530 | XMSSMT_SHA3-256_M32_W8_H60_D6 | 32 | 32 | 8 | 90 | 60 | 6 | 1531 | | | | | | | | 1532 | XMSSMT_SHA3-256_M32_W8_H60_D12 | 32 | 32 | 8 | 90 | 60 | 12 | 1533 | | | | | | | | 1534 | XMSSMT_SHA3-256_M32_W16_H20_D2 | 32 | 32 | 16 | 67 | 20 | 2 | 1535 | | | | | | | | 1536 | XMSSMT_SHA3-256_M32_W16_H20_D4 | 32 | 32 | 16 | 67 | 20 | 4 | 1537 | | | | | | | | 1538 | XMSSMT_SHA3-256_M32_W16_H40_D2 | 32 | 32 | 16 | 67 | 40 | 2 | 1539 | | | | | | | | 1540 | XMSSMT_SHA3-256_M32_W16_H40_D4 | 32 | 32 | 16 | 67 | 40 | 4 | 1541 | | | | | | | | 1542 | XMSSMT_SHA3-256_M32_W16_H40_D8 | 32 | 32 | 16 | 67 | 40 | 8 | 1543 | | | | | | | | 1544 | XMSSMT_SHA3-256_M32_W16_H60_D3 | 32 | 32 | 16 | 67 | 60 | 3 | 1545 | | | | | | | | 1546 | XMSSMT_SHA3-256_M32_W16_H60_D6 | 32 | 32 | 16 | 67 | 60 | 6 | 1547 | | | | | | | | 1548 | XMSSMT_SHA3-256_M32_W16_H60_D12 | 32 | 32 | 16 | 67 | 60 | 12 | 1549 | | | | | | | | 1550 | XMSSMT_SHA3-512_M64_W4_H20_D2 | 64 | 64 | 4 | 261 | 20 | 2 | 1551 | | | | | | | | 1552 | XMSSMT_SHA3-512_M64_W4_H20_D4 | 64 | 64 | 4 | 261 | 20 | 4 | 1553 | | | | | | | | 1554 | XMSSMT_SHA3-512_M64_W4_H40_D2 | 64 | 64 | 4 | 261 | 40 | 2 | 1555 | | | | | | | | 1556 | XMSSMT_SHA3-512_M64_W4_H40_D4 | 64 | 64 | 4 | 261 | 40 | 4 | 1557 | | | | | | | | 1558 | XMSSMT_SHA3-512_M64_W4_H40_D8 | 64 | 64 | 4 | 261 | 40 | 8 | 1559 | | | | | | | | 1560 | XMSSMT_SHA3-512_M64_W4_H60_D3 | 64 | 64 | 4 | 261 | 60 | 3 | 1561 | | | | | | | | 1562 | XMSSMT_SHA3-512_M64_W4_H60_D6 | 64 | 64 | 4 | 261 | 60 | 6 | 1563 | | | | | | | | 1564 | XMSSMT_SHA3-512_M64_W4_H60_D12 | 64 | 64 | 4 | 261 | 60 | 12 | 1565 | | | | | | | | 1566 | XMSSMT_SHA3-512_M64_W8_H20_D2 | 64 | 64 | 8 | 175 | 20 | 2 | 1567 | | | | | | | | 1568 | XMSSMT_SHA3-512_M64_W8_H20_D4 | 64 | 64 | 8 | 175 | 20 | 4 | 1569 | | | | | | | | 1570 | XMSSMT_SHA3-512_M64_W8_H40_D2 | 64 | 64 | 8 | 175 | 40 | 2 | 1571 | | | | | | | | 1572 | XMSSMT_SHA3-512_M64_W8_H40_D4 | 64 | 64 | 8 | 175 | 40 | 4 | 1573 | | | | | | | | 1574 | XMSSMT_SHA3-512_M64_W8_H40_D8 | 64 | 64 | 8 | 175 | 40 | 8 | 1575 | | | | | | | | 1576 | XMSSMT_SHA3-512_M64_W8_H60_D3 | 64 | 64 | 8 | 175 | 60 | 3 | 1577 | | | | | | | | 1578 | XMSSMT_SHA3-512_M64_W8_H60_D6 | 64 | 64 | 8 | 175 | 60 | 6 | 1579 | | | | | | | | 1580 | XMSSMT_SHA3-512_M64_W8_H60_D12 | 64 | 64 | 8 | 175 | 60 | 12 | 1581 | | | | | | | | 1582 | XMSSMT_SHA3-512_M64_W16_H20_D2 | 64 | 64 | 16 | 131 | 20 | 2 | 1583 | | | | | | | | 1584 | XMSSMT_SHA3-512_M64_W16_H20_D4 | 64 | 64 | 16 | 131 | 20 | 4 | 1585 | | | | | | | | 1586 | XMSSMT_SHA3-512_M64_W16_H40_D2 | 64 | 64 | 16 | 131 | 40 | 2 | 1587 | | | | | | | | 1588 | XMSSMT_SHA3-512_M64_W16_H40_D4 | 64 | 64 | 16 | 131 | 40 | 4 | 1589 | | | | | | | | 1590 | XMSSMT_SHA3-512_M64_W16_H40_D8 | 64 | 64 | 16 | 131 | 40 | 8 | 1591 | | | | | | | | 1592 | XMSSMT_SHA3-512_M64_W16_H60_D3 | 64 | 64 | 16 | 131 | 60 | 3 | 1593 | | | | | | | | 1594 | XMSSMT_SHA3-512_M64_W16_H60_D6 | 64 | 64 | 16 | 131 | 60 | 6 | 1595 | | | | | | | | 1596 | XMSSMT_SHA3-512_M64_W16_H60_D12 | 64 | 64 | 16 | 131 | 60 | 12 | 1597 +----------------------------------+----+----+----+-----+----+----+ 1599 Table 6 1601 5.4.2. XMSS^MT Parameters With Empty Bitmasks 1603 We now define XMSS^MT signature methods for the zero bitmasks special 1604 case described in Section 5.1. For this setting all signature 1605 methods implement the functions F, H, H_m and PRF_m solely using SHA3 1606 as described above. 1608 +-----------------------------------+----+----+----+-----+----+----+ 1609 | Name | m | n | w | l | h | d | 1610 +-----------------------------------+----+----+----+-----+----+----+ 1611 | XMSSMT_SHA3-256_M32_W4_H20_D2_z | 32 | 32 | 4 | 133 | 20 | 2 | 1612 | | | | | | | | 1613 | XMSSMT_SHA3-256_M32_W4_H20_D4_z | 32 | 32 | 4 | 133 | 20 | 4 | 1614 | | | | | | | | 1615 | XMSSMT_SHA3-256_M32_W4_H40_D2_z | 32 | 32 | 4 | 133 | 40 | 2 | 1616 | | | | | | | | 1617 | XMSSMT_SHA3-256_M32_W4_H40_D4_z | 32 | 32 | 4 | 133 | 40 | 4 | 1618 | | | | | | | | 1619 | XMSSMT_SHA3-256_M32_W4_H40_D8_z | 32 | 32 | 4 | 133 | 40 | 8 | 1620 | | | | | | | | 1621 | XMSSMT_SHA3-256_M32_W4_H60_D3_z | 32 | 32 | 4 | 133 | 60 | 3 | 1622 | | | | | | | | 1623 | XMSSMT_SHA3-256_M32_W4_H60_D6_z | 32 | 32 | 4 | 133 | 60 | 6 | 1624 | | | | | | | | 1625 | XMSSMT_SHA3-256_M32_W4_H60_D12_z | 32 | 32 | 4 | 133 | 60 | 12 | 1626 | | | | | | | | 1627 | XMSSMT_SHA3-256_M32_W8_H20_D2_z | 32 | 32 | 8 | 90 | 20 | 2 | 1628 | | | | | | | | 1629 | XMSSMT_SHA3-256_M32_W8_H20_D4_z | 32 | 32 | 8 | 90 | 20 | 4 | 1630 | | | | | | | | 1631 | XMSSMT_SHA3-256_M32_W8_H40_D2_z | 32 | 32 | 8 | 90 | 40 | 2 | 1632 | | | | | | | | 1633 | XMSSMT_SHA3-256_M32_W8_H40_D4_z | 32 | 32 | 8 | 90 | 40 | 4 | 1634 | | | | | | | | 1635 | XMSSMT_SHA3-256_M32_W8_H40_D8_z | 32 | 32 | 8 | 90 | 40 | 8 | 1636 | | | | | | | | 1637 | XMSSMT_SHA3-256_M32_W8_H60_D3_z | 32 | 32 | 8 | 90 | 60 | 3 | 1638 | | | | | | | | 1639 | XMSSMT_SHA3-256_M32_W8_H60_D6_z | 32 | 32 | 8 | 90 | 60 | 6 | 1640 | | | | | | | | 1641 | XMSSMT_SHA3-256_M32_W8_H60_D12_z | 32 | 32 | 16 | 67 | 60 | 12 | 1642 | | | | | | | | 1643 | XMSSMT_SHA3-256_M32_W16_H20_D2_z | 32 | 32 | 16 | 67 | 20 | 2 | 1644 | | | | | | | | 1645 | XMSSMT_SHA3-256_M32_W16_H20_D4_z | 32 | 32 | 16 | 67 | 20 | 4 | 1646 | | | | | | | | 1647 | XMSSMT_SHA3-256_M32_W16_H40_D2_z | 32 | 32 | 16 | 67 | 40 | 2 | 1648 | | | | | | | | 1649 | XMSSMT_SHA3-256_M32_W16_H40_D4_z | 32 | 32 | 16 | 67 | 40 | 4 | 1650 | | | | | | | | 1651 | XMSSMT_SHA3-256_M32_W16_H40_D8_z | 32 | 32 | 16 | 67 | 40 | 8 | 1652 | | | | | | | | 1653 | XMSSMT_SHA3-256_M32_W16_H60_D3_z | 32 | 32 | 16 | 67 | 60 | 3 | 1654 | | | | | | | | 1655 | XMSSMT_SHA3-256_M32_W16_H60_D6_z | 32 | 32 | 16 | 67 | 60 | 6 | 1656 | | | | | | | | 1657 | XMSSMT_SHA3-256_M32_W16_H60_D12_z | 32 | 32 | 16 | 67 | 60 | 12 | 1658 | | | | | | | | 1659 | XMSSMT_SHA3-512_M64_W4_H20_D2_z | 64 | 64 | 4 | 261 | 20 | 2 | 1660 | | | | | | | | 1661 | XMSSMT_SHA3-512_M64_W4_H20_D4_z | 64 | 64 | 4 | 261 | 20 | 4 | 1662 | | | | | | | | 1663 | XMSSMT_SHA3-512_M64_W4_H40_D2_z | 64 | 64 | 4 | 261 | 40 | 2 | 1664 | | | | | | | | 1665 | XMSSMT_SHA3-512_M64_W4_H40_D4_z | 64 | 64 | 4 | 261 | 40 | 4 | 1666 | | | | | | | | 1667 | XMSSMT_SHA3-512_M64_W4_H40_D8_z | 64 | 64 | 4 | 261 | 40 | 8 | 1668 | | | | | | | | 1669 | XMSSMT_SHA3-512_M64_W4_H60_D3_z | 64 | 64 | 4 | 261 | 60 | 3 | 1670 | | | | | | | | 1671 | XMSSMT_SHA3-512_M64_W4_H60_D6_z | 64 | 64 | 4 | 261 | 60 | 6 | 1672 | | | | | | | | 1673 | XMSSMT_SHA3-512_M64_W4_H60_D12_z | 64 | 64 | 4 | 261 | 60 | 12 | 1674 | | | | | | | | 1675 | XMSSMT_SHA3-512_M64_W8_H20_D2_z | 64 | 64 | 8 | 175 | 20 | 2 | 1676 | | | | | | | | 1677 | XMSSMT_SHA3-512_M64_W8_H20_D4_z | 64 | 64 | 8 | 175 | 20 | 4 | 1678 | | | | | | | | 1679 | XMSSMT_SHA3-512_M64_W8_H40_D2_z | 64 | 64 | 8 | 175 | 40 | 2 | 1680 | | | | | | | | 1681 | XMSSMT_SHA3-512_M64_W8_H40_D4_z | 64 | 64 | 8 | 175 | 40 | 4 | 1682 | | | | | | | | 1683 | XMSSMT_SHA3-512_M64_W8_H40_D8_z | 64 | 64 | 8 | 175 | 40 | 8 | 1684 | | | | | | | | 1685 | XMSSMT_SHA3-512_M64_W8_H60_D3_z | 64 | 64 | 8 | 175 | 60 | 3 | 1686 | | | | | | | | 1687 | XMSSMT_SHA3-512_M64_W8_H60_D6_z | 64 | 64 | 8 | 175 | 60 | 6 | 1688 | | | | | | | | 1689 | XMSSMT_SHA3-512_M64_W8_H60_D12_z | 64 | 64 | 8 | 175 | 60 | 12 | 1690 | | | | | | | | 1691 | XMSSMT_SHA3-512_M64_W16_H20_D2_z | 64 | 64 | 16 | 131 | 20 | 2 | 1692 | | | | | | | | 1693 | XMSSMT_SHA3-512_M64_W16_H20_D4_z | 64 | 64 | 16 | 131 | 20 | 4 | 1694 | | | | | | | | 1695 | XMSSMT_SHA3-512_M64_W16_H40_D2_z | 64 | 64 | 16 | 131 | 40 | 2 | 1696 | | | | | | | | 1697 | XMSSMT_SHA3-512_M64_W16_H40_D4_z | 64 | 64 | 16 | 131 | 40 | 4 | 1698 | | | | | | | | 1699 | XMSSMT_SHA3-512_M64_W16_H40_D8_z | 64 | 64 | 16 | 131 | 40 | 8 | 1700 | | | | | | | | 1701 | XMSSMT_SHA3-512_M64_W16_H60_D3_z | 64 | 64 | 16 | 131 | 60 | 3 | 1702 | | | | | | | | 1703 | XMSSMT_SHA3-512_M64_W16_H60_D6_z | 64 | 64 | 16 | 131 | 60 | 6 | 1704 | | | | | | | | 1705 | XMSSMT_SHA3-512_M64_W16_H60_D12_z | 64 | 64 | 16 | 131 | 60 | 12 | 1706 +-----------------------------------+----+----+----+-----+----+----+ 1707 Table 7 1709 6. Rationale 1711 The goal of this note is to describe the WOTS+, XMSS and XMSS^MT 1712 algorithms following the scientific literature. Other signature 1713 methods are out of scope and may be an interesting follow-on work. 1714 The description is done in a modular way that allows to base a 1715 description of stateless hash-based signature algorithms like SPHINCS 1716 [BHH15] on it. 1718 The parameter w is constrained to powers of 2 to support simpler and 1719 more efficient implementations. Furthermore, w is restricted to the 1720 set {4, 8, 16}. No bigger values are included since the decrease in 1721 signature size then becomes less significant. The value w = 2 was 1722 not included since w = 4 leads to similar runtimes but a halved 1723 signature size. This is the case because while chains get twice as 1724 long, thereby increasing runtime, the number of chains is roughly 1725 halved. For instance, assuming m = n = 32, one obtains l = 38 for w 1726 = 2 and l = 19 for w = 4. 1728 The signature and public key formats are designed so that they are 1729 easy to parse. Each format starts with a 32-bit enumeration value 1730 that indicates all of the details of the signature algorithm and 1731 hence defines all of the information that is needed in order to parse 1732 the format. 1734 The enumeration values used in this note are palindromes, which have 1735 the same byte representation in either host order or network order. 1736 This fact allows an implementation to omit the conversion between 1737 byte order for those enumerations. Note however that the idx field 1738 used in XMSS and XMSS^MT signatures and secret keys must be properly 1739 converted to and from network byte order; this is the only field that 1740 requires such conversion. There are 2^32 XDR enumeration values, 1741 2^16 of which are palindromes, which is adequate for the foreseeable 1742 future. If there is a need for more assignments, non-palindromes can 1743 be assigned. 1745 7. IANA Considerations 1747 The Internet Assigned Numbers Authority (IANA) is requested to create 1748 three registries: one for WOTS+ signatures as defined in Section 3, 1749 one for XMSS signatures and one for XMSS^MT signatures; the latter 1750 two being defined in Section 4. For the sake of clarity and 1751 convenience, the first sets of WOTS+, XMSS, and XMSS^MT parameter 1752 sets are defined in Section 5. Additions to these registries require 1753 that a specification be documented in an RFC or another permanent and 1754 readily available reference in sufficient details to make 1755 interoperability between independent implementations possible. Each 1756 entry in the registry contains the following elements: 1758 a short name, such as "XMSS_SHA3-512_M64_W16_H20", 1760 a positive number, and 1762 a reference to a specification that completely defines the 1763 signature method test cases that can be used to verify the 1764 correctness of an implementation. 1766 Requests to add an entry to the registry MUST include the name and 1767 the reference. The number is assigned by IANA. These number 1768 assignments SHOULD use the smallest available palindromic number. 1769 Submitters SHOULD have their requests reviewed by the IRTF Crypto 1770 Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants 1771 that are unfamiliar with IANA processes should visit http:// 1772 www.iana.org. 1774 The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF 1775 (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and 1776 are reserved for private use; no attempt will be made to prevent 1777 multiple sites from using the same value in different (and 1778 incompatible) ways [RFC2434]. 1780 The WOTS+ registry is as follows. 1782 +-------------------------+-------------+--------------------+ 1783 | Name | Reference | Numeric Identifier | 1784 +-------------------------+-------------+--------------------+ 1785 | WOTSP_AES128_M32_W4 | Section 5.2 | 0x01000001 | 1786 | | | | 1787 | WOTSP_AES128_M32_W8 | Section 5.2 | 0x02000002 | 1788 | | | | 1789 | WOTSP_AES128_M32_W16 | Section 5.2 | 0x03000003 | 1790 | | | | 1791 | WOTSP_SHA3-256_M32_W4 | Section 5.2 | 0x04000004 | 1792 | | | | 1793 | WOTSP_SHA3-256_M32_W8 | Section 5.2 | 0x05000005 | 1794 | | | | 1795 | WOTSP_SHA3-256_M32_W16 | Section 5.2 | 0x06000006 | 1796 | | | | 1797 | WOTSP_SHA3-512_M64_W4 | Section 5.2 | 0x07000007 | 1798 | | | | 1799 | WOTSP_SHA3-512_M64_W8 | Section 5.2 | 0x08000008 | 1800 | | | | 1801 | WOTSP_SHA3-512_M64_W16 | Section 5.2 | 0x09000009 | 1802 +-------------------------+-------------+--------------------+ 1803 Table 8 1805 The XMSS registry is as follows. 1807 +------------------------------+-------------+--------------------+ 1808 | Name | Reference | Numeric Identifier | 1809 +------------------------------+-------------+--------------------+ 1810 | XMSS_SHA3-256_M32_W4_H10_Z | Section 5.3 | 0x01000001 | 1811 | | | | 1812 | XMSS_SHA3-256_M32_W4_H16_Z | Section 5.3 | 0x02000002 | 1813 | | | | 1814 | XMSS_SHA3-256_M32_W4_H20_Z | Section 5.3 | 0x03000003 | 1815 | | | | 1816 | XMSS_SHA3-256_M32_W8_H10_Z | Section 5.3 | 0x04000004 | 1817 | | | | 1818 | XMSS_SHA3-256_M32_W8_H16_Z | Section 5.3 | 0x05000005 | 1819 | | | | 1820 | XMSS_SHA3-256_M32_W8_H20_Z | Section 5.3 | 0x06000006 | 1821 | | | | 1822 | XMSS_SHA3-256_M32_W16_H10_Z | Section 5.3 | 0x07000007 | 1823 | | | | 1824 | XMSS_SHA3-256_M32_W16_H16_Z | Section 5.3 | 0x08000008 | 1825 | | | | 1826 | XMSS_SHA3-256_M32_W16_H20_Z | Section 5.3 | 0x09000009 | 1827 | | | | 1828 | XMSS_SHA3-512_M64_W4_H10_Z | Section 5.3 | 0x0a00000a | 1829 | | | | 1830 | XMSS_SHA3-512_M64_W4_H16_Z | Section 5.3 | 0x0b00000b | 1831 | | | | 1832 | XMSS_SHA3-512_M64_W4_H20_Z | Section 5.3 | 0x0c00000c | 1833 | | | | 1834 | XMSS_SHA3-512_M64_W8_H10_Z | Section 5.3 | 0x0d00000d | 1835 | | | | 1836 | XMSS_SHA3-512_M64_W8_H16_Z | Section 5.3 | 0x0e00000e | 1837 | | | | 1838 | XMSS_SHA3-512_M64_W8_H20_Z | Section 5.3 | 0x0f00000f | 1839 | | | | 1840 | XMSS_SHA3-512_M64_W16_H10_Z | Section 5.3 | 0x01010101 | 1841 | | | | 1842 | XMSS_SHA3-512_M64_W16_H16_Z | Section 5.3 | 0x02010102 | 1843 | | | | 1844 | XMSS_SHA3-512_M64_W16_H20_Z | Section 5.3 | 0x03010103 | 1845 | | | | 1846 | XMSS_AES128_M32_W4_H10 | Section 5.3 | 0x04010104 | 1847 | | | | 1848 | XMSS_AES128_M32_W4_H16 | Section 5.3 | 0x05010105 | 1849 | | | | 1850 | XMSS_AES128_M32_W4_H20 | Section 5.3 | 0x06010106 | 1851 | | | | 1852 | XMSS_AES128_M32_W8_H10 | Section 5.3 | 0x07010107 | 1853 | | | | 1854 | XMSS_AES128_M32_W8_H16 | Section 5.3 | 0x08010108 | 1855 | | | | 1856 | XMSS_AES128_M32_W8_H20 | Section 5.3 | 0x09010109 | 1857 | | | | 1858 | XMSS_AES128_M32_W16_H10 | Section 5.3 | 0x0a01010a | 1859 | | | | 1860 | XMSS_AES128_M32_W16_H16 | Section 5.3 | 0x0b01010b | 1861 | | | | 1862 | XMSS_AES128_M32_W16_H20 | Section 5.3 | 0x0c01010c | 1863 | | | | 1864 | XMSS_SHA3-256_M32_W4_H10 | Section 5.3 | 0x0d01010d | 1865 | | | | 1866 | XMSS_SHA3-256_M32_W4_H16 | Section 5.3 | 0x0e01010e | 1867 | | | | 1868 | XMSS_SHA3-256_M32_W4_H20 | Section 5.3 | 0x0f01010f | 1869 | | | | 1870 | XMSS_SHA3-256_M32_W8_H10 | Section 5.3 | 0x01020201 | 1871 | | | | 1872 | XMSS_SHA3-256_M32_W8_H16 | Section 5.3 | 0x02020202 | 1873 | | | | 1874 | XMSS_SHA3-256_M32_W8_H20 | Section 5.3 | 0x03020203 | 1875 | | | | 1876 | XMSS_SHA3-256_M32_W16_H10 | Section 5.3 | 0x04020204 | 1877 | | | | 1878 | XMSS_SHA3-256_M32_W16_H16 | Section 5.3 | 0x05020205 | 1879 | | | | 1880 | XMSS_SHA3-256_M32_W16_H20 | Section 5.3 | 0x06020206 | 1881 | | | | 1882 | XMSS_SHA3-512_M64_W4_H10 | Section 5.3 | 0x07020207 | 1883 | | | | 1884 | XMSS_SHA3-512_M64_W4_H16 | Section 5.3 | 0x08020208 | 1885 | | | | 1886 | XMSS_SHA3-512_M64_W4_H20 | Section 5.3 | 0x09020209 | 1887 | | | | 1888 | XMSS_SHA3-512_M64_W8_H10 | Section 5.3 | 0x0a02020a | 1889 | | | | 1890 | XMSS_SHA3-512_M64_W8_H16 | Section 5.3 | 0x0b02020b | 1891 | | | | 1892 | XMSS_SHA3-512_M64_W8_H20 | Section 5.3 | 0x0c02020c | 1893 | | | | 1894 | XMSS_SHA3-512_M64_W16_H10 | Section 5.3 | 0x0d02020d | 1895 | | | | 1896 | XMSS_SHA3-512_M64_W16_H16 | Section 5.3 | 0x0e02020e | 1897 | | | | 1898 | XMSS_SHA3-512_M64_W16_H20 | Section 5.3 | 0x0f02020f | 1899 +------------------------------+-------------+--------------------+ 1901 Table 9 1903 The XMSS^MT registry is as follows. 1905 +---------------------------------------+------------+--------------+ 1906 | Name | Reference | Numeric | 1907 | | | Identifier | 1908 +---------------------------------------+------------+--------------+ 1909 | XMSSMT_SHA3-256_M32_W4_H20_D2_Z | Section | 0x01000001 | 1910 | | 5.4 | | 1911 | | | | 1912 | XMSSMT_SHA3-256_M32_W4_H20_D4_Z | Section | 0x02000002 | 1913 | | 5.4 | | 1914 | | | | 1915 | XMSSMT_SHA3-256_M32_W4_H40_D2_Z | Section | 0x03000003 | 1916 | | 5.4 | | 1917 | | | | 1918 | XMSSMT_SHA3-256_M32_W4_H40_D4_Z | Section | 0x04000004 | 1919 | | 5.4 | | 1920 | | | | 1921 | XMSSMT_SHA3-256_M32_W4_H40_D8_Z | Section | 0x05000005 | 1922 | | 5.4 | | 1923 | | | | 1924 | XMSSMT_SHA3-256_M32_W4_H60_D3_Z | Section | 0x06000006 | 1925 | | 5.4 | | 1926 | | | | 1927 | XMSSMT_SHA3-256_M32_W4_H60_D6_Z | Section | 0x07000007 | 1928 | | 5.4 | | 1929 | | | | 1930 | XMSSMT_SHA3-256_M32_W4_H60_D12_Z | Section | 0x08000008 | 1931 | | 5.4 | | 1932 | | | | 1933 | XMSSMT_SHA3-256_M32_W8_H20_D2_Z | Section | 0x09000009 | 1934 | | 5.4 | | 1935 | | | | 1936 | XMSSMT_SHA3-256_M32_W8_H20_D4_Z | Section | 0x0a00000a | 1937 | | 5.4 | | 1938 | | | | 1939 | XMSSMT_SHA3-256_M32_W8_H40_D2_Z | Section | 0x0b00000b | 1940 | | 5.4 | | 1941 | | | | 1942 | XMSSMT_SHA3-256_M32_W8_H40_D4_Z | Section | 0x0c00000c | 1943 | | 5.4 | | 1944 | | | | 1945 | XMSSMT_SHA3-256_M32_W8_H40_D8_Z | Section | 0x0d00000d | 1946 | | 5.4 | | 1947 | | | | 1948 | XMSSMT_SHA3-256_M32_W8_H60_D3_Z | Section | 0x0e00000e | 1949 | | 5.4 | | 1950 | | | | 1951 | XMSSMT_SHA3-256_M32_W8_H60_D6_Z | Section | 0x0f00000f | 1952 | | 5.4 | | 1953 | | | | 1954 | XMSSMT_SHA3-256_M32_W8_H60_D12_Z | Section | 0x00010100 | 1955 | | 5.4 | | 1956 | | | | 1957 | XMSSMT_SHA3-256_M32_W16_H20_D2_Z | Section | 0x01010101 | 1958 | | 5.4 | | 1959 | | | | 1960 | XMSSMT_SHA3-256_M32_W16_H20_D4_Z | Section | 0x02010102 | 1961 | | 5.4 | | 1962 | | | | 1963 | XMSSMT_SHA3-256_M32_W16_H40_D2_Z | Section | 0x03010103 | 1964 | | 5.4 | | 1965 | | | | 1966 | XMSSMT_SHA3-256_M32_W16_H40_D4_Z | Section | 0x04010104 | 1967 | | 5.4 | | 1968 | | | | 1969 | XMSSMT_SHA3-256_M32_W16_H40_D8_Z | Section | 0x05010105 | 1970 | | 5.4 | | 1971 | | | | 1972 | XMSSMT_SHA3-256_M32_W16_H60_D3_Z | Section | 0x06010106 | 1973 | | 5.4 | | 1974 | | | | 1975 | XMSSMT_SHA3-256_M32_W16_H60_D6_Z | Section | 0x07010107 | 1976 | | 5.4 | | 1977 | | | | 1978 | XMSSMT_SHA3-256_M32_W16_H60_D12_Z | Section | 0x08010108 | 1979 | | 5.4 | | 1980 | | | | 1981 | XMSSMT_SHA3-512_M64_W4_H20_D2_Z | Section | 0x09010109 | 1982 | | 5.4 | | 1983 | | | | 1984 | XMSSMT_SHA3-512_M64_W4_H20_D4_Z | Section | 0x0a01010a | 1985 | | 5.4 | | 1986 | | | | 1987 | XMSSMT_SHA3-512_M64_W4_H40_D2_Z | Section | 0x0b01010b | 1988 | | 5.4 | | 1989 | | | | 1990 | XMSSMT_SHA3-512_M64_W4_H40_D4_Z | Section | 0x0c01010c | 1991 | | 5.4 | | 1992 | | | | 1993 | XMSSMT_SHA3-512_M64_W4_H40_D8_Z | Section | 0x0d01010d | 1994 | | 5.4 | | 1995 | | | | 1996 | XMSSMT_SHA3-512_M64_W4_H60_D3_Z | Section | 0x0e01010e | 1997 | | 5.4 | | 1998 | | | | 1999 | XMSSMT_SHA3-512_M64_W4_H60_D6_Z | Section | 0x0f01010f | 2000 | | 5.4 | | 2001 | | | | 2002 | XMSSMT_SHA3-512_M64_W4_H60_D12_Z | Section | 0x00020200 | 2003 | | 5.4 | | 2004 | | | | 2005 | XMSSMT_SHA3-512_M64_W8_H20_D2_Z | Section | 0x01020201 | 2006 | | 5.4 | | 2007 | | | | 2008 | XMSSMT_SHA3-512_M64_W8_H20_D4_Z | Section | 0x02020202 | 2009 | | 5.4 | | 2010 | | | | 2011 | XMSSMT_SHA3-512_M64_W8_H40_D2_Z | Section | 0x03020203 | 2012 | | 5.4 | | 2013 | | | | 2014 | XMSSMT_SHA3-512_M64_W8_H40_D4_Z | Section | 0x04020204 | 2015 | | 5.4 | | 2016 | | | | 2017 | XMSSMT_SHA3-512_M64_W8_H40_D8_Z | Section | 0x05020205 | 2018 | | 5.4 | | 2019 | | | | 2020 | XMSSMT_SHA3-512_M64_W8_H60_D3_Z | Section | 0x06020206 | 2021 | | 5.4 | | 2022 | | | | 2023 | XMSSMT_SHA3-512_M64_W8_H60_D6_Z | Section | 0x07020207 | 2024 | | 5.4 | | 2025 | | | | 2026 | XMSSMT_SHA3-512_M64_W8_H60_D12_Z | Section | 0x08020208 | 2027 | | 5.4 | | 2028 | | | | 2029 | XMSSMT_SHA3-512_M64_W16_H20_D2_Z | Section | 0x09020209 | 2030 | | 5.4 | | 2031 | | | | 2032 | XMSSMT_SHA3-512_M64_W16_H20_D4_Z | Section | 0x0a02020a | 2033 | | 5.4 | | 2034 | | | | 2035 | XMSSMT_SHA3-512_M64_W16_H40_D2_Z | Section | 0x0b02020b | 2036 | | 5.4 | | 2037 | | | | 2038 | XMSSMT_SHA3-512_M64_W16_H40_D4_Z | Section | 0x0c02020c | 2039 | | 5.4 | | 2040 | | | | 2041 | XMSSMT_SHA3-512_M64_W16_H40_D8_Z | Section | 0x0d02020d | 2042 | | 5.4 | | 2043 | | | | 2044 | XMSSMT_SHA3-512_M64_W16_H60_D3_Z | Section | 0x0e02020e | 2045 | | 5.4 | | 2046 | | | | 2047 | XMSSMT_SHA3-512_M64_W16_H60_D6_Z | Section | 0x0f02020f | 2048 | | 5.4 | | 2049 | | | | 2050 | XMSSMT_SHA3-512_M64_W16_H60_D12_Z | Section | 0x00030300 | 2051 | | 5.4 | | 2052 | | | | 2053 | XMSSMT_AES128_M32_W4_H20_D2 | Section | 0x01030301 | 2054 | | 5.4 | | 2055 | | | | 2056 | XMSSMT_AES128_M32_W4_H20_D4 | Section | 0x02030302 | 2057 | | 5.4 | | 2058 | | | | 2059 | XMSSMT_AES128_M32_W4_H40_D2 | Section | 0x03030303 | 2060 | | 5.4 | | 2061 | | | | 2062 | XMSSMT_AES128_M32_W4_H40_D4 | Section | 0x04030304 | 2063 | | 5.4 | | 2064 | | | | 2065 | XMSSMT_AES128_M32_W4_H40_D8 | Section | 0x05030305 | 2066 | | 5.4 | | 2067 | | | | 2068 | XMSSMT_AES128_M32_W4_H60_D3 | Section | 0x06030306 | 2069 | | 5.4 | | 2070 | | | | 2071 | XMSSMT_AES128_M32_W4_H60_D6 | Section | 0x07030307 | 2072 | | 5.4 | | 2073 | | | | 2074 | XMSSMT_AES128_M32_W4_H60_D12 | Section | 0x08030308 | 2075 | | 5.4 | | 2076 | | | | 2077 | XMSSMT_AES128_M32_W8_H20_D2 | Section | 0x09030309 | 2078 | | 5.4 | | 2079 | | | | 2080 | XMSSMT_AES128_M32_W8_H20_D4 | Section | 0x0a03030a | 2081 | | 5.4 | | 2082 | | | | 2083 | XMSSMT_AES128_M32_W8_H40_D2 | Section | 0x0b03030b | 2084 | | 5.4 | | 2085 | | | | 2086 | XMSSMT_AES128_M32_W8_H40_D4 | Section | 0x0c03030c | 2087 | | 5.4 | | 2088 | | | | 2089 | XMSSMT_AES128_M32_W8_H40_D8 | Section | 0x0d03030d | 2090 | | 5.4 | | 2091 | | | | 2092 | XMSSMT_AES128_M32_W8_H60_D3 | Section | 0x0e03030e | 2093 | | 5.4 | | 2094 | | | | 2095 | XMSSMT_AES128_M32_W8_H60_D6 | Section | 0x0f03030f | 2096 | | 5.4 | | 2097 | | | | 2098 | XMSSMT_AES128_M32_W8_H60_D12 | Section | 0x00040400 | 2099 | | 5.4 | | 2100 | | | | 2101 | XMSSMT_AES128_M32_W16_H20_D2 | Section | 0x01040401 | 2102 | | 5.4 | | 2103 | | | | 2104 | XMSSMT_AES128_M32_W16_H20_D4 | Section | 0x02040402 | 2105 | | 5.4 | | 2106 | | | | 2107 | XMSSMT_AES128_M32_W16_H40_D2 | Section | 0x03040403 | 2108 | | 5.4 | | 2109 | | | | 2110 | XMSSMT_AES128_M32_W16_H40_D4 | Section | 0x04040404 | 2111 | | 5.4 | | 2112 | | | | 2113 | XMSSMT_AES128_M32_W16_H40_D8 | Section | 0x05040405 | 2114 | | 5.4 | | 2115 | | | | 2116 | XMSSMT_AES128_M32_W16_H60_D3 | Section | 0x06040406 | 2117 | | 5.4 | | 2118 | | | | 2119 | XMSSMT_AES128_M32_W16_H60_D6 | Section | 0x07040407 | 2120 | | 5.4 | | 2121 | | | | 2122 | XMSSMT_AES128_M32_W16_H60_D12 | Section | 0x08040408 | 2123 | | 5.4 | | 2124 | | | | 2125 | XMSSMT_SHA3-256_M32_W4_H20_D2 | Section | 0x09040409 | 2126 | | 5.4 | | 2127 | | | | 2128 | XMSSMT_SHA3-256_M32_W4_H20_D4 | Section | 0x0a04040a | 2129 | | 5.4 | | 2130 | | | | 2131 | XMSSMT_SHA3-256_M32_W4_H40_D2 | Section | 0x0b04040b | 2132 | | 5.4 | | 2133 | | | | 2134 | XMSSMT_SHA3-256_M32_W4_H40_D4 | Section | 0x0c04040c | 2135 | | 5.4 | | 2136 | | | | 2137 | XMSSMT_SHA3-256_M32_W4_H40_D8 | Section | 0x0d04040d | 2138 | | 5.4 | | 2139 | | | | 2140 | XMSSMT_SHA3-256_M32_W4_H60_D3 | Section | 0x0e04040e | 2141 | | 5.4 | | 2142 | | | | 2143 | XMSSMT_SHA3-256_M32_W4_H60_D6 | Section | 0x0f04040f | 2144 | | 5.4 | | 2145 | | | | 2146 | XMSSMT_SHA3-256_M32_W4_H60_D12 | Section | 0x00050500 | 2147 | | 5.4 | | 2148 | | | | 2149 | XMSSMT_SHA3-256_M32_W8_H20_D2 | Section | 0x01050501 | 2150 | | 5.4 | | 2151 | | | | 2152 | XMSSMT_SHA3-256_M32_W8_H20_D4 | Section | 0x02050502 | 2153 | | 5.4 | | 2154 | | | | 2155 | XMSSMT_SHA3-256_M32_W8_H40_D2 | Section | 0x03050503 | 2156 | | 5.4 | | 2157 | | | | 2158 | XMSSMT_SHA3-256_M32_W8_H40_D4 | Section | 0x04050504 | 2159 | | 5.4 | | 2160 | | | | 2161 | XMSSMT_SHA3-256_M32_W8_H40_D8 | Section | 0x05050505 | 2162 | | 5.4 | | 2163 | | | | 2164 | XMSSMT_SHA3-256_M32_W8_H60_D3 | Section | 0x06050506 | 2165 | | 5.4 | | 2166 | | | | 2167 | XMSSMT_SHA3-256_M32_W8_H60_D6 | Section | 0x07050507 | 2168 | | 5.4 | | 2169 | | | | 2170 | XMSSMT_SHA3-256_M32_W8_H60_D12 | Section | 0x08050508 | 2171 | | 5.4 | | 2172 | | | | 2173 | XMSSMT_SHA3-256_M32_W16_H20_D2 | Section | 0x09050509 | 2174 | | 5.4 | | 2175 | | | | 2176 | XMSSMT_SHA3-256_M32_W16_H20_D4 | Section | 0x0a05050a | 2177 | | 5.4 | | 2178 | | | | 2179 | XMSSMT_SHA3-256_M32_W16_H40_D2 | Section | 0x0b05050b | 2180 | | 5.4 | | 2181 | | | | 2182 | XMSSMT_SHA3-256_M32_W16_H40_D4 | Section | 0x0c05050c | 2183 | | 5.4 | | 2184 | | | | 2185 | XMSSMT_SHA3-256_M32_W16_H40_D8 | Section | 0x0d05050d | 2186 | | 5.4 | | 2187 | | | | 2188 | XMSSMT_SHA3-256_M32_W16_H60_D3 | Section | 0x0e05050e | 2189 | | 5.4 | | 2190 | | | | 2191 | XMSSMT_SHA3-256_M32_W16_H60_D6 | Section | 0x0f05050f | 2192 | | 5.4 | | 2193 | | | | 2194 | XMSSMT_SHA3-256_M32_W16_H60_D12 | Section | 0x00060600 | 2195 | | 5.4 | | 2196 | | | | 2197 | XMSSMT_SHA3-512_M64_W4_H20_D2 | Section | 0x01060601 | 2198 | | 5.4 | | 2199 | | | | 2200 | XMSSMT_SHA3-512_M64_W4_H20_D4 | Section | 0x02060602 | 2201 | | 5.4 | | 2202 | | | | 2203 | XMSSMT_SHA3-512_M64_W4_H40_D2 | Section | 0x03060603 | 2204 | | 5.4 | | 2205 | | | | 2206 | XMSSMT_SHA3-512_M64_W4_H40_D4 | Section | 0x04060604 | 2207 | | 5.4 | | 2208 | | | | 2209 | XMSSMT_SHA3-512_M64_W4_H40_D8 | Section | 0x05060605 | 2210 | | 5.4 | | 2211 | | | | 2212 | XMSSMT_SHA3-512_M64_W4_H60_D3 | Section | 0x06060606 | 2213 | | 5.4 | | 2214 | | | | 2215 | XMSSMT_SHA3-512_M64_W4_H60_D6 | Section | 0x07060607 | 2216 | | 5.4 | | 2217 | | | | 2218 | XMSSMT_SHA3-512_M64_W4_H60_D12 | Section | 0x08060608 | 2219 | | 5.4 | | 2220 | | | | 2221 | XMSSMT_SHA3-512_M64_W8_H20_D2 | Section | 0x09060609 | 2222 | | 5.4 | | 2223 | | | | 2224 | XMSSMT_SHA3-512_M64_W8_H20_D4 | Section | 0x0a06060a | 2225 | | 5.4 | | 2226 | | | | 2227 | XMSSMT_SHA3-512_M64_W8_H40_D2 | Section | 0x0b06060b | 2228 | | 5.4 | | 2229 | | | | 2230 | XMSSMT_SHA3-512_M64_W8_H40_D4 | Section | 0x0c06060c | 2231 | | 5.4 | | 2232 | | | | 2233 | XMSSMT_SHA3-512_M64_W8_H40_D8 | Section | 0x0d06060d | 2234 | | 5.4 | | 2235 | | | | 2236 | XMSSMT_SHA3-512_M64_W8_H60_D3 | Section | 0x0e06060e | 2237 | | 5.4 | | 2238 | | | | 2239 | XMSSMT_SHA3-512_M64_W8_H60_D6 | Section | 0x0f06060f | 2240 | | 5.4 | | 2241 | | | | 2242 | XMSSMT_SHA3-512_M64_W8_H60_D12 | Section | 0x00070700 | 2243 | | 5.4 | | 2244 | | | | 2245 | XMSSMT_SHA3-512_M64_W16_H20_D2 | Section | 0x01070701 | 2246 | | 5.4 | | 2247 | | | | 2248 | XMSSMT_SHA3-512_M64_W16_H20_D4 | Section | 0x02070702 | 2249 | | 5.4 | | 2250 | | | | 2251 | XMSSMT_SHA3-512_M64_W16_H40_D2 | Section | 0x03070703 | 2252 | | 5.4 | | 2253 | | | | 2254 | XMSSMT_SHA3-512_M64_W16_H40_D4 | Section | 0x04070704 | 2255 | | 5.4 | | 2256 | | | | 2257 | XMSSMT_SHA3-512_M64_W16_H40_D8 | Section | 0x05070705 | 2258 | | 5.4 | | 2259 | | | | 2260 | XMSSMT_SHA3-512_M64_W16_H60_D3 | Section | 0x06070706 | 2261 | | 5.4 | | 2262 | | | | 2263 | XMSSMT_SHA3-512_M64_W16_H60_D6 | Section | 0x07070707 | 2264 | | 5.4 | | 2265 | | | | 2266 | XMSSMT_SHA3-512_M64_W16_H60_D12 | Section | 0x08070708 | 2267 | | 5.4 | | 2268 +---------------------------------------+------------+--------------+ 2270 Table 10 2272 An IANA registration of a signature system does not constitute an 2273 endorsement of that system or its security. 2275 8. Security Considerations 2276 A signature system is considered secure if it prevents an attacker 2277 from forging a valid signature. More specifically, consider a 2278 setting in which an attacker gets a public key and can learn 2279 signatures on arbitrary messages of his choice. A signature system 2280 is secure if, even in this setting, the attacker can not produce a 2281 message signature pair of his choosing such that the verification 2282 algorithm accepts. 2284 Preventing an attacker from mounting an attack means that the attack 2285 is computationally too expensive to be carried out. There exist 2286 various estimates when a computation is too expensive to be done. 2287 For that reason, this note only describes how expensive it is for an 2288 attacker to generate a forgery. Parameters are accompanied by a bit 2289 security value. The meaning of bit security is as follows. A 2290 parameter set grants b bits of security if the best attack takes at 2291 least 2^(b-1) bit operations to achieve a success probability of 1/2. 2292 Hence, to mount a successful attack, an attacker needs to perform 2^b 2293 bit operations on average. How the given values for bit security 2294 were estimated is described below. 2296 8.1. Security Proofs 2298 There exist formal security proofs for the schemes described here in 2299 the literature [Huelsing13a]. These proofs show that an attacker has 2300 to break at least one out of certain security properties of the used 2301 hash functions and PRFs to forge a signature. The proofs in 2302 [Huelsing13a] do not consider the initial message compression. For 2303 the scheme without initial message compression, these proofs show 2304 that an attacker has to break certain minimal security properties. 2305 In particular, it is not sufficient to break the collision resistance 2306 of the hash functions to generate a forgery. 2308 It is a folklore that one can securely combine a secure signature 2309 scheme for fixed length messages with an initial message digest. It 2310 is easy to proof that an attacker either must break the security of 2311 the fixed-input-length signature scheme or the collision resistance 2312 of the used hash function. XMSS and XMSS^MT use a known trick to 2313 prevent the applicability of collision attacks. Namely, the schemes 2314 use a randomized message hash. For technical reasons, it is not 2315 possible to formally prove that the resulting scheme is secure if the 2316 hash function is not collision-resistant but fulfills some weaker 2317 security properties. 2319 The given bit security values were estimated based on the complexity 2320 of the best known generic attacks against the required security 2321 properties of the used hash functions and PRFs. 2323 8.2. Security Assumptions 2325 The security assumptions made to argue for the security of the 2326 described schemes are minimal. Any signature algorithm that allows 2327 arbitrary size messages relies on the security of a cryptographic 2328 hash function. For the schemes described here this is already 2329 sufficient to be secure. In contrast, common signature schemes like 2330 RSA, DSA, and ECDSA additionally rely on the conjectured hardness of 2331 certain mathematical problems. 2333 8.3. Post-Quantum Security 2335 A post-quantum cryptosystem is a system that is secure against 2336 attackers with access to a reasonably sized quantum computer. At the 2337 time of writing this note, whether or not it is feasible to build 2338 such machine is an open conjecture. However, significant progress 2339 was made over the last few years in this regard. 2341 In contrast to RSA, DSA, and ECDSA, the described signature systems 2342 are post-quantum-secure if they are used with an appropriate 2343 cryptographic hash function. In particular, for post-quantum 2344 security, the size of m and n must be twice the size required for 2345 classical security. This is in order to protect against quantum 2346 square root attacks due to Grover's algorithm. It has been shown 2347 that Grover's algorithm is optimal for finding preimages and 2348 collisions. 2350 9. Acknowledgements 2352 We would like to thank Burt Kaliski, and David McGrew for their help. 2354 10. References 2356 10.1. Normative References 2358 [DRAFTFIPS202] 2359 National Institute of Standards and Technology, "SHA-3 2360 Standard: Permutation-Based Hash and Extendable-Output 2361 Functions", Draft FIPS 202, 2014. 2363 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2364 Requirement Levels", BCP 14, RFC 2119, March 1997. 2366 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 2367 IANA Considerations Section in RFCs", BCP 26, RFC 2434, 2368 October 1998. 2370 [RFC4506] Eisler, M., "XDR: External Data Representation Standard", 2371 STD 67, RFC 4506, May 2006. 2373 10.2. Informative References 2375 [BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A 2376 Practical Forward Secure Signature Scheme Based on Minimal 2377 Security Assumptions", Lecture Notes in Computer Science 2378 volume 7071. Post-Quantum Cryptography, 2011. 2380 [BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based 2381 Digital Signature Schemes", Book chapter Post-Quantum 2382 Cryptography, Springer, 2009. 2384 [BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., 2385 Niederhagen, R., Papachristodoulou, L., Schneider, M., 2386 Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: practical 2387 stateless hash-based signatures", To appear. Advances in 2388 Cryptology - EUROCRYPT, 2015. 2390 [DC14] McGrew, D. and M. Curcio, "Hash-based signatures", draft- 2391 mcgrew-hash-sigs-02 (work in progress), July 2014. 2393 [HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal 2394 Parameters for XMSS^MT", Lecture Notes in Computer Science 2395 volume 8128. CD-ARES, 2013. 2397 [Huelsing13] 2398 Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based 2399 Signature Schemes", Lecture Notes in Computer Science 2400 volume 7918. Progress in Cryptology - AFRICACRYPT, 2013. 2402 [Huelsing13a] 2403 Huelsing, A., "Practical Forward Secure Signatures using 2404 Minimal Security Assumptions", PhD thesis TU Darmstadt, 2405 2013. 2407 [Kaliski15] 2408 Kaliski, B., "Shoring up the Infrastructure: A Strategy 2409 for Standardizing Hash Signatures", Post Quantum NIST 2410 Workshop on Cybersecurity in a Post-Quantum World, 2015. 2412 [Merkle79] 2413 Merkle, R., "Secrecy, Authentication, and Public Key 2414 Systems", Stanford University Information Systems 2415 Laboratory Technical Report 1979-1, 1979. 2417 Appendix A. WOTS+ XDR Formats 2419 The WOTS+ signature and public key formats are formally defined using 2420 XDR [RFC4506] in order to provide an unambiguous, machine readable 2421 definition. Though XDR is used, these formats are simple and easy to 2422 parse without any special tools. To avoid the need to convert to and 2423 from network / host byte order, the enumeration values are all 2424 palindromes. 2426 WOTS+ parameter sets are defined using XDR syntax as follows: 2428 /* ots_algorithm_type identifies a particular 2429 signature algorithm */ 2431 enum ots_algorithm_type { 2432 wotsp_reserved = 0x00000000, 2433 wotsp_aes128_m32_w4 = 0x01000001, 2434 wotsp_aes128_m32_w8 = 0x02000002, 2435 wotsp_aes128_m32_w16 = 0x03000003, 2436 wotsp_sha3-256_m32_w4 = 0x04000004, 2437 wotsp_sha3-256_m32_w8 = 0x05000005, 2438 wotsp_sha3-256_m32_w16 = 0x06000006, 2439 wotsp_sha3-512_m64_w4 = 0x07000007, 2440 wotsp_sha3-512_m64_w8 = 0x08000008, 2441 wotsp_sha3-512_m64_w16 = 0x09000009, 2442 }; 2444 WOTS+ signatures are defined using XDR syntax as follows: 2446 /* Byte strings */ 2448 typedef opaque bytestring32[32]; 2449 typedef opaque bytestring64[64]; 2451 union ots_signature switch (ots_algorithm_type type) { 2452 case wotsp_aes128_m32_w4: 2453 case wotsp_sha3-256_m32_w4: 2454 bytestring32 ots_sig_m32_l133[133]; 2456 case wotsp_aes128_m32_w8: 2457 case wotsp_sha3-256_m32_w8: 2458 bytestring32 ots_sig_m32_l90[90]; 2460 case wotsp_aes128_m32_w16: 2461 case wotsp_sha3-256_m32_w16: 2462 bytestring32 ots_sig_m32_l67[67]; 2464 case wotsp_sha3-512_m64_w4: 2465 bytestring64 ots_sig_m64_l261[261]; 2467 case wotsp_sha3-512_m64_w8: 2468 bytestring64 ots_sig_m64_l75[175]; 2470 case wotsp_sha3-512_m64_w16: 2471 bytestring64 ots_sig_m64_l18[131]; 2473 default: 2474 void; /* error condition */ 2475 }; 2477 WOTS+ public keys are defined using XDR syntax as follows: 2479 union ots_pubkey switch (ots_algorithm_type type) { 2480 case wotsp_aes128_m32_w4: 2481 case wotsp_sha3-256_m32_w4: 2482 bytestring32 ots_pubk_m32_l133[133]; 2484 case wotsp_aes128_m32_w8: 2485 case wotsp_sha3-256_m32_w8: 2486 bytestring32 ots_pubk_m32_l90[90]; 2488 case wotsp_aes128_m32_w16: 2489 case wotsp_sha3-256_m32_w16: 2490 bytestring32 ots_pubk_m32_l67[67]; 2492 case wotsp_sha3-512_m64_w4: 2493 bytestring64 ots_pubk_m64_l261[261]; 2495 case wotsp_sha3-512_m64_w8: 2496 bytestring64 ots_pubk_m64_l75[175]; 2498 case wotsp_sha3-512_m64_w16: 2499 bytestring64 ots_pubk_m64_l18[131]; 2501 default: 2502 void; /* error condition */ 2503 }; 2505 Appendix B. XMSS XDR Formats 2507 XMSS parameter sets are defined using XDR syntax as follows: 2509 /* Byte strings */ 2511 typedef opaque bytestring4[4]; 2512 typedef opaque bytestring16[16]; 2514 /* Definition of parameter sets */ 2516 enum xmss_algorithm_type { 2517 xmss_reserved = 0x00000000, 2519 /* Empty bitmasks */ 2521 /* 128 bit classical security, 85 bit post-quantum security */ 2523 xmss_sha3-256_m32_w4_h10_z = 0x01000001, 2524 xmss_sha3-256_m32_w4_h16_z = 0x02000002, 2525 xmss_sha3-256_m32_w4_h20_z = 0x03000003, 2527 xmss_sha3-256_m32_w8_h10_z = 0x04000004, 2528 xmss_sha3-256_m32_w8_h16_z = 0x05000005, 2529 xmss_sha3-256_m32_w8_h20_z = 0x06000006, 2531 xmss_sha3-256_m32_w16_h10_z = 0x07000007, 2532 xmss_sha3-256_m32_w16_h16_z = 0x08000008, 2533 xmss_sha3-256_m32_w16_h20_z = 0x09000009, 2535 /* 256 bit classical security, 170 bit post-quantum security */ 2537 xmss_sha3-512_m64_w4_h10_z = 0x0a00000a, 2538 xmss_sha3-512_m64_w4_h16_z = 0x0b00000b, 2539 xmss_sha3-512_m64_w4_h20_z = 0x0c00000c, 2541 xmss_sha3-512_m64_w8_h10_z = 0x0d00000d, 2542 xmss_sha3-512_m64_w8_h16_z = 0x0e00000e, 2543 xmss_sha3-512_m64_w8_h20_z = 0x0f00000f, 2545 xmss_sha3-512_m64_w16_h10_z = 0x01010101, 2546 xmss_sha3-512_m64_w16_h16_z = 0x02010102, 2547 xmss_sha3-512_m64_w16_h20_z = 0x03010103, 2549 /* Non-empty bitmasks */ 2551 /* 128 bit classical security, 64 bit post-quantum security */ 2553 xmss_aes128_m32_w4_h10 = 0x04010104, 2554 xmss_aes128_m32_w4_h16 = 0x05010105, 2555 xmss_aes128_m32_w4_h20 = 0x06010106, 2557 xmss_aes128_m32_w8_h10 = 0x07010107, 2558 xmss_aes128_m32_w8_h16 = 0x08010108, 2559 xmss_aes128_m32_w8_h20 = 0x09010109, 2561 xmss_aes128_m32_w16_h10 = 0x0a01010a, 2562 xmss_aes128_m32_w16_h16 = 0x0b01010b, 2563 xmss_aes128_m32_w16_h20 = 0x0c01010c, 2565 /* 256 bit classical security, 128 bit post-quantum security */ 2567 xmss_sha3-256_m32_w4_h10 = 0x0d01010d, 2568 xmss_sha3-256_m32_w4_h16 = 0x0e01010e, 2569 xmss_sha3-256_m32_w4_h20 = 0x0f01010f, 2571 xmss_sha3-256_m32_w8_h10 = 0x01020201, 2572 xmss_sha3-256_m32_w8_h16 = 0x02020202, 2573 xmss_sha3-256_m32_w8_h20 = 0x03020203, 2575 xmss_sha3-256_m32_w16_h10 = 0x04020204, 2576 xmss_sha3-256_m32_w16_h16 = 0x05020205, 2577 xmss_sha3-256_m32_w16_h20 = 0x06020206, 2579 /* 512 bit classical security, 256 bit post-quantum security */ 2581 xmss_sha3-512_m64_w4_h10 = 0x07020207, 2582 xmss_sha3-512_m64_w4_h16 = 0x08020208, 2583 xmss_sha3-512_m64_w4_h20 = 0x09020209, 2585 xmss_sha3-512_m64_w8_h10 = 0x0a02020a, 2586 xmss_sha3-512_m64_w8_h16 = 0x0b02020b, 2587 xmss_sha3-512_m64_w8_h20 = 0x0c02020c, 2589 xmss_sha3-512_m64_w16_h10 = 0x0d02020d, 2590 xmss_sha3-512_m64_w16_h16 = 0x0e02020e, 2591 xmss_sha3-512_m64_w16_h20 = 0x0f02020f, 2592 }; 2594 XMSS signatures are defined using XDR syntax as follows: 2596 /* Authentication path types */ 2598 union xmss_path switch (xmss_algorithm_type type) { 2599 case xmss_sha3-256_m32_w4_h10_z: 2600 case xmss_sha3-256_m32_w8_h10_z: 2601 case xmss_sha3-256_m32_w16_h10_z: 2602 case xmss_sha3-256_m32_w4_h10: 2603 case xmss_sha3-256_m32_w8_h10: 2604 case xmss_sha3-256_m32_w16_h10: 2605 bytestring32 path_n32_t10[10]; 2607 case xmss_sha3-256_m32_w4_h16_z: 2608 case xmss_sha3-256_m32_w8_h16_z: 2609 case xmss_sha3-256_m32_w16_h16_z: 2610 case xmss_sha3-256_m32_w4_h16: 2611 case xmss_sha3-256_m32_w8_h16: 2612 case xmss_sha3-256_m32_w16_h16: 2613 bytestring32 path_n32_t16[16]; 2615 case xmss_sha3-256_m32_w4_h20_z: 2616 case xmss_sha3-256_m32_w8_h20_z: 2617 case xmss_sha3-256_m32_w16_h20_z: 2618 case xmss_sha3-256_m32_w4_h20: 2620 case xmss_sha3-256_m32_w8_h20: 2621 case xmss_sha3-256_m32_w16_h20: 2622 bytestring32 path_n32_t20[20]; 2624 case xmss_sha3-512_m64_w4_h10_z: 2625 case xmss_sha3-512_m64_w8_h10_z: 2626 case xmss_sha3-512_m64_w16_h10_z: 2627 case xmss_sha3-512_m64_w4_h10: 2628 case xmss_sha3-512_m64_w8_h10: 2629 case xmss_sha3-512_m64_w16_h10: 2630 bytestring64 path_n64_t10[10]; 2632 case xmss_sha3-512_m64_w4_h16_z: 2633 case xmss_sha3-512_m64_w8_h16_z: 2634 case xmss_sha3-512_m64_w16_h16_z: 2635 case xmss_sha3-512_m64_w4_h16: 2636 case xmss_sha3-512_m64_w8_h16: 2637 case xmss_sha3-512_m64_w16_h16: 2638 bytestring64 path_n64_t16[16]; 2640 case xmss_sha3-512_m64_w4_h20_z: 2641 case xmss_sha3-512_m64_w8_h20_z: 2642 case xmss_sha3-512_m64_w16_h20_z: 2643 case xmss_sha3-512_m64_w4_h20: 2644 case xmss_sha3-512_m64_w8_h20: 2645 case xmss_sha3-512_m64_w16_h20: 2646 bytestring64 path_n64_t20[20]; 2648 case xmss_aes128_m32_w4_h10: 2649 case xmss_aes128_m32_w8_h10: 2650 case xmss_aes128_m32_w16_h10: 2651 bytestring16 path_n16_t10[10]; 2653 case xmss_aes128_m32_w4_h16: 2654 case xmss_aes128_m32_w8_h16: 2655 case xmss_aes128_m32_w16_h16: 2656 bytestring16 path_n16_t16[16]; 2658 case xmss_aes128_m32_w4_h20: 2659 case xmss_aes128_m32_w8_h20: 2660 case xmss_aes128_m32_w16_h20: 2661 bytestring16 path_n16_t20[20]; 2663 default: 2664 void; /* error condition */ 2665 }; 2667 /* Types for XMSS random strings */ 2668 union random_string_xmss switch (xmss_algorithm_type type) { 2669 case xmss_sha3-256_m32_w4_h10_z: 2670 case xmss_sha3-256_m32_w4_h16_z: 2671 case xmss_sha3-256_m32_w4_h20_z: 2672 case xmss_sha3-256_m32_w8_h10_z: 2673 case xmss_sha3-256_m32_w8_h16_z: 2674 case xmss_sha3-256_m32_w8_h20_z: 2675 case xmss_sha3-256_m32_w16_h10_z: 2676 case xmss_sha3-256_m32_w16_h16_z: 2677 case xmss_sha3-256_m32_w16_h20_z: 2678 case xmss_sha3-256_m32_w4_h10: 2679 case xmss_sha3-256_m32_w4_h16: 2680 case xmss_sha3-256_m32_w4_h20: 2681 case xmss_sha3-256_m32_w8_h10: 2682 case xmss_sha3-256_m32_w8_h16: 2683 case xmss_sha3-256_m32_w8_h20: 2684 case xmss_sha3-256_m32_w16_h10: 2685 case xmss_sha3-256_m32_w16_h16: 2686 case xmss_sha3-256_m32_w16_h20: 2687 case xmss_aes128_m32_w4_h10: 2688 case xmss_aes128_m32_w4_h16: 2689 case xmss_aes128_m32_w4_h20: 2690 case xmss_aes128_m32_w8_h10: 2691 case xmss_aes128_m32_w8_h16: 2692 case xmss_aes128_m32_w8_h20: 2693 case xmss_aes128_m32_w16_h10: 2694 case xmss_aes128_m32_w16_h16: 2695 case xmss_aes128_m32_w16_h20: 2696 bytestring32 rand_m32; 2698 case xmss_sha3-512_m64_w4_h10_z: 2699 case xmss_sha3-512_m64_w4_h16_z: 2700 case xmss_sha3-512_m64_w4_h20_z: 2701 case xmss_sha3-512_m64_w8_h10_z: 2702 case xmss_sha3-512_m64_w8_h16_z: 2703 case xmss_sha3-512_m64_w8_h20_z: 2704 case xmss_sha3-512_m64_w16_h10_z: 2705 case xmss_sha3-512_m64_w16_h16_z: 2706 case xmss_sha3-512_m64_w16_h20_z: 2707 case xmss_sha3-512_m64_w4_h10: 2708 case xmss_sha3-512_m64_w4_h16: 2709 case xmss_sha3-512_m64_w4_h20: 2710 case xmss_sha3-512_m64_w8_h10: 2711 case xmss_sha3-512_m64_w8_h16: 2712 case xmss_sha3-512_m64_w8_h20: 2713 case xmss_sha3-512_m64_w16_h10: 2714 case xmss_sha3-512_m64_w16_h16: 2715 case xmss_sha3-512_m64_w16_h20: 2717 bytestring64 rand_m64; 2719 default: 2720 void; /* error condition */ 2721 }; 2723 /* Corresponding WOTS+ type for given XMSS type */ 2725 union xmss_ots_signature switch (xmss_algorithm_type type) { 2726 case xmss_sha3-256_m32_w4_h10_z: 2727 case xmss_sha3-256_m32_w4_h16_z: 2728 case xmss_sha3-256_m32_w4_h20_z: 2729 wotsp_sha3-256_m32_w4; 2731 case xmss_sha3-256_m32_w8_h10_z: 2732 case xmss_sha3-256_m32_w8_h16_z: 2733 case xmss_sha3-256_m32_w8_h20_z: 2734 wotsp_sha3-256_m32_w8; 2736 case xmss_sha3-256_m32_w16_h10_z: 2737 case xmss_sha3-256_m32_w16_h16_z: 2738 case xmss_sha3-256_m32_w16_h20_z: 2739 wotsp_sha3-256_m32_w16 2741 case xmss_sha3-512_m64_w4_h10_z: 2742 case xmss_sha3-512_m64_w4_h16_z: 2743 case xmss_sha3-512_m64_w4_h20_z: 2744 wotsp_sha3-512_m64_w4; 2746 case xmss_sha3-512_m64_w8_h10_z: 2747 case xmss_sha3-512_m64_w8_h16_z: 2748 case xmss_sha3-512_m64_w8_h20_z: 2749 wotsp_sha3-512_m64_w8; 2751 case xmss_sha3-512_m64_w16_h10_z: 2752 case xmss_sha3-512_m64_w16_h16_z: 2753 case xmss_sha3-512_m64_w16_h20_z: 2754 wotsp_sha3-512_m64_w16; 2756 case xmss_aes128_m32_w4_h10: 2757 case xmss_aes128_m32_w4_h16: 2758 case xmss_aes128_m32_w4_h20: 2759 wotsp_aes128_m32_w4; 2761 case xmss_aes128_m32_w8_h10: 2762 case xmss_aes128_m32_w8_h16: 2763 case xmss_aes128_m32_w8_h20: 2764 wotsp_aes128_m32_w8; 2766 case xmss_aes128_m32_w16_h10: 2767 case xmss_aes128_m32_w16_h16: 2768 case xmss_aes128_m32_w16_h20: 2769 wotsp_aes128_m32_w16; 2771 case xmss_sha3-256_m32_w4_h10: 2772 case xmss_sha3-256_m32_w4_h16: 2773 case xmss_sha3-256_m32_w4_h20: 2774 wotsp_sha3-256_m32_w4; 2776 case xmss_sha3-256_m32_w8_h10: 2777 case xmss_sha3-256_m32_w8_h16: 2778 case xmss_sha3-256_m32_w8_h20: 2779 wotsp_sha3-256_m32_w8; 2781 case xmss_sha3-256_m32_w16_h10: 2782 case xmss_sha3-256_m32_w16_h16: 2783 case xmss_sha3-256_m32_w16_h20: 2784 wotsp_sha3-256_m32_w16; 2786 case xmss_sha3-512_m64_w4_h10: 2787 case xmss_sha3-512_m64_w4_h16: 2788 case xmss_sha3-512_m64_w4_h20: 2789 wotsp_sha3-512_m64_w4; 2791 case xmss_sha3-512_m64_w8_h10: 2792 case xmss_sha3-512_m64_w8_h16: 2793 case xmss_sha3-512_m64_w8_h20: 2794 wotsp_sha3-512_m64_w8; 2796 case xmss_sha3-512_m64_w16_h10: 2797 case xmss_sha3-512_m64_w16_h16: 2798 case xmss_sha3-512_m64_w16_h20: 2799 wotsp_sha3-512_m64_w16; 2801 default: 2802 void; /* error condition */ 2803 }; 2805 /* XMSS signature structure */ 2807 struct xmss_signature { 2808 /* WOTS+ key pair index */ 2809 bytestring4 idx_sig; 2810 /* Random string for randomized hashing */ 2811 random_string_xmss rand_string; 2812 /* WOTS+ signature */ 2813 xmss_ots_signature sig_ots; 2814 /* authentication path */ 2815 xmss_path nodes; 2816 }; 2818 When no bitmasks are used, XMSS public keys are defined using XDR 2819 syntax as follows: 2821 /* Types for XMSS root node */ 2823 union xmss_root switch (xmss_algorithm_type type) { 2824 case xmss_sha3-256_m32_w4_h10_z: 2825 case xmss_sha3-256_m32_w4_h16_z: 2826 case xmss_sha3-256_m32_w4_h20_z: 2827 case xmss_sha3-256_m32_w8_h10_z: 2828 case xmss_sha3-256_m32_w16_h10_z: 2829 case xmss_sha3-256_m32_w8_h16_z: 2830 case xmss_sha3-256_m32_w16_h16_z: 2831 case xmss_sha3-256_m32_w8_h20_z: 2832 case xmss_sha3-256_m32_w16_h20_z: 2833 bytestring32 root_n32; 2835 case xmss_sha3-512_m64_w4_h10_z: 2836 case xmss_sha3-512_m64_w4_h16_z: 2837 case xmss_sha3-512_m64_w4_h20_z: 2838 case xmss_sha3-512_m64_w8_h10_z: 2839 case xmss_sha3-512_m64_w16_h10_z: 2840 case xmss_sha3-512_m64_w8_h16_z: 2841 case xmss_sha3-512_m64_w16_h16_z: 2842 case xmss_sha3-512_m64_w8_h20_z: 2843 case xmss_sha3-512_m64_w16_h20_z: 2844 bytestring64 root_n64; 2846 default: 2847 void; /* error condition */ 2848 }; 2850 /* XMSS public key structure */ 2852 struct xmss_public_key { 2853 xmss_root root; /* Root node */ 2854 }; 2856 When bitmasks are used, XMSS public keys are defined using XDR syntax 2857 as follows: 2859 /* Types for XMSS bitmasks */ 2861 union xmss_bm switch (xmss_algorithm_type type) { 2862 case xmss_aes128_m32_w4_h10: 2863 bytestring16 bm_n16_bm36[36]; 2865 case xmss_aes128_m32_w4_h16: 2866 bytestring16 bm_n16_bm48[48]; 2868 case xmss_aes128_m32_w4_h20: 2869 bytestring16 bm_n16_bm56[56]; 2871 case xmss_aes128_m32_w8_h10: 2872 case xmss_aes128_m32_w16_h10: 2873 bytestring16 bm_n16_bm34[34]; 2875 case xmss_aes128_m32_w8_h16: 2876 case xmss_aes128_m32_w16_h16: 2877 bytestring16 bm_n16_bm46[46]; 2879 case xmss_aes128_m32_w8_h20: 2880 case xmss_aes128_m32_w16_h20: 2881 bytestring16 bm_n16_bm54[54]; 2883 case xmss_sha3-256_m32_w4_h10: 2884 bytestring32 bm_n32_bm36[36]; 2886 case xmss_sha3-256_m32_w4_h16: 2887 bytestring32 bm_n32_bm48[48]; 2889 case xmss_sha3-256_m32_w4_h20: 2890 bytestring32 bm_n32_bm56[56]; 2892 case xmss_sha3-256_m32_w8_h10: 2893 case xmss_sha3-256_m32_w16_h10: 2894 bytestring32 bm_n32_bm34[34]; 2896 case xmss_sha3-256_m32_w8_h16: 2897 case xmss_sha3-256_m32_w16_h16: 2898 bytestring32 bm_n32_bm46[46]; 2900 case xmss_sha3-256_m32_w8_h20: 2901 case xmss_sha3-256_m32_w16_h20: 2902 bytestring32 bm_n32_bm54[54]; 2904 case xmss_sha3-512_m64_w4_h10: 2905 bytestring64 bm_n64_bm38[38]; 2907 case xmss_sha3-512_m64_w4_h16: 2908 bytestring64 bm_n64_bm50[50]; 2910 case xmss_sha3-512_m64_w4_h20: 2911 bytestring64 bm_n64_bm58[58]; 2913 case xmss_sha3-512_m64_w8_h10: 2914 case xmss_sha3-512_m64_w16_h10: 2915 bytestring64 bm_n64_bm36[36]; 2917 case xmss_sha3-512_m64_w8_h16: 2918 case xmss_sha3-512_m64_w16_h16: 2919 bytestring64 bm_n64_bm48[48]; 2921 case xmss_sha3-512_m64_w8_h20: 2922 case xmss_sha3-512_m64_w16_h20: 2923 bytestring64 bm_n64_bm56[56]; 2925 default: 2926 void; /* error condition */ 2927 }; 2929 /* Types for XMSS root node */ 2931 union xmss_root switch (xmss_algorithm_type type) { 2932 case xmss_aes128_m32_w4_h10: 2933 case xmss_aes128_m32_w4_h16: 2934 case xmss_aes128_m32_w4_h20: 2935 case xmss_aes128_m32_w8_h10: 2936 case xmss_aes128_m32_w16_h10: 2937 case xmss_aes128_m32_w8_h16: 2938 case xmss_aes128_m32_w16_h16: 2939 case xmss_aes128_m32_w8_h20: 2940 case xmss_aes128_m32_w16_h20: 2941 bytestring16 root_n16; 2943 case xmss_sha3-256_m32_w4_h10: 2944 case xmss_sha3-256_m32_w4_h16: 2945 case xmss_sha3-256_m32_w4_h20: 2946 case xmss_sha3-256_m32_w8_h10: 2947 case xmss_sha3-256_m32_w16_h10: 2948 case xmss_sha3-256_m32_w8_h16: 2949 case xmss_sha3-256_m32_w16_h16: 2950 case xmss_sha3-256_m32_w8_h20: 2951 case xmss_sha3-256_m32_w16_h20: 2952 bytestring32 root_n32; 2954 case xmss_sha3-512_m64_w4_h10: 2956 case xmss_sha3-512_m64_w4_h16: 2957 case xmss_sha3-512_m64_w4_h20: 2958 case xmss_sha3-512_m64_w8_h10: 2959 case xmss_sha3-512_m64_w16_h10: 2960 case xmss_sha3-512_m64_w8_h16: 2961 case xmss_sha3-512_m64_w16_h16: 2962 case xmss_sha3-512_m64_w8_h20: 2963 case xmss_sha3-512_m64_w16_h20: 2964 bytestring64 root_n64; 2966 default: 2967 void; /* error condition */ 2968 }; 2970 /* XMSS public key structure */ 2972 struct xmss_public_key { 2973 xmss_bm bm; /* Bitmasks */ 2974 xmss_root root; /* Root node */ 2975 }; 2977 Appendix C. XMSS^MT XDR Formats 2979 XMSS^MT parameter sets are defined using XDR syntax as follows: 2981 /* Byte strings */ 2983 typedef opaque bytestring3[3]; 2984 typedef opaque bytestring5[5]; 2985 typedef opaque bytestring8[8]; 2987 /* Definition of parameter sets */ 2989 enum xmssmt_algorithm_type { 2990 xmssmt_reserved = 0x00000000, 2992 /* Empty bitmasks */ 2994 /* 128 bit classical security, 85 bit post-quantum security */ 2996 xmssmt_sha3-256_m32_w4_h20_d2_z = 0x01000001, 2997 xmssmt_sha3-256_m32_w4_h20_d4_z = 0x02000002, 2998 xmssmt_sha3-256_m32_w4_h40_d2_z = 0x03000003, 2999 xmssmt_sha3-256_m32_w4_h40_d4_z = 0x04000004, 3000 xmssmt_sha3-256_m32_w4_h40_d8_z = 0x05000005, 3001 xmssmt_sha3-256_m32_w4_h60_d3_z = 0x06000006, 3002 xmssmt_sha3-256_m32_w4_h60_d6_z = 0x07000007, 3003 xmssmt_sha3-256_m32_w4_h60_d12_z = 0x08000008, 3005 xmssmt_sha3-256_m32_w8_h20_d2_z = 0x09000009, 3006 xmssmt_sha3-256_m32_w8_h20_d4_z = 0x0a00000a, 3007 xmssmt_sha3-256_m32_w8_h40_d2_z = 0x0b00000b, 3008 xmssmt_sha3-256_m32_w8_h40_d4_z = 0x0c00000c, 3009 xmssmt_sha3-256_m32_w8_h40_d8_z = 0x0d00000d, 3010 xmssmt_sha3-256_m32_w8_h60_d3_z = 0x0e00000e, 3011 xmssmt_sha3-256_m32_w8_h60_d6_z = 0x0f00000f, 3012 xmssmt_sha3-256_m32_w8_h60_d12_z = 0x00010100, 3014 xmssmt_sha3-256_m32_w16_h20_d2_z = 0x01010101, 3015 xmssmt_sha3-256_m32_w16_h20_d4_z = 0x02010102, 3016 xmssmt_sha3-256_m32_w16_h40_d2_z = 0x03010103, 3017 xmssmt_sha3-256_m32_w16_h40_d4_z = 0x04010104, 3018 xmssmt_sha3-256_m32_w16_h40_d8_z = 0x05010105, 3019 xmssmt_sha3-256_m32_w16_h60_d3_z = 0x06010106, 3020 xmssmt_sha3-256_m32_w16_h60_d6_z = 0x07010107, 3021 xmssmt_sha3-256_m32_w16_h60_d12_z = 0x08010108, 3023 /* 256 bit classical security, 170 bit post-quantum security */ 3025 xmssmt_sha3-512_m64_w4_h20_d2_z = 0x09010109, 3026 xmssmt_sha3-512_m64_w4_h20_d4_z = 0x0a01010a, 3027 xmssmt_sha3-512_m64_w4_h40_d2_z = 0x0b01010b, 3028 xmssmt_sha3-512_m64_w4_h40_d4_z = 0x0c01010c, 3029 xmssmt_sha3-512_m64_w4_h40_d8_z = 0x0d01010d, 3030 xmssmt_sha3-512_m64_w4_h60_d3_z = 0x0e01010e, 3031 xmssmt_sha3-512_m64_w4_h60_d6_z = 0x0f01010f, 3032 xmssmt_sha3-512_m64_w4_h60_d12_z = 0x00020200, 3034 xmssmt_sha3-512_m64_w8_h20_d2_z = 0x01020201, 3035 xmssmt_sha3-512_m64_w8_h20_d4_z = 0x02020202, 3036 xmssmt_sha3-512_m64_w8_h40_d2_z = 0x03020203, 3037 xmssmt_sha3-512_m64_w8_h40_d4_z = 0x04020204, 3038 xmssmt_sha3-512_m64_w8_h40_d8_z = 0x05020205, 3039 xmssmt_sha3-512_m64_w8_h60_d3_z = 0x06020206, 3040 xmssmt_sha3-512_m64_w8_h60_d6_z = 0x07020207, 3041 xmssmt_sha3-512_m64_w8_h60_d12_z = 0x08020208, 3043 xmssmt_sha3-512_m64_w16_h20_d2_z = 0x09020209, 3044 xmssmt_sha3-512_m64_w16_h20_d4_z = 0x0a02020a, 3045 xmssmt_sha3-512_m64_w16_h40_d2_z = 0x0b02020b, 3046 xmssmt_sha3-512_m64_w16_h40_d4_z = 0x0c02020c, 3047 xmssmt_sha3-512_m64_w16_h40_d8_z = 0x0d02020d, 3048 xmssmt_sha3-512_m64_w16_h60_d3_z = 0x0e02020e, 3049 xmssmt_sha3-512_m64_w16_h60_d6_z = 0x0f02020f, 3050 xmssmt_sha3-512_m64_w16_h60_d12_z = 0x00030300, 3052 /* Non-empty bitmasks */ 3054 /* 128 bit classical security, 64 bit post-quantum security */ 3056 xmssmt_aes128_m32_w4_h20_d2 = 0x01030301, 3057 xmssmt_aes128_m32_w4_h20_d4 = 0x02030302, 3058 xmssmt_aes128_m32_w4_h40_d2 = 0x03030303, 3059 xmssmt_aes128_m32_w4_h40_d4 = 0x04030304, 3060 xmssmt_aes128_m32_w4_h40_d8 = 0x05030305, 3061 xmssmt_aes128_m32_w4_h60_d3 = 0x06030306, 3062 xmssmt_aes128_m32_w4_h60_d6 = 0x07030307, 3063 xmssmt_aes128_m32_w4_h60_d12 = 0x08030308, 3065 xmssmt_aes128_m32_w8_h20_d2 = 0x09030309, 3066 xmssmt_aes128_m32_w8_h20_d4 = 0x0a03030a, 3067 xmssmt_aes128_m32_w8_h40_d2 = 0x0b03030b, 3068 xmssmt_aes128_m32_w8_h40_d4 = 0x0c03030c, 3069 xmssmt_aes128_m32_w8_h40_d8 = 0x0d03030d, 3070 xmssmt_aes128_m32_w8_h60_d3 = 0x0e03030e, 3071 xmssmt_aes128_m32_w8_h60_d6 = 0x0f03030f, 3072 xmssmt_aes128_m32_w8_h60_d12 = 0x00040400, 3074 xmssmt_aes128_m32_w16_h20_d2 = 0x01040401, 3075 xmssmt_aes128_m32_w16_h20_d4 = 0x02040402, 3076 xmssmt_aes128_m32_w16_h40_d2 = 0x03040403, 3077 xmssmt_aes128_m32_w16_h40_d4 = 0x04040404, 3078 xmssmt_aes128_m32_w16_h40_d8 = 0x05040405, 3079 xmssmt_aes128_m32_w16_h60_d3 = 0x06040406, 3080 xmssmt_aes128_m32_w16_h60_d6 = 0x07040407, 3081 xmssmt_aes128_m32_w16_h60_d12 = 0x08040408, 3083 /* 256 bit classical security, 128 bit post-quantum security */ 3085 xmssmt_sha3-256_m32_w4_h20_d2 = 0x09040409, 3086 xmssmt_sha3-256_m32_w4_h20_d4 = 0x0a04040a, 3087 xmssmt_sha3-256_m32_w4_h40_d2 = 0x0b04040b, 3088 xmssmt_sha3-256_m32_w4_h40_d4 = 0x0c04040c, 3089 xmssmt_sha3-256_m32_w4_h40_d8 = 0x0d04040d, 3090 xmssmt_sha3-256_m32_w4_h60_d3 = 0x0e04040e, 3091 xmssmt_sha3-256_m32_w4_h60_d6 = 0x0f04040f, 3092 xmssmt_sha3-256_m32_w4_h60_d12 = 0x00050500, 3094 xmssmt_sha3-256_m32_w8_h20_d2 = 0x01050501, 3095 xmssmt_sha3-256_m32_w8_h20_d4 = 0x02050502, 3096 xmssmt_sha3-256_m32_w8_h40_d2 = 0x03050503, 3097 xmssmt_sha3-256_m32_w8_h40_d4 = 0x04050504, 3098 xmssmt_sha3-256_m32_w8_h40_d8 = 0x05050505, 3099 xmssmt_sha3-256_m32_w8_h60_d3 = 0x06050506, 3100 xmssmt_sha3-256_m32_w8_h60_d6 = 0x07050507, 3101 xmssmt_sha3-256_m32_w8_h60_d12 = 0x08050508, 3103 xmssmt_sha3-256_m32_w16_h20_d2 = 0x09050509, 3104 xmssmt_sha3-256_m32_w16_h20_d4 = 0x0a05050a, 3105 xmssmt_sha3-256_m32_w16_h40_d2 = 0x0b05050b, 3106 xmssmt_sha3-256_m32_w16_h40_d4 = 0x0c05050c, 3107 xmssmt_sha3-256_m32_w16_h40_d8 = 0x0d05050d, 3108 xmssmt_sha3-256_m32_w16_h60_d3 = 0x0e05050e, 3109 xmssmt_sha3-256_m32_w16_h60_d6 = 0x0f05050f, 3110 xmssmt_sha3-256_m32_w16_h60_d12 = 0x00060600, 3112 /* 512 bit classical security, 256 bit post-quantum security */ 3114 xmssmt_sha3-512_m64_w4_h20_d2 = 0x01060601, 3115 xmssmt_sha3-512_m64_w4_h20_d4 = 0x02060602, 3116 xmssmt_sha3-512_m64_w4_h40_d2 = 0x03060603, 3117 xmssmt_sha3-512_m64_w4_h40_d4 = 0x04060604, 3118 xmssmt_sha3-512_m64_w4_h40_d8 = 0x05060605, 3119 xmssmt_sha3-512_m64_w4_h60_d3 = 0x06060606, 3120 xmssmt_sha3-512_m64_w4_h60_d6 = 0x07060607, 3121 xmssmt_sha3-512_m64_w4_h60_d12 = 0x08060608, 3123 xmssmt_sha3-512_m64_w8_h20_d2 = 0x09060609, 3124 xmssmt_sha3-512_m64_w8_h20_d4 = 0x0a06060a, 3125 xmssmt_sha3-512_m64_w8_h40_d2 = 0x0b06060b, 3126 xmssmt_sha3-512_m64_w8_h40_d4 = 0x0c06060c, 3127 xmssmt_sha3-512_m64_w8_h40_d8 = 0x0d06060d, 3128 xmssmt_sha3-512_m64_w8_h60_d3 = 0x0e06060e, 3129 xmssmt_sha3-512_m64_w8_h60_d6 = 0x0f06060f, 3130 xmssmt_sha3-512_m64_w8_h60_d12 = 0x00070700, 3132 xmssmt_sha3-512_m64_w16_h20_d2 = 0x01070701, 3133 xmssmt_sha3-512_m64_w16_h20_d4 = 0x02070702, 3134 xmssmt_sha3-512_m64_w16_h40_d2 = 0x03070703, 3135 xmssmt_sha3-512_m64_w16_h40_d4 = 0x04070704, 3136 xmssmt_sha3-512_m64_w16_h40_d8 = 0x05070705, 3137 xmssmt_sha3-512_m64_w16_h60_d3 = 0x06070706, 3138 xmssmt_sha3-512_m64_w16_h60_d6 = 0x07070707, 3139 xmssmt_sha3-512_m64_w16_h60_d12 = 0x08070708, 3140 }; 3142 XMSS^MT signatures are defined using XDR syntax as follows: 3144 /* Type for XMSS^MT key pair index */ 3145 /* Depends solely on h */ 3147 union idx_sig_xmssmt switch (xmss_algorithm_type type) { 3148 case xmssmt_sha3-256_m32_w4_h20_d2_z: 3149 case xmssmt_sha3-256_m32_w4_h20_d4_z: 3150 case xmssmt_sha3-256_m32_w8_h20_d2_z: 3151 case xmssmt_sha3-256_m32_w8_h20_d4_z: 3152 case xmssmt_sha3-256_m32_w16_h20_d2_z: 3153 case xmssmt_sha3-256_m32_w16_h20_d4_z: 3154 case xmssmt_sha3-512_m64_w4_h20_d2_z: 3155 case xmssmt_sha3-512_m64_w4_h20_d4_z: 3156 case xmssmt_sha3-512_m64_w8_h20_d2_z: 3157 case xmssmt_sha3-512_m64_w8_h20_d4_z: 3158 case xmssmt_sha3-512_m64_w16_h20_d2_z: 3159 case xmssmt_sha3-512_m64_w16_h20_d4_z: 3160 case xmssmt_aes128_m32_w4_h20_d2: 3161 case xmssmt_aes128_m32_w4_h20_d4: 3162 case xmssmt_aes128_m32_w8_h20_d2: 3163 case xmssmt_aes128_m32_w8_h20_d4: 3164 case xmssmt_aes128_m32_w16_h20_d2: 3165 case xmssmt_aes128_m32_w16_h20_d4: 3166 case xmssmt_sha3-256_m32_w4_h20_d2: 3167 case xmssmt_sha3-256_m32_w4_h20_d4: 3168 case xmssmt_sha3-256_m32_w8_h20_d2: 3169 case xmssmt_sha3-256_m32_w8_h20_d4: 3170 case xmssmt_sha3-256_m32_w16_h20_d2: 3171 case xmssmt_sha3-256_m32_w16_h20_d4: 3172 case xmssmt_sha3-512_m64_w4_h20_d2: 3173 case xmssmt_sha3-512_m64_w4_h20_d4: 3174 case xmssmt_sha3-512_m64_w8_h20_d2: 3175 case xmssmt_sha3-512_m64_w8_h20_d4: 3176 case xmssmt_sha3-512_m64_w16_h20_d2: 3177 case xmssmt_sha3-512_m64_w16_h20_d4: 3178 bytestring3 idx3; 3180 case xmssmt_sha3-256_m32_w4_h40_d2_z: 3181 case xmssmt_sha3-256_m32_w4_h40_d4_z: 3182 case xmssmt_sha3-256_m32_w4_h40_d8_z: 3183 case xmssmt_sha3-256_m32_w8_h40_d2_z: 3184 case xmssmt_sha3-256_m32_w8_h40_d4_z: 3185 case xmssmt_sha3-256_m32_w8_h40_d8_z: 3186 case xmssmt_sha3-256_m32_w16_h40_d2_z: 3187 case xmssmt_sha3-256_m32_w16_h40_d4_z: 3188 case xmssmt_sha3-256_m32_w16_h40_d8_z: 3189 case xmssmt_sha3-512_m64_w4_h40_d2_z: 3190 case xmssmt_sha3-512_m64_w4_h40_d4_z: 3191 case xmssmt_sha3-512_m64_w4_h40_d8_z: 3193 case xmssmt_sha3-512_m64_w8_h40_d2_z: 3194 case xmssmt_sha3-512_m64_w8_h40_d4_z: 3195 case xmssmt_sha3-512_m64_w8_h40_d8_z: 3196 case xmssmt_sha3-512_m64_w16_h40_d2_z: 3197 case xmssmt_sha3-512_m64_w16_h40_d4_z: 3198 case xmssmt_sha3-512_m64_w16_h40_d8_z: 3199 case xmssmt_aes128_m32_w4_h40_d2: 3200 case xmssmt_aes128_m32_w4_h40_d4: 3201 case xmssmt_aes128_m32_w4_h40_d8: 3202 case xmssmt_aes128_m32_w8_h40_d2: 3203 case xmssmt_aes128_m32_w8_h40_d4: 3204 case xmssmt_aes128_m32_w8_h40_d8: 3205 case xmssmt_aes128_m32_w16_h40_d2: 3206 case xmssmt_aes128_m32_w16_h40_d4: 3207 case xmssmt_aes128_m32_w16_h40_d8: 3208 case xmssmt_sha3-256_m32_w4_h40_d2: 3209 case xmssmt_sha3-256_m32_w4_h40_d4: 3210 case xmssmt_sha3-256_m32_w4_h40_d8: 3211 case xmssmt_sha3-256_m32_w8_h40_d2: 3212 case xmssmt_sha3-256_m32_w8_h40_d4: 3213 case xmssmt_sha3-256_m32_w8_h40_d8: 3214 case xmssmt_sha3-512_m64_w4_h40_d2: 3215 case xmssmt_sha3-512_m64_w4_h40_d4: 3216 case xmssmt_sha3-512_m64_w4_h40_d8: 3217 case xmssmt_sha3-256_m32_w16_h40_d2: 3218 case xmssmt_sha3-256_m32_w16_h40_d4: 3219 case xmssmt_sha3-256_m32_w16_h40_d8: 3220 case xmssmt_sha3-512_m64_w8_h40_d2: 3221 case xmssmt_sha3-512_m64_w8_h40_d4: 3222 case xmssmt_sha3-512_m64_w8_h40_d8: 3223 case xmssmt_sha3-512_m64_w16_h40_d2: 3224 case xmssmt_sha3-512_m64_w16_h40_d4: 3225 case xmssmt_sha3-512_m64_w16_h40_d8: 3226 bytestring5 idx5; 3228 case xmssmt_sha3-256_m32_w4_h60_d3_z: 3229 case xmssmt_sha3-256_m32_w4_h60_d6_z: 3230 case xmssmt_sha3-256_m32_w4_h60_d12_z: 3231 case xmssmt_sha3-256_m32_w8_h60_d3_z: 3232 case xmssmt_sha3-256_m32_w8_h60_d6_z: 3233 case xmssmt_sha3-256_m32_w8_h60_d12_z: 3234 case xmssmt_sha3-256_m32_w16_h60_d3_z: 3235 case xmssmt_sha3-256_m32_w16_h60_d6_z: 3236 case xmssmt_sha3-256_m32_w16_h60_d12_z: 3237 case xmssmt_sha3-512_m64_w4_h60_d3_z: 3238 case xmssmt_sha3-512_m64_w4_h60_d6_z: 3239 case xmssmt_sha3-512_m64_w4_h60_d12_z: 3240 case xmssmt_sha3-512_m64_w8_h60_d3_z: 3242 case xmssmt_sha3-512_m64_w8_h60_d6_z: 3243 case xmssmt_sha3-512_m64_w8_h60_d12_z: 3244 case xmssmt_sha3-512_m64_w16_h60_d3_z: 3245 case xmssmt_sha3-512_m64_w16_h60_d6_z: 3246 case xmssmt_sha3-512_m64_w16_h60_d12_z: 3247 case xmssmt_aes128_m32_w4_h60_d3: 3248 case xmssmt_aes128_m32_w4_h60_d6: 3249 case xmssmt_aes128_m32_w4_h60_d12: 3250 case xmssmt_aes128_m32_w8_h60_d3: 3251 case xmssmt_aes128_m32_w8_h60_d6: 3252 case xmssmt_aes128_m32_w8_h60_d12: 3253 case xmssmt_aes128_m32_w16_h60_d3: 3254 case xmssmt_aes128_m32_w16_h60_d6: 3255 case xmssmt_aes128_m32_w16_h60_d12: 3256 case xmssmt_sha3-256_m32_w4_h60_d3: 3257 case xmssmt_sha3-256_m32_w4_h60_d6: 3258 case xmssmt_sha3-256_m32_w4_h60_d12: 3259 case xmssmt_sha3-256_m32_w8_h60_d3: 3260 case xmssmt_sha3-256_m32_w8_h60_d6: 3261 case xmssmt_sha3-256_m32_w8_h60_d12: 3262 case xmssmt_sha3-256_m32_w16_h60_d3: 3263 case xmssmt_sha3-256_m32_w16_h60_d6: 3264 case xmssmt_sha3-256_m32_w16_h60_d12: 3265 case xmssmt_sha3-512_m64_w4_h60_d3: 3266 case xmssmt_sha3-512_m64_w4_h60_d6: 3267 case xmssmt_sha3-512_m64_w4_h60_d12: 3268 case xmssmt_sha3-512_m64_w8_h60_d3: 3269 case xmssmt_sha3-512_m64_w8_h60_d6: 3270 case xmssmt_sha3-512_m64_w8_h60_d12: 3271 case xmssmt_sha3-512_m64_w16_h60_d3: 3272 case xmssmt_sha3-512_m64_w16_h60_d6: 3273 case xmssmt_sha3-512_m64_w16_h60_d12: 3274 bytestring8 idx8; 3276 default: 3277 void; /* error condition */ 3278 }; 3280 union random_string_xmssmt switch (xmssmt_algorithm_type type) { 3281 case xmssmt_aes128_m32_w4_h20_d2: 3282 case xmssmt_aes128_m32_w4_h20_d4: 3283 case xmssmt_aes128_m32_w4_h40_d2: 3284 case xmssmt_aes128_m32_w4_h40_d4: 3285 case xmssmt_aes128_m32_w4_h40_d8: 3286 case xmssmt_aes128_m32_w4_h60_d3: 3287 case xmssmt_aes128_m32_w4_h60_d6: 3288 case xmssmt_aes128_m32_w4_h60_d12: 3289 case xmssmt_aes128_m32_w8_h20_d2: 3291 case xmssmt_aes128_m32_w8_h20_d4: 3292 case xmssmt_aes128_m32_w8_h40_d2: 3293 case xmssmt_aes128_m32_w8_h40_d4: 3294 case xmssmt_aes128_m32_w8_h40_d8: 3295 case xmssmt_aes128_m32_w8_h60_d3: 3296 case xmssmt_aes128_m32_w8_h60_d6: 3297 case xmssmt_aes128_m32_w8_h60_d12: 3298 case xmssmt_aes128_m32_w16_h20_d2: 3299 case xmssmt_aes128_m32_w16_h20_d4: 3300 case xmssmt_aes128_m32_w16_h40_d2: 3301 case xmssmt_aes128_m32_w16_h40_d4: 3302 case xmssmt_aes128_m32_w16_h40_d8: 3303 case xmssmt_aes128_m32_w16_h60_d3: 3304 case xmssmt_aes128_m32_w16_h60_d6: 3305 case xmssmt_aes128_m32_w16_h60_d12: 3306 case xmssmt_sha3-256_m32_w4_h20_d2_z: 3307 case xmssmt_sha3-256_m32_w4_h20_d4_z: 3308 case xmssmt_sha3-256_m32_w4_h40_d2_z: 3309 case xmssmt_sha3-256_m32_w4_h40_d4_z: 3310 case xmssmt_sha3-256_m32_w4_h40_d8_z: 3311 case xmssmt_sha3-256_m32_w4_h60_d3_z: 3312 case xmssmt_sha3-256_m32_w4_h60_d6_z: 3313 case xmssmt_sha3-256_m32_w4_h60_d12_z: 3314 case xmssmt_sha3-256_m32_w8_h20_d2_z: 3315 case xmssmt_sha3-256_m32_w8_h20_d4_z: 3316 case xmssmt_sha3-256_m32_w8_h40_d2_z: 3317 case xmssmt_sha3-256_m32_w8_h40_d4_z: 3318 case xmssmt_sha3-256_m32_w8_h40_d8_z: 3319 case xmssmt_sha3-256_m32_w8_h60_d3_z: 3320 case xmssmt_sha3-256_m32_w8_h60_d6_z: 3321 case xmssmt_sha3-256_m32_w8_h60_d12_z: 3322 case xmssmt_sha3-256_m32_w16_h20_d2_z: 3323 case xmssmt_sha3-256_m32_w16_h20_d4_z: 3324 case xmssmt_sha3-256_m32_w16_h40_d2_z: 3325 case xmssmt_sha3-256_m32_w16_h40_d4_z: 3326 case xmssmt_sha3-256_m32_w16_h40_d8_z: 3327 case xmssmt_sha3-256_m32_w16_h60_d3_z: 3328 case xmssmt_sha3-256_m32_w16_h60_d6_z: 3329 case xmssmt_sha3-256_m32_w16_h60_d12_z: 3330 case xmssmt_sha3-256_m32_w4_h20_d2: 3331 case xmssmt_sha3-256_m32_w4_h20_d4: 3332 case xmssmt_sha3-256_m32_w4_h40_d2: 3333 case xmssmt_sha3-256_m32_w4_h40_d4: 3334 case xmssmt_sha3-256_m32_w4_h40_d8: 3335 case xmssmt_sha3-256_m32_w4_h60_d3: 3336 case xmssmt_sha3-256_m32_w4_h60_d6: 3337 case xmssmt_sha3-256_m32_w4_h60_d12: 3338 case xmssmt_sha3-256_m32_w8_h20_d2: 3340 case xmssmt_sha3-256_m32_w8_h20_d4: 3341 case xmssmt_sha3-256_m32_w8_h40_d2: 3342 case xmssmt_sha3-256_m32_w8_h40_d4: 3343 case xmssmt_sha3-256_m32_w8_h40_d8: 3344 case xmssmt_sha3-256_m32_w8_h60_d3: 3345 case xmssmt_sha3-256_m32_w8_h60_d6: 3346 case xmssmt_sha3-256_m32_w8_h60_d12: 3347 case xmssmt_sha3-256_m32_w16_h20_d2: 3348 case xmssmt_sha3-256_m32_w16_h20_d4: 3349 case xmssmt_sha3-256_m32_w16_h40_d2: 3350 case xmssmt_sha3-256_m32_w16_h40_d4: 3351 case xmssmt_sha3-256_m32_w16_h40_d8: 3352 case xmssmt_sha3-256_m32_w16_h60_d3: 3353 case xmssmt_sha3-256_m32_w16_h60_d6: 3354 case xmssmt_sha3-256_m32_w16_h60_d12: 3355 bytestring32 rand_m32; 3357 case xmssmt_sha3-512_m64_w4_h20_d2_z: 3358 case xmssmt_sha3-512_m64_w4_h20_d4_z: 3359 case xmssmt_sha3-512_m64_w4_h40_d2_z: 3360 case xmssmt_sha3-512_m64_w4_h40_d4_z: 3361 case xmssmt_sha3-512_m64_w4_h40_d8_z: 3362 case xmssmt_sha3-512_m64_w4_h60_d3_z: 3363 case xmssmt_sha3-512_m64_w4_h60_d6_z: 3364 case xmssmt_sha3-512_m64_w4_h60_d12_z: 3365 case xmssmt_sha3-512_m64_w8_h20_d2_z: 3366 case xmssmt_sha3-512_m64_w8_h20_d4_z: 3367 case xmssmt_sha3-512_m64_w8_h40_d2_z: 3368 case xmssmt_sha3-512_m64_w8_h40_d4_z: 3369 case xmssmt_sha3-512_m64_w8_h40_d8_z: 3370 case xmssmt_sha3-512_m64_w8_h60_d3_z: 3371 case xmssmt_sha3-512_m64_w8_h60_d6_z: 3372 case xmssmt_sha3-512_m64_w8_h60_d12_z: 3373 case xmssmt_sha3-512_m64_w16_h20_d2_z: 3374 case xmssmt_sha3-512_m64_w16_h20_d4_z: 3375 case xmssmt_sha3-512_m64_w16_h40_d2_z: 3376 case xmssmt_sha3-512_m64_w16_h40_d4_z: 3377 case xmssmt_sha3-512_m64_w16_h40_d8_z: 3378 case xmssmt_sha3-512_m64_w16_h60_d3_z: 3379 case xmssmt_sha3-512_m64_w16_h60_d6_z: 3380 case xmssmt_sha3-512_m64_w16_h60_d12_z: 3381 case xmssmt_sha3-512_m64_w4_h20_d2: 3382 case xmssmt_sha3-512_m64_w4_h20_d4: 3383 case xmssmt_sha3-512_m64_w4_h40_d2: 3384 case xmssmt_sha3-512_m64_w4_h40_d4: 3385 case xmssmt_sha3-512_m64_w4_h40_d8: 3386 case xmssmt_sha3-512_m64_w4_h60_d3: 3387 case xmssmt_sha3-512_m64_w4_h60_d6: 3389 case xmssmt_sha3-512_m64_w4_h60_d12: 3390 case xmssmt_sha3-512_m64_w8_h20_d2: 3391 case xmssmt_sha3-512_m64_w8_h20_d4: 3392 case xmssmt_sha3-512_m64_w8_h40_d2: 3393 case xmssmt_sha3-512_m64_w8_h40_d4: 3394 case xmssmt_sha3-512_m64_w8_h40_d8: 3395 case xmssmt_sha3-512_m64_w8_h60_d3: 3396 case xmssmt_sha3-512_m64_w8_h60_d6: 3397 case xmssmt_sha3-512_m64_w8_h60_d12: 3398 case xmssmt_sha3-512_m64_w16_h20_d2: 3399 case xmssmt_sha3-512_m64_w16_h20_d4: 3400 case xmssmt_sha3-512_m64_w16_h40_d2: 3401 case xmssmt_sha3-512_m64_w16_h40_d4: 3402 case xmssmt_sha3-512_m64_w16_h40_d8: 3403 case xmssmt_sha3-512_m64_w16_h60_d3: 3404 case xmssmt_sha3-512_m64_w16_h60_d6: 3405 case xmssmt_sha3-512_m64_w16_h60_d12: 3406 bytestring64 rand_m64; 3408 default: 3409 void; /* error condition */ 3410 }; 3412 struct xmss_reduced_bottom { 3413 xmss_ots_signature sig_ots; /* WOTS+ signature */ 3414 xmss_path nodes; /* authentication path */ 3415 }; 3417 /* Type for individual reduced XMSS signatures on higher layers */ 3419 union xmss_reduced_others (xmss_algorithm_type type) { 3420 case xmssmt_aes128_m32_w4_h20_d2: 3421 case xmssmt_aes128_m32_w4_h20_d4: 3422 bytestring16 xmss_reduced_n16_t88[88]; 3424 case xmssmt_aes128_m32_w4_h40_d2: 3425 case xmssmt_aes128_m32_w4_h40_d4: 3426 case xmssmt_aes128_m32_w4_h40_d8: 3427 bytestring16 xmss_reduced_n16_t108[108]; 3429 case xmssmt_aes128_m32_w4_h60_d3: 3430 case xmssmt_aes128_m32_w4_h60_d6: 3431 case xmssmt_aes128_m32_w4_h60_d12: 3432 bytestring16 xmss_reduced_n16_t128[128]; 3434 case xmssmt_aes128_m32_w8_h20_d2: 3435 case xmssmt_aes128_m32_w8_h20_d4: 3436 bytestring16 xmss_reduced_n16_t66[66]; 3438 case xmssmt_aes128_m32_w8_h40_d2: 3439 case xmssmt_aes128_m32_w8_h40_d4: 3440 case xmssmt_aes128_m32_w8_h40_d8: 3441 bytestring16 xmss_reduced_n16_t86[86]; 3443 case xmssmt_aes128_m32_w8_h60_d3: 3444 case xmssmt_aes128_m32_w8_h60_d6: 3445 case xmssmt_aes128_m32_w8_h60_d12: 3446 bytestring16 xmss_reduced_n16_t106[106]; 3448 case xmssmt_aes128_m32_w16_h20_d2: 3449 case xmssmt_aes128_m32_w16_h20_d4: 3450 bytestring16 xmss_reduced_n16_t55[55]; 3452 case xmssmt_aes128_m32_w16_h40_d2: 3453 case xmssmt_aes128_m32_w16_h40_d4: 3454 case xmssmt_aes128_m32_w16_h40_d8: 3455 bytestring16 xmss_reduced_n16_t75[75]; 3457 case xmssmt_aes128_m32_w16_h60_d3: 3458 case xmssmt_aes128_m32_w16_h60_d6: 3459 case xmssmt_aes128_m32_w16_h60_d12: 3460 bytestring16 xmss_reduced_n16_t95[95]; 3462 case xmssmt_sha3-256_m32_w4_h20_d2_z: 3463 case xmssmt_sha3-256_m32_w4_h20_d4_z: 3464 case xmssmt_sha3-256_m32_w4_h20_d2: 3465 case xmssmt_sha3-256_m32_w4_h20_d4: 3466 bytestring32 xmss_reduced_n32_t153[153]; 3468 case xmssmt_sha3-256_m32_w4_h40_d2_z: 3469 case xmssmt_sha3-256_m32_w4_h40_d4_z: 3470 case xmssmt_sha3-256_m32_w4_h40_d8_z: 3471 case xmssmt_sha3-256_m32_w4_h40_d2: 3472 case xmssmt_sha3-256_m32_w4_h40_d4: 3473 case xmssmt_sha3-256_m32_w4_h40_d8: 3474 bytestring32 xmss_reduced_n32_t173[173]; 3476 case xmssmt_sha3-256_m32_w4_h60_d3_z: 3477 case xmssmt_sha3-256_m32_w4_h60_d6_z: 3478 case xmssmt_sha3-256_m32_w4_h60_d12_z: 3479 case xmssmt_sha3-256_m32_w4_h60_d3: 3480 case xmssmt_sha3-256_m32_w4_h60_d6: 3481 case xmssmt_sha3-256_m32_w4_h60_d12: 3482 bytestring32 xmss_reduced_n32_t193[193]; 3484 case xmssmt_sha3-256_m32_w8_h20_d2_z: 3485 case xmssmt_sha3-256_m32_w8_h20_d4_z: 3487 case xmssmt_sha3-256_m32_w8_h20_d2: 3488 case xmssmt_sha3-256_m32_w8_h20_d4: 3489 bytestring32 xmss_reduced_n32_t110[110]; 3491 case xmssmt_sha3-256_m32_w8_h40_d2_z: 3492 case xmssmt_sha3-256_m32_w8_h40_d4_z: 3493 case xmssmt_sha3-256_m32_w8_h40_d8_z: 3494 case xmssmt_sha3-256_m32_w8_h40_d2: 3495 case xmssmt_sha3-256_m32_w8_h40_d4: 3496 case xmssmt_sha3-256_m32_w8_h40_d8: 3497 bytestring32 xmss_reduced_n32_t130[130]; 3499 case xmssmt_sha3-256_m32_w8_h60_d3_z: 3500 case xmssmt_sha3-256_m32_w8_h60_d6_z: 3501 case xmssmt_sha3-256_m32_w8_h60_d12_z: 3502 case xmssmt_sha3-256_m32_w8_h60_d3: 3503 case xmssmt_sha3-256_m32_w8_h60_d6: 3504 case xmssmt_sha3-256_m32_w8_h60_d12: 3505 bytestring32 xmss_reduced_n32_t150[150]; 3507 case xmssmt_sha3-256_m32_w16_h20_d2_z: 3508 case xmssmt_sha3-256_m32_w16_h20_d4_z: 3509 case xmssmt_sha3-256_m32_w16_h20_d2: 3510 case xmssmt_sha3-256_m32_w16_h20_d4: 3511 bytestring32 xmss_reduced_n32_t87[87]; 3513 case xmssmt_sha3-256_m32_w16_h40_d2_z: 3514 case xmssmt_sha3-256_m32_w16_h40_d4_z: 3515 case xmssmt_sha3-256_m32_w16_h40_d8_z: 3516 case xmssmt_sha3-256_m32_w16_h40_d2: 3517 case xmssmt_sha3-256_m32_w16_h40_d4: 3518 case xmssmt_sha3-256_m32_w16_h40_d8: 3519 bytestring32 xmss_reduced_n32_t107[107]; 3521 case xmssmt_sha3-256_m32_w16_h60_d3_z: 3522 case xmssmt_sha3-256_m32_w16_h60_d6_z: 3523 case xmssmt_sha3-256_m32_w16_h60_d12_z: 3524 case xmssmt_sha3-256_m32_w16_h60_d3: 3525 case xmssmt_sha3-256_m32_w16_h60_d6: 3526 case xmssmt_sha3-256_m32_w16_h60_d12: 3527 bytestring32 xmss_reduced_n32_t127[127]; 3529 case xmssmt_sha3-512_m64_w4_h20_d2_z: 3530 case xmssmt_sha3-512_m64_w4_h20_d4_z: 3531 case xmssmt_sha3-512_m64_w4_h20_d2: 3532 case xmssmt_sha3-512_m64_w4_h20_d4: 3533 bytestring64 xmss_reduced_n64_t281[281]; 3535 case xmssmt_sha3-512_m64_w4_h40_d2_z: 3536 case xmssmt_sha3-512_m64_w4_h40_d4_z: 3537 case xmssmt_sha3-512_m64_w4_h40_d8_z: 3538 case xmssmt_sha3-512_m64_w4_h40_d2: 3539 case xmssmt_sha3-512_m64_w4_h40_d4: 3540 case xmssmt_sha3-512_m64_w4_h40_d8: 3541 bytestring64 xmss_reduced_n64_t301[301]; 3543 case xmssmt_sha3-512_m64_w4_h60_d3_z: 3544 case xmssmt_sha3-512_m64_w4_h60_d6_z: 3545 case xmssmt_sha3-512_m64_w4_h60_d12_z: 3546 case xmssmt_sha3-512_m64_w4_h60_d3: 3547 case xmssmt_sha3-512_m64_w4_h60_d6: 3548 case xmssmt_sha3-512_m64_w4_h60_d12: 3549 bytestring64 xmss_reduced_n64_t321[321]; 3551 case xmssmt_sha3-512_m64_w8_h20_d2_z: 3552 case xmssmt_sha3-512_m64_w8_h20_d4_z: 3553 bytestring64 xmss_reduced_n64_t195[195]; 3555 case xmssmt_sha3-512_m64_w8_h40_d2_z: 3556 case xmssmt_sha3-512_m64_w8_h40_d4_z: 3557 case xmssmt_sha3-512_m64_w8_h40_d8_z: 3558 case xmssmt_sha3-512_m64_w8_h40_d2: 3559 case xmssmt_sha3-512_m64_w8_h40_d4: 3560 case xmssmt_sha3-512_m64_w8_h40_d8: 3561 bytestring64 xmss_reduced_n64_t215[215]; 3563 case xmssmt_sha3-512_m64_w8_h60_d3_z: 3564 case xmssmt_sha3-512_m64_w8_h60_d6_z: 3565 case xmssmt_sha3-512_m64_w8_h60_d12_z: 3566 case xmssmt_sha3-512_m64_w8_h60_d3: 3567 case xmssmt_sha3-512_m64_w8_h60_d6: 3568 case xmssmt_sha3-512_m64_w8_h60_d12: 3569 bytestring64 xmss_reduced_n64_t235[235]; 3571 case xmssmt_sha3-512_m64_w16_h20_d2_z: 3572 case xmssmt_sha3-512_m64_w16_h20_d4_z: 3573 case xmssmt_sha3-512_m64_w16_h20_d2: 3574 case xmssmt_sha3-512_m64_w16_h20_d4: 3575 bytestring64 xmss_reduced_n64_t151[151]; 3577 case xmssmt_sha3-512_m64_w16_h40_d2_z: 3578 case xmssmt_sha3-512_m64_w16_h40_d4_z: 3579 case xmssmt_sha3-512_m64_w16_h40_d8_z: 3580 case xmssmt_sha3-512_m64_w16_h40_d2: 3581 case xmssmt_sha3-512_m64_w16_h40_d4: 3582 case xmssmt_sha3-512_m64_w16_h40_d8: 3584 bytestring64 xmss_reduced_n64_t171[171]; 3586 case xmssmt_sha3-512_m64_w16_h60_d3_z: 3587 case xmssmt_sha3-512_m64_w16_h60_d6_z: 3588 case xmssmt_sha3-512_m64_w16_h60_d12_z: 3589 case xmssmt_sha3-512_m64_w16_h60_d3: 3590 case xmssmt_sha3-512_m64_w16_h60_d6: 3591 case xmssmt_sha3-512_m64_w16_h60_d12: 3592 bytestring64 xmss_reduced_n64_t191[191]; 3594 default: 3595 void; /* error condition */ 3596 }; 3598 /* xmss_reduced_array depends on d */ 3600 union xmss_reduced_array (xmss_algorithm_type type) { 3601 case xmssmt_sha3-256_m32_w4_h20_d2_z: 3602 case xmssmt_sha3-256_m32_w8_h20_d2_z: 3603 case xmssmt_sha3-256_m32_w16_h20_d2_z: 3604 case xmssmt_sha3-512_m64_w4_h20_d2_z: 3605 case xmssmt_sha3-512_m64_w8_h20_d2_z: 3606 case xmssmt_sha3-512_m64_w16_h20_d2_z: 3607 case xmssmt_aes128_m32_w4_h20_d2: 3608 case xmssmt_aes128_m32_w8_h20_d2: 3609 case xmssmt_aes128_m32_w16_h20_d2: 3610 case xmssmt_sha3-256_m32_w4_h20_d2: 3611 case xmssmt_sha3-256_m32_w8_h20_d2: 3612 case xmssmt_sha3-256_m32_w16_h20_d2: 3613 case xmssmt_sha3-512_m64_w4_h20_d2: 3614 case xmssmt_sha3-512_m64_w8_h20_d2: 3615 case xmssmt_sha3-512_m64_w16_h20_d2: 3616 case xmssmt_sha3-256_m32_w4_h40_d2_z: 3617 case xmssmt_sha3-256_m32_w8_h40_d2_z: 3618 case xmssmt_sha3-256_m32_w16_h40_d2_z: 3619 case xmssmt_sha3-512_m64_w4_h40_d2_z: 3620 case xmssmt_sha3-512_m64_w8_h40_d2_z: 3621 case xmssmt_sha3-512_m64_w16_h40_d2_z: 3622 case xmssmt_aes128_m32_w4_h40_d2: 3623 case xmssmt_aes128_m32_w8_h40_d2: 3624 case xmssmt_aes128_m32_w16_h40_d2: 3625 case xmssmt_sha3-256_m32_w4_h40_d2: 3626 case xmssmt_sha3-256_m32_w8_h40_d2: 3627 case xmssmt_sha3-512_m64_w4_h40_d2: 3628 case xmssmt_sha3-256_m32_w16_h40_d2: 3629 case xmssmt_sha3-512_m64_w8_h40_d2: 3630 case xmssmt_sha3-512_m64_w16_h40_d2: 3631 xmss_reduced_others xmss_red_arr_d2[1]; 3633 case xmssmt_sha3-256_m32_w4_h60_d3_z: 3634 case xmssmt_sha3-256_m32_w8_h60_d3_z: 3635 case xmssmt_sha3-256_m32_w16_h60_d3_z: 3636 case xmssmt_sha3-512_m64_w4_h60_d3_z: 3637 case xmssmt_sha3-512_m64_w8_h60_d3_z: 3638 case xmssmt_sha3-512_m64_w16_h60_d3_z: 3639 case xmssmt_aes128_m32_w4_h60_d3: 3640 case xmssmt_aes128_m32_w8_h60_d3: 3641 case xmssmt_aes128_m32_w16_h60_d3: 3642 case xmssmt_sha3-256_m32_w4_h60_d3: 3643 case xmssmt_sha3-256_m32_w8_h60_d3: 3644 case xmssmt_sha3-256_m32_w16_h60_d3: 3645 case xmssmt_sha3-512_m64_w4_h60_d3: 3646 case xmssmt_sha3-512_m64_w8_h60_d3: 3647 case xmssmt_sha3-512_m64_w16_h60_d3: 3648 xmss_reduced_others xmss_red_arr_d3[2]; 3650 case xmssmt_sha3-256_m32_w4_h20_d4_z: 3651 case xmssmt_sha3-256_m32_w8_h20_d4_z: 3652 case xmssmt_sha3-256_m32_w16_h20_d4_z: 3653 case xmssmt_sha3-512_m64_w4_h20_d4_z: 3654 case xmssmt_sha3-512_m64_w8_h20_d4_z: 3655 case xmssmt_sha3-512_m64_w16_h20_d4_z: 3656 case xmssmt_aes128_m32_w4_h20_d4: 3657 case xmssmt_aes128_m32_w8_h20_d4: 3658 case xmssmt_aes128_m32_w16_h20_d4: 3659 case xmssmt_sha3-256_m32_w4_h20_d4: 3660 case xmssmt_sha3-256_m32_w8_h20_d4: 3661 case xmssmt_sha3-256_m32_w16_h20_d4: 3662 case xmssmt_sha3-512_m64_w4_h20_d4: 3663 case xmssmt_sha3-512_m64_w8_h20_d4: 3664 case xmssmt_sha3-512_m64_w16_h20_d4: 3665 case xmssmt_sha3-256_m32_w4_h40_d4_z: 3666 case xmssmt_sha3-256_m32_w8_h40_d4_z: 3667 case xmssmt_sha3-256_m32_w16_h40_d4_z: 3668 case xmssmt_sha3-512_m64_w4_h40_d4_z: 3669 case xmssmt_sha3-512_m64_w8_h40_d4_z: 3670 case xmssmt_sha3-512_m64_w16_h40_d4_z: 3671 case xmssmt_aes128_m32_w4_h40_d4: 3672 case xmssmt_aes128_m32_w8_h40_d4: 3673 case xmssmt_aes128_m32_w16_h40_d4: 3674 case xmssmt_sha3-256_m32_w4_h40_d4: 3675 case xmssmt_sha3-256_m32_w8_h40_d4: 3676 case xmssmt_sha3-512_m64_w4_h40_d4: 3677 case xmssmt_sha3-256_m32_w16_h40_d4: 3678 case xmssmt_sha3-512_m64_w8_h40_d4: 3679 case xmssmt_sha3-512_m64_w16_h40_d4: 3680 xmss_reduced_others xmss_red_arr_d4[3]; 3682 case xmssmt_sha3-256_m32_w4_h60_d6_z: 3683 case xmssmt_sha3-256_m32_w8_h60_d6_z: 3684 case xmssmt_sha3-256_m32_w16_h60_d6_z: 3685 case xmssmt_sha3-512_m64_w4_h60_d6_z: 3686 case xmssmt_sha3-512_m64_w8_h60_d6_z: 3687 case xmssmt_sha3-512_m64_w16_h60_d6_z: 3688 case xmssmt_aes128_m32_w4_h60_d6: 3689 case xmssmt_aes128_m32_w8_h60_d6: 3690 case xmssmt_aes128_m32_w16_h60_d6: 3691 case xmssmt_sha3-256_m32_w4_h60_d6: 3692 case xmssmt_sha3-256_m32_w8_h60_d6: 3693 case xmssmt_sha3-256_m32_w16_h60_d6: 3694 case xmssmt_sha3-512_m64_w4_h60_d6: 3695 case xmssmt_sha3-512_m64_w8_h60_d6: 3696 case xmssmt_sha3-512_m64_w16_h60_d6: 3697 xmss_reduced_others xmss_red_arr_d6[5]; 3699 case xmssmt_sha3-256_m32_w4_h40_d8_z: 3700 case xmssmt_sha3-256_m32_w8_h40_d8_z: 3701 case xmssmt_sha3-256_m32_w16_h40_d8_z: 3702 case xmssmt_sha3-512_m64_w4_h40_d8_z: 3703 case xmssmt_sha3-512_m64_w8_h40_d8_z: 3704 case xmssmt_sha3-512_m64_w16_h40_d8_z: 3705 case xmssmt_aes128_m32_w4_h40_d8: 3706 case xmssmt_aes128_m32_w8_h40_d8: 3707 case xmssmt_aes128_m32_w16_h40_d8: 3708 case xmssmt_sha3-256_m32_w4_h40_d8: 3709 case xmssmt_sha3-256_m32_w8_h40_d8: 3710 case xmssmt_sha3-512_m64_w4_h40_d8: 3711 case xmssmt_sha3-256_m32_w16_h40_d8: 3712 case xmssmt_sha3-512_m64_w8_h40_d8: 3713 case xmssmt_sha3-512_m64_w16_h40_d8: 3714 xmss_reduced_others xmss_red_arr_d8[7]; 3716 case xmssmt_sha3-256_m32_w4_h60_d12_z: 3717 case xmssmt_sha3-256_m32_w8_h60_d12_z: 3718 case xmssmt_sha3-256_m32_w16_h60_d12_z: 3719 case xmssmt_sha3-512_m64_w4_h60_d12_z: 3720 case xmssmt_sha3-512_m64_w8_h60_d12_z: 3721 case xmssmt_sha3-512_m64_w16_h60_d12_z: 3722 case xmssmt_aes128_m32_w4_h60_d12: 3723 case xmssmt_aes128_m32_w8_h60_d12: 3724 case xmssmt_aes128_m32_w16_h60_d12: 3725 case xmssmt_sha3-256_m32_w4_h60_d12: 3726 case xmssmt_sha3-256_m32_w8_h60_d12: 3727 case xmssmt_sha3-256_m32_w16_h60_d12: 3728 case xmssmt_sha3-512_m64_w4_h60_d12: 3729 case xmssmt_sha3-512_m64_w8_h60_d12: 3731 case xmssmt_sha3-512_m64_w16_h60_d12: 3732 xmss_reduced_others xmss_red_arr_d12[11]; 3734 default: 3735 void; /* error condition */ 3736 }; 3738 /* XMSS^MT signature structure */ 3740 struct xmssmt_signature { 3741 /* WOTS+ key pair index */ 3742 idx_sig_xmssmt idx_sig; 3743 /* Random string for randomized hashing */ 3744 random_string_xmssmt randomness; 3745 /* Reduced bottom layer XMSS signature */ 3746 xmss_reduced_bottom; 3747 /* Array of reduced XMSS signatures with message length n */ 3748 xmss_reduced_array; 3749 }; 3751 When no bitmasks are used, XMSS^MT public keys are defined using XDR 3752 syntax as follows: 3754 /* Types for XMSS^MT root node */ 3756 union xmssmt_root switch (xmssmt_algorithm_type type) { 3757 case xmssmt_sha3-256_m32_w4_h20_d2_z: 3758 case xmssmt_sha3-256_m32_w4_h20_d4_z: 3759 case xmssmt_sha3-256_m32_w4_h40_d2_z: 3760 case xmssmt_sha3-256_m32_w4_h40_d4_z: 3761 case xmssmt_sha3-256_m32_w4_h40_d8_z: 3762 case xmssmt_sha3-256_m32_w4_h60_d3_z: 3763 case xmssmt_sha3-256_m32_w4_h60_d6_z: 3764 case xmssmt_sha3-256_m32_w4_h60_d12_z: 3765 case xmssmt_sha3-256_m32_w8_h20_d2_z: 3766 case xmssmt_sha3-256_m32_w8_h20_d4_z: 3767 case xmssmt_sha3-256_m32_w8_h40_d2_z: 3768 case xmssmt_sha3-256_m32_w8_h40_d4_z: 3769 case xmssmt_sha3-256_m32_w8_h40_d8_z: 3770 case xmssmt_sha3-256_m32_w8_h60_d3_z: 3771 case xmssmt_sha3-256_m32_w8_h60_d6_z: 3772 case xmssmt_sha3-256_m32_w8_h60_d12_z: 3773 case xmssmt_sha3-256_m32_w16_h20_d2_z: 3774 case xmssmt_sha3-256_m32_w16_h20_d4_z: 3775 case xmssmt_sha3-256_m32_w16_h40_d2_z: 3776 case xmssmt_sha3-256_m32_w16_h40_d4_z: 3778 case xmssmt_sha3-256_m32_w16_h40_d8_z: 3779 case xmssmt_sha3-256_m32_w16_h60_d3_z: 3780 case xmssmt_sha3-256_m32_w16_h60_d6_z: 3781 case xmssmt_sha3-256_m32_w16_h60_d12_z: 3782 bytestring32 root_n32; 3784 case xmssmt_sha3-512_m64_w4_h20_d2_z: 3785 case xmssmt_sha3-512_m64_w4_h20_d4_z: 3786 case xmssmt_sha3-512_m64_w4_h40_d2_z: 3787 case xmssmt_sha3-512_m64_w4_h40_d4_z: 3788 case xmssmt_sha3-512_m64_w4_h40_d8_z: 3789 case xmssmt_sha3-512_m64_w4_h60_d3_z: 3790 case xmssmt_sha3-512_m64_w4_h60_d6_z: 3791 case xmssmt_sha3-512_m64_w4_h60_d12_z: 3792 case xmssmt_sha3-512_m64_w8_h20_d2_z: 3793 case xmssmt_sha3-512_m64_w8_h20_d4_z: 3794 case xmssmt_sha3-512_m64_w8_h40_d2_z: 3795 case xmssmt_sha3-512_m64_w8_h40_d4_z: 3796 case xmssmt_sha3-512_m64_w8_h40_d8_z: 3797 case xmssmt_sha3-512_m64_w8_h60_d3_z: 3798 case xmssmt_sha3-512_m64_w8_h60_d6_z: 3799 case xmssmt_sha3-512_m64_w8_h60_d12_z: 3800 case xmssmt_sha3-512_m64_w16_h20_d2_z: 3801 case xmssmt_sha3-512_m64_w16_h20_d4_z: 3802 case xmssmt_sha3-512_m64_w16_h40_d2_z: 3803 case xmssmt_sha3-512_m64_w16_h40_d4_z: 3804 case xmssmt_sha3-512_m64_w16_h40_d8_z: 3805 case xmssmt_sha3-512_m64_w16_h60_d3_z: 3806 case xmssmt_sha3-512_m64_w16_h60_d6_z: 3807 case xmssmt_sha3-512_m64_w16_h60_d12_z: 3808 bytestring64 root_n64; 3810 default: 3811 void; /* error condition */ 3812 }; 3814 /* XMSS^MT public key structure */ 3816 struct xmssmt_public_key { 3817 xmssmt_root root; /* Root node */ 3818 }; 3820 When bitmasks are used, XMSS^MT public keys are defined using XDR 3821 syntax as follows: 3823 /* Types for XMSS^MT bitmasks */ 3824 union xmssmt_bm switch (xmssmt_algorithm_type type) { 3825 case xmssmt_aes128_m32_w4_h20_d2: 3826 case xmssmt_aes128_m32_w4_h40_d4: 3827 case xmssmt_aes128_m32_w4_h60_d6: 3828 bytestring16 bm_n16_t36[36]; 3830 case xmssmt_aes128_m32_w4_h60_d3: 3831 case xmssmt_aes128_m32_w4_h40_d2: 3832 bytestring16 bm_n16_t36[56]; 3834 case xmssmt_aes128_m32_w4_h20_d4: 3835 case xmssmt_aes128_m32_w4_h40_d8: 3836 case xmssmt_aes128_m32_w4_h60_d12: 3837 bytestring16 bm_n16_t26[26]; 3839 case xmssmt_aes128_m32_w8_h20_d2: 3840 case xmssmt_aes128_m32_w8_h40_d4: 3841 case xmssmt_aes128_m32_w8_h60_d6: 3842 case xmssmt_aes128_m32_w16_h20_d2: 3843 case xmssmt_aes128_m32_w16_h40_d4: 3844 case xmssmt_aes128_m32_w16_h60_d6: 3845 bytestring16 bm_n16_t34[34]; 3847 case xmssmt_aes128_m32_w8_h20_d4: 3848 case xmssmt_aes128_m32_w8_h40_d8: 3849 case xmssmt_aes128_m32_w8_h60_d12: 3850 case xmssmt_aes128_m32_w16_h20_d4: 3851 case xmssmt_aes128_m32_w16_h40_d8: 3852 case xmssmt_aes128_m32_w16_h60_d12: 3853 bytestring16 bm_n16_t24[24]; 3855 case xmssmt_aes128_m32_w8_h40_d2: 3856 case xmssmt_aes128_m32_w8_h60_d3: 3857 case xmssmt_aes128_m32_w16_h40_d2: 3858 case xmssmt_aes128_m32_w16_h60_d3: 3859 bytestring16 bm_n16_t54[54]; 3861 case xmssmt_sha3-256_m32_w4_h20_d2: 3862 case xmssmt_sha3-256_m32_w4_h40_d4: 3863 case xmssmt_sha3-256_m32_w4_h60_d6: 3864 bytestring32 bm_n32_t36[36]; 3866 case xmssmt_sha3-256_m32_w4_h20_d4: 3867 case xmssmt_sha3-256_m32_w4_h40_d8: 3868 case xmssmt_sha3-256_m32_w4_h60_d12: 3869 bytestring32 bm_n32_t26[26]; 3871 case xmssmt_sha3-256_m32_w4_h40_d2: 3873 case xmssmt_sha3-256_m32_w4_h60_d3: 3874 bytestring32 bm_n32_t56[56]; 3876 case xmssmt_sha3-256_m32_w8_h20_d2: 3877 case xmssmt_sha3-256_m32_w8_h40_d4: 3878 case xmssmt_sha3-256_m32_w8_h60_d6: 3879 case xmssmt_sha3-256_m32_w16_h20_d2: 3880 case xmssmt_sha3-256_m32_w16_h40_d4: 3881 case xmssmt_sha3-256_m32_w16_h60_d6: 3882 bytestring32 bm_n32_t34[34]; 3884 case xmssmt_sha3-256_m32_w8_h20_d4: 3885 case xmssmt_sha3-256_m32_w8_h40_d8: 3886 case xmssmt_sha3-256_m32_w8_h60_d12: 3887 case xmssmt_sha3-256_m32_w16_h20_d4: 3888 case xmssmt_sha3-256_m32_w16_h40_d8: 3889 case xmssmt_sha3-256_m32_w16_h60_d12: 3890 bytestring32 bm_n32_t24[24]; 3892 case xmssmt_sha3-256_m32_w8_h40_d2: 3893 case xmssmt_sha3-256_m32_w8_h60_d3: 3894 case xmssmt_sha3-256_m32_w16_h40_d2: 3895 case xmssmt_sha3-256_m32_w16_h60_d3: 3896 bytestring32 bm_n32_t54[54]; 3898 case xmssmt_sha3-512_m64_w4_h20_d2: 3899 case xmssmt_sha3-512_m64_w4_h40_d4: 3900 case xmssmt_sha3-512_m64_w4_h60_d6: 3901 bytestring64 bm_n64_t38[38]; 3903 case xmssmt_sha3-512_m64_w4_h20_d4: 3904 case xmssmt_sha3-512_m64_w4_h40_d8: 3905 case xmssmt_sha3-512_m64_w4_h60_d12: 3906 bytestring64 bm_n64_t28[28]; 3908 case xmssmt_sha3-512_m64_w4_h40_d2: 3909 case xmssmt_sha3-512_m64_w4_h60_d3: 3910 bytestring64 bm_n64_t58[58]; 3912 case xmssmt_sha3-512_m64_w8_h20_d2: 3913 case xmssmt_sha3-512_m64_w8_h40_d4: 3914 case xmssmt_sha3-512_m64_w8_h60_d6: 3915 case xmssmt_sha3-512_m64_w16_h20_d2: 3916 case xmssmt_sha3-512_m64_w16_h40_d4: 3917 case xmssmt_sha3-512_m64_w16_h60_d6: 3918 bytestring64 bm_n64_t36[36]; 3920 case xmssmt_sha3-512_m64_w8_h20_d4: 3922 case xmssmt_sha3-512_m64_w8_h40_d8: 3923 case xmssmt_sha3-512_m64_w8_h60_d12: 3924 case xmssmt_sha3-512_m64_w16_h20_d4: 3925 case xmssmt_sha3-512_m64_w16_h40_d8: 3926 case xmssmt_sha3-512_m64_w16_h60_d12: 3927 bytestring64 bm_n64_t26[26]; 3929 case xmssmt_sha3-512_m64_w8_h40_d2: 3930 case xmssmt_sha3-512_m64_w8_h60_d3: 3931 case xmssmt_sha3-512_m64_w16_h40_d2: 3932 case xmssmt_sha3-512_m64_w16_h60_d3: 3933 bytestring64 bm_n64_t56[56]; 3935 default: 3936 void; /* error condition */ 3937 }; 3939 /* Types for XMSS^MT root node */ 3941 union xmssmt_root switch (xmssmt_algorithm_type type) { 3942 case xmssmt_aes128_m32_w4_h20_d2: 3943 case xmssmt_aes128_m32_w4_h20_d4: 3944 case xmssmt_aes128_m32_w4_h40_d2: 3945 case xmssmt_aes128_m32_w4_h40_d4: 3946 case xmssmt_aes128_m32_w4_h40_d8: 3947 case xmssmt_aes128_m32_w4_h60_d3: 3948 case xmssmt_aes128_m32_w4_h60_d6: 3949 case xmssmt_aes128_m32_w4_h60_d12: 3950 case xmssmt_aes128_m32_w8_h20_d2: 3951 case xmssmt_aes128_m32_w8_h20_d4: 3952 case xmssmt_aes128_m32_w8_h40_d2: 3953 case xmssmt_aes128_m32_w8_h40_d4: 3954 case xmssmt_aes128_m32_w8_h40_d8: 3955 case xmssmt_aes128_m32_w8_h60_d3: 3956 case xmssmt_aes128_m32_w8_h60_d6: 3957 case xmssmt_aes128_m32_w8_h60_d12: 3958 case xmssmt_aes128_m32_w16_h20_d2: 3959 case xmssmt_aes128_m32_w16_h20_d4: 3960 case xmssmt_aes128_m32_w16_h40_d2: 3961 case xmssmt_aes128_m32_w16_h40_d4: 3962 case xmssmt_aes128_m32_w16_h40_d8: 3963 case xmssmt_aes128_m32_w16_h60_d3: 3964 case xmssmt_aes128_m32_w16_h60_d6: 3965 case xmssmt_aes128_m32_w16_h60_d12: 3966 bytestring16 root_n16; 3968 case xmssmt_sha3-256_m32_w4_h20_d2: 3969 case xmssmt_sha3-256_m32_w4_h20_d4: 3971 case xmssmt_sha3-256_m32_w4_h40_d2: 3972 case xmssmt_sha3-256_m32_w4_h40_d4: 3973 case xmssmt_sha3-256_m32_w4_h40_d8: 3974 case xmssmt_sha3-256_m32_w4_h60_d3: 3975 case xmssmt_sha3-256_m32_w4_h60_d6: 3976 case xmssmt_sha3-256_m32_w4_h60_d12: 3977 case xmssmt_sha3-256_m32_w8_h20_d2: 3978 case xmssmt_sha3-256_m32_w8_h20_d4: 3979 case xmssmt_sha3-256_m32_w8_h40_d2: 3980 case xmssmt_sha3-256_m32_w8_h40_d4: 3981 case xmssmt_sha3-256_m32_w8_h40_d8: 3982 case xmssmt_sha3-256_m32_w8_h60_d3: 3983 case xmssmt_sha3-256_m32_w8_h60_d6: 3984 case xmssmt_sha3-256_m32_w8_h60_d12: 3985 case xmssmt_sha3-256_m32_w16_h20_d2: 3986 case xmssmt_sha3-256_m32_w16_h20_d4: 3987 case xmssmt_sha3-256_m32_w16_h40_d2: 3988 case xmssmt_sha3-256_m32_w16_h40_d4: 3989 case xmssmt_sha3-256_m32_w16_h40_d8: 3990 case xmssmt_sha3-256_m32_w16_h60_d3: 3991 case xmssmt_sha3-256_m32_w16_h60_d6: 3992 case xmssmt_sha3-256_m32_w16_h60_d12: 3993 bytestring32 root_n32; 3995 case xmssmt_sha3-512_m64_w4_h20_d2: 3996 case xmssmt_sha3-512_m64_w4_h20_d4: 3997 case xmssmt_sha3-512_m64_w4_h40_d2: 3998 case xmssmt_sha3-512_m64_w4_h40_d4: 3999 case xmssmt_sha3-512_m64_w4_h40_d8: 4000 case xmssmt_sha3-512_m64_w4_h60_d3: 4001 case xmssmt_sha3-512_m64_w4_h60_d6: 4002 case xmssmt_sha3-512_m64_w4_h60_d12: 4003 case xmssmt_sha3-512_m64_w8_h20_d2: 4004 case xmssmt_sha3-512_m64_w8_h20_d4: 4005 case xmssmt_sha3-512_m64_w8_h40_d2: 4006 case xmssmt_sha3-512_m64_w8_h40_d4: 4007 case xmssmt_sha3-512_m64_w8_h40_d8: 4008 case xmssmt_sha3-512_m64_w8_h60_d3: 4009 case xmssmt_sha3-512_m64_w8_h60_d6: 4010 case xmssmt_sha3-512_m64_w8_h60_d12: 4011 case xmssmt_sha3-512_m64_w16_h20_d2: 4012 case xmssmt_sha3-512_m64_w16_h20_d4: 4013 case xmssmt_sha3-512_m64_w16_h40_d2: 4014 case xmssmt_sha3-512_m64_w16_h40_d4: 4015 case xmssmt_sha3-512_m64_w16_h40_d8: 4016 case xmssmt_sha3-512_m64_w16_h60_d3: 4017 case xmssmt_sha3-512_m64_w16_h60_d6: 4018 case xmssmt_sha3-512_m64_w16_h60_d12: 4020 bytestring64 root_n64; 4022 default: 4023 void; /* error condition */ 4024 }; 4026 /* XMSS^MT public key structure */ 4028 struct xmssmt_public_key { 4029 xmssmt_bm bm; /* Bitmasks */ 4030 xmssmt_root root; /* Root node */ 4031 }; 4033 Authors' Addresses 4035 Andreas Huelsing 4036 TU Eindhoven 4037 P.O. Box 513 4038 Eindhoven 5600 MB 4039 The Netherlands 4041 Email: a.t.huelsing@tue.nl 4043 Denis Butin 4044 TU Darmstadt 4045 Hochschulstrasse 10 4046 Darmstadt 64289 4047 Germany 4049 Email: dbutin@cdc.informatik.tu-darmstadt.de 4051 Stefan-Lukas Gazdag 4052 genua mbH 4053 Domagkstrasse 7 4054 Kirchheim bei Muenchen 85551 4055 Germany 4057 Email: stefan-lukas_gazdag@genua.eu 4058 Aziz Mohaisen 4059 Verisign Labs 4060 12061 Bluemont Way 4061 Reston, VA 20190 4063 Phone: +1 703 948-3200 4064 Email: amohaisen@verisign.com