RFC 8391
XMSS: eXtended Merkle Signature Scheme
Internet Research Task Force (IRTF) A. Huelsing Request for Comments: 8391 TU Eindhoven Category: Informational D. Butin ISSN: 2070-1721 TU Darmstadt S. Gazdag genua GmbH J. Rijneveld Radboud University A. Mohaisen University of Central Florida May 2018 XMSS: eXtended Merkle Signature SchemeAbstract
This note describes the eXtended Merkle Signature Scheme (XMSS), a hash-based digital signature system that is based on existing descriptions in scientific literature. This note specifies Winternitz One-Time Signature Plus (WOTS+), a one-time signature scheme; XMSS, a single-tree scheme; and XMSS^MT, a multi-tree variant of XMSS. Both XMSS and XMSS^MT use WOTS+ as a main building block. XMSS provides cryptographic digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it is proven that it only relies on the properties of cryptographic hash functions. XMSS provides strong security guarantees and is even secure when the collision resistance of the underlying hash function is broken. It is suitable for compact implementations, is relatively simple to implement, and naturally resists side-channel attacks. Unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers.
Status of This Memo This document is not an Internet Standards Track specification; it is published for informational purposes. This document is a product of the Internet Research Task Force (IRTF). The IRTF publishes the results of Internet-related research and development activities. These results might not be suitable for deployment. This RFC represents the consensus of the Crypto Forum Research Group of the Internet Research Task Force (IRTF). Documents approved for publication by the IRSG are not candidates for any level of Internet Standard; see Section 2 of RFC 7841. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at 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) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to 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 ................................................74
1. Introduction
A (cryptographic) digital signature scheme provides asymmetric message authentication. The key generation algorithm produces a key pair consisting of a private and a public key. A message is signed using a private key to produce a signature. A message/signature pair can be verified using a public key. A One-Time Signature (OTS) scheme allows using a key pair to sign exactly one message securely. A Many-Time Signature (MTS) system can be used to sign multiple messages. OTS schemes, and MTS schemes composed from them, were proposed by Merkle in 1979 [Merkle83]. They were well-studied in the 1990s and have regained interest from the mid 2000s onwards because of their resistance against quantum-computer-aided attacks. These kinds of signature schemes are called hash-based signature schemes as they are built out of a cryptographic hash function. Hash-based signature schemes generally feature small private and public keys as well as fast signature generation and verification; however, they also feature large signatures and relatively slow key generation. In addition, they are suitable for compact implementations that benefit various applications and are naturally resistant to most kinds of side-channel attacks. Some progress has already been made toward introducing and standardizing hash-based signatures. Buchmann, Dahmen, and Huelsing proposed the eXtended Merkle Signature Scheme (XMSS) [BDH11], which offers better efficiency than Merkle's original scheme and a modern security proof in the standard model. McGrew, Curcio, and Fluhrer authored an Internet-Draft [MCF18] specifying the Leighton-Micali Signature (LMS) scheme, which builds on the seminal works by Lamport, Diffie, Winternitz, and Merkle, taking a different approach than XMSS and relying entirely on security arguments in the random oracle model. Very recently, the stateless hash-based signature scheme SPHINCS was introduced [BHH15], with the intent of being easier to deploy in current applications. A reasonable next step toward introducing hash-based signatures is to complete the specifications of the basic algorithms -- LMS, XMSS, SPHINCS, and/or variants. The eXtended Merkle Signature Scheme (XMSS) [BDH11] is the latest stateful hash-based signature scheme. It has the smallest signatures out of such schemes and comes with a multi-tree variant that solves the problem of slow key generation. Moreover, it can be shown that XMSS is secure, making only mild assumptions on the underlying hash function. In particular, it is not required that the cryptographic hash function is collision-resistant for the security of XMSS. Improvements upon XMSS, as described in [HRS16], are part of this note.
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] that is used by XMSS. The schemes are described with enough specificity to ensure interoperability between implementations. This document is structured as follows. Notation is introduced in Section 2. Section 3 describes the WOTS+ signature system. MTS schemes are defined in Section 4: the eXtended Merkle Signature Scheme (XMSS) in Section 4.1 and its multi-tree variant (XMSS^MT) in Section 4.2. Parameter sets are described in Section 5. Section 6 describes the rationale behind choices in this note. Section 7 gives information about the reference code. The IANA registry for these signature systems is described in Section 8. Finally, security considerations are presented in Section 9.1.1. CFRG Note on Post-Quantum Cryptography
All post-quantum algorithms documented by the Crypto Forum Research Group (CFRG) are today considered ready for experimentation and further engineering development (e.g., to establish the impact of performance and sizes on IETF protocols). However, at the time of writing, we do not have significant deployment experience with such algorithms. Many of these algorithms come with specific restrictions, e.g., change of classical interface or less cryptanalysis of proposed parameters than established schemes. CFRG has consensus that all documents describing post-quantum technologies include the above paragraph and a clear additional warning about any specific restrictions, especially as those might affect use or deployment of the specific scheme. That guidance may be changed over time via document updates. Additionally, for XMSS: CFRG consensus is that we are confident in the cryptographic security of the signature schemes described in this document against quantum computers, given the current state of the research community's knowledge about quantum algorithms. Indeed, we are confident that the security of a significant part of the Internet could be made dependent on the signature schemes defined in this document, if developers take care of the following. In contrast to traditional signature schemes, the signature schemes described in this document are stateful, meaning the secret key changes over time. If a secret key state is used twice, no cryptographic security guarantees remain. In consequence, it becomes
feasible to forge a signature on a new message. This is a new property that most developers will not be familiar with and requires careful handling of secret keys. Developers should not use the schemes described here except in systems that prevent the reuse of secret key states. Note that the fact that the schemes described in this document are stateful also implies that classical APIs for digital signatures cannot be used without modification. The API MUST be able to handle a secret key state; in particular, this means that the API MUST allow to return 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.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 denoted as a pair of hexadecimal digits with a leading "0x". A byte string is an ordered sequence of zero or more bytes and is denoted 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 starting with index 0 in which all byte strings have identical 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, mathematical operators are defined as follows: ^ : 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 are used in the common way, where the i^th element of an array A is denoted A[i]. Byte strings are treated as arrays of bytes where necessary: if X is a byte string, then X[i] denotes its i^th byte, where X[0] is the leftmost byte. If A and B are byte strings of equal length, then: o A AND B denotes the bitwise logical conjunction operation. o A XOR B denotes the bitwise logical exclusive disjunction operation. When B is a byte and i is an integer, then B >> i denotes the logical right-shift operation.
If X is an x-byte string and Y a y-byte string, then X || Y denotes the concatenation of X and Y, with 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) to be the y-byte string containing the binary representation of x in big-endian byte order.2.5. Hash Function Address Scheme
The schemes described in this document randomize each hash function call. This means that aside from the initial message digest, a different key and different bitmask is used for each hash function call. These values are pseudorandomly generated using a pseudorandom function that takes a key SEED and a 32-byte address ADRS as input and outputs an n-byte value, where n is the security parameter. Here we explain the structure of address ADRS and propose setter methods to manipulate the address. We explain the generation of the addresses in the following sections where they are used. The schemes in the next two sections use two kinds of hash functions parameterized by security parameter n. For the hash tree constructions, a hash function that maps an n-byte key and 2n-byte inputs to n-byte outputs is used. To randomize this function, 3n bytes are needed -- n bytes for the key and 2n bytes for a bitmask. For the OTS scheme constructions, a hash function that maps n-byte keys and n-byte inputs to n-byte outputs is used. To randomize this function, 2n bytes are needed -- n bytes for the key and n bytes for a bitmask. Consequently, three addresses are needed for the first function and two addresses for the second one. There are three different types of addresses for the different use cases. One type is used for the hashes in OTS schemes, one is used for hashes within the main Merkle tree construction, and one is used for hashes in the L-trees. The latter is used to compress one-time public keys. All these types share as much format as possible. In the remainder of this section, we describe these types in detail. The structure of an address complies with word borders, with a word being 32 bits long in this context. Only the tree address is too long to fit a single word, but it can fit a double word. An address is structured as follows. It always starts with a layer address of one word in the most significant bits, followed by a tree address of two words. Both addresses are needed for the multi-tree variant (see Section 4.2) and describe the position of a tree within a multi-tree. They are therefore set to zero in single-tree applications. For
multi-tree hash-based signatures, the layer address describes the
height of a tree within the multi-tree, starting from height zero for
trees at the bottom layer. The tree address describes the position
of a tree within a layer of a multi-tree starting with index zero for
the leftmost tree. The next word defines the type of the address.
It is set to 0 for an OTS address, to 1 for an L-tree address, and to
2 for a hash tree address. Whenever the type word of an address is
changed, all following words should be initialized with 0 to prevent
non-zero values in unused padding words.
We first describe the OTS address case. In this case, the type word
is followed by an OTS address word that encodes the index of the OTS
key pair within the tree. The next word encodes the chain address
followed by a word that encodes the address of the hash function call
within the chain. The last word, called keyAndMask, is used to
generate two different addresses for one hash function call. The
word is set to zero to generate the key. To generate the n-byte
bitmask, the word is set to one.
+-------------------------+
| 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 Address
We now discuss the L-tree case, which means that the type word is set
to one. In that case, the type word is followed by an L-tree address
word that encodes the index of the leaf computed with this L-tree.
The next word encodes the height of the node being input for the next
computation inside the L-tree. The following word encodes the index
of the node at that height, inside the L-tree. This time, the last
word, keyAndMask, is used to generate three different addresses for
one function call. The word is set to zero to generate the key. To
generate the most significant n bytes of the 2n-byte bitmask, the
word is set to one. The least significant bytes are generated using
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 Address
We now describe the remaining type for the main tree hash addresses.
In this case, the type word is set to two, followed by a zero padding
of one word. The next word encodes the height of the tree node being
input for the next computation, followed by a word that encodes the
index of this node at that height. As for the L-tree addresses, the
last word, keyAndMask, is used to generate three different addresses
for one function call. The word is set to zero to generate the key.
To generate the most significant n bytes of the 2n-byte bitmask, the
word is set to one. The least significant bytes are generated using
the address with the word set to two.
+-------------------------+
| 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 Address
All fields within these addresses encode unsigned integers. When describing the generation of addresses we use setter methods that take positive integers and set the bits of a field to the binary representation of that integer of the length of the field. We furthermore assume that the setType() method sets the four words following the type word to zero.2.6. Strings of Base w Numbers
A byte string can be considered as a string of base w numbers, i.e., integers in the set {0, ... , w - 1}. The correspondence is defined by the function base_w(X, w, out_len) (Algorithm 1) as follows. 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 between 0 and w - 1. The length out_len is REQUIRED to be less than or equal to 8 * len_X / lg(w). 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}.
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]
Example
2.7. Member Functions
To simplify algorithm descriptions, we assume the existence of member
functions. If a complex data structure like a public key PK contains
a value X, then getX(PK) returns the value of X for this public key.
Accordingly, setX(PK, X, Y) sets value X in PK to the value held by
Y. Since camelCase is used for member function names, a value z may
be referred to as Z in the function name, e.g., getZ.
3. Primitives
3.1. WOTS+: One-Time Signatures
This section describes the WOTS+ system in a manner similar to that in [Huelsing13]. WOTS+ is an OTS scheme; while a private key can be used to sign any message, each private key MUST be used only once to sign a single message. In particular, if a private key is used to sign two different messages, the scheme becomes insecure. This section starts with an explanation of parameters. Afterwards, the so-called chaining function, which forms the main building block of the WOTS+ scheme, is explained. A description of the algorithms for key generation, signing, and verification follows. Finally, pseudorandom key generation is discussed.3.1.1. WOTS+ Parameters
WOTS+ uses the parameters n and w; they both take positive integer values. These parameters are summarized as follows: n: the message length as well as the length of a private key, public key, or signature element in bytes. w: the Winternitz parameter; it is a member of the set {4, 16}. The parameters are used to compute values len, len_1, and len_2: len: the number of n-byte string elements in a WOTS+ private key, public key, and signature. It is computed as len = len_1 + len_2, with len_1 = ceil(8n / lg(w)) and len_2 = floor(lg(len_1 * (w - 1)) / lg(w)) + 1. The value of n is determined by the cryptographic hash function used for WOTS+. The hash function is chosen to ensure an appropriate level of security. The value of n is the input length that can be processed by the signing algorithm. It is often the length of a message digest. The parameter w can be chosen from the set {4, 16}. A larger value of w results in shorter signatures but slower overall signing operations; it has little effect on security. Choices of w are limited to the values 4 and 16 since these values yield optimal trade-offs and easy implementation. WOTS+ parameters are implicitly included in algorithm inputs as needed.
3.1.1.1. WOTS+ Functions
The WOTS+ algorithm uses a keyed cryptographic hash function F. F accepts and returns byte strings of length n using keys of length n. More detail on specific instantiations can be found in Section 5. Security requirements on F are discussed in Section 9. In addition, WOTS+ uses a pseudorandom function PRF. PRF takes as input an n-byte key and a 32-byte index and generates pseudorandom outputs of length n. More detail on specific instantiations can be found in Section 5. Security requirements on PRF are discussed in Section 9.3.1.2. WOTS+ Chaining Function
The chaining function (Algorithm 2) computes an iteration of F on an n-byte input using outputs of PRF. It takes an OTS hash address as input. This address will have the first six 32-bit words set to encode the address of this chain. In each iteration, PRF is used to generate a key for F and a bitmask that is XORed to the intermediate result before it is processed by F. In the following, ADRS is a 32-byte OTS hash address as specified in Section 2.5 and SEED is an n-byte string. To generate the keys and bitmasks, PRF is called with SEED as key and ADRS as input. The chaining function takes as input an n-byte string X, a start index i, a number of steps s, as well as ADRS and SEED. The chaining function returns as output the value obtained by iterating F for 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+, denoted by sk (s for secret), is a length
len array of n-byte strings. This private key MUST be only used to
sign at most one message. Each n-byte string MUST either be selected
randomly from the uniform distribution or be selected using a
cryptographically secure pseudorandom procedure. In the latter case,
the security of the used procedure MUST at least match that of the
WOTS+ parameters used. For a further discussion on pseudorandom key
generation, see Section 3.1.7. The following pseudocode (Algorithm
3) describes an algorithm for generating 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 that consists of len hash chains of length w. The len n-byte strings in the private key each define the start node for one hash chain. The public key consists of the end nodes of these hash chains. Therefore, like the private key, the public key is also a length len array of n-byte strings. To compute the hash chain, the chaining function (Algorithm 2) is used. An OTS hash address ADRS and a seed SEED have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. Please note that the SEED used here is public information also available to a verifier. The following pseudocode (Algorithm 4) describes an algorithm for generating the public key pk, where sk is the private key. 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. The WOTS+ signature is generated by mapping a message to len integers between 0 and w - 1. To this end, the message is transformed into len_1 base w numbers using the base_w function defined in Section 2.6. Next, a checksum is computed and appended to the transformed message as len_2 base w numbers using the base_w function. Note that the checksum may reach a maximum integer value of len_1 * (w - 1) * 2^8 and therefore depends on the parameters n and w. For the parameter sets given in Section 5, a 32-bit unsigned integer is sufficient to hold the checksum. If other parameter settings are used, the size of the variable holding the integer value of the checksum MUST be sufficiently large. Each of the base w integers is used to select a node from a different hash chain. The signature is formed by concatenating the selected nodes. An OTS hash address ADRS and a seed SEED have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT manipulate any parts of
ADRS except for the last three 32-bit words. Please note that the
SEED used here is public information also available to a verifier.
The pseudocode for signature generation is shown below (Algorithm 5),
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;
The data format for a signature is given below.
+---------------------------------+
| |
| sig_ots[0] | n bytes
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| sig_ots[len - 1] | n bytes
| |
+---------------------------------+
WOTS+ Signature
3.1.6. WOTS+ Signature Verification
In order to verify a signature sig on a message M, the verifier computes a WOTS+ public key value from the signature. This can be done by "completing" the chain computations starting from the signature values, using the base w values of the message hash and its checksum. This step, called WOTS_pkFromSig, is described below in Algorithm 6. The result of WOTS_pkFromSig is then compared to the given public key. If the values are equal, the signature is accepted. Otherwise, the signature MUST be rejected. An OTS hash address ADRS and a seed SEED have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. Please note that the SEED used here is public information also available to a verifier. 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; Note: XMSS uses WOTS_pkFromSig to compute a public key value and delays the comparison to 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. Other methods MAY be used. The choice of a pseudorandom method does not affect interoperability, but the cryptographic strength MUST match that of the used WOTS+ parameters. The advantage of generating the private key elements from a random n-byte string is that only this n-byte string needs to be stored instead of the full private key. The key can be regenerated when needed. 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 string S is stored as private key. The private key elements are computed as sk[i] = PRF(S, toByte(i, 32)) whenever 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. 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.
(page 20 continued on part 2)
