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