RFC 8391
XMSS: eXtended Merkle Signature Scheme
RFC 8391: XMSS: eXtended Merkle Signature Scheme 🎀
Okay bestie, let's start with the title block 💅 It tells you who wrote this, what kind of document it is, and when it dropped:
- Series: Internet Research Task Force (IRTF) 🌈
- RFC number: 8391
- Category: Informational ✨
- ISSN: 2070-1721
- Date: May 2018 🍓
- Authors: A. Huelsing (TU Eindhoven), D. Butin (TU Darmstadt), S. Gazdag (genua GmbH), J. Rijneveld (Radboud University), and A. Mohaisen (University of Central Florida) 🫶
- Obsoletes / Updates: the title block doesn't list anything here, so this RFC doesn't obsolete or update any other document 🙈
Abstract
Okay so this one is all about the eXtended Merkle Signature Scheme (XMSS) 🔥 It's a hash-based digital signature system, and the whole design is built on stuff that's already been described in scientific literature. The doc specifies three things: WOTS+ (Winternitz One-Time Signature Plus), which is a one-time signature scheme 🦋; XMSS, the single-tree scheme; and XMSS^MT, the multi-tree version of XMSS 🧚 Both XMSS and XMSS^MT use WOTS+ as their main building block.
Here's the highkey iconic part 👑 XMSS gives you digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it's proven that it only depends on the properties of cryptographic hash functions. The security guarantees are strong, and it stays secure even if the collision resistance of the underlying hash function gets broken 😭 It's also suitable for compact implementations, it's relatively simple to implement, and it naturally resists side-channel attacks 💜
And the last bit is lowkey the main character moment ✨ Unlike most other signature systems, hash-based signatures can, so far, withstand known attacks that use quantum computers 🌸
Status of This Memo
Here's the tea 🫖 This document is not an Internet Standards Track specification. It's published for informational purposes only 💀
It's a product of the Internet Research Task Force (IRTF). The IRTF publishes the results of Internet-related research and development work, and those results might not be suitable for deployment 🙈 This RFC represents the consensus of the Crypto Forum Research Group of the IRTF 🫶 Documents approved for publication by the IRSG aren't candidates for any level of Internet Standard, so check Section 2 of RFC 7841 if you want the full story 🎀
If you want the current status of this document, any errata, or a way to send feedback, head to https://www.rfc-editor.org/info/rfc8391 🦋
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved. 🌈
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as they're in effect on the date this document was published. Please read those carefully, because they spell out your rights and restrictions for this document 💅
Table of Contents
1. Introduction ....................................................5
1.1. CFRG Note on Post-Quantum Cryptography .....................6
1.2. Conventions Used in This Document ..........................7
2. Notation ........................................................7
2.1. Data Types .................................................7
2.2. Functions ..................................................7
2.3. Operators ..................................................8
2.4. Integer-to-Byte Conversion .................................9
2.5. Hash Function Address Scheme ...............................9
2.6. Strings of Base w Numbers .................................12
2.7. Member Functions ..........................................13
3. Primitives .....................................................14
3.1. WOTS+: One-Time Signatures ................................14
3.1.1. WOTS+ Parameters ...................................14
3.1.1.1. WOTS+ Functions ...........................15
3.1.2. WOTS+ Chaining Function ............................15
3.1.3. WOTS+ Private Key ..................................16
3.1.4. WOTS+ Public Key ...................................17
3.1.5. WOTS+ Signature Generation .........................17
3.1.6. WOTS+ Signature Verification .......................19
3.1.7. Pseudorandom Key Generation ........................20
4. Schemes ........................................................20
4.1. XMSS: eXtended Merkle Signature Scheme ....................20
4.1.1. XMSS Parameters ....................................21
4.1.2. XMSS Hash Functions ................................22
4.1.3. XMSS Private Key ...................................22
4.1.4. Randomized Tree Hashing ............................23
4.1.5. L-Trees ............................................23
4.1.6. TreeHash ...........................................24
4.1.7. XMSS Key Generation ................................25
4.1.8. XMSS Signature .....................................27
4.1.9. XMSS Signature Generation ..........................28
4.1.10. XMSS Signature Verification .......................30
4.1.11. Pseudorandom Key Generation .......................32
4.1.12. Free Index Handling and Partial Private Keys ......33
4.2. XMSS^MT: Multi-Tree XMSS ..................................33
4.2.1. XMSS^MT Parameters .................................33
4.2.2. XMSS^MT Key Generation .............................33
4.2.3. XMSS^MT Signature ..................................36
4.2.4. XMSS^MT Signature Generation .......................37
4.2.5. XMSS^MT Signature Verification .....................39
4.2.6. Pseudorandom Key Generation ........................40
4.2.7. Free Index Handling and Partial Private Keys .......40
5. Parameter Sets .................................................40
5.1. Implementing the Functions ................................41
5.2. WOTS+ Parameters ..........................................43
5.3. XMSS Parameters ...........................................43
5.3.1. Parameter Guide ....................................44
5.4. XMSS^MT Parameters ........................................45
5.4.1. Parameter Guide ....................................47
6. Rationale ......................................................49
7. Reference Code .................................................50
8. IANA Considerations ............................................50
9. Security Considerations ........................................54
9.1. Security Proofs ...........................................55
9.2. Minimal Security Assumptions ..............................56
9.3. Post-Quantum Security .....................................56
10. References ....................................................57
10.1. Normative References .....................................57
10.2. Informative References ...................................58
Appendix A. WOTS+ XDR Formats ....................................60
A.1. WOTS+ Parameter Sets ......................................60
A.2. WOTS+ Signatures ..........................................60
A.3. WOTS+ Public Keys .........................................61
Appendix B. XMSS XDR Formats .....................................61
B.1. XMSS Parameter Sets .......................................61
B.2. XMSS Signatures ...........................................62
B.3. XMSS Public Keys ..........................................64
Appendix C. XMSS^MT XDR Formats ..................................65
C.1. XMSS^MT Parameter Sets ....................................65
C.2. XMSS^MT Signatures ........................................67
C.3. XMSS^MT Public Keys .......................................71
Acknowledgements ..................................................73
Authors' Addresses ................................................741. Introduction ✨
okay so bestie, let's start with the basics 🧚. A (cryptographic) digital signature scheme gives you asymmetric message authentication. The key generation algorithm makes a key pair: a private key and a public key 🔑. You sign a message with the private key to get a signature, and anyone with the public key can verify that message/signature pair. A One-Time Signature (OTS) scheme lets you use a key pair to sign exactly one message securely. A Many-Time Signature (MTS) system lets you sign multiple messages. Main character energy, obviously 👑.
OTS schemes, and MTS schemes built out of them, were proposed by Merkle in 1979 [Merkle83] 🕰️. They got a lot of attention in the 1990s, then came back into the spotlight from the mid 2000s onwards, mostly because they resist attacks from quantum computers 🌈. These are called hash-based signature schemes, since they're built out of a cryptographic hash function. The vibe: small private and public keys, fast signing and verifying ⚡, but big signatures and kinda slow key generation 🐢. They also fit into compact implementations really nicely, and they're naturally resistant to most kinds of side-channel attacks 🛡️.
A few people have already been doing the work to get hash-based signatures standardized 💅. Buchmann, Dahmen, and Huelsing proposed the eXtended Merkle Signature Scheme (XMSS) [BDH11], which is more efficient than Merkle's original scheme and has a modern security proof in the standard model 🎀. McGrew, Curcio, and Fluhrer wrote an Internet-Draft [MCF18] for the Leighton-Micali Signature (LMS) scheme. LMS builds on the seminal works by Lamport, Diffie, Winternitz, and Merkle, and it takes a different route from XMSS, relying entirely on security arguments in the random oracle model 🦋. Then really recently, the stateless hash-based signature scheme SPHINCS dropped [BHH15], aiming to be easier to deploy in current applications 🍓. The next logical move is finishing the specs for the basic algorithms: LMS, XMSS, SPHINCS, and/or variants 📝.
XMSS [BDH11] is the newest stateful hash-based signature scheme, and honestly it's iconic 😭. It has the smallest signatures of this family, and it comes with a multi-tree variant that fixes the slow key generation problem 🙌. It can also be shown that XMSS is secure while only making mild assumptions about the underlying hash function 🔒. Most importantly, the security of XMSS does not require the cryptographic hash function to be collision-resistant ✨. This note also covers the improvements to XMSS described in [HRS16] 🌸.
This document describes a single-tree and a multi-tree variant of XMSS 🌳. It also describes WOTS+, a variant of the Winternitz OTS scheme introduced in [Huelsing13], which XMSS uses 🧩. Everything is specified in enough detail that different implementations can interoperate 🫶.
Here's how the doc is laid out 🗺️. Notation is in Section 2. Section 3 covers the WOTS+ signature system. MTS schemes are in Section 4: XMSS in Section 4.1 and its multi-tree variant (XMSS^MT) in Section 4.2. Parameter sets are in Section 5. Section 6 explains the reasoning behind the choices in this note. Section 7 has info about the reference code. The IANA registry for these signature systems is in Section 8. And finally, Section 9 has the security considerations, which you do NOT skip 💀.
1.1. CFRG Note on Post-Quantum Cryptography ✨
Every post-quantum algorithm documented by the Crypto Forum Research Group (CFRG) is considered ready for experimentation and further engineering development today 🧪. Think of things like checking how performance and sizes affect IETF protocols 📊. Real talk though: at the time of writing, we don't have a lot of deployment experience with these algorithms yet 🙈.
A lot of them come with specific restrictions. For example, they might change the classical interface, or the proposed parameters might have had less cryptanalysis than established schemes 🧐. CFRG has consensus that every document describing post-quantum technologies should include the paragraph above, plus a clear extra warning about any specific restrictions, especially if those could affect how the scheme gets used or deployed ⚠️. That guidance can change over time through document updates 🔄.
Also, for XMSS:
CFRG consensus is that we're confident in the cryptographic security of the signature schemes in this document against quantum computers, based on what the research community currently knows about quantum algorithms 🔮. Honestly, we're confident that a big chunk of the Internet could depend on the signature schemes defined here, as long as developers take care of the following 💖.
Here's the twist 🌀. Unlike traditional signature schemes, these signature schemes are stateful, which means the secret key changes over time 🔁. If a secret key state gets used twice, there are no cryptographic security guarantees left. As a result, forging a signature on a new message becomes feasible 😱. This is a brand new property that most developers won't be familiar with, so secret keys need really careful handling 🔐. Developers should not use the schemes described here except in systems that prevent the reuse of secret key states 🚫.
Stateful means the key state is part of the danger zone. Reusing a state is basically handing out the keys to the castle 🏰💀.
Being stateful also means classical APIs for digital signatures can't be used without modification 🛠️. The API MUST be able to handle a secret key state. In particular, that means the API MUST allow returning an updated secret key state 🔑✨.
1.2. Conventions Used in This Document 📚
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🎀. Lowercase versions don't count, so they're just regular words 💅.
2. Notation 🔤
2.1. Data Types 🧱
Bytes and byte strings are the fundamental data types 🧩. A byte is a sequence of eight bits. A single byte is written as a pair of hexadecimal digits with a leading "0x". A byte string is an ordered sequence of zero or more bytes, written as an ordered sequence of hexadecimal characters with a leading "0x". For example, 0xe534f0 is a byte string of length 3 🧮. An array of byte strings is an ordered, indexed set that starts at index 0, and every byte string in it has the same length 📏. We assume big-endian representation for any data types or structures 🌊.
2.2. Functions 🎯
If x is a non-negative real number, then we define the following functions:
ceil(x): returns the smallest integer greater than or equal to x.
floor(x): returns the largest integer less than or equal to x.
lg(x): returns the logarithm to base 2 of x.2.3. Operators ➕
When a and b are integers, the mathematical operators work like this:
^ : a ^ b denotes the result of a raised to the power of b.
* : a * b denotes the product of a and b. This operator is
sometimes omitted in the absence of ambiguity, as in usual
mathematical notation.
/ : a / b denotes the quotient of a by non-zero b.
% : a % b denotes the non-negative remainder of the integer
division of a by b.
+ : a + b denotes the sum of a and b.
- : a - b denotes the difference of a and b.
++ : a++ denotes incrementing a by 1, i.e., a = a + 1.
<< : a << b denotes a logical left shift with b being non-
negative, i.e., a * 2^b.
>> : a >> b denotes a logical right shift with b being non-
negative, i.e., floor(a / 2^b).The standard order of operations is used when evaluating arithmetic expressions 🧠.
Arrays work the usual way: the i^th element of an array A is written A[i] 📦. Byte strings get treated as arrays of bytes whenever that's needed. If X is a byte string, then X[i] is its i^th byte, and X[0] is the leftmost byte 👈.
If A and B are byte strings of equal length, then:
- A AND B is the bitwise logical conjunction operation 🤝.
- A XOR B is the bitwise logical exclusive disjunction operation 💫.
When B is a byte and i is an integer, B >> i is the logical right-shift operation ➡️.
If X is an x-byte string and Y is a y-byte string, then X || Y is the concatenation of X and Y, meaning:
X || Y = X[0] ... X[x-1] Y[0] ... Y[y-1]2.4. Integer-to-Byte Conversion 🔢
If x and y are non-negative integers, we define Z = toByte(x, y) as the y-byte string containing the binary representation of x in big-endian byte order 🌸.
2.5. Hash Function Address Scheme 🦋
okay so the schemes in this doc randomize EVERY single hash function call 💅 aside from the initial message digest, each call gets its own key and its own bitmask. bestie these come from a pseudorandom function that takes a key SEED and a 32-byte address ADRS as input and spits out an n-byte value, where n is the security parameter ✨. this section explains how ADRS is built and suggests some setter methods to tweak it. we'll see how the addresses get generated later, wherever they're actually used 🌸
the next two sections use two kinds of hash functions, both parameterized by the security parameter n 🔥. for the hash tree constructions, the function maps an n-byte key and 2n-byte inputs to n-byte outputs, so randomizing it takes 3n bytes total: n for the key and 2n for a bitmask 💖. for the OTS scheme constructions, the function maps n-byte keys and n-byte inputs to n-byte outputs, and randomizing it takes 2n bytes: n for the key and n for the bitmask 🎀. so yeah, three addresses for the first function and two for the second one 👑
there are three types of addresses for three different use cases 🧚. one type is for hashes in OTS schemes, one is for hashes inside the main Merkle tree construction, and one is for hashes in the L-trees (the ones that compress one-time public keys) 🌈. they all share as much format as possible, which is very cute of them. the rest of this section breaks each type down 🫶
the address is word-aligned, and a word is 32 bits in this context 💜. only the tree address is too long for one word, but it fits in a double word 🍓. an address always starts with a layer address (one word, in the most significant bits), followed by a tree address (two words) ✨. both of those are needed for the multi-tree variant (see Section 4.2) and describe where a tree sits inside a multi-tree 🦋. in single-tree applications they're just set to zero 🌸. for multi-tree hash-based signatures, the layer address tells you the height of a tree within the multi-tree, starting at height zero for the trees at the bottom layer 💅. the tree address tells you the position of a tree within its layer, starting at index zero for the leftmost tree 🎀. the next word defines the type of the address: 0 for an OTS address, 1 for an L-tree address, and 2 for a hash tree address 💖. whenever the type word changes, all the words after it should be initialized to 0, so no random non-zero values sneak into the unused padding words 😭
first up, the OTS address case 🌸. the type word is followed by an OTS address word, which encodes the index of the OTS key pair within the tree 💅. then comes a chain address word, followed by a word that encodes the address of the hash function call within the chain 🧚. the last word, called keyAndMask, is what lets you generate two different addresses for one hash function call. set it to zero to generate the key, and set it to one to generate the n-byte bitmask 👑
+-------------------------+
| layer address (32 bits)|
+-------------------------+
| tree address (64 bits)|
+-------------------------+
| type = 0 (32 bits)|
+-------------------------+
| OTS address (32 bits)|
+-------------------------+
| chain address (32 bits)|
+-------------------------+
| hash address (32 bits)|
+-------------------------+
| keyAndMask (32 bits)|
+-------------------------+
An OTS Hash Addressnow the L-tree case, where the type word is set to one 🦋. the type word is followed by an L-tree address word, which encodes the index of the leaf computed with this L-tree 🌈. the next word encodes the height of the node that gets fed into the next computation inside the L-tree 🍓. the word after that encodes the index of that node at that height, inside the L-tree ✨. this time the keyAndMask word is used to generate three different addresses for one function call 🔥. set it to zero to generate the key. to generate the most significant n bytes of the 2n-byte bitmask, set it to one. the least significant bytes come from the address with the word set to two 💜
+-------------------------+
| layer address (32 bits)|
+-------------------------+
| tree address (64 bits)|
+-------------------------+
| type = 1 (32 bits)|
+-------------------------+
| L-tree address (32 bits)|
+-------------------------+
| tree height (32 bits)|
+-------------------------+
| tree index (32 bits)|
+-------------------------+
| keyAndMask (32 bits)|
+-------------------------+
An L-tree Addresslast but not least, the remaining type for the main tree hash addresses 🎀. here the type word is set to two, followed by one word of zero padding 🧚. the next word encodes the height of the tree node being fed into the next computation, followed by a word that encodes that node's index at that height 💖. same as the L-tree addresses, the keyAndMask word does triple duty: zero for the key, one for the most significant n bytes of the 2n-byte bitmask, and two for the least significant bytes 🌸
+-------------------------+
| layer address (32 bits)|
+-------------------------+
| tree address (64 bits)|
+-------------------------+
| type = 2 (32 bits)|
+-------------------------+
| Padding = 0 (32 bits)|
+-------------------------+
| tree height (32 bits)|
+-------------------------+
| tree index (32 bits)|
+-------------------------+
| keyAndMask (32 bits)|
+-------------------------+
A Hash Tree Addressevery field in these addresses encodes an unsigned integer 💅. when we describe how addresses get generated, we use setter methods that take positive integers and write their binary representation into the field, padded out to the field's length ✨. we also assume that setType() zeroes out the four words right after the type word 🫶
2.6. Strings of Base w Numbers 🌈
a byte string can be seen as a string of base w numbers, which are integers in the set {0, ... , w - 1} 💜. the correspondence is defined by the function base_w(X, w, out_len) (Algorithm 1) 🦋. so if X is a len_X-byte string and w is a member of the set {4, 16}, then base_w(X, w, out_len) outputs an array of out_len integers, each between 0 and w - 1 🍓. the length out_len is REQUIRED to be less than or equal to 8 * len_X / lg(w) 🔥. ngl this is the kind of math that looks scary but is actually just bit-shuffling 💅
Algorithm 1: base_w
Input: len_X-byte string X, int w, output length out_len
Output: out_len int array basew
int in = 0;
int out = 0;
unsigned int total = 0;
int bits = 0;
int consumed;
for ( consumed = 0; consumed < out_len; consumed++ ) {
if ( bits == 0 ) {
total = X[in];
in++;
bits += 8;
}
bits -= lg(w);
basew[out] = (total >> bits) AND (w - 1);
out++;
}
return basew;for example, if X is the (big-endian) byte string 0x1234, then base_w(X, 16, 4) returns the array a = {1, 2, 3, 4} 🎀. look at how the bits get chopped up 👇
X (represented as bits)
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
X[0] | X[1]
X (represented as base 16 numbers)
+-----------+-----------+-----------+-----------+
| 1 | 2 | 3 | 4 |
+-----------+-----------+-----------+-----------+
base_w(X, 16, 4)
+-----------+-----------+-----------+-----------+
| 1 | 2 | 3 | 4 |
+-----------+-----------+-----------+-----------+
a[0] a[1] a[2] a[3]
base_w(X, 16, 3)
+-----------+-----------+-----------+
| 1 | 2 | 3 |
+-----------+-----------+-----------+
a[0] a[1] a[2]
base_w(X, 16, 2)
+-----------+-----------+
| 1 | 2 |
+-----------+-----------+
a[0] a[1]
Example2.7. Member Functions 💖
to keep the algorithm descriptions tidy, we just assume member functions exist 🧚. if a complex data structure like a public key PK contains a value X, then getX(PK) returns the value of X for that public key 🌸. likewise, setX(PK, X, Y) sets the value X in PK to whatever value Y holds 🦋. since camelCase is used for member function names, a value z can be referred to as Z in the function name, like getZ 💅
3. Primitives ✨
3.1. WOTS+: One-Time Signatures 🔥
this section describes the WOTS+ system in a way that's similar to [Huelsing13] 🌈. WOTS+ is an OTS scheme, which means a private key can technically be used to sign any message, BUT each private key MUST be used only once to sign a single message 💀. if a private key ends up signing two different messages, the scheme becomes insecure 😭
this section kicks off by explaining the parameters 🎀. after that we get the so-called chaining function, which is the main building block of WOTS+ 💜. then comes a description of the algorithms for key generation, signing, and verification 🍓. finally, we talk about pseudorandom key generation 👑
3.1.1. WOTS+ Parameters ✨
okay so WOTS+ runs on just two params, n and w, and both have to be positive integers 🎀 Here's the rundown:
n: the message length, and also the length (in bytes) of a private key, public key, or signature element.w: the Winternitz parameter. It has to be a member of the set{4, 16}.
From those two we get len, len_1, and len_2 💅
len = len_1 + len_2
len_1 = ceil(8n / lg(w))
len_2 = floor(lg(len_1 * (w - 1)) / lg(w)) + 1len is the number of n-byte string elements in a WOTS+ private key, public key, and signature.
The value of n comes from whichever cryptographic hash function you pick for WOTS+. You pick that hash for its security level, and n is the input length the signing algorithm can handle. It's often the length of a message digest 🦋 w can be 4 or 16, and here's the tea: a bigger w gives you shorter signatures but slower signing, and it barely changes security. The values are limited to 4 and 16 because those hit the best trade-offs and are easy to implement 💖
WOTS+ params are implicitly included in algorithm inputs whenever they're needed 🧚
3.1.1.1. WOTS+ Functions 🌸
The WOTS+ algorithm uses a keyed cryptographic hash function F. F takes in and spits out byte strings of length n, using keys of length n. You'll find specific instantiations in Section 5, and the security requirements on F are covered in Section 9. WOTS+ also uses a pseudorandom function PRF. PRF takes an n-byte key and a 32-byte index, and it generates pseudorandom outputs of length n. Specific instantiations are in Section 5 again, and its security requirements are in Section 9 too 🫶
3.1.2. WOTS+ Chaining Function 🔥
The chaining function (Algorithm 2) computes one iteration of F on an n-byte input, using outputs of PRF. It takes an OTS hash address as input. That address has its first six 32-bit words set to encode the address of this chain. For each iteration, PRF makes a key for F and a bitmask, and the bitmask gets XORed into the intermediate result before F processes it. Here, ADRS is a 32-byte OTS hash address as specified in Section 2.5, and SEED is an n-byte string. To make the keys and bitmasks, PRF gets called with SEED as the key and ADRS as the input.
The chaining function takes an n-byte string X, a start index i, a number of steps s, plus ADRS and SEED. What it returns is the value you get by iterating F s times on input X, using the outputs of PRF ✨
Algorithm 2: chain - Chaining Function
Input: Input string X, start index i, number of steps s,
seed SEED, address ADRS
Output: value of F iterated s times on X
if ( s == 0 ) {
return X;
}
if ( (i + s) > (w - 1) ) {
return NULL;
}
byte[n] tmp = chain(X, i, s - 1, SEED, ADRS);
ADRS.setHashAddress(i + s - 1);
ADRS.setKeyAndMask(0);
KEY = PRF(SEED, ADRS);
ADRS.setKeyAndMask(1);
BM = PRF(SEED, ADRS);
tmp = F(KEY, tmp XOR BM);
return tmp;3.1.3. WOTS+ Private Key 🔐
The private key in WOTS+ is called sk (s for secret). It's a length len array of n-byte strings. This private key MUST be only used to sign at most one message, so don't you dare reuse it bestie 💀 Each n-byte string MUST either be selected randomly from the uniform distribution or be selected using a cryptographically secure pseudorandom procedure. If you go the pseudorandom route, the security of that procedure MUST at least match the WOTS+ parameters you're using. For more on pseudorandom key generation, check Section 3.1.7. Algorithm 3 below shows how to generate sk 🌈
Algorithm 3: WOTS_genSK - Generating a WOTS+ Private Key
Input: No input
Output: WOTS+ private key sk
for ( i = 0; i < len; i++ ) {
initialize sk[i] with a uniformly random n-byte string;
}
return sk;3.1.4. WOTS+ Public Key 💜
A WOTS+ key pair defines a virtual structure made of len hash chains, each of length w. The len n-byte strings in the private key each act as the start node for one hash chain. The public key is made of the end nodes of those chains, so like the private key, it's also a length len array of n-byte strings. To compute each hash chain, you use the chaining function (Algorithm 2). The calling algorithm has to provide an OTS hash address ADRS and a seed SEED. That address encodes where the WOTS+ key pair sits inside a bigger structure, so a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. Also, SEED is public information, so a verifier has it too 🙈 Algorithm 4 generates the public key pk from the private key sk.
Algorithm 4: WOTS_genPK - Generating a WOTS+ Public Key From a Private Key
Input: WOTS+ private key sk, address ADRS, seed SEED
Output: WOTS+ public key pk
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS);
}
return pk;3.1.5. WOTS+ Signature Generation 🖋️
A WOTS+ signature is a length len array of n-byte strings. To make one, you map the message to len integers between 0 and w - 1. First, the message gets turned into len_1 base w numbers with the base_w function from Section 2.6. Then a checksum gets computed and tacked onto the end as len_2 base w numbers, again using base_w. Heads up: the checksum can reach a max integer value of len_1 * (w - 1) * 2^8, so it depends on n and w. For the parameter sets in Section 5, a 32-bit unsigned integer can hold the checksum. If you use other parameter settings, the variable holding the checksum's integer value MUST be sufficiently large. Each base w integer picks one node from a different hash chain, and the signature is those selected nodes stuck together 🎀
Same deal as before: the calling algorithm provides an OTS hash address ADRS and a seed SEED. The address encodes where the key pair lives in a bigger structure, so a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. SEED is public and a verifier can see it too. Algorithm 5 shows the signature generation, where M is the message and sig is the resulting signature.
Algorithm 5: WOTS_sign - Generating a signature from a private key and a message
Input: Message M, WOTS+ private key sk, address ADRS, seed SEED
Output: WOTS+ signature sig
csum = 0;
// Convert message to base w
msg = base_w(M, w, len_1);
// Compute checksum
for ( i = 0; i < len_1; i++ ) {
csum = csum + w - 1 - msg[i];
}
// Convert csum to base w
csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS);
}
return sig;Here's how a signature is laid out 🦋
+---------------------------------+
| |
| sig_ots[0] | n bytes
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| sig_ots[len - 1] | n bytes
| |
+---------------------------------+
WOTS+ Signature3.1.6. WOTS+ Signature Verification 👀
To verify a signature sig on a message M, the verifier computes a WOTS+ public key value from the signature. You do that by "completing" the chain computations that start from the signature values, using the base w values of the message hash and its checksum. This step is called WOTS_pkFromSig, and it's in Algorithm 6 below. Next, the result of WOTS_pkFromSig gets compared to the given public key. If they match, the signature is accepted. Otherwise, the signature MUST be rejected. The calling algorithm again provides an OTS hash address ADRS and a seed SEED. That address encodes where the key pair sits inside a bigger structure, so a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. And yep, SEED is public information that a verifier can see too 🧚
Algorithm 6: WOTS_pkFromSig - Computing a WOTS+ public key from a message and its signature
Input: Message M, WOTS+ signature sig, address ADRS, seed SEED
Output: 'Temporary' WOTS+ public key tmp_pk
csum = 0;
// Convert message to base w
msg = base_w(M, w, len_1);
// Compute checksum
for ( i = 0; i < len_1; i++ ) {
csum = csum + w - 1 - msg[i];
}
// Convert csum to base w
csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS);
}
return tmp_pk;Heads up: XMSS uses WOTS_pkFromSig to compute a public key value, but it holds off on the comparison until a later point 💅
3.1.7. Pseudorandom Key Generation 🌟
An implementation MAY use a cryptographically secure pseudorandom method to generate the private key from a single n-byte value. For example, the method suggested in [BDH11] and explained below MAY be used, and other methods MAY be used too. Which pseudorandom method you choose doesn't affect interoperability, but the cryptographic strength MUST match the WOTS+ parameters you're using 🔥
Why bother? Because you only have to store that one n-byte string instead of the whole private key, and you can regenerate the key whenever you need it. Here's the method from [BDH11], described with PRF. During key generation, you sample a uniformly random n-byte string S from a secure source of randomness. S gets stored as the private key. The private key elements are computed as sk[i] = PRF(S, toByte(i, 32)) whenever they're needed. Please note that this seed S MUST be different from the seed SEED used to randomize the hash function calls. Also, this seed S MUST be kept secret. And the seed S MUST NOT be a low entropy, human-memorable value, since private key elements are derived from S deterministically and their confidentiality is security-critical 🫶
4. Schemes ✨
okay so this section is where the fun really starts 🌸 we're going to look at the eXtended Merkle Signature Scheme (XMSS), built on top of WOTS+. there are two flavors: a single-tree one (XMSS) and a multi-tree one (XMSS^MT) 💅 both let you squish a huge pile of WOTS+ key pairs under one tiny public key 🦋 the big new ingredient is a binary hash tree, and the difference is that XMSS uses one tree while XMSS^MT uses a tree of XMSS key pairs 🌈
4.1. XMSS: eXtended Merkle Signature Scheme
okay bestie, XMSS is a way to sign a big-but-fixed number of messages 🎀 it's based on the Merkle signature scheme and it uses four crypto ingredients: WOTS+ as the one-time signature method, two extra hash functions called H and H_msg, and a pseudorandom function PRF 💜 the lowkey iconic part is that XMSS with WOTS+ doesn't rely on the collision resistance of the hash functions, it leans on weaker properties instead 🙈 every XMSS key pair is hooked to a perfect binary tree, and every node holds an n-byte value 🌳 each leaf holds a special tree hash of a WOTS+ public key value. each non-leaf node is made by concatenating its two children, XORing with a bitmask, and then running the keyed hash function H on the result ✨ the bitmasks and H's keys come from a public seed (which lives in the public key) via PRF 🔑 and the root value of the tree plus the seed together make up the XMSS public key 👑
so to make a key pair that can sign 2^h messages, you use a tree of height h 🧚 XMSS is stateful, which means the private key changes every time you sign 😭 to stop anyone reusing a one-time key, the WOTS+ key pairs get numbered from 0 to (2^h) - 1 by their leaf, starting from index 0 on the leftmost leaf 🍓 the private key holds an index that ticks up with each signature, so it always points at the next unused WOTS+ key pair 💖
a signature is made of three things: the index of the WOTS+ key pair used, the WOTS+ signature on the message, and the so-called authentication path 🦋 the authentication path is a list of tree nodes that let a verifier work out the root starting from the WOTS+ signature 🧩 the verifier computes the root and checks it against the matching value in the XMSS public key, and if they match, the signature is declared valid ✅ the XMSS private key is all the WOTS+ private keys plus the current index 🗝️ to save storage, a pseudorandom key generation procedure (as described in [BDH11]) MAY be used 🌸 and the security of whatever method you pick MUST at least match the security of the XMSS instance 🔥
4.1.1. XMSS Parameters
XMSS has these parameters, and they're giving very organized ✨
h: the height (number of levels - 1) of the treen: the length in bytes of the message digest as well as each nodew: the Winternitz parameter as defined for WOTS+ in Section 3.1
there are 2^h leaves in the tree 🌿
for XMSS and XMSS^MT, private and public keys are called SK (S for secret) and PK 🔐 for WOTS+, they're sk (s for secret) and pk 🗝️ XMSS and XMSS^MT signatures are called Sig, and WOTS+ signatures are called sig 💜
XMSS and XMSS^MT parameters get included in algorithm inputs whenever they're needed, so you don't have to hunt for them 🫶
4.1.2. XMSS Hash Functions
besides the cryptographic hash function F and the pseudorandom function PRF that WOTS+ needs, XMSS uses two more functions 🎀
- A cryptographic hash function H. H takes n-byte keys and byte strings of length 2n, and returns an n-byte string. 🌈
- A cryptographic hash function H_msg. H_msg takes 3n-byte keys and byte strings of arbitrary length, and returns an n-byte string. 💅
more detail on specific instantiations is in Section 5, and the security requirements for H and H_msg are discussed in Section 9 📚
4.1.3. XMSS Private Key
an XMSS private key SK holds 2^h WOTS+ private keys, plus the leaf index idx of the next WOTS+ private key that hasn't been used yet 🌸 it also has SK_PRF (an n-byte key for making pseudorandom values for randomized message hashing), the n-byte value root (the root node of the tree, which is also SEED), and the n-byte public seed used to pseudorandomly generate bitmasks and hash function keys ✨ root and SEED are formally only part of the public key, but they're needed for things like signature generation, so they're also required for functions that don't take the public key as input 💖
the leaf index idx starts at zero when the XMSS private key is created 🍼 the key SK_PRF MUST be sampled from a secure source of randomness that follows the uniform distribution 🔐 the WOTS+ private keys MUST be generated as described in Section 3.1 🗝️ or, to keep the private key size down, a cryptographic pseudorandom method MUST be used, as discussed in Section 4.1.11 🌟 SEED is a uniformly random n-byte string 🎲 even though SEED is public, it's critical for security that it comes from a good entropy source 😭 the root node gets generated as described below in the key generation section (Section 4.1.7), which also has an example algorithm for generating the private and public keys together 🧚
for the algorithm descriptions that follow, we assume there's a method getWOTS_SK(SK, i) 🪄 it takes an XMSS private key SK and an integer i, and outputs the i^th WOTS+ private key of SK 💜
4.1.4. Randomized Tree Hashing
to make things more readable, we introduce a function RAND_HASH(LEFT, RIGHT, SEED, ADRS) (Algorithm 7) that does the randomized hashing in the tree 🌳 it takes two n-byte values, LEFT and RIGHT, which are the left and right halves of the hash function input, plus the seed SEED (used as the key for PRF) and the address ADRS of this hash call 📍 RAND_HASH first uses PRF with SEED and ADRS to generate a key KEY and two n-byte bitmasks, BM_0 and BM_1 🎭 then it returns the randomized hash H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)) 🦋
Algorithm 7: RAND_HASH
Input: n-byte value LEFT, n-byte value RIGHT, seed SEED,
address ADRS
Output: n-byte randomized hash
ADRS.setKeyAndMask(0);
KEY = PRF(SEED, ADRS);
ADRS.setKeyAndMask(1);
BM_0 = PRF(SEED, ADRS);
ADRS.setKeyAndMask(2);
BM_1 = PRF(SEED, ADRS);
return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));4.1.5. L-Trees
to compute the leaves of the binary hash tree, we use a so-called L-tree 🌿 an L-tree is an unbalanced binary hash tree, which is distinct but similar to the main XMSS binary hash tree 🧩 the algorithm ltree (Algorithm 8) takes a WOTS+ public key pk and compresses it down to a single n-byte value, pk[0] 🫧 it also takes an L-tree address ADRS, which encodes the address of the L-tree, and the seed SEED 💜
Algorithm 8: ltree
Input: WOTS+ public key pk, address ADRS, seed SEED
Output: n-byte compressed public key value pk[0]
unsigned int len' = len;
ADRS.setTreeHeight(0);
while ( len' > 1 ) {
for ( i = 0; i < floor(len' / 2); i++ ) {
ADRS.setTreeIndex(i);
pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS);
}
if ( len' % 2 == 1 ) {
pk[floor(len' / 2)] = pk[len' - 1];
}
len' = ceil(len' / 2);
ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
}
return pk[0];4.1.6. TreeHash
for computing the internal n-byte nodes of a Merkle tree, the subroutine treeHash (Algorithm 9) takes an XMSS private key SK (including the seed SEED) 🔑 an unsigned integer s (the start index), an unsigned integer t (the target node height), and an address ADRS that encodes the address of the containing tree 📦 node height in a tree is counted from the leaves, which start at height zero 🌱 treeHash returns the root node of a tree of height t, with the leftmost leaf being the hash of the WOTS+ pk with index s 🌳 it is REQUIRED that s % 2^t = 0, meaning the leaf at index s has to be the leftmost leaf of a sub-tree of height t 🚨 otherwise the hash-addressing scheme fails 💀 the treeHash algorithm described here uses a stack that holds up to (t - 1) nodes, with the usual stack functions push() and pop() 🥞 we also assume that each node's height (an unsigned integer) is stored alongside its value (an n-byte string) on the stack 🧠
Algorithm 9: treeHash
Input: XMSS private key SK, start index s, target node height t,
address ADRS
Output: n-byte root node - top node on Stack
if( s % (1 << t) != 0 ) return -1;
for ( i = 0; i < 2^t; i++ ) {
SEED = getSEED(SK);
ADRS.setType(0); // Type = OTS hash address
ADRS.setOTSAddress(s + i);
pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
ADRS.setType(1); // Type = L-tree address
ADRS.setLTreeAddress(s + i);
node = ltree(pk, SEED, ADRS);
ADRS.setType(2); // Type = hash tree address
ADRS.setTreeHeight(0);
ADRS.setTreeIndex(i + s);
while ( Top node on Stack has same height t' as node ) {
ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
}
Stack.push(node);
}
return Stack.pop();4.1.7. XMSS Key Generation 🔑✨
Okay bestie, so the XMSS key pair gets made the way XMSS_keyGen (Algorithm 10) lays it out 💅. The public key PK is the root of the binary hash tree plus the SEED, and both of those also get stored in SK. The root is computed with treeHash. XMSS only has one main tree, so the address starts out as all zeros 🌸. We don't define any specific format or handling for the XMSS private key SK here. This is just a super basic (and very inefficient 💀) example of how you could start one.
Algorithm 10: XMSS_keyGen - Generate an XMSS key pair
Input: No input
Output: XMSS private key SK, XMSS public key PK
// Example initialization for SK-specific contents
idx = 0;
for ( i = 0; i < 2^h; i++ ) {
wots_sk[i] = WOTS_genSK();
}
initialize SK_PRF with a uniformly random n-byte string;
setSK_PRF(SK, SK_PRF);
// Initialization for common contents
initialize SEED with a uniformly random n-byte string;
setSEED(SK, SEED);
setWOTS_SK(SK, wots_sk));
ADRS = toByte(0, 32);
root = treeHash(SK, 0, h, ADRS);
SK = idx || wots_sk || SK_PRF || root || SEED;
PK = OID || root || SEED;
return (SK || PK);The above is just an example algorithm, so take it as a vibe check and not the final answer 🫶. It is strongly RECOMMENDED to use pseudorandom key generation to reduce the private key size, and that's the move ✨. Public and private key generation MAY be interleaved to save space 🧚. Especially when a pseudorandom method is used to generate the private key, generation MAY be done right when the respective WOTS+ key pair is needed by treeHash 🦋.
Here's how the public key is laid out:
+---------------------------------+
| algorithm OID |
+---------------------------------+
| |
| root node | n bytes
| |
+---------------------------------+
| |
| SEED | n bytes
| |
+---------------------------------+
XMSS Public Key4.1.8. XMSS Signature 🖊️💜
An XMSS signature is a (4 + n + (len + h) * n)-byte string 🍓. It's made up of:
- the index idx_sig of the used WOTS+ key pair (
4bytes), - a byte string r used for randomized message hashing (
nbytes), - a WOTS+ signature sig_ots (
len * nbytes), and - the so-called authentication path 'auth' for the leaf associated with the used WOTS+ key pair (
h * nbytes).
The authentication path is an array of h n-byte strings 🌈. It holds the siblings of the nodes on the path from the used leaf up to the root. It does NOT hold the nodes on the path itself, which is a key detail 👑. A verifier needs these nodes to compute a root node for the tree from the WOTS+ public key. A node is addressed by its position in the tree. Node(x, y) means the y^th node on level x, where y = 0 is the leftmost node on a level. The leaves live on level 0, and the root lives on level h. An authentication path has exactly one node on every layer 0 <= x <= (h - 1). For the i^th WOTS+ key pair (counting from zero), the j^th authentication path node is:
Node(j, floor(i / (2^j)) XOR 1)We'll get into how this path is computed in Section 4.1.9 🫶.
The data format for a signature looks like this:
+---------------------------------+
| |
| index idx_sig | 4 bytes
| |
+---------------------------------+
| |
| randomness r | n bytes
| |
+---------------------------------+
| |
| WOTS+ signature sig_ots | len * n bytes
| |
+---------------------------------+
| |
| auth[0] | n bytes
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| auth[h - 1] | n bytes
| |
+---------------------------------+
XMSS Signature4.1.9. XMSS Signature Generation 🔥🌸
So to compute the XMSS signature of a message M with an XMSS private key, the signer first computes a randomized message digest. It uses a random value r, idx_sig (the index of the WOTS+ key pair to be used), and the root value from the public key as the key 🧚. Then a WOTS+ signature of the message digest gets computed using the next unused WOTS+ private key. After that, the authentication path gets computed. Finally, the private key gets updated, meaning idx gets incremented. An implementation MUST NOT output the signature before the private key is updated 🚨. Don't skip that step, bestie!
The order here is a big deal: the private key update has to happen before the signature comes out. Iykyk 🙈
The node values of the authentication path MAY be computed in any way 🦋. This computation is assumed to be handled by the subroutine buildAuth for the function XMSS_sign (Algorithm 12). The speediest option is to store all tree nodes and fill the array in the signature by copying the respective nodes. The least storage-intensive option is to recompute all nodes for each signature online using the treeHash algorithm (Algorithm 9). There are several algorithms in between, with different time/storage trade-offs. For an overview, check [BDS09]. A further approach can be found in [KMN14]. The details of this procedure don't matter for interoperability, and you don't need to know any of them to do signature verification 🌈. The version of buildAuth below is included for completeness. It's a simple example for understanding, but extremely inefficient 😭. Using one of the alternative algorithms is strongly RECOMMENDED 👑.
Given an XMSS private key SK, all nodes in a tree are determined, and their values are defined in terms of treeHash (Algorithm 9). So you can compute the authentication path like this:
(Example) buildAuth - Compute the authentication path for the i^th
WOTS+ key pair
Input: XMSS private key SK, WOTS+ key pair index i, ADRS
Output: Authentication path auth
for ( j = 0; j < h; j++ ) {
k = floor(i / (2^j)) XOR 1;
auth[j] = treeHash(SK, k * 2^j, j, ADRS);
}We split the signature generation into two main algorithms ✂️. The first one, treeSig (Algorithm 11), makes the main part of an XMSS signature, and it's also used by the multi-tree variant XMSS^MT. XMSS_sign (Algorithm 12) calls treeSig, but it handles the message compression before and the private key update afterwards 💖.
The algorithm treeSig (Algorithm 11) calculates the WOTS+ signature on an n-byte message and the matching authentication path. It takes as input an n-byte message M', an XMSS private key SK, a signature index idx_sig, and an address ADRS. It returns the concatenation of the WOTS+ signature sig_ots and the authentication path auth.
Algorithm 11: treeSig - Generate a WOTS+ signature on a message with
corresponding authentication path
Input: n-byte message M', XMSS private key SK,
signature index idx_sig, ADRS
Output: Concatenation of WOTS+ signature sig_ots and
authentication path auth
auth = buildAuth(SK, idx_sig, ADRS);
ADRS.setType(0); // Type = OTS hash address
ADRS.setOTSAddress(idx_sig);
sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
M', getSEED(SK), ADRS);
Sig = sig_ots || auth;
return Sig;The algorithm XMSS_sign (Algorithm 12) calculates an updated private key SK and a signature on a message M. It takes as input a message M of arbitrary length and an XMSS private key SK, and it returns the byte string containing the concatenation of the updated private key SK and the signature Sig ✨.
Algorithm 12: XMSS_sign - Generate an XMSS signature and update the
XMSS private key
Input: Message M, XMSS private key SK
Output: Updated SK, XMSS signature Sig
idx_sig = getIdx(SK);
setIdx(SK, idx_sig + 1);
ADRS = toByte(0, 32);
byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32));
byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M);
Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS);
return (SK || Sig);4.1.10. XMSS Signature Verification ✨
okay so verifying an XMSS signature is basically a detective move 🕵️♀️ first you recompute the message digest using the randomness r, the index idx_sig, the root from PK, and the message M. Then you rebuild the used WOTS+ public key pk_ots from the WOTS+ signature with WOTS_pkFromSig. That WOTS+ public key gets turned into its leaf using an L-tree, and the leaf, plus idx_sig and the authentication path auth, gives you an alternative root for the tree. The verification succeeds if and only if that computed root matches the one in the XMSS public key. In any other case, it MUST return fail 💀
As for signature generation, we split verification into two parts so it can be reused in the XMSS^MT description 🔁 The steps XMSS^MT also needs are done by the function XMSS_rootFromSig (Algorithm 13). XMSS_verify (Algorithm 14) calls XMSS_rootFromSig as a subroutine and handles the XMSS-specific stuff.
The main part of XMSS signature verification happens in XMSS_rootFromSig (Algorithm 13), which is up next 👀 It takes an index idx_sig, a WOTS+ signature sig_ots, an authentication path auth, an n-byte message M', a seed SEED, and an address ADRS. It returns an n-byte string holding the value of the root of the tree defined by those inputs.
Algorithm 13: XMSS_rootFromSig - Compute a root node from a tree signature
Input: index idx_sig, WOTS+ signature sig_ots, authentication path
auth, n-byte message M', seed SEED, address ADRS
Output: n-byte root value node[0]
ADRS.setType(0); // Type = OTS hash address
ADRS.setOTSAddress(idx_sig);
pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS);
ADRS.setType(1); // Type = L-tree address
ADRS.setLTreeAddress(idx_sig);
byte[n][2] node;
node[0] = ltree(pk_ots, SEED, ADRS);
ADRS.setType(2); // Type = hash tree address
ADRS.setTreeIndex(idx_sig);
for ( k = 0; k < h; k++ ) {
ADRS.setTreeHeight(k);
if ( (floor(idx_sig / (2^k)) % 2) == 0 ) {
ADRS.setTreeIndex(ADRS.getTreeIndex() / 2);
node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS);
} else {
ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS);
}
node[0] = node[1];
}
return node[0];The full XMSS signature verification is shown below (Algorithm 14) 🎀 It handles message compression, hands the root computation off to XMSS_rootFromSig, and compares the result with the value in the public key. XMSS_verify takes an XMSS signature Sig, a message M, and an XMSS public key PK. It returns true if and only if Sig is a valid signature on M under public key PK. Otherwise, it returns false.
Algorithm 14: XMSS_verify - Verify an XMSS signature using the corresponding XMSS public key and a message
Input: XMSS signature Sig, message M, XMSS public key PK
Output: Boolean
ADRS = toByte(0, 32);
byte[n] M' = H_msg(r || getRoot(PK) || (toByte(idx_sig, n)), M);
byte[n] node = XMSS_rootFromSig(idx_sig, sig_ots, auth, M',
getSEED(PK), ADRS);
if ( node == getRoot(PK) ) {
return true;
} else {
return false;
}4.1.11. Pseudorandom Key Generation 🌈
An implementation MAY use a cryptographically secure pseudorandom method to generate the XMSS private key from a single n-byte value. For example, the method suggested in [BDH11] and explained below MAY be used. Other methods, such as the one in [HRS16], MAY be used too. Picking a pseudorandom method doesn't affect interoperability, but the cryptographic strength MUST match that of the XMSS parameters being used 🔐
For XMSS, a method similar to the one for WOTS+ can be used 🧁 The suggested method from [BDH11] can be described using PRF. During key generation, a uniformly random n-byte string S is sampled from a secure source of randomness. This seed S MUST NOT be confused with the public seed SEED. The seed S MUST be independent of SEED, and because it's the main secret, it MUST be kept secret 🤫 This seed S is used to generate an n-byte value S_ots for each WOTS+ key pair. The n-byte value S_ots can then be used to compute the matching WOTS+ private key using the method described in Section 3.1.7. The seeds for the WOTS+ key pairs are computed as S_ots[i] = PRF(S, toByte(i, 32)), where i is the index of the WOTS+ key pair. The nice part is that a WOTS+ key can be computed using only len + 1 evaluations of PRF once S is given ✨
4.1.12. Free Index Handling and Partial Private Keys 🧩
Some applications might need partial private keys or copies of private keys. Examples include load balancing and delegation of signing rights, or proxy signatures. Such applications MAY use their own key format and MAY use a signing algorithm different from the one described above 🙌 The index in partial private keys or copies of a private key MAY be manipulated however the application needs. However, applications MUST establish means that guarantee each index, and thereby each WOTS+ key pair, is used to sign only a single message. This is non-negotiable bestie 🚨
4.2. XMSS^MT: Multi-Tree XMSS 🌳
XMSS^MT is a method for signing a large but fixed number of messages 💖 It was first described in [HRB13] and it builds on XMSS. XMSS^MT uses a tree of several layers of XMSS trees, which is called a hypertree. The trees on the top and intermediate layers are used to sign the root nodes of the trees on the layer right below them. Trees on the lowest layer are used to sign the actual messages. All XMSS trees have equal height.
Consider an XMSS^MT tree of total height h that has d layers of XMSS trees, each of height h / d. Then layer d - 1 contains one XMSS tree, layer d - 2 contains 2^(h / d) XMSS trees, and so on. Finally, layer 0 contains 2^(h - h / d) XMSS trees 🪜
4.2.1. XMSS^MT Parameters 📋
In addition to all the XMSS parameters, an XMSS^MT system needs the number of tree layers d, given as an integer that divides h without remainder. The same tree height h / d and the same Winternitz parameter w are used for all tree layers.
All the trees on higher layers sign root nodes of other trees, and those root nodes are n-byte strings. So no message compression is needed, and WOTS+ is used to sign the root nodes themselves instead of their hash values 🧠
4.2.2. XMSS^MT Key Generation 🔑
An XMSS^MT private key SK_MT (S for secret) consists of one reduced XMSS private key for each XMSS tree. These reduced XMSS private keys just contain the WOTS+ private keys for that XMSS key pair. They do NOT contain a pseudorandom function key, index, public seed, or root node 🙅♀️ Instead, SK_MT holds a single n-byte pseudorandom function key SK_PRF, a single (ceil(h / 8))-byte index idx_MT, a single n-byte seed SEED, and a single root value root (the root of the one tree on the top layer). The index is a global index over all WOTS+ key pairs of all XMSS trees on layer 0. It starts at 0 and stores the index of the last used WOTS+ key pair on the bottom layer, so it's a number between 0 and 2^h - 1.
The reduced XMSS private keys MUST either be generated as described in Section 4.1.3 or be generated using a cryptographic pseudorandom method as discussed in Section 4.2.6. As with XMSS, the PRF key SK_PRF MUST be sampled from a secure source of randomness that follows the uniform distribution. SEED is generated as a uniformly random n-byte string. Even though SEED is public, it's critical for security that it comes from a good entropy source 🫶 The root is the root node of the single XMSS tree on the top layer, and its computation is explained below. As with XMSS, root and SEED are public information and would classically be considered part of the public key. But since both are needed for signing, which only takes the private key, they're also part of SK_MT 💜
This document does not define a specific format for the XMSS^MT private key SK_MT, because it's not required for interoperability 🤷♀️ Algorithms 15 and 16 use a function getXMSS_SK(SK, x, y) that outputs the reduced private key of the x^th XMSS tree on the y^th layer.
The XMSS^MT public key PK_MT contains the root of the single XMSS tree on layer d - 1 and the seed SEED. These are the same values as in the private key SK_MT. The pseudorandom function PRF, keyed with SEED, is used to generate the bitmasks and keys for all XMSS trees. XMSSMT_keyGen (Algorithm 15) shows example pseudocode for generating SK_MT and PK_MT. The n-byte root node of the top-layer tree is computed using treeHash. The algorithm XMSSMT_keyGen outputs an XMSS^MT private key SK_MT and an XMSS^MT public key PK_MT. The algorithm below gives an example of how the reduced XMSS private keys can be generated. However, any of the methods mentioned above is acceptable, as long as the cryptographic strength of the method used matches or beats that of the XMSS^MT parameter set 🌸
Algorithm 15: XMSSMT_keyGen - Generate an XMSS^MT key pair
Input: No input
Output: XMSS^MT private key SK_MT, XMSS^MT public key PK_MT
// Example initialization
idx_MT = 0;
setIdx(SK_MT, idx_MT);
initialize SK_PRF with a uniformly random n-byte string;
setSK_PRF(SK_MT, SK_PRF);
initialize SEED with a uniformly random n-byte string;
setSEED(SK_MT, SEED);
// Generate reduced XMSS private keys
ADRS = toByte(0, 32);
for ( layer = 0; layer < d; layer++ ) {
ADRS.setLayerAddress(layer);
for ( tree = 0; tree <
(1 << ((d - 1 - layer) * (h / d)));
tree++ ) {
ADRS.setTreeAddress(tree);
for ( i = 0; i < 2^(h / d); i++ ) {
wots_sk[i] = WOTS_genSK();
}
setXMSS_SK(SK_MT, wots_sk, tree, layer);
}
}
SK = getXMSS_SK(SK_MT, 0, d - 1);
setSEED(SK, SEED);
root = treeHash(SK, 0, h / d, ADRS);
setRoot(SK_MT, root);
PK_MT = OID || root || SEED;
return (SK_MT || PK_MT);The above is just an example algorithm. It is strongly RECOMMENDED to use pseudorandom key generation to reduce the private key size 🌟 Public and private key generation MAY be interleaved to save space. In particular, when a pseudorandom method is used to generate the private key, generation MAY be delayed until the respective WOTS+ key pair is needed by another algorithm 🦋
The format of an XMSS^MT public key is shown below 🧚
+---------------------------------+
| algorithm OID |
+---------------------------------+
| |
| root node | n bytes
| |
+---------------------------------+
| |
| SEED | n bytes
| |
+---------------------------------+
XMSS^MT Public Key4.2.3. XMSS^MT Signature ✨
okay so an XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) + n + (h + d * len) * n) 🎀. it's made up of:
- the index
idx_sigof the used WOTS+ key pair on the bottom layer (ceil(h / 8)bytes), - a byte string
rused for randomized message hashing (nbytes), and dreduced XMSS signatures ((h / d + len) * nbytes each).
the reduced XMSS signatures only contain a WOTS+ signature sig_ots and an authentication path auth. they contain no index idx and no byte string r 💅. bestie, look at how neatly it's laid out:
+---------------------------------+
| |
| index idx_sig | ceil(h / 8) bytes
| |
+---------------------------------+
| |
| randomness r | n bytes
| |
+---------------------------------+
| |
| (reduced) XMSS signature Sig | (h / d + len) * n bytes
| (bottom layer 0) |
| |
+---------------------------------+
| |
| (reduced) XMSS signature Sig | (h / d + len) * n bytes
| (layer 1) |
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| (reduced) XMSS signature Sig | (h / d + len) * n bytes
| (layer d - 1) |
| |
+---------------------------------+
XMSS^MT Signature4.2.4. XMSS^MT Signature Generation 🦋
so to compute the XMSS^MT signature Sig_MT of a message M using an XMSS^MT private key SK_MT, XMSSMT_sign (Algorithm 16, described below) uses treeSig from Section 4.1.9. first, the signature index is set to idx_sig. next, PRF is used to compute a pseudorandom n-byte string r. this n-byte string, idx_sig, and the root node from PK_MT are then used to compute a randomized message digest of length n. the message digest is signed using the WOTS+ key pair on the bottom layer with absolute index idx. the authentication path for the WOTS+ key pair and the root of the containing XMSS tree are computed. the root is signed by the parent XMSS tree. this keeps going until the top tree is reached ✨.
Algorithm 16: XMSSMT_sign - Generate an XMSS^MT signature and update the XMSS^MT private key
Input: Message M, XMSS^MT private key SK_MT
Output: Updated SK_MT, signature Sig_MT
// Init
ADRS = toByte(0, 32);
SEED = getSEED(SK_MT);
SK_PRF = getSK_PRF(SK_MT);
idx_sig = getIdx(SK_MT);
// Update SK_MT
setIdx(SK_MT, idx_sig + 1);
// Message compression
byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32));
byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
// Sign
Sig_MT = idx_sig;
unsigned int idx_tree
= (h - h / d) most significant bits of idx_sig;
unsigned int idx_leaf = (h / d) least significant bits of idx_sig;
SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF
|| toByte(0, n) || SEED;
ADRS.setLayerAddress(0);
ADRS.setTreeAddress(idx_tree);
Sig_tmp = treeSig(M', SK, idx_leaf, ADRS);
Sig_MT = Sig_MT || r || Sig_tmp;
for ( j = 1; j < d; j++ ) {
root = treeHash(SK, 0, h / d, ADRS);
idx_leaf = (h / d) least significant bits of idx_tree;
idx_tree = (h - j * (h / d)) most significant bits of idx_tree;
SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF
|| toByte(0, n) || SEED;
ADRS.setLayerAddress(j);
ADRS.setTreeAddress(idx_tree);
Sig_tmp = treeSig(root, SK, idx_leaf, ADRS);
Sig_MT = Sig_MT || Sig_tmp;
}
return SK_MT || Sig_MT;algorithm 16 is only one way to compute XMSS^MT signatures!! there are time-memory trade-offs that let you cut the signing time to less than the signing time of an XMSS scheme with tree height h / d. these trade-offs 1) stop certain values from being recomputed several times by keeping a state, and 2) spread all the computations over all signature generations. the details are in [Huelsing13a] 📚.
4.2.5. XMSS^MT Signature Verification 💜
XMSS^MT signature verification (Algorithm 17) can be summarized as d XMSS signature verifications with small changes 🔥. first, the message is hashed. the XMSS signatures are then all on n-byte values. second, instead of comparing the computed root node to a given value, a signature on this root node is verified. only the root node of the top tree is compared to the value in the XMSS^MT public key. XMSSMT_verify uses XMSS_rootFromSig. the function getXMSSSignature(Sig_MT, i) returns the ith reduced XMSS signature from the XMSS^MT signature Sig_MT. XMSSMT_verify takes as input an XMSS^MT signature Sig_MT, a message M, and a public key PK_MT. XMSSMT_verify returns true if and only if Sig_MT is a valid signature on M under public key PK_MT. otherwise, it returns false.
Algorithm 17: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a message M using an XMSS^MT public key PK_MT
Input: XMSS^MT signature Sig_MT, message M,
XMSS^MT public key PK_MT
Output: Boolean
idx_sig = getIdx(Sig_MT);
SEED = getSEED(PK_MT);
ADRS = toByte(0, 32);
byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT)
|| (toByte(idx_sig, n)), M);
unsigned int idx_leaf
= (h / d) least significant bits of idx_sig;
unsigned int idx_tree
= (h - h / d) most significant bits of idx_sig;
Sig' = getXMSSSignature(Sig_MT, 0);
ADRS.setLayerAddress(0);
ADRS.setTreeAddress(idx_tree);
byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
getAuth(Sig'), M', SEED, ADRS);
for ( j = 1; j < d; j++ ) {
idx_leaf = (h / d) least significant bits of idx_tree;
idx_tree = (h - j * h / d) most significant bits of idx_tree;
Sig' = getXMSSSignature(Sig_MT, j);
ADRS.setLayerAddress(j);
ADRS.setTreeAddress(idx_tree);
node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
getAuth(Sig'), node, SEED, ADRS);
}
if ( node == getRoot(PK_MT) ) {
return true;
} else {
return false;
}4.2.6. Pseudorandom Key Generation 🌸
like for XMSS, an implementation MAY use a cryptographically secure pseudorandom method to generate the XMSS^MT private key from a single n-byte value. for example, the method explained below MAY be used. other methods, such as the one in [HRS16], MAY be used. the choice of a pseudorandom method does not affect interoperability, but the cryptographic strength MUST match that of the used XMSS^MT parameters 🫶.
for XMSS^MT, a method similar to the one for XMSS and WOTS+ can be used. the method uses PRF. during key generation, a uniformly random n-byte string S_MT is sampled from a secure source of randomness. this seed S_MT is used to generate one n-byte value S for each XMSS key pair. this n-byte value can be used to compute the respective XMSS private key using the method described in Section 4.1.11. let S[x][y] be the seed for the xth XMSS private key on layer y. the seeds are computed as S[x][y] = PRF(PRF(S, toByte(y, 32)), toByte(x, 32)).
4.2.7. Free Index Handling and Partial Private Keys 🧚
the content of Section 4.1.12 also applies to XMSS^MT.
5. Parameter Sets 👑
this section gives basic parameter sets that are assumed to cover most relevant applications 💖. parameter sets for two classical security levels are defined. parameters with n = 32 provide a classical security level of 256 bits. parameters with n = 64 provide a classical security level of 512 bits. considering quantum-computer-aided attacks, these output sizes yield post-quantum security of 128 and 256 bits, respectively.
while this document specifies several parameter sets, an implementation is only REQUIRED to provide support for verification of all REQUIRED parameter sets. the REQUIRED parameter sets all use SHA2-256 to instantiate all functions. the REQUIRED parameter sets are only distinguished by the tree height parameter h (which determines the number of signatures that can be done with a single key pair) and the number of layers d (which defines a trade-off between speed and signature size). an implementation MAY provide support for signature generation using any of the proposed parameter sets. for convenience, this document defines a default option for XMSS (XMSS_SHA2_20_256) and XMSS^MT (XMSSMT-SHA2_60/3_256). these are supposed to match the most generic requirements 🌈.
5.1. Implementing the Functions ✨
Okay so for n = 32 there are two flavours. The SHA2-256 sets use SHA2-256 from [FIPS180], and the other sets use the SHA3/Keccak extendable-output function SHAKE-128 from [FIPS202]. For n = 64 it's the same deal: SHA2-512 from [FIPS180] for some sets, and SHAKE-256 from [FIPS202] for the rest 🌈
The SHA2-256 parameter sets are mandatory for deployment, so they MUST be provided by any implementation 💖 Everything else in this doc is OPTIONAL, so you're free to skip those if you don't need them 🫶
SHA2 doesn't have a keyed mode of its own, so we build the keyed hash functions by hand. Here's how it goes for SHA2 with n = 32:
F: SHA2-256(toByte(0, 32) || KEY || M),
H: SHA2-256(toByte(1, 32) || KEY || M),
H_msg: SHA2-256(toByte(2, 32) || KEY || M), and
PRF: SHA2-256(toByte(3, 32) || KEY || M).And for SHA2 with n = 64 it's:
F: SHA2-512(toByte(0, 64) || KEY || M),
H: SHA2-512(toByte(1, 64) || KEY || M),
H_msg: SHA2-512(toByte(2, 64) || KEY || M), and
PRF: SHA2-512(toByte(3, 64) || KEY || M).So why the n-byte padding? Two reasons, bestie 🎀 First, the internal compression function needs 2n-byte blocks, but the keys are only n and 3n bytes long, so the padding fills that gap. Second, it keeps the different function families independent of each other. And the PRF is a special case: since its message length is fixed, a full HMAC isn't needed, and standard length extension attacks aren't a concern here. That's why the simpler construction above is enough 💅
SHA3 gets similar treatment. For SHA3 with n = 32:
F: SHAKE128(toByte(0, 32) || KEY || M, 256),
H: SHAKE128(toByte(1, 32) || KEY || M, 256),
H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256),
PRF: SHAKE128(toByte(3, 32) || KEY || M, 256).And for SHA3 with n = 64:
F: SHAKE256(toByte(0, 64) || KEY || M, 512),
H: SHAKE256(toByte(1, 64) || KEY || M, 512),
H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512),
PRF: SHAKE256(toByte(3, 64) || KEY || M, 512).Just like with SHA2, every function family gets its own n-byte identifier so they stay independent 🦋 A shorter identifier would also work with SHA3, but we're using n bytes anyway so everything matches the SHA2 versions. Consistency is iconic ✨
5.2. WOTS+ Parameters 🌸
To fully describe a WOTS+ signature method, you MUST specify the parameters n and w, plus the functions F and PRF. The table below defines a few WOTS+ signature systems, each with its own name. The naming goes like WOTSP-[Hashfamily]_[n in bits]. We don't put w in the name because every parameter set here uses w=16. The len values are included just for convenience 💜
+-----------------+----------+----+----+-----+
| Name | F / PRF | n | w | len |
+-----------------+----------+----+----+-----+
| REQUIRED: | | | | |
| | | | | |
| WOTSP-SHA2_256 | SHA2-256 | 32 | 16 | 67 |
| | | | | |
| OPTIONAL: | | | | |
| | | | | |
| WOTSP-SHA2_512 | SHA2-512 | 64 | 16 | 131 |
| | | | | |
| WOTSP-SHAKE_256 | SHAKE128 | 32 | 16 | 67 |
| | | | | |
| WOTSP-SHAKE_512 | SHAKE256 | 64 | 16 | 131 |
+-----------------+----------+----+----+-----+
Table 1The single functions get implemented the way we described above. The XDR (External Data Representation) formats for WOTS+ are listed in Appendix A 🍓
5.3. XMSS Parameters 👑
To fully describe an XMSS signature method, you MUST specify the parameters n, w, and h, plus the functions F, H, H_msg, and PRF. The table below defines different XMSS signature systems, each with its own name. The naming goes like XMSS-[Hashfamily]_[h]_[n in bits]. Again, w isn't in the name because every parameter set here uses w=16 🧚
+-------------------+-----------+----+----+-----+----+
| Name | Functions | n | w | len | h |
+-------------------+-----------+----+----+-----+----+
| REQUIRED: | | | | | |
| | | | | | |
| XMSS-SHA2_10_256 | SHA2-256 | 32 | 16 | 67 | 10 |
| | | | | | |
| XMSS-SHA2_16_256 | SHA2-256 | 32 | 16 | 67 | 16 |
| | | | | | |
| XMSS-SHA2_20_256 | SHA2-256 | 32 | 16 | 67 | 20 |
| | | | | | |
| OPTIONAL: | | | | | |
| | | | | | |
| XMSS-SHA2_10_512 | SHA2-512 | 64 | 16 | 131 | 10 |
| | | | | | |
| XMSS-SHA2_16_512 | SHA2-512 | 64 | 16 | 131 | 16 |
| | | | | | |
| XMSS-SHA2_20_512 | SHA2-512 | 64 | 16 | 131 | 20 |
| | | | | | |
| XMSS-SHAKE_10_256 | SHAKE128 | 32 | 16 | 67 | 10 |
| | | | | | |
| XMSS-SHAKE_16_256 | SHAKE128 | 32 | 16 | 67 | 16 |
| | | | | | |
| XMSS-SHAKE_20_256 | SHAKE128 | 32 | 16 | 67 | 20 |
| | | | | | |
| XMSS-SHAKE_10_512 | SHAKE256 | 64 | 16 | 131 | 10 |
| | | | | | |
| XMSS-SHAKE_16_512 | SHAKE256 | 64 | 16 | 131 | 16 |
| | | | | | |
| XMSS-SHAKE_20_512 | SHAKE256 | 64 | 16 | 131 | 20 |
+-------------------+-----------+----+----+-----+----+
Table 2The XDR formats for XMSS are listed in Appendix B 🎀
5.3.1. Parameter Guide 💅
Okay, here's the vibe check. Unlike traditional signature schemes like RSA or Digital Signature Algorithm (DSA), XMSS has a tree height parameter h that decides how many messages you can sign with one key pair 🔥 Bigger height means more signatures per key, but also bigger signatures and slower key generation, signing, and verification. To show how different values of h play out, here's a table of signature sizes and runtimes. The runtimes are counted as calls to F and H when the BDS algorithm computes authentication paths in the worst case. The last column is how many messages one key pair can sign. The numbers are the same for the XMSS-SHAKE instances with the same h and n values 🦋
+------------------+-------+------------+--------+--------+-------+
| Name | |Sig| | KeyGen | Sign | Verify | #Sigs |
+------------------+-------+------------+--------+--------+-------+
| REQUIRED: | | | | | |
| | | | | | |
| XMSS-SHA2_10_256 | 2,500 | 1,238,016 | 5,725 | 1,149 | 2^10 |
| | | | | | |
| XMSS-SHA2_16_256 | 2,692 | 79*10^6 | 9,163 | 1,155 | 2^16 |
| | | | | | |
| XMSS-SHA2_20_256 | 2,820 | 1,268*10^6 | 11,455 | 1,159 | 2^20 |
| | | | | | |
| OPTIONAL: | | | | | |
| | | | | | |
| XMSS-SHA2_10_512 | 9,092 | 2,417,664 | 11,165 | 2,237 | 2^10 |
| | | | | | |
| XMSS-SHA2_16_512 | 9,476 | 155*10^6 | 17,867 | 2,243 | 2^16 |
| | | | | | |
| XMSS-SHA2_20_512 | 9,732 | 2,476*10^6 | 22,335 | 2,247 | 2^20 |
+------------------+-------+------------+--------+--------+-------+
Table 3So if you're a default user with no special requirements, go with XMSS-SHA2_20_256 🫶 It lets you sign 2^20 messages with one key pair and gives you reasonable speed and signature size, so it's giving balance. If you need more signatures per key pair or faster key generation, you should look at XMSS^MT instead 👑
5.4. XMSS^MT Parameters 💜
Okay so, to fully describe an XMSS^MT signature method, the parameters n, w, h, and d plus the functions F, H, H_msg, and PRF MUST be specified 🎀. No skipping, bestie. The table below is the ultimate menu of named XMSS^MT signature systems, and each one has its own name. The naming goes like XMSSMT-[Hashfamily]_[h]/[d]_[n in bits], and there's no w in the name because every parameter set in this doc uses w=16 💅.
Here's Table 4 (don't panic, it's just a table 😭):
+------------------------+-----------+----+----+-----+----+----+
| Name | Functions | n | w | len | h | d |
+------------------------+-----------+----+----+-----+----+----+
| REQUIRED: | | | | | | |
| | | | | | | |
| XMSSMT-SHA2_20/2_256 | SHA2-256 | 32 | 16 | 67 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHA2_20/4_256 | SHA2-256 | 32 | 16 | 67 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/2_256 | SHA2-256 | 32 | 16 | 67 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHA2_40/4_256 | SHA2-256 | 32 | 16 | 67 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/8_256 | SHA2-256 | 32 | 16 | 67 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHA2_60/3_256 | SHA2-256 | 32 | 16 | 67 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHA2_60/6_256 | SHA2-256 | 32 | 16 | 67 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHA2_60/12_256 | SHA2-256 | 32 | 16 | 67 | 60 | 12 |
| | | | | | | |
| OPTIONAL: | | | | | | |
| | | | | | | |
| XMSSMT-SHA2_20/2_512 | SHA2-512 | 64 | 16 | 131 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHA2_20/4_512 | SHA2-512 | 64 | 16 | 131 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/2_512 | SHA2-512 | 64 | 16 | 131 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHA2_40/4_512 | SHA2-512 | 64 | 16 | 131 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/8_512 | SHA2-512 | 64 | 16 | 131 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHA2_60/3_512 | SHA2-512 | 64 | 16 | 131 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHA2_60/6_512 | SHA2-512 | 64 | 16 | 131 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHA2_60/12_512 | SHA2-512 | 64 | 16 | 131 | 60 | 12 |
| | | | | | | |
| XMSSMT-SHAKE_20/2_256 | SHAKE128 | 32 | 16 | 67 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_20/4_256 | SHAKE128 | 32 | 16 | 67 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/2_256 | SHAKE128 | 32 | 16 | 67 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_40/4_256 | SHAKE128 | 32 | 16 | 67 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/8_256 | SHAKE128 | 32 | 16 | 67 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHAKE_60/3_256 | SHAKE128 | 32 | 16 | 67 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHAKE_60/6_256 | SHAKE128 | 32 | 16 | 67 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHAKE_60/12_256 | SHAKE128 | 32 | 16 | 67 | 60 | 12 |
| | | | | | | |
| XMSSMT-SHAKE_20/2_512 | SHAKE256 | 64 | 16 | 131 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_20/4_512 | SHAKE256 | 64 | 16 | 131 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/2_512 | SHAKE256 | 64 | 16 | 131 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_40/4_512 | SHAKE256 | 64 | 16 | 131 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/8_512 | SHAKE256 | 64 | 16 | 131 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHAKE_60/3_512 | SHAKE256 | 64 | 16 | 131 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHAKE_60/6_512 | SHAKE256 | 64 | 16 | 131 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHAKE_60/12_512 | SHAKE256 | 64 | 16 | 131 | 60 | 12 |
+------------------------+-----------+----+----+-----+----+----+
Table 4Want the XDR formats for XMSS^MT? They're all chilling in Appendix C 🧚.
5.4.1. Parameter Guide 🦋
So XMSS^MT has this extra parameter d on top of the tree height h we already know from XMSS, and d decides how many tree layers you get. Fun fact: XMSS is basically XMSS^MT with a single layer, aka d=1 💅, so h does the same job it always did. The number of layers is a trade-off between signature size on one side and key generation and signing speed on the other. More layers makes key generation time drop exponentially and signing time drop linearly, but the signature size grows linearly. Essentially, an XMSS^MT signature contains one WOTSP signature per layer. And speed roughly corresponds to d-times the speed for XMSS with trees of height h/d. It's giving math but make it cute 🌸
To show how h and d affect things, here's the table of signature sizes and runtimes. The runtimes are the number of calls to F and H when the BDS algorithm and distributed signature generation are used, and they're worst-case times 🙈. The last column is how many messages one key pair can sign. The numbers are the same for the XMSS-SHAKE instances with the same parameters h and n. Formatting is being a little difficult, so only the parameter part of the names is shown and the name "XMSSMT" is left out.
+----------------+---------+------------+--------+--------+-------+
| Name | |Sig| | KeyGen | Sign | Verify | #Sigs |
+----------------+---------+------------+--------+--------+-------+
| REQUIRED: | | | | | |
| | | | | | |
| SHA2_20/2_256 | 4,963 | 2,476,032 | 7,227 | 2,298 | 2^20 |
| | | | | | |
| SHA2_20/4_256 | 9,251 | 154,752 | 4,170 | 4,576 | 2^20 |
| | | | | | |
| SHA2_40/2_256 | 5,605 | 2,535*10^6 | 13,417 | 2,318 | 2^40 |
| | | | | | |
| SHA2_40/4_256 | 9,893 | 4,952,064 | 7,227 | 4,596 | 2^40 |
| | | | | | |
| SHA2_40/8_256 | 18,469 | 309,504 | 4,170 | 9,152 | 2^40 |
| | | | | | |
| SHA2_60/3_256 | 8,392 | 3,803*10^6 | 13,417 | 3,477 | 2^60 |
| | | | | | |
| SHA2_60/6_256 | 14,824 | 7,428,096 | 7,227 | 6,894 | 2^60 |
| | | | | | |
| SHA2_60/12_256 | 27,688 | 464,256 | 4,170 | 13,728 | 2^60 |
| | | | | | |
| OPTIONAL: | | | | | |
| | | | | | |
| SHA2_20/2_512 | 18,115 | 4,835,328 | 14,075 | 4,474 | 2^20 |
| | | | | | |
| SHA2_20/4_512 | 34,883 | 302,208 | 8,138 | 8,928 | 2^20 |
| | | | | | |
| SHA2_40/2_512 | 19,397 | 4,951*10^6 | 26,025 | 4,494 | 2^40 |
| | | | | | |
| SHA2_40/4_512 | 36,165 | 9,670,656 | 14,075 | 8,948 | 2^40 |
| | | | | | |
| SHA2_40/8_512 | 69,701 | 604,416 | 8,138 | 17,856 | 2^40 |
| | | | | | |
| SHA2_60/3_512 | 29,064 | 7,427*10^6 | 26,025 | 6,741 | 2^60 |
| | | | | | |
| SHA2_60/6_512 | 54,216 | 14,505,984 | 14,075 | 13,422 | 2^60 |
| | | | | | |
| SHA2_60/12_512 | 104,520 | 906,624 | 8,138 | 26,784 | 2^60 |
+----------------+---------+------------+--------+--------+-------+
Table 5As a default, if you don't have any special requirements, you should go with XMSSMT-SHA2_60/3_256. It lets you sign 2^60 messages with one key pair (which is a virtually unbounded number of signatures, ngl 💀), and the signature size and speed are super well balanced 👑
6. Rationale 💅
okay bestie, this section is the "why did we do it this way" tea ☕. The goal is to describe WOTS+, XMSS, and XMSS^MT based on the scientific literature 📚. It's done in a modular way so you can base a description of stateless hash-based signature algorithms like SPHINCS [BHH15] on it 🧚.
ngl we deviate from the literature a little bit 👀. We use a tweak that prevents multi-user and multi-target attacks against H_msg. The public key AND the index of the one-time key pair being used become part of the hash function key 🔑. That gives us domain separation, which forces an attacker to decide which hash value to attack. iconic 💀
For the randomness used in randomized message hashing, we apply a PRF keyed with a secret value to the index of the one-time key pair being used, instead of to the message 🦋. Why? Because the message only gets processed once instead of twice ✨. For long messages that's faster, and it's way easier on resource-constrained devices that can't hold the whole message in storage 🫶.
We give one mandatory set of parameters using SHA2-256 💖. There are two reasons. First, SHA2-256 is part of most cryptographic libraries. Second, a 256-bit hash function gives parameters that provide 128 bits of security even against quantum-computer-aided attacks 🔥. A post-quantum security level of 256 bits seems overly conservative 🙈. But to prepare for possible cryptanalytic breakthroughs, we also provide OPTIONAL parameter sets using the less widely supported SHA2-512, SHAKE-256, and SHAKE-512 functions 🌈.
For the Winternitz parameter, we suggest w = 16 🍓. We don't include bigger values because the decrease in signature size becomes less significant 📉. w = 16 also considerably simplifies the implementations of some of the algorithms 💅. Please note that we do allow w = 4, but we limit the specified parameter sets to w = 16 for efficiency reasons 🎀.
The signature and public key formats are designed to be easy to parse 👑. Each format starts with a 32-bit enumeration value that indicates all of the details of the signature algorithm, and so defines all of the information needed to parse the format ✨.
7. Reference Code 🧚
For testing purposes, there's a reference implementation in C 🫶. The code has a basic implementation that closely follows the pseudocode in this document, plus an optimized implementation. The optimized one uses the BDS algorithm [BDS08] to compute authentication paths, and distributed signature generation as described in [HRB13] for XMSS^MT 💜.
The code is permanently available at <https://github.com/joostrijneveld/xmss-reference> 🌸
8. IANA Considerations ✨
okay so bestie, IANA has made three registries 📋: one for WOTS+ signatures (Section 3 stuff), one for XMSS signatures (Section 4 stuff), and one for XMSS^MT signatures (also Section 4 stuff) 🦋. to keep things clean and easy to find, the first batch of WOTS+, XMSS, and XMSS^MT parameter sets gets defined in Section 5 🎀.
new entries need a spec that's written down in an RFC or some other permanent, easy-to-find reference 📚. it has to be detailed enough, following the "Specification Required" policy from [RFC8126], so that independent implementations can actually interoperate 🫶. every entry has three things:
- a short name, like "XMSS_SHA2_20_256" 💖
- a positive number 🔢
- a reference to a spec that either fully defines the signature method test cases or gives a reference implementation you can check your code against (or points to one) ✨
requests to add an entry MUST include the name and the reference 🌸. the number is assigned by IANA, and those assignments SHOULD use the smallest available positive number 💅. submitters MUST have their requests reviewed and approved 👑. the Designated Experts for this, under the "Specification Required" policy from [RFC8126], get assigned by the Internet Engineering Steering Group (IESG) 🧚. you can reach the IESG at iesg@ietf.org 💌. if you're new to IANA processes, go check out <http://www.iana.org> 🌈.
number 0x00000000 (decimal 0) is Reserved 🙈. the numbers from 0xDDDDDDDD (decimal 3,722,304,989) up through 0xFFFFFFFF (decimal 4,294,967,295), inclusive, won't be handed out by IANA and are Reserved for Private Use 🔒. nobody's going to police that, so multiple sites might use the same value in different, incompatible ways [RFC8126] 💀.
the "WOTS+ Signatures" registry looks like this 🍓:
+--------------------+-----------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+-----------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | WOTSP-SHA2_256 | Section 5.2 |
| | | |
| 0x00000002 | WOTSP-SHA2_512 | Section 5.2 |
| | | |
| 0x00000003 | WOTSP-SHAKE_256 | Section 5.2 |
| | | |
| 0x00000004 | WOTSP-SHAKE_512 | Section 5.2 |
+--------------------+-----------------+-------------+
Table 6and the "XMSS Signatures" registry 🌷:
+--------------------+-------------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+-------------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | XMSS-SHA2_10_256 | Section 5.3 |
| | | |
| 0x00000002 | XMSS-SHA2_16_256 | Section 5.3 |
| | | |
| 0x00000003 | XMSS-SHA2_20_256 | Section 5.3 |
| | | |
| 0x00000004 | XMSS-SHA2_10_512 | Section 5.3 |
| | | |
| 0x00000005 | XMSS-SHA2_16_512 | Section 5.3 |
| | | |
| 0x00000006 | XMSS-SHA2_20_512 | Section 5.3 |
| | | |
| 0x00000007 | XMSS-SHAKE_10_256 | Section 5.3 |
| | | |
| 0x00000008 | XMSS-SHAKE_16_256 | Section 5.3 |
| | | |
| 0x00000009 | XMSS-SHAKE_20_256 | Section 5.3 |
| | | |
| 0x0000000A | XMSS-SHAKE_10_512 | Section 5.3 |
| | | |
| 0x0000000B | XMSS-SHAKE_16_512 | Section 5.3 |
| | | |
| 0x0000000C | XMSS-SHAKE_20_512 | Section 5.3 |
+--------------------+-------------------+-------------+
Table 7and last but not least, the "XMSS^MT Signatures" registry 🎀:
+--------------------+------------------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+------------------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | XMSSMT-SHA2_20/2_256 | Section 5.4 |
| | | |
| 0x00000002 | XMSSMT-SHA2_20/4_256 | Section 5.4 |
| | | |
| 0x00000003 | XMSSMT-SHA2_40/2_256 | Section 5.4 |
| | | |
| 0x00000004 | XMSSMT-SHA2_40/4_256 | Section 5.4 |
| | | |
| 0x00000005 | XMSSMT-SHA2_40/8_256 | Section 5.4 |
| | | |
| 0x00000006 | XMSSMT-SHA2_60/3_256 | Section 5.4 |
| | | |
| 0x00000007 | XMSSMT-SHA2_60/6_256 | Section 5.4 |
| | | |
| 0x00000008 | XMSSMT-SHA2_60/12_256 | Section 5.4 |
| | | |
| 0x00000009 | XMSSMT-SHA2_20/2_512 | Section 5.4 |
| | | |
| 0x0000000A | XMSSMT-SHA2_20/4_512 | Section 5.4 |
| | | |
| 0x0000000B | XMSSMT-SHA2_40/2_512 | Section 5.4 |
| | | |
| 0x0000000C | XMSSMT-SHA2_40/4_512 | Section 5.4 |
| | | |
| 0x0000000D | XMSSMT-SHA2_40/8_512 | Section 5.4 |
| | | |
| 0x0000000E | XMSSMT-SHA2_60/3_512 | Section 5.4 |
| | | |
| 0x0000000F | XMSSMT-SHA2_60/6_512 | Section 5.4 |
| | | |
| 0x00000010 | XMSSMT-SHA2_60/12_512 | Section 5.4 |
| | | |
| 0x00000011 | XMSSMT-SHAKE_20/2_256 | Section 5.4 |
| | | |
| 0x00000012 | XMSSMT-SHAKE_20/4_256 | Section 5.4 |
| | | |
| 0x00000013 | XMSSMT-SHAKE_40/2_256 | Section 5.4 |
| | | |
| 0x00000014 | XMSSMT-SHAKE_40/4_256 | Section 5.4 |
| | | |
| 0x00000015 | XMSSMT-SHAKE_40/8_256 | Section 5.4 |
| | | |
| 0x00000016 | XMSSMT-SHAKE_60/3_256 | Section 5.4 |
| | | |
| 0x00000017 | XMSSMT-SHAKE_60/6_256 | Section 5.4 |
| | | |
| 0x00000018 | XMSSMT-SHAKE_60/12_256 | Section 5.4 |
| | | |
| 0x00000019 | XMSSMT-SHAKE_20/2_512 | Section 5.4 |
| | | |
| 0x0000001A | XMSSMT-SHAKE_20/4_512 | Section 5.4 |
| | | |
| 0x0000001B | XMSSMT-SHAKE_40/2_512 | Section 5.4 |
| | | |
| 0x0000001C | XMSSMT-SHAKE_40/4_512 | Section 5.4 |
| | | |
| 0x0000001D | XMSSMT-SHAKE_40/8_512 | Section 5.4 |
| | | |
| 0x0000001E | XMSSMT-SHAKE_60/3_512 | Section 5.4 |
| | | |
| 0x0000001F | XMSSMT-SHAKE_60/6_512 | Section 5.4 |
| | | |
| 0x00000020 | XMSSMT-SHAKE_60/12_512 | Section 5.4 |
+--------------------+------------------------+-------------+
Table 8registering a signature system is not an endorsement of that system or how secure it is 🙈.
9. Security Considerations 💀
okay this section is the most serious one, so listen up 🚨. a signature system counts as secure if it stops an attacker from forging a valid signature 🔐. more specifically, picture this: the attacker gets a public key and can ask for signatures on any messages they want 👀. the system is secure if, even then, the attacker still can't make a brand new message/signature pair of their own choosing that the verification algorithm accepts 😤.
stopping an attack really just means it's too computationally expensive to actually pull off 💸. people have different estimates for when something counts as too expensive 🤷♀️. so this note only talks about how costly it is for an attacker to generate a forgery 🧮. parameter sets come with a bit security value 🎟️. here's what that means: a parameter set grants b bits of security if the best attack needs at least 2^(b - 1) bit operations to reach a success probability of 1/2 🎯. so to actually pull off a successful attack, an attacker has to do about 2^b bit operations on average 🚀. the bit security numbers were estimated following [HRS16] 📖.
that's the end of part 12 of the IANA and Security stuff, we'll keep going next time 🌈💜
9.1. Security Proofs ✨
okay bestie, this is the part where the authors show their homework 🤓💖 A full security proof for every scheme in this document lives in [HRS16]. And it's lowkey iconic, because it shows an attacker has to break at least one of certain security properties of the hash functions and PRFs to forge a signature in any of these schemes. It is NOT enough to just break collision resistance to make a forgery 🙅♀️ For the original schemes, the proofs show an attacker needs to break some minimal security properties. The [HRS16] proof uses a slightly different initial message compression than the randomized hashing used here, so we'll comment on that below 🎀
Here's the requirement list, no cap 💅 The functions F and H have to be post-quantum multi-function multi-target second-preimage resistant keyed functions. F also has a statistical requirement that roughly says most images have at least two preimages 🦋 PRF has to be a post-quantum pseudorandom function, and H_msg has to be a post-quantum multi-target extended target collision-resistant keyed hash function. The detailed definitions are in [HRS16], bestie 📚
Quick intuition check 🧠 Multi-function multi-target second-preimage resistance is basically second-preimage resistance extended to keyed hash functions. The adversary wins if it finds a second preimage for just one out of many values 🎯 Multi-target extended target collision resistance is the same vibe, it just doesn't have the multi-function identifier, because target collision resistance already considers keyed hash functions 💜 The [HRS16] proof splits PRF into two functions. When PRF makes pseudorandom keys or randomness for randomized message hashing, it's still treated as a pseudorandom function 🌸 But whenever PRF generates bitmasks and hash function keys, it gets modeled as a random oracle. That's purely for technical reasons in the proof, and an implementation using a pseudorandom function is secure 🙌
Now the spicy part 🌶️ The [HRS16] proof uses classical randomized hashing for the initial message compression, which is H(r, M) instead of H(r || getRoot(PK) || index, M). Classical randomized hashing gives a security reduction from extended target collision resistance [HRS16], which is conjectured to be strictly weaker than collision resistance 🫢 BUT, and this is a big but 😭, an attacker could still pull off a multi-target attack even against multiple users at once. Why? The adversary attacking u users at the same time learns u * 2^h randomized hashes H(r_i_j || M_i_j), with signature index i in [0, 2^h - 1] and user index j in [0, u]. It only takes finding a single pair (r*, M*) such that H(r* || M*) = H(r_i_u || M_i_u) for one of those u * 2^h learned hashes. So an attacker can brute-force in time 2^n / u * 2^h instead of 2^n 💀
The fix is the indexed randomized hashing used in this work, H(r || getRoot(PK) || toByte(idx, n), M). It makes the hash calls position- and user-dependent 🧚 This thwarts the attack, because each hash evaluation during an attack can only target one of the learned randomized hash values. The attacker now has to decide which index idx and which root value to use for each query 👑 If you assume the hash function is a random function, a multi-user existential forgery attack against this message compression has a complexity of 2^n hash function calls. Iconic 😤✨
The bit security values were estimated from the complexity of the best-known generic attacks against the required security properties of the hash and pseudorandom functions, for both conventional and quantum adversaries 📊 At the time of writing, generic attacks are the best-known attacks for the parameters suggested in the classical setting. In the quantum setting, there are no dedicated attacks known that beat generic attacks either. Still, quantum cryptanalysis of hash functions isn't as well understood as the classical side, so keep that in mind 🥺
9.2. Minimal Security Assumptions 🎀
These schemes are minimal in the following sense, and it's giving clean design 💅 Any signature algorithm that allows arbitrary size messages relies on a cryptographic hash function's security, either collision resistance or, if randomized hashing is used for message compression, extended target collision resistance. For the schemes described here, that's already enough to be secure 🔥 Meanwhile, common signature schemes like RSA, DSA, and Elliptic Curve Digital Signature Algorithm (ECDSA) also rely on the conjectured hardness of certain mathematical problems. Not me relying on extra conjectures 🙄💜
9.3. Post-Quantum Security 🌈
A post-quantum cryptosystem is one that stays secure against attackers with access to a reasonably sized quantum computer 🧪 At the time of writing, whether it's feasible to build such a machine is an open conjecture. However, significant progress has been made over the last few years, so we treat preparing for it as a matter of risk assessment 📈
Here's the plot twist 🦋 In contrast to RSA, DSA, and ECDSA, the described signature systems are post-quantum-secure if they're used with an appropriate cryptographic hash function. For post-quantum security, n must be twice the size required for classical security. That's to protect against quantum square-root attacks due to Grover's algorithm 🧠 [HRS16] shows that variants of Grover's algorithm are the optimal generic attacks against the hash function security properties required for these schemes.
Also, we only consider generic attacks here, because cryptographic hash functions should be deprecated as soon as dedicated attacks that perform significantly better exist 🙃 That applies to the quantum setting too. If dedicated quantum attacks against the used hash function show up that beat the described generic attacks significantly, then these hash functions should not be used anymore for these schemes, or the security level has to be recomputed 🚨 Stay vigilant, bestie 💖
10. References 📚
10.1. Normative References 🫶
- [FIPS180]: National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS PUB 180-4, DOI 10.6028/NIST.FIPS.180-4, August 2015.
- [FIPS202]: National Institute of Standards and Technology, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, DOI 10.6028/NIST.FIPS.202, August 2015.
- [RFC2119]: Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.
- [RFC4506]: Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, <https://www.rfc-editor.org/info/rfc4506>.
- [RFC8126]: Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, <https://www.rfc-editor.org/info/rfc8126>.
- [RFC8174]: Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.
10.2. Informative References 🌸
- [BDH11]: Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions", Lecture Notes in Computer Science, Volume 7071, Post-Quantum Cryptography, DOI 10.1007/978-3-642-25405-5_8, 2011.
- [BDS08]: Buchmann, J., Dahmen, E., and M. Schneider, "Merkle Tree Traversal Revisited", Lecture Notes in Computer Science, Volume 5299, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88403-3_5, 2008.
- [BDS09]: Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based Digital Signature Schemes", Book chapter, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88702-7_3, 2009.
- [BHH15]: Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical Stateless Hash-Based Signatures", Lecture Notes in Computer Science, Volume 9056, Advances in Cryptology - EUROCRYPT, DOI 10.1007/978-3-662-46800-5_15, 2015.
- [HRB13]: Huelsing, A., Rausch, L., and J. Buchmann, "Optimal Parameters for XMSS^MT", Lecture Notes in Computer Science, Volume 8128, CD-ARES, DOI 10.1007/978-3-642-40588-4_14, 2013.
- [HRS16]: Huelsing, A., Rijneveld, J., and F. Song, "Mitigating Multi-Target Attacks in Hash-based Signatures", Lecture Notes in Computer Science, Volume 9614, Public-Key Cryptography - PKC, DOI 10.1007/978-3-662-49384-7_15, 2016.
- [Huelsing13]: Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based Signature Schemes", Lecture Notes in Computer Science, Volume 7918, Progress in Cryptology - AFRICACRYPT, DOI 10.1007/978-3-642-38553-7_10, 2013.
- [Huelsing13a]: Huelsing, A., "Practical Forward Secure Signatures using Minimal Security Assumptions", PhD thesis TU Darmstadt, 2013, <http://tuprints.ulb.tu-darmstadt.de/3651/1/Thesis.pdf>.
- [KMN14]: Knecht, M., Meier, W., and C. Nicola, "A space- and time-efficient Implementation of the Merkle Tree Traversal Algorithm", Computing Research Repository (CoRR), arXiv:1409.4081, 2014.
- [MCF18]: McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based Signatures", Work in Progress, draft-mcgrew-hash-sigs-11, April 2018.
- [Merkle83]: Merkle, R., "Secrecy, Authentication, and Public Key Systems", Computer Science Series, UMI Research Press, ISBN: 9780835713849, 1983.
Appendix A. WOTS+ XDR Formats 🧚
okay so this appendix is where the formats get formally defined 🤓 The WOTS+ signature and public key formats use XDR [RFC4506] so there's an unambiguous, machine-readable definition. XDR is used, but these formats are simple and easy to parse without any special tools 💖 Also, this representation includes all optional parameter sets, and the same goes for the XMSS and XMSS^MT formats below 🎀
A.1. WOTS+ Parameter Sets ✨
WOTS+ parameter sets are defined in XDR syntax like this 👇
/* ots_algorithm_type identifies a particular
signature algorithm */
enum ots_algorithm_type {
wotsp_reserved = 0x00000000,
wotsp-sha2_256 = 0x00000001,
wotsp-sha2_512 = 0x00000002,
wotsp-shake_256 = 0x00000003,
wotsp-shake_512 = 0x00000004,
};A.2. WOTS+ Signatures
Okay so the WOTS+ signature gets described with XDR syntax, and it's giving very precise bestie energy 💅✨
/* Byte strings */
typedef opaque bytestring32[32];
typedef opaque bytestring64[64];
union ots_signature switch (ots_algorithm_type type) {
case wotsp-sha2_256:
case wotsp-shake_256:
bytestring32 ots_sig_n32_len67[67];
case wotsp-sha2_512:
case wotsp-shake_512:
bytestring64 ots_sig_n64_len18[131];
default:
void; /* error condition */
};A.3. WOTS+ Public Keys
Now the WOTS+ public keys get the same treatment 🔑🎀 The union is literally the mirror image of the signature one, so it's giving consistency and I am here for it 🫶
union ots_pubkey switch (ots_algorithm_type type) {
case wotsp-sha2_256:
case wotsp-shake_256:
bytestring32 ots_pubk_n32_len67[67];
case wotsp-sha2_512:
case wotsp-shake_512:
bytestring64 ots_pubk_n64_len18[131];
default:
void; /* error condition */
};Appendix B. XMSS XDR Formats
B.1. XMSS Parameter Sets
Next up is XMSS, and bestie, this section is the main character 👑🌈 Everything in here is defined with XDR syntax, so let's go.
XMSS parameter sets are defined using XDR syntax as follows:
/* Byte strings */
typedef opaque bytestring4[4];
/* Definition of parameter sets */
enum xmss_algorithm_type {
xmss_reserved = 0x00000000,
/* 256 bit classical security, 128 bit post-quantum security */
xmss-sha2_10_256 = 0x00000001,
xmss-sha2_16_256 = 0x00000002,
xmss-sha2_20_256 = 0x00000003,
/* 512 bit classical security, 256 bit post-quantum security */
xmss-sha2_10_512 = 0x00000004,
xmss-sha2_16_512 = 0x00000005,
xmss-sha2_20_512 = 0x00000006,
/* 256 bit classical security, 128 bit post-quantum security */
xmss-shake_10_256 = 0x00000007,
xmss-shake_16_256 = 0x00000008,
xmss-shake_20_256 = 0x00000009,
/* 512 bit classical security, 256 bit post-quantum security */
xmss-shake_10_512 = 0x0000000A,
xmss-shake_16_512 = 0x0000000B,
xmss-shake_20_512 = 0x0000000C,
};B.2. XMSS Signatures
XMSS signatures are defined using XDR syntax as follows 🦋 Brace yourself, there are a lot of unions in here, but they're all super organised.
/* Authentication path types */
union xmss_path switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-shake_10_256:
bytestring32 path_n32_t10[10];
case xmss-sha2_16_256:
case xmss-shake_16_256:
bytestring32 path_n32_t16[16];
case xmss-sha2_20_256:
case xmss-shake_20_256:
bytestring32 path_n32_t20[20];
case xmss-sha2_10_512:
case xmss-shake_10_512:
bytestring64 path_n64_t10[10];
case xmss-sha2_16_512:
case xmss-shake_16_512:
bytestring64 path_n64_t16[16];
case xmss-sha2_20_512:
case xmss-shake_20_512:
bytestring64 path_n64_t20[20];
default:
void; /* error condition */
};
/* Types for XMSS random strings */
union random_string_xmss switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
bytestring32 rand_n32;
case xmss-sha2_10_512:
case xmss-sha2_16_512:
case xmss-sha2_20_512:
case xmss-shake_10_512:
case xmss-shake_16_512:
case xmss-shake_20_512:
bytestring64 rand_n64;
default:
void; /* error condition */
};
/* Corresponding WOTS+ type for given XMSS type */
union xmss_ots_signature switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
wotsp-sha2_256;
case xmss-sha2_10_512:
case xmss-sha2_16_512:
case xmss-sha2_20_512:
wotsp-sha2_512;
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
wotsp-shake_256;
case xmss-shake_10_512:
case xmss-shake_16_512:
case xmss-shake_20_512:
wotsp-shake_512;
default:
void; /* error condition */
};
/* XMSS signature structure */
struct xmss_signature {
/* WOTS+ key pair index */
bytestring4 idx_sig;
/* Random string for randomized hashing */
random_string_xmss rand_string;
/* WOTS+ signature */
xmss_ots_signature sig_ots;
/* authentication path */
xmss_path nodes;
};B.3. XMSS Public Keys
XMSS public keys are next, and they're built from two pieces: a seed for the bitmasks and a root node 🌸 Both get their own union so the sizes match the parameter set.
/* Types for bitmask seed */
union seed switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
bytestring32 seed_n32;
case xmss-sha2_10_512:
case xmss-sha2_16_512:
case xmss-sha2_20_512:
case xmss-shake_10_512:
case xmss-shake_16_512:
case xmss-shake_20_512:
bytestring64 seed_n64;
default:
void; /* error condition */
};
/* Types for XMSS root node */
union xmss_root switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
bytestring32 root_n32;
case xmss-sha2_10_512:
case xmss-sha2_16_512:
case xmss-sha2_20_512:
case xmss-shake_10_512:
case xmss-shake_16_512:
case xmss-shake_20_512:
bytestring64 root_n64;
default:
void; /* error condition */
};
/* XMSS public key structure */
struct xmss_public_key {
xmss_root root; /* Root node */
seed SEED; /* Seed for bitmasks */
};Appendix C. XMSS^MT XDR Formats
C.1. XMSS^MT Parameter Sets
Last stop for this part: XMSS^MT, the multi-tree cousin 🧚💜 Same XDR vibes, just with more parameter sets to vibe with.
XMSS^MT parameter sets are defined using XDR syntax as follows:
/* Byte strings */
typedef opaque bytestring3[3];
typedef opaque bytestring5[5];
typedef opaque bytestring8[8];
/* Definition of parameter sets */
enum xmssmt_algorithm_type {
xmssmt_reserved = 0x00000000,
/* 256 bit classical security, 128 bit post-quantum security */
xmssmt-sha2_20/2_256 = 0x00000001,
xmssmt-sha2_20/4_256 = 0x00000002,
xmssmt-sha2_40/2_256 = 0x00000003,
xmssmt-sha2_40/4_256 = 0x00000004,
xmssmt-sha2_40/8_256 = 0x00000005,
xmssmt-sha2_60/3_256 = 0x00000006,
xmssmt-sha2_60/6_256 = 0x00000007,
xmssmt-sha2_60/12_256 = 0x00000008,
/* 512 bit classical security, 256 bit post-quantum security */
xmssmt-sha2_20/2_512 = 0x00000009,
xmssmt-sha2_20/4_512 = 0x0000000A,
xmssmt-sha2_40/2_512 = 0x0000000B,
xmssmt-sha2_40/4_512 = 0x0000000C,
xmssmt-sha2_40/8_512 = 0x0000000D,
xmssmt-sha2_60/3_512 = 0x0000000E,
xmssmt-sha2_60/6_512 = 0x0000000F,
xmssmt-sha2_60/12_512 = 0x00000010,
/* 256 bit classical security, 128 bit post-quantum security */
xmssmt-shake_20/2_256 = 0x00000011,
xmssmt-shake_20/4_256 = 0x00000012,
xmssmt-shake_40/2_256 = 0x00000013,
xmssmt-shake_40/4_256 = 0x00000014,
xmssmt-shake_40/8_256 = 0x00000015,
xmssmt-shake_60/3_256 = 0x00000016,
xmssmt-shake_60/6_256 = 0x00000017,
xmssmt-shake_60/12_256 = 0x00000018,
/* 512 bit classical security, 256 bit post-quantum security */
xmssmt-shake_20/2_512 = 0x00000019,
xmssmt-shake_20/4_512 = 0x0000001A,
xmssmt-shake_40/2_512 = 0x0000001B,
xmssmt-shake_40/4_512 = 0x0000001C,
xmssmt-shake_40/8_512 = 0x0000001D,
xmssmt-shake_60/3_512 = 0x0000001E,
xmssmt-shake_60/6_512 = 0x0000001F,
xmssmt-shake_60/12_512 = 0x00000020,
};C.2. XMSS^MT Signatures
Okay bestie, this is where the XMSS^MT signature layout lives 🦋 Everything is written in XDR, and the unions pick the right field sizes based on which xmssmt- algorithm type you're using. Lowkey iconic 💅
/* Type for XMSS^MT key pair index */
/* Depends solely on h */
union idx_sig_xmssmt switch (xmss_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_20/4_512:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_20/2_512:
case xmssmt-shake_20/4_512:
bytestring3 idx3;
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_40/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_40/8_512:
bytestring5 idx5;
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/12_256:
case xmssmt-sha2_60/3_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/12_256:
case xmssmt-shake_60/3_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_60/12_512:
bytestring8 idx8;
default:
void; /* error condition */
};
union random_string_xmssmt switch (xmssmt_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/12_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/12_256:
bytestring32 rand_n32;
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/3_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/3_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_60/12_512:
bytestring64 rand_n64;
default:
void; /* error condition */
};
/* Type for reduced XMSS signatures */
union xmss_reduced (xmss_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_60/6_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_60/6_256:
bytestring32 xmss_reduced_n32_t77[77];
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/12_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/12_256:
bytestring32 xmss_reduced_n32_t72[72];
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_60/3_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_60/3_256:
bytestring32 xmss_reduced_n32_t87[87];
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_60/6_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_60/6_512:
bytestring64 xmss_reduced_n32_t141[141];
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/12_512:
bytestring64 xmss_reduced_n32_t136[136];
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_60/3_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_60/3_512:
bytestring64 xmss_reduced_n32_t151[151];
default:
void; /* error condition */
};
/* xmss_reduced_array depends on d */
union xmss_reduced_array (xmss_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/2_512:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/2_512:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/2_512:
xmss_reduced xmss_red_arr_d2[2];
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/3_512:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/3_512:
xmss_reduced xmss_red_arr_d3[3];
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/4_512:
case xmssmt-shake_20/4_256:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/4_512:
xmss_reduced xmss_red_arr_d4[4];
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/6_512:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/6_512:
xmss_reduced xmss_red_arr_d6[6];
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_40/8_512:
case xmssmt-shake_40/8_256:
case xmssmt-shake_40/8_512:
xmss_reduced xmss_red_arr_d8[8];
case xmssmt-sha2_60/12_256:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_60/12_256:
case xmssmt-shake_60/12_512:
xmss_reduced xmss_red_arr_d12[12];
default:
void; /* error condition */
};
/* XMSS^MT signature structure */
struct xmssmt_signature {
/* WOTS+ key pair index */
idx_sig_xmssmt idx_sig;
/* Random string for randomized hashing */
random_string_xmssmt randomness;
/* Array of d reduced XMSS signatures */
xmss_reduced_array;
};C.3. XMSS^MT Public Keys
Next up are the public keys 🔑✨ Same deal: XDR unions keyed on the algorithm type, so the seed and root sizes always match your chosen parameter set 💜
/* Types for bitmask seed */
union seed switch (xmssmt_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/12_256:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_60/3_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/12_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_60/3_256:
bytestring32 seed_n32;
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/12_512:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_60/3_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/12_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_60/3_512:
bytestring64 seed_n64;
default:
void; /* error condition */
};
/* Types for XMSS^MT root node */
union xmssmt_root switch (xmssmt_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/12_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/12_256:
bytestring32 root_n32;
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/3_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/3_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_60/12_512:
bytestring64 root_n64;
default:
void; /* error condition */
};
/* XMSS^MT public key structure */
struct xmssmt_public_key {
xmssmt_root root; /* Root node */
seed SEED; /* Seed for bitmasks */
};Acknowledgements ✨
Huge thank you to Johannes Braun, Peter Campbell, Florian Caullery, Stephen Farrell, Scott Fluhrer, Burt Kaliski, Adam Langley, Marcos Manzano, David McGrew, Rafael Misoczki, Sean Parkinson, Sebastian Roland, and the Keccak team for helping out and leaving comments 🫶🌸 You're all literal legends.
Authors' Addresses 🦋
Andreas Huelsing TU Eindhoven P.O. Box 513 Eindhoven 5600 MB The Netherlands
Email: ietf@huelsing.net
Denis Butin TU Darmstadt Hochschulstrasse 10 Darmstadt 64289 Germany
Email: dbutin@cdc.informatik.tu-darmstadt.de
Stefan-Lukas Gazdag genua GmbH Domagkstrasse 7 Kirchheim bei Muenchen 85551 Germany
Email: ietf@gazdag.de
Joost Rijneveld Radboud University Toernooiveld 212 Nijmegen 6525 EC The Netherlands
Email: ietf@joostrijneveld.nl
Aziz Mohaisen University of Central Florida 4000 Central Florida Blvd Orlando, FL 32816 United States of America
Phone: +1 407 823-1294 Email: mohaisen@ieee.org
📦 where this page comes from
- ietf: rfc8391 2018-05
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms