Tech-invite   3GPPspecs   RFCs   Search in Tech-invite

868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100IETF‑orgGroupsStats
in Index   Prev   Next

RFC 8391

XMSS: eXtended Merkle Signature Scheme

Pages: 74
Group: IRTF
Informational
Errata
Part 1 of 4 – Pages 1 to 20
None   None   Next

Top   ToC   RFC8391 - Page 1
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 Scheme

Abstract

   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.
Top   ToC   RFC8391 - Page 2
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.
Top   ToC   RFC8391 - Page 3
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
Top   ToC   RFC8391 - Page 4
   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
Top   ToC   RFC8391 - Page 5
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.
Top   ToC   RFC8391 - Page 6
   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
Top   ToC   RFC8391 - Page 7
   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.
Top   ToC   RFC8391 - Page 8
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.
Top   ToC   RFC8391 - Page 9
   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
Top   ToC   RFC8391 - Page 10
   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.
Top   ToC   RFC8391 - Page 11
                     +-------------------------+
                     | 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
Top   ToC   RFC8391 - Page 12
   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}.
Top   ToC   RFC8391 - Page 13
                      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.
Top   ToC   RFC8391 - Page 14
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.
Top   ToC   RFC8391 - Page 15
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.
Top   ToC   RFC8391 - Page 16
   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;
Top   ToC   RFC8391 - Page 17
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
Top   ToC   RFC8391 - Page 18
   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
Top   ToC   RFC8391 - Page 19
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.
Top   ToC   RFC8391 - Page 20
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)

Next Section