[RFC Home] [TEXT|PDF|HTML] [Tracker] [IPR]

Internet Research Task Force (IRTF)                            D. McGrew
Request for Comments: 8554                                     M. Curcio
Category: Informational                                       S. Fluhrer
ISSN: 2070-1721                                            Cisco Systems
                                                              April 2019

                 Leighton-Micali Hash-Based Signatures


   This note describes a digital-signature system based on cryptographic
   hash functions, following the seminal work in this area of Lamport,
   Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in
   1995.  It specifies a one-time signature scheme and a general
   signature scheme.  These systems provide asymmetric authentication
   without using large integer mathematics and can achieve a high
   security level.  They are suitable for compact implementations, are
   relatively simple to implement, and are naturally resistant to side-
   channel attacks.  Unlike many other signature systems, hash-based
   signatures would still be secure even if it proves feasible for an
   attacker to build a quantum computer.

   This document is a product of the Crypto Forum Research Group (CFRG)
   in the IRTF.  This has been reviewed by many researchers, both in the
   research group and outside of it.  The Acknowledgements section lists
   many of them.

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

McGrew, et al.                Informational                     [Page 1]

RFC 8554                LMS Hash-Based Signatures             April 2019

Copyright Notice

   Copyright (c) 2019 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  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  CFRG Note on Post-Quantum Cryptography  . . . . . . . . .   5
     1.2.  Intellectual Property . . . . . . . . . . . . . . . . . .   6
       1.2.1.  Disclaimer  . . . . . . . . . . . . . . . . . . . . .   6
     1.3.  Conventions Used in This Document . . . . . . . . . . . .   6
   2.  Interface . . . . . . . . . . . . . . . . . . . . . . . . . .   6
   3.  Notation  . . . . . . . . . . . . . . . . . . . . . . . . . .   7
     3.1.  Data Types  . . . . . . . . . . . . . . . . . . . . . . .   7
       3.1.1.  Operators . . . . . . . . . . . . . . . . . . . . . .   7
       3.1.2.  Functions . . . . . . . . . . . . . . . . . . . . . .   8
       3.1.3.  Strings of w-Bit Elements . . . . . . . . . . . . . .   8
     3.2.  Typecodes . . . . . . . . . . . . . . . . . . . . . . . .   9
     3.3.  Notation and Formats  . . . . . . . . . . . . . . . . . .   9
   4.  LM-OTS One-Time Signatures  . . . . . . . . . . . . . . . . .  12
     4.1.  Parameters  . . . . . . . . . . . . . . . . . . . . . . .  13
     4.2.  Private Key . . . . . . . . . . . . . . . . . . . . . . .  14
     4.3.  Public Key  . . . . . . . . . . . . . . . . . . . . . . .  15
     4.4.  Checksum  . . . . . . . . . . . . . . . . . . . . . . . .  15
     4.5.  Signature Generation  . . . . . . . . . . . . . . . . . .  16
     4.6.  Signature Verification  . . . . . . . . . . . . . . . . .  17
   5.  Leighton-Micali Signatures  . . . . . . . . . . . . . . . . .  19
     5.1.  Parameters  . . . . . . . . . . . . . . . . . . . . . . .  19
     5.2.  LMS Private Key . . . . . . . . . . . . . . . . . . . . .  20
     5.3.  LMS Public Key  . . . . . . . . . . . . . . . . . . . . .  21
     5.4.  LMS Signature . . . . . . . . . . . . . . . . . . . . . .  22
       5.4.1.  LMS Signature Generation  . . . . . . . . . . . . . .  23
       5.4.2.  LMS Signature Verification  . . . . . . . . . . . . .  24
   6.  Hierarchical Signatures . . . . . . . . . . . . . . . . . . .  26
     6.1.  Key Generation  . . . . . . . . . . . . . . . . . . . . .  29
     6.2.  Signature Generation  . . . . . . . . . . . . . . . . . .  30
     6.3.  Signature Verification  . . . . . . . . . . . . . . . . .  32
     6.4.  Parameter Set Recommendations . . . . . . . . . . . . . .  32
   7.  Rationale . . . . . . . . . . . . . . . . . . . . . . . . . .  34
     7.1.  Security String . . . . . . . . . . . . . . . . . . . . .  35

McGrew, et al.                Informational                     [Page 2]

RFC 8554                LMS Hash-Based Signatures             April 2019

   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  36
   9.  Security Considerations . . . . . . . . . . . . . . . . . . .  38
     9.1.  Hash Formats  . . . . . . . . . . . . . . . . . . . . . .  39
     9.2.  Stateful Signature Algorithm  . . . . . . . . . . . . . .  40
     9.3.  Security of LM-OTS Checksum . . . . . . . . . . . . . . .  41
   10. Comparison with Other Work  . . . . . . . . . . . . . . . . .  42
   11. References  . . . . . . . . . . . . . . . . . . . . . . . . .  43
     11.1.  Normative References . . . . . . . . . . . . . . . . . .  43
     11.2.  Informative References . . . . . . . . . . . . . . . . .  43
   Appendix A.  Pseudorandom Key Generation  . . . . . . . . . . . .  45
   Appendix B.  LM-OTS Parameter Options . . . . . . . . . . . . . .  45
   Appendix C.  An Iterative Algorithm for Computing an LMS Public
                Key  . . . . . . . . . . . . . . . . . . . . . . . .  47
   Appendix D.  Method for Deriving Authentication Path for a
                Signature  . . . . . . . . . . . . . . . . . . . . .  48
   Appendix E.  Example Implementation . . . . . . . . . . . . . . .  49
   Appendix F.  Test Cases . . . . . . . . . . . . . . . . . . . . .  49
   Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  60
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  61

1.  Introduction

   One-time signature systems, and general-purpose signature systems
   built out of one-time signature systems, have been known since 1979
   [Merkle79], were well studied in the 1990s [USPTO5432852], and have
   benefited from renewed attention in the last decade.  The
   characteristics of these signature systems are small private and
   public keys and fast signature generation and verification, but large
   signatures and moderately slow key generation (in comparison with RSA
   and ECDSA (Elliptic Curve Digital Signature Algorithm)).  Private
   keys can be made very small by appropriate key generation, for
   example, as described in Appendix A.  In recent years, there has been
   interest in these systems because of their post-quantum security and
   their suitability for compact verifier implementations.

   This note describes the Leighton and Micali adaptation [USPTO5432852]
   of the original Lamport-Diffie-Winternitz-Merkle one-time signature
   system [Merkle79] [C:Merkle87] [C:Merkle89a] [C:Merkle89b] and
   general signature system [Merkle79] with enough specificity to ensure
   interoperability between implementations.

   A signature system provides asymmetric message authentication.  The
   key-generation algorithm produces a public/private key pair.  A
   message is signed by a private key, producing a signature, and a
   message/signature pair can be verified by a public key.  A One-Time
   Signature (OTS) system can be used to sign one message securely but
   will become insecure if more than one is signed with the same public/

McGrew, et al.                Informational                     [Page 3]

RFC 8554                LMS Hash-Based Signatures             April 2019

   private key pair.  An N-time signature system can be used to sign N
   or fewer messages securely.  A Merkle-tree signature scheme is an
   N-time signature system that uses an OTS system as a component.

   In the Merkle scheme, a binary tree of height h is used to hold 2^h
   OTS key pairs.  Each interior node of the tree holds a value that is
   the hash of the values of its two child nodes.  The public key of the
   tree is the value of the root node (a recursive hash of the OTS
   public keys), while the private key of the tree is the collection of
   all the OTS private keys, together with the index of the next OTS
   private key to sign the next message with.

   In this note, we describe the Leighton-Micali Signature (LMS) system
   (a variant of the Merkle scheme) with the Hierarchical Signature
   System (HSS) built on top of it that allows it to efficiently scale
   to larger numbers of signatures.  In order to support signing a large
   number of messages on resource-constrained systems, the Merkle tree
   can be subdivided into a number of smaller trees.  Only the
   bottommost tree is used to sign messages, while trees above that are
   used to sign the public keys of their children.  For example, in the
   simplest case with two levels with both levels consisting of height h
   trees, the root tree is used to sign 2^h trees with 2^h OTS key
   pairs, and each second-level tree has 2^h OTS key pairs, for a total
   of 2^(2h) bottom-level key pairs, and so can sign 2^(2h) messages.
   The advantage of this scheme is that only the active trees need to be
   instantiated, which saves both time (for key generation) and space
   (for key storage).  On the other hand, using a multilevel signature
   scheme increases the size of the signature as well as the signature
   verification time.

   This note is structured as follows.  Notes on post-quantum
   cryptography are discussed in Section 1.1.  Intellectual property
   issues are discussed in Section 1.2.  The notation used within this
   note is defined in Section 3, and the public formats are described in
   Section 3.3.  The Leighton-Micali One-Time Signature (LM-OTS) system
   is described in Section 4, and the LMS and HSS N-time signature
   systems are described in Sections 5 and 6, respectively.  Sufficient
   detail is provided to ensure interoperability.  The rationale for the
   design decisions is given in Section 7.  The IANA registry for these
   signature systems is described in Section 8.  Security considerations
   are presented in Section 9.  Comparison with another hash-based
   signature algorithm (eXtended Merkle Signature Scheme (XMSS)) is in
   Section 10.

   This document represents the rough consensus of the CFRG.

McGrew, et al.                Informational                     [Page 4]

RFC 8554                LMS Hash-Based Signatures             April 2019

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

   Many of these algorithms come with specific restrictions, e.g.,
   change of classical interface or less cryptanalysis of proposed
   parameters than established schemes.  The 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 LMS:

   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 dynamic secret key state; that is, the API MUST allow the
   signature-generation algorithm to update the secret key state.

McGrew, et al.                Informational                     [Page 5]

RFC 8554                LMS Hash-Based Signatures             April 2019

1.2.  Intellectual Property

   This document is based on U.S. Patent 5,432,852, which was issued
   over twenty years ago and is thus expired.

1.2.1.  Disclaimer

   This document is not intended as legal advice.  Readers are advised
   to consult with their own legal advisers if they would like a legal
   interpretation of their rights.

   The IETF policies and processes regarding intellectual property and
   patents are outlined in [RFC8179] and at

1.3.  Conventions Used in This Document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "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.  Interface

   The LMS signing algorithm is stateful; it modifies and updates the
   private key as a side effect of generating a signature.  Once a
   particular value of the private key is used to sign one message, it
   MUST NOT be used to sign another.

   The key-generation algorithm takes as input an indication of the
   parameters for the signature system.  If it is successful, it returns
   both a private key and a public key.  Otherwise, it returns an
   indication of failure.

   The signing algorithm takes as input the message to be signed and the
   current value of the private key.  If successful, it returns a
   signature and the next value of the private key, if there is such a
   value.  After the private key of an N-time signature system has
   signed N messages, the signing algorithm returns the signature and an
   indication that there is no next value of the private key that can be
   used for signing.  If unsuccessful, it returns an indication of

   The verification algorithm takes as input the public key, a message,
   and a signature; it returns an indication of whether or not the
   signature-and-message pair is valid.

McGrew, et al.                Informational                     [Page 6]

RFC 8554                LMS Hash-Based Signatures             April 2019

   A message/signature pair is valid if the signature was returned by
   the signing algorithm upon input of the message and the private key
   corresponding to the public key; otherwise, the signature and message
   pair is not valid with probability very close to one.

3.  Notation

3.1.  Data Types

   Bytes and byte strings are the fundamental data types.  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 with a length
   of three.  An array of byte strings is an ordered set, indexed
   starting at zero, in which all strings have the same length.

   Unsigned integers are converted into byte strings by representing
   them in network byte order.  To make the number of bytes in the
   representation explicit, we define the functions u8str(X), u16str(X),
   and u32str(X), which take a nonnegative integer X as input and return
   one-, two-, and four-byte strings, respectively.  We also make use of
   the function strTou32(S), which takes a four-byte string S as input
   and returns a nonnegative integer; the identity u32str(strTou32(S)) =
   S holds for any four-byte string S.

3.1.1.  Operators

   When a and b are real numbers, mathematical operators are defined as

      ^ : a ^ b denotes the result of a raised to the power of b

      * : a * b denotes the product of a multiplied by b

      / : a / b denotes the quotient of a divided by b

      % : a % b denotes the remainder of the integer division of a by b
      (with a and b being restricted to integers in this case)

      + : a + b denotes the sum of a and b

      - : a - b denotes the difference of a and b

      AND : a AND b denotes the bitwise AND of the two nonnegative
      integers a and b (represented in binary notation)

McGrew, et al.                Informational                     [Page 7]

RFC 8554                LMS Hash-Based Signatures             April 2019

   The standard order of operations is used when evaluating arithmetic

   When B is a byte and i is an integer, then B >> i denotes the logical
   right-shift operation by i bit positions.  Similarly, B << i denotes
   the logical left-shift operation.

   If S and T are byte strings, then S || T denotes the concatenation of
   S and T.  If S and T are equal-length byte strings, then S AND T
   denotes the bitwise logical and operation.

   The i-th element in an array A is denoted as A[i].

3.1.2.  Functions

   If r is a nonnegative real number, then we define the following

      ceil(r) : returns the smallest integer greater than or equal to r

      floor(r) : returns the largest integer less than or equal to r

      lg(r) : returns the base-2 logarithm of r

3.1.3.  Strings of w-Bit Elements

   If S is a byte string, then byte(S, i) denotes its i-th byte, where
   the index starts at 0 at the left.  Hence, byte(S, 0) is the leftmost
   byte of S, byte(S, 1) is the second byte from the left, and (assuming
   S is n bytes long) byte(S, n-1) is the rightmost byte of S.  In
   addition, bytes(S, i, j) denotes the range of bytes from the i-th to
   the j-th byte, inclusive.  For example, if S = 0x02040608, then
   byte(S, 0) is 0x02 and bytes(S, 1, 2) is 0x0406.

   A byte string can be considered to be a string of w-bit unsigned
   integers; the correspondence is defined by the function coef(S, i, w)
   as follows:

   If S is a string, i is a positive integer, and w is a member of the
   set { 1, 2, 4, 8 }, then coef(S, i, w) is the i-th, w-bit value, if S
   is interpreted as a sequence of w-bit values.  That is,

       coef(S, i, w) = (2^w - 1) AND
                       ( byte(S, floor(i * w / 8)) >>
                         (8 - (w * (i % (8 / w)) + w)) )

McGrew, et al.                Informational                     [Page 8]

RFC 8554                LMS Hash-Based Signatures             April 2019

   For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and
   coef(S, 0, 4) is 1.

                      S (represented as bits)
         | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0|
                          coef(S, 7, 1)

                 S (represented as four-bit values)
         |     1     |     2     |     3     |     4     |
         coef(S, 0, 4)

   The return value of coef is an unsigned integer.  If i is larger than
   the number of w-bit values in S, then coef(S, i, w) is undefined, and
   an attempt to compute that value MUST raise an error.

3.2.  Typecodes

   A typecode is an unsigned integer that is associated with a
   particular data format.  The format of the LM-OTS, LMS, and HSS
   signatures and public keys all begin with a typecode that indicates
   the precise details used in that format.  These typecodes are
   represented as four-byte unsigned integers in network byte order;
   equivalently, they are External Data Representation (XDR)
   enumerations (see Section 3.3).

3.3.  Notation and Formats

   The signature and public key formats are formally defined in XDR to
   provide an unambiguous, machine-readable definition [RFC4506].  The
   private key format is not included as it is not needed for
   interoperability and an implementation MAY use any private key
   format.  However, for clarity, we include an example of private key
   data in Test Case 2 of Appendix F.  Though XDR is used, these formats

McGrew, et al.                Informational                     [Page 9]

RFC 8554                LMS Hash-Based Signatures             April 2019

   are simple and easy to parse without any special tools.  An
   illustration of the layout of data in these objects is provided
   below.  The definitions are as follows:

   /* one-time signatures */

   enum lmots_algorithm_type {
     lmots_reserved       = 0,
     lmots_sha256_n32_w1  = 1,
     lmots_sha256_n32_w2  = 2,
     lmots_sha256_n32_w4  = 3,
     lmots_sha256_n32_w8  = 4

   typedef opaque bytestring32[32];

   struct lmots_signature_n32_p265 {
     bytestring32 C;
     bytestring32 y[265];

   struct lmots_signature_n32_p133 {
     bytestring32 C;
     bytestring32 y[133];

   struct lmots_signature_n32_p67 {
     bytestring32 C;
     bytestring32 y[67];

   struct lmots_signature_n32_p34 {
     bytestring32 C;
     bytestring32 y[34];

   union lmots_signature switch (lmots_algorithm_type type) {
    case lmots_sha256_n32_w1:
      lmots_signature_n32_p265 sig_n32_p265;
    case lmots_sha256_n32_w2:
      lmots_signature_n32_p133 sig_n32_p133;
    case lmots_sha256_n32_w4:
      lmots_signature_n32_p67  sig_n32_p67;
    case lmots_sha256_n32_w8:
      lmots_signature_n32_p34  sig_n32_p34;
      void;   /* error condition */

McGrew, et al.                Informational                    [Page 10]

RFC 8554                LMS Hash-Based Signatures             April 2019

   /* hash-based signatures (hbs) */

   enum lms_algorithm_type {

     lms_reserved       = 0,
     lms_sha256_n32_h5  = 5,
     lms_sha256_n32_h10 = 6,
     lms_sha256_n32_h15 = 7,
     lms_sha256_n32_h20 = 8,
     lms_sha256_n32_h25 = 9

   /* leighton-micali signatures (lms) */

   union lms_path switch (lms_algorithm_type type) {
    case lms_sha256_n32_h5:
      bytestring32 path_n32_h5[5];
    case lms_sha256_n32_h10:
      bytestring32 path_n32_h10[10];
    case lms_sha256_n32_h15:
      bytestring32 path_n32_h15[15];
    case lms_sha256_n32_h20:
      bytestring32 path_n32_h20[20];
    case lms_sha256_n32_h25:
      bytestring32 path_n32_h25[25];
      void;     /* error condition */

   struct lms_signature {
     unsigned int q;
     lmots_signature lmots_sig;
     lms_path nodes;

   struct lms_key_n32 {
     lmots_algorithm_type ots_alg_type;
     opaque I[16];
     opaque K[32];

   union lms_public_key switch (lms_algorithm_type type) {
    case lms_sha256_n32_h5:
    case lms_sha256_n32_h10:
    case lms_sha256_n32_h15:
    case lms_sha256_n32_h20:
    case lms_sha256_n32_h25:
         lms_key_n32 z_n32;

McGrew, et al.                Informational                    [Page 11]

RFC 8554                LMS Hash-Based Signatures             April 2019

      void;     /* error condition */

   /* hierarchical signature system (hss) */

   struct hss_public_key {
     unsigned int L;
     lms_public_key pub;

   struct signed_public_key {
     lms_signature sig;
     lms_public_key pub;

   struct hss_signature {
     signed_public_key signed_keys<7>;
     lms_signature sig_of_message;

4.  LM-OTS One-Time Signatures

   This section defines LM-OTS signatures.  The signature is used to
   validate the authenticity of a message by associating a secret
   private key with a shared public key.  These are one-time signatures;
   each private key MUST be used at most one time to sign any given

   As part of the signing process, a digest of the original message is
   computed using the cryptographic hash function H (see Section 4.1),
   and the resulting digest is signed.

   In order to facilitate its use in an N-time signature system, the
   LM-OTS key generation, signing, and verification algorithms all take
   as input parameters I and q.  The parameter I is a 16-byte string
   that indicates which Merkle tree this LM-OTS is used with.  The
   parameter q is a 32-bit integer that indicates the leaf of the Merkle
   tree where the OTS public key appears.  These parameters are used as
   part of the security string, as listed in Section 7.1.  When the
   LM-OTS signature system is used outside of an N-time signature
   system, the value I MAY be used to differentiate this one-time
   signature from others; however, the value q MUST be set to the all-
   zero value.

McGrew, et al.                Informational                    [Page 12]

RFC 8554                LMS Hash-Based Signatures             April 2019

4.1.  Parameters

   The signature system uses the parameters n and w, which are both
   positive integers.  The algorithm description also makes use of the
   internal parameters p and ls, which are dependent on n and w.  These
   parameters are summarized as follows:

      n : the number of bytes of the output of the hash function.

      w : the width (in bits) of the Winternitz coefficients; that is,
      the number of bits from the hash or checksum that is used with a
      single Winternitz chain.  It is a member of the set
      { 1, 2, 4, 8 }.

      p : the number of n-byte string elements that make up the LM-OTS
      signature.  This is a function of n and w; the values for the
      defined parameter sets are listed in Table 1; it can also be
      computed by the algorithm given in Appendix B.

      ls : the number of left-shift bits used in the checksum function
      Cksm (defined in Section 4.4).

      H : a second-preimage-resistant cryptographic hash function that
      accepts byte strings of any length and returns an n-byte string.

   For more background on the cryptographic security requirements for H,
   see Section 9.

   The value of n is determined by the hash function selected for use as
   part of the LM-OTS algorithm; the choice of this value has a strong
   effect on the security of the system.  The parameter w determines the
   length of the Winternitz chains computed as a part of the OTS
   signature (which involve 2^w - 1 invocations of the hash function);
   it has little effect on security.  Increasing w will shorten the
   signature, but at a cost of a larger computation to generate and
   verify a signature.  The values of p and ls are dependent on the
   choices of the parameters n and w, as described in Appendix B.
   Table 1 illustrates various combinations of n, w, p and ls, along
   with the resulting signature length.

   The value of w describes a space/time trade-off; increasing the value
   of w will cause the signature to shrink (by decreasing the value of
   p) while increasing the amount of time needed to perform operations
   with it: generate the public key and generate and verify the
   signature.  In general, the LM-OTS signature is 4+n*(p+1) bytes long,
   and public key generation will take p*(2^w - 1) + 1 hash computations
   (and signature generation and verification will take approximately
   half that on average).

McGrew, et al.                Informational                    [Page 13]

RFC 8554                LMS Hash-Based Signatures             April 2019

      | Parameter Set Name  | H      | n  | w | p   | ls | sig_len |
      | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7  | 8516    |
      |                     |        |    |   |     |    |         |
      | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6  | 4292    |
      |                     |        |    |   |     |    |         |
      | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67  | 4  | 2180    |
      |                     |        |    |   |     |    |         |
      | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34  | 0  | 1124    |

                                  Table 1

   Here SHA256 denotes the SHA-256 hash function defined in NIST
   standard [FIPS180].

4.2.  Private Key

   The format of the LM-OTS private key is an internal matter to the
   implementation, and this document does not attempt to define it.  One
   possibility is that the private key may consist of a typecode
   indicating the particular LM-OTS algorithm, an array x[] containing p
   n-byte strings, and the 16-byte string I and the 4-byte string q.
   This private key MUST be used to sign (at most) one message.  The
   following algorithm shows pseudocode for generating a private key.

   Algorithm 0: Generating a Private Key

     1. Retrieve the values of q and I (the 16-byte identifier of the
        LMS public/private key pair) from the LMS tree that this LM-OTS
        private key will be used with

     2. Set type to the typecode of the algorithm

     3. Set n and p according to the typecode and Table 1

     4. Compute the array x as follows:
        for ( i = 0; i < p; i = i + 1 ) {
          set x[i] to a uniformly random n-byte string

     5. Return u32str(type) || I || u32str(q) || x[0] || x[1] || ...
                                              || x[p-1]

   An implementation MAY use a pseudorandom method to compute x[i], as
   suggested in [Merkle79], page 46.  The details of the pseudorandom
   method do not affect interoperability, but the cryptographic strength

McGrew, et al.                Informational                    [Page 14]

RFC 8554                LMS Hash-Based Signatures             April 2019

   MUST match that of the LM-OTS algorithm.  Appendix A provides an
   example of a pseudorandom method for computing the LM-OTS private

4.3.  Public Key

   The LM-OTS public key is generated from the private key by
   iteratively applying the function H to each individual element of x,
   for 2^w - 1 iterations, then hashing all of the resulting values.

   The public key is generated from the private key using the following
   algorithm, or any equivalent process.

   Algorithm 1: Generating a One-Time Signature Public Key From a
   Private Key

     1. Set type to the typecode of the algorithm

     2. Set the integers n, p, and w according to the typecode and
        Table 1

     3. Determine x, I, and q from the private key

     4. Compute the string K as follows:
        for ( i = 0; i < p; i = i + 1 ) {
          tmp = x[i]
          for ( j = 0; j < 2^w - 1; j = j + 1 ) {
            tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
          y[i] = tmp
        K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])

     5. Return u32str(type) || I || u32str(q) || K

   where D_PBLC is the fixed two-byte value 0x8080, which is used to
   distinguish the last hash from every other hash in this system.

   The public key is the value returned by Algorithm 1.

4.4.  Checksum

   A checksum is used to ensure that any forgery attempt that
   manipulates the elements of an existing signature will be detected.
   This checksum is needed because an attacker can freely advance any of
   the Winternitz chains.  That is, if this checksum were not present,
   then an attacker who could find a hash that has every digit larger
   than the valid hash could replace it (and adjust the Winternitz

McGrew, et al.                Informational                    [Page 15]

RFC 8554                LMS Hash-Based Signatures             April 2019

   chains).  The security property that the checksum provides is
   detailed in Section 9.  The checksum function Cksm is defined as
   follows, where S denotes the n-byte string that is input to that
   function, and the value sum is a 16-bit unsigned integer:

   Algorithm 2: Checksum Calculation

     sum = 0
     for ( i = 0; i < (n*8/w); i = i + 1 ) {
       sum = sum + (2^w - 1) - coef(S, i, w)
     return (sum << ls)

   ls is the parameter that shifts the significant bits of the checksum
   into the positions that will actually be used by the coef function
   when encoding the digits of the checksum.  The actual ls parameter is
   a function of the n and w parameters; the values for the currently
   defined parameter sets are shown in Table 1.  It is calculated by the
   algorithm given in Appendix B.

   Because of the left-shift operation, the rightmost bits of the result
   of Cksm will often be zeros.  Due to the value of p, these bits will
   not be used during signature generation or verification.

4.5.  Signature Generation

   The LM-OTS signature of a message is generated by doing the following
   in sequence: prepending the LMS key identifier I, the LMS leaf
   identifier q, the value D_MESG (0x8181), and the randomizer C to the
   message; computing the hash; concatenating the checksum of the hash
   to the hash itself; considering the resulting value as a sequence of
   w-bit values; and using each of the w-bit values to determine the
   number of times to apply the function H to the corresponding element
   of the private key.  The outputs of the function H are concatenated
   together and returned as the signature.  The pseudocode for this
   procedure is shown below.

   Algorithm 3: Generating a One-Time Signature From a Private Key and a

     1. Set type to the typecode of the algorithm

     2. Set n, p, and w according to the typecode and Table 1

     3. Determine x, I, and q from the private key

     4. Set C to a uniformly random n-byte string

McGrew, et al.                Informational                    [Page 16]

RFC 8554                LMS Hash-Based Signatures             April 2019

     5. Compute the array y as follows:
        Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
        for ( i = 0; i < p; i = i + 1 ) {
          a = coef(Q || Cksm(Q), i, w)
          tmp = x[i]
          for ( j = 0; j < a; j = j + 1 ) {
            tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
          y[i] = tmp

      6. Return u32str(type) || C || y[0] || ... || y[p-1]

   Note that this algorithm results in a signature whose elements are
   intermediate values of the elements computed by the public key
   algorithm in Section 4.3.

   The signature is the string returned by Algorithm 3.  Section 3.3
   formally defines the structure of the string as the lmots_signature

4.6.  Signature Verification

   In order to verify a message with its signature (an array of n-byte
   strings, denoted as y), the receiver must "complete" the chain of
   iterations of H using the w-bit coefficients of the string resulting
   from the concatenation of the message hash and its checksum.  This
   computation should result in a value that matches the provided public

   Algorithm 4a: Verifying a Signature and Message Using a Public Key

     1. If the public key is not at least four bytes long,
        return INVALID.

     2. Parse pubtype, I, q, and K from the public key as follows:
        a. pubtype = strTou32(first 4 bytes of public key)

        b. Set n according to the pubkey and Table 1; if the public key
           is not exactly 24 + n bytes long, return INVALID.

        c. I = next 16 bytes of public key

        d. q = strTou32(next 4 bytes of public key)

        e. K = next n bytes of public key

McGrew, et al.                Informational                    [Page 17]

RFC 8554                LMS Hash-Based Signatures             April 2019

     3. Compute the public key candidate Kc from the signature,
        message, pubtype, and the identifiers I and q obtained from the
        public key, using Algorithm 4b.  If Algorithm 4b returns
        INVALID, then return INVALID.

     4. If Kc is equal to K, return VALID; otherwise, return INVALID.

   Algorithm 4b: Computing a Public Key Candidate Kc from a Signature,
   Message, Signature Typecode pubtype, and Identifiers I, q

     1. If the signature is not at least four bytes long,
        return INVALID.

     2. Parse sigtype, C, and y from the signature as follows:
        a. sigtype = strTou32(first 4 bytes of signature)

        b. If sigtype is not equal to pubtype, return INVALID.

        c. Set n and p according to the pubtype and Table 1; if the
           signature is not exactly 4 + n * (p+1) bytes long,
           return INVALID.

        d. C = next n bytes of signature

        e.   y[0] = next n bytes of signature
             y[1] = next n bytes of signature
           y[p-1] = next n bytes of signature

     3. Compute the string Kc as follows:
        Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
        for ( i = 0; i < p; i = i + 1 ) {
          a = coef(Q || Cksm(Q), i, w)
          tmp = y[i]
          for ( j = a; j < 2^w - 1; j = j + 1 ) {
            tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
          z[i] = tmp
        Kc = H(I || u32str(q) || u16str(D_PBLC) ||
                                      z[0] || z[1] || ... || z[p-1])

     4. Return Kc.

McGrew, et al.                Informational                    [Page 18]

RFC 8554                LMS Hash-Based Signatures             April 2019

5.  Leighton-Micali Signatures

   The Leighton-Micali Signature (LMS) method can sign a potentially
   large but fixed number of messages.  An LMS system uses two
   cryptographic components: a one-time signature method and a hash
   function.  Each LMS public/private key pair is associated with a
   perfect binary tree, each node of which contains an m-byte value,
   where m is the output length of the hash function.  Each leaf of the
   tree contains the value of the public key of an LM-OTS public/private
   key pair.  The value contained by the root of the tree is the LMS
   public key.  Each interior node is computed by applying the hash
   function to the concatenation of the values of its children nodes.

   Each node of the tree is associated with a node number, an unsigned
   integer that is denoted as node_num in the algorithms below, which is
   computed as follows.  The root node has node number 1; for each node
   with node number N < 2^h (where h is the height of the tree), its
   left child has node number 2*N, while its right child has node number
   2*N + 1.  The result of this is that each node within the tree will
   have a unique node number, and the leaves will have node numbers 2^h,
   (2^h)+1, (2^h)+2, ..., (2^h)+(2^h)-1.  In general, the j-th node at
   level i has node number 2^i + j.  The node number can conveniently be
   computed when it is needed in the LMS algorithms, as described in
   those algorithms.

5.1.  Parameters

   An LMS system has the following parameters:

      h : the height of the tree

      m : the number of bytes associated with each node

      H : a second-preimage-resistant cryptographic hash function that
      accepts byte strings of any length and returns an m-byte string.

   There are 2^h leaves in the tree.

   The overall strength of LMS signatures is governed by the weaker of
   the hash function used within the LM-OTS and the hash function used
   within the LMS system.  In order to minimize the risk, these two hash
   functions SHOULD be the same (so that an attacker could not take
   advantage of the weaker hash function choice).

McGrew, et al.                Informational                    [Page 19]

RFC 8554                LMS Hash-Based Signatures             April 2019

                 | Name               | H      | m  | h  |
                 | LMS_SHA256_M32_H5  | SHA256 | 32 | 5  |
                 |                    |        |    |    |
                 | LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
                 |                    |        |    |    |
                 | LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
                 |                    |        |    |    |
                 | LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
                 |                    |        |    |    |
                 | LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |

                                  Table 2

5.2.  LMS Private Key

   The format of the LMS private key is an internal matter to the
   implementation, and this document does not attempt to define it.  One
   possibility is that it may consist of an array OTS_PRIV[] of 2^h
   LM-OTS private keys and the leaf number q of the next LM-OTS private
   key that has not yet been used.  The q-th element of OTS_PRIV[] is
   generated using Algorithm 0 with the identifiers I, q.  The leaf
   number q is initialized to zero when the LMS private key is created.
   The process is as follows:

   Algorithm 5: Computing an LMS Private Key.

     1. Determine h and m from the typecode and Table 2.

     2. Set I to a uniformly random 16-byte string.

     3. Compute the array OTS_PRIV[] as follows:
        for ( q = 0; q < 2^h; q = q + 1) {
          OTS_PRIV[q] = LM-OTS private key with identifiers I, q

     4. q = 0

   An LMS private key MAY be generated pseudorandomly from a secret
   value; in this case, the secret value MUST be at least m bytes long
   and uniformly random and MUST NOT be used for any other purpose than
   the generation of the LMS private key.  The details of how this
   process is done do not affect interoperability; that is, the public
   key verification operation is independent of these details.
   Appendix A provides an example of a pseudorandom method for computing
   an LMS private key.

McGrew, et al.                Informational                    [Page 20]

RFC 8554                LMS Hash-Based Signatures             April 2019

   The signature-generation logic uses q as the next leaf to use; hence,
   step 4 starts it off at the leftmost leaf.  Because the signature
   process increments q after the signature operation, the first
   signature will have q=0.

5.3.  LMS Public Key

   An LMS public key is defined as follows, where we denote the public
   key final hash value (namely, the K value computed in Algorithm 1)
   associated with the i-th LM-OTS private key as OTS_PUB_HASH[i], with
   i ranging from 0 to (2^h)-1.  Each instance of an LMS public/private
   key pair is associated with a balanced binary tree, and the nodes of
   that tree are indexed from 1 to 2^(h+1)-1.  Each node is associated
   with an m-byte string.  The string for the r-th node is denoted as
   T[r] and defined as

     if r >= 2^h:

   where D_LEAF is the fixed two-byte value 0x8282 and D_INTR is the
   fixed two-byte value 0x8383, both of which are used to distinguish
   this hash from every other hash in this system.

   When we have r >= 2^h, then we are processing a leaf node (and thus
   hashing only a single LM-OTS public key).  When we have r < 2^h, then
   we are processing an internal node -- that is, a node with two child
   nodes that we need to combine.

   The LMS public key can be represented as the byte string

     u32str(type) || u32str(otstype) || I || T[1]

   Section 3.3 specifies the format of the type variable.  The value
   otstype is the parameter set for the LM-OTS public/private key pairs
   used.  The value I is the private key identifier and is the value
   used for all computations for the same LMS tree.  The value T[1] can
   be computed via recursive application of the above equation or by any
   equivalent method.  An iterative procedure is outlined in Appendix C.

McGrew, et al.                Informational                    [Page 21]

RFC 8554                LMS Hash-Based Signatures             April 2019

5.4.  LMS Signature

   An LMS signature consists of

      the number q of the leaf associated with the LM-OTS signature, as
      a four-byte unsigned integer in network byte order, an LM-OTS

      a typecode indicating the particular LMS algorithm,

      an array of h m-byte values that is associated with the path
      through the tree from the leaf associated with the LM-OTS
      signature to the root.

   Symbolically, the signature can be represented as

       u32str(q) || lmots_signature || u32str(type) ||
                 path[0] || path[1] || path[2] || ... || path[h-1]

   Section 3.3 formally defines the format of the signature as the
   lms_signature structure.  The array for a tree with height h will
   have h values and contains the values of the siblings of (that is, is
   adjacent to) the nodes on the path from the leaf to the root, where
   the sibling to node A is the other node that shares node A's parent.
   In the signature, 0 is counted from the bottom level of the tree, and
   so path[0] is the value of the node adjacent to leaf node q; path[1]
   is the second-level node that is adjacent to leaf node q's parent,
   and so on up the tree until we get to path[h-1], which is the value
   of the next-to-the-top-level node whose branch the leaf node q does
   not reside in.

   Below is a simple example of the authentication path for h=3 and q=2.
   The leaf marked OTS is the one-time signature that is used to sign
   the actual message.  The nodes on the path from the OTS public key to
   the root are marked with a *, while the nodes that are used within
   the path array are marked with **.  The values in the path array are
   those nodes that are siblings of the nodes on the path; path[0] is
   the leaf** node that is adjacent to the OTS public key (which is the
   start of the path); path[1] is the T[4]** node that is the sibling of
   the second node T[5]* on the path, and path[2] is the T[3]** node
   that is the sibling of the third node T[2]* on the path.

McGrew, et al.                Informational                    [Page 22]

RFC 8554                LMS Hash-Based Signatures             April 2019

                 |                               |
               T[2]*                          T[3]**
                 |                               |
          ------------------            -----------------
          |                |            |               |
       T[4]**           T[5]*         T[6]            T[7]
          |                |            |               |
      ---------       ----------     --------       ---------
      |       |       |        |     |      |       |       |
     leaf    leaf    OTS  leaf**   leaf   leaf    leaf    leaf

   The idea behind this authentication path is that it allows us to
   validate the OTS hash with using h path array values and hash
   computations.  What the verifier does is recompute the hashes up the
   path; first, it hashes the given OTS and path[0] value, giving a
   tentative T[5]' value.  Then, it hashes its path[1] and tentative
   T[5]' value to get a tentative T[2]' value.  Then, it hashes that and
   the path[2] value to get a tentative Root' value.  If that value is
   the known public key of the Merkle tree, then we can assume that the
   value T[2]' it got was the correct T[2] value in the original tree,
   and so the T[5]' value it got was the correct T[5] value in the
   original tree, and so the OTS public key is the same as in the
   original and, hence, is correct.

5.4.1.  LMS Signature Generation

   To compute the LMS signature of a message with an LMS private key,
   the signer first computes the LM-OTS signature of the message using
   the leaf number of the next unused LM-OTS private key.  The leaf
   number q in the signature is set to the leaf number of the LMS
   private key that was used in the signature.  Before releasing the
   signature, the leaf number q in the LMS private key MUST be
   incremented to prevent the LM-OTS private key from being used again.
   If the LMS private key is maintained in nonvolatile memory, then the
   implementation MUST ensure that the incremented value has been stored
   before releasing the signature.  The issue this tries to prevent is a
   scenario where a) we generate a signature using one LM-OTS private
   key and release it to the application, b) before we update the
   nonvolatile memory, we crash, and c) we reboot and generate a second
   signature using the same LM-OTS private key.  With two different
   signatures using the same LM-OTS private key, an attacker could
   potentially generate a forged signature of a third message.

McGrew, et al.                Informational                    [Page 23]

RFC 8554                LMS Hash-Based Signatures             April 2019

   The array of node values in the signature MAY be computed in any way.
   There are many potential time/storage trade-offs that can be applied.
   The fastest alternative is to store all of the nodes of the tree and
   set the array in the signature by copying them; pseudocode to do so
   appears in Appendix D.  The least storage-intensive alternative is to
   recompute all of the nodes for each signature.  Note that the details
   of this procedure are not important for interoperability; it is not
   necessary to know any of these details in order to perform the
   signature-verification operation.  The internal nodes of the tree
   need not be kept secret, and thus a node-caching scheme that stores
   only internal nodes can sidestep the need for strong protections.

   Several useful time/storage trade-offs are described in the "Small-
   Memory LM Schemes" section of [USPTO5432852].

5.4.2.  LMS Signature Verification

   An LMS signature is verified by first using the LM-OTS signature
   verification algorithm (Algorithm 4b) to compute the LM-OTS public
   key from the LM-OTS signature and the message.  The value of that
   public key is then assigned to the associated leaf of the LMS tree,
   and then the root of the tree is computed from the leaf value and the
   array path[] as described in Algorithm 6 below.  If the root value
   matches the public key, then the signature is valid; otherwise, the
   signature verification fails.

   Algorithm 6: LMS Signature Verification

     1. If the public key is not at least eight bytes long, return

     2. Parse pubtype, I, and T[1] from the public key as follows:

        a. pubtype = strTou32(first 4 bytes of public key)

        b. ots_typecode = strTou32(next 4 bytes of public key)

        c. Set m according to pubtype, based on Table 2.

        d. If the public key is not exactly 24 + m bytes
           long, return INVALID.

        e. I = next 16 bytes of the public key

        f. T[1] = next m bytes of the public key

McGrew, et al.                Informational                    [Page 24]

RFC 8554                LMS Hash-Based Signatures             April 2019

     3. Compute the LMS Public Key Candidate Tc from the signature,
        message, identifier, pubtype, and ots_typecode, using
        Algorithm 6a.

     4. If Tc is equal to T[1], return VALID; otherwise, return INVALID.

   Algorithm 6a: Computing an LMS Public Key Candidate from a Signature,
   Message, Identifier, and Algorithm Typecodes

     1. If the signature is not at least eight bytes long,
        return INVALID.

     2. Parse sigtype, q, lmots_signature, and path from the signature
        as follows:

        a. q = strTou32(first 4 bytes of signature)

        b. otssigtype = strTou32(next 4 bytes of signature)

        c. If otssigtype is not the OTS typecode from the public key,
           return INVALID.

        d. Set n, p according to otssigtype and Table 1; if the
           signature is not at least 12 + n * (p + 1) bytes long,
           return INVALID.

        e. lmots_signature = bytes 4 through 7 + n * (p + 1)
           of signature

        f. sigtype = strTou32(bytes 8 + n * (p + 1)) through
           11 + n * (p + 1) of signature)

        g. If sigtype is not the LM typecode from the public key,
           return INVALID.

        h. Set m, h according to sigtype and Table 2.

        i. If q >= 2^h or the signature is not exactly
           12 + n * (p + 1) + m * h bytes long,
           return INVALID.

        j. Set path as follows:
             path[0] = next m bytes of signature
             path[1] = next m bytes of signature
           path[h-1] = next m bytes of signature

McGrew, et al.                Informational                    [Page 25]

RFC 8554                LMS Hash-Based Signatures             April 2019

     3. Kc = candidate public key computed by applying Algorithm 4b
        to the signature lmots_signature, the message, and the
        identifiers I, q

     4. Compute the candidate LMS root value Tc as follows:
        node_num = 2^h + q
        tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc)
        i = 0
        while (node_num > 1) {
          if (node_num is odd):
            tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp)
            tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i])
          node_num = node_num/2
          i = i + 1
        Tc = tmp

     5. Return Tc.

6.  Hierarchical Signatures

   In scenarios where it is necessary to minimize the time taken by the
   public key generation process, the Hierarchical Signature System
   (HSS) can be used.  This hierarchical scheme, which we describe in
   this section, uses the LMS scheme as a component.  In HSS, we have a
   sequence of L LMS trees, where the public key for the first LMS tree
   is included in the public key of the HSS system, each LMS private key
   signs the next LMS public key, and the last LMS private key signs the
   actual message.  For example, if we have a three-level hierarchy
   (L=3), then to sign a message, we would have:

      The first LMS private key (level 0) signs a level 1 LMS public

      The second LMS private key (level 1) signs a level 2 LMS public

      The third LMS private key (level 2) signs the message.

   The root of the level 0 LMS tree is contained in the HSS public key.

   To verify the LMS signature, we would verify all the signatures:

      We would verify that the level 1 LMS public key is correctly
      signed by the level 0 signature.

McGrew, et al.                Informational                    [Page 26]

RFC 8554                LMS Hash-Based Signatures             April 2019

      We would verify that the level 2 LMS public key is correctly
      signed by the level 1 signature.

      We would verify that the message is correctly signed by the level
      2 signature.

   We would accept the HSS signature only if all the signatures

   During the signature-generation process, we sign messages with the
   lowest (level L-1) LMS tree.  Once we have used all the leafs in that
   tree to sign messages, we would discard it, generate a fresh LMS
   tree, and sign it with the next (level L-2) LMS tree (and when that
   is used up, recursively generate and sign a fresh level L-2 LMS

   HSS, in essence, utilizes a tree of LMS trees.  There is a single LMS
   tree at level 0 (the root).  Each LMS tree (actually, the private key
   corresponding to the LMS tree) at level i is used to sign 2^h objects
   (where h is the height of trees at level i).  If i < L-1, then each
   object will be another LMS tree (actually, the public key) at level
   i+1; if i = L-1, we've reached the bottom of the HSS tree, and so
   each object will be a message from the application.  The HSS public
   key contains the public key of the LMS tree at the root, and an HSS
   signature is associated with a path from the root of the HSS tree to
   the leaf.

   Compared to LMS, HSS has a much reduced public key generation time,
   as only the root tree needs to be generated prior to the distribution
   of the HSS public key.  For example, an L=3 tree (with h=10 at each
   level) would have one level 0 LMS tree, 2^10 level 1 LMS trees (with
   each such level 1 public key signed by one of the 1024 level 0 OTS
   public keys), and 2^20 level 2 LMS trees.  Only 1024 OTS public keys
   need to be computed to generate the HSS public key (as you need to
   compute only the level 0 LMS tree to compute that value; you can, of
   course, decide to compute the initial level 1 and level 2 LMS trees).
   In addition, the 2^20 level 2 LMS trees can jointly sign a total of
   over a billion messages.  In contrast, a single LMS tree that could
   sign a billion messages would require a billion OTS public keys to be
   computed first (if h=30 were allowed in a supported parameter set).

   Each LMS tree within the hierarchy is associated with a distinct LMS
   public key, private key, signature, and identifier.  The number of
   levels is denoted as L and is between one and eight, inclusive.  The
   following notation is used, where i is an integer between 0 and L-1
   inclusive, and the root of the hierarchy is level 0:

      prv[i] is the current LMS private key of the i-th level.

McGrew, et al.                Informational                    [Page 27]

RFC 8554                LMS Hash-Based Signatures             April 2019

      pub[i] is the current LMS public key of the i-th level, as
      described in Section 5.3.

      sig[i] is the LMS signature of public key pub[i+1] generated using
      the private key prv[i].

   It is expected that the above arrays are maintained for the course of
   the HSS key.  The contents of the prv[] array MUST be kept private;
   the pub[] and sig[] array may be revealed should the implementation
   find that convenient.

   In this section, we say that an N-time private key is exhausted when
   it has generated N signatures; thus, it can no longer be used for

   For i > 0, the values prv[i], pub[i], and (for all values of i)
   sig[i] will be updated over time as private keys are exhausted and
   replaced by newer keys.

   When these key pairs are updated (or initially generated before the
   first message is signed), then the LMS key generation processes
   outlined in Sections 5.2 and 5.3 are performed.  If the generated key
   pairs are for level i of the HSS hierarchy, then we store the public
   key in pub[i] and the private key in prv[i].  In addition, if i > 0,
   then we sign the generated public key with the LMS private key at
   level i-1, placing the signature into sig[i-1].  When the LMS key
   pair is generated, the key pair and the corresponding identifier MUST
   be generated independently of all other key pairs.

   HSS allows L=1, in which case the HSS public key and signature
   formats are essentially the LMS public key and signature formats,
   prepended by a fixed field.  Since HSS with L=1 has very little
   overhead compared to LMS, all implementations MUST support HSS in
   order to maximize interoperability.

   We specifically allow different LMS levels to use different parameter
   sets.  For example, the 0-th LMS public key (the root) may use the
   LMS_SHA256_M32_H15 parameter set, while the 1-th public key may use
   LMS_SHA256_M32_H10.  There are practical reasons to allow this; for
   one, the signer may decide to store parts of the 0-th LMS tree (that
   it needs to construct while computing the public key) to accelerate
   later operations.  As the 0-th tree is never updated, these internal
   nodes will never need to be recomputed.  In addition, during the
   signature-generation operation, almost all the operations involved
   with updating the authentication path occur with the bottom (L-1th)
   LMS public key; hence, it may be useful to select the parameter set
   for that public key to have a shorter LMS tree.

McGrew, et al.                Informational                    [Page 28]

RFC 8554                LMS Hash-Based Signatures             April 2019

   A close reading of the HSS verification pseudocode shows that it
   would allow the parameters of the nontop LMS public keys to change
   over time; for example, the signer might initially have the 1-th LMS
   public key use the LMS_SHA256_M32_H10 parameter set, but when that
   tree is exhausted, the signer might replace it with an LMS public key
   that uses the LMS_SHA256_M32_H15 parameter set.  While this would
   work with the example verification pseudocode, the signer MUST NOT
   change the parameter sets for a specific level.  This prohibition is
   to support verifiers that may keep state over the course of several
   signature verifications.

6.1.  Key Generation

   The public key of the HSS scheme consists of the number of levels L,
   followed by pub[0], the public key of the top level.

   The HSS private key consists of prv[0], ... , prv[L-1], along with
   the associated pub[0], ... pub[L-1] and sig[0], ..., sig[L-2] values.
   As stated earlier, the values of the pub[] and sig[] arrays need not
   be kept secret and may be revealed.  The value of pub[0] does not
   change (and, except for the index q, the value of prv[0] need not
   change); however, the values of pub[i] and prv[i] are dynamic for i >
   0 and are changed by the signature-generation algorithm.

   During the key generation, the public and private keys are
   initialized.  Here is some pseudocode that explains the key-
   generation logic:

   Algorithm 7: Generating an HSS Key Pair

     1. Generate an LMS key pair, as specified in Sections 5.2 and 5.3,
        placing the private key into priv[0], and the public key into

     2. For i = 1 to L-1 do {
          generate an LMS key pair, placing the private key into priv[i]
          and the public key into pub[i]

          sig[i-1] = lms_signature( pub[i], priv[i-1] )

     3. Return u32str(L) || pub[0] as the public key and the priv[],
        pub[], and sig[] arrays as the private key

   In the above algorithm, each LMS public/private key pair generated
   MUST be generated independently.

McGrew, et al.                Informational                    [Page 29]

RFC 8554                LMS Hash-Based Signatures             April 2019

   Note that the value of the public key does not depend on the
   execution of step 2.  As a result, an implementation may decide to
   delay step 2 until later -- for example, during the initial
   signature-generation operation.

6.2.  Signature Generation

   To sign a message using an HSS key pair, the following steps are

      If prv[L-1] is exhausted, then determine the smallest integer d
      such that all of the private keys prv[d], prv[d+1], ... , prv[L-1]
      are exhausted.  If d is equal to zero, then the HSS key pair is
      exhausted, and it MUST NOT generate any more signatures.
      Otherwise, the key pairs for levels d through L-1 must be
      regenerated during the signature-generation process, as follows.
      For i from d to L-1, a new LMS public and private key pair with a
      new identifier is generated, pub[i] and prv[i] are set to those
      values, then the public key pub[i] is signed with prv[i-1], and
      sig[i-1] is set to the resulting value.

      The message is signed with prv[L-1], and the value sig[L-1] is set
      to that result.

      The value of the HSS signature is set as follows.  We let
      signed_pub_key denote an array of octet strings, where
      signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and
      Nspk-1, inclusive, where Nspk = L-1 denotes the number of signed
      public keys.  Then the HSS signature is u32str(Nspk) ||
      signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk].

      Note that the number of signed_pub_key elements in the signature
      is indicated by the value Nspk that appears in the initial four
      bytes of the signature.

   Here is some pseudocode of the above logic:

   Algorithm 8: Generating an HSS signature

     1. If the message-signing key prv[L-1] is exhausted, regenerate
        that key pair, together with any parent key pairs that might
        be necessary.

        If the root key pair is exhausted, then the HSS key pair is
        exhausted and MUST NOT generate any more signatures.

McGrew, et al.                Informational                    [Page 30]

RFC 8554                LMS Hash-Based Signatures             April 2019

        d = L
        while (prv[d-1].q == 2^(prv[d-1].h)) {
          d = d - 1
          if (d == 0)
            return FAILURE
        while (d < L) {
          create lms key pair pub[d], prv[d]
          sig[d-1] = lms_signature( pub[d], prv[d-1] )
          d = d + 1

     2. Sign the message.
        sig[L-1] = lms_signature( msg, prv[L-1] )

     3. Create the list of signed public keys.
        i = 0;
        while (i < L-1) {
          signed_pub_key[i] = sig[i] || pub[i+1]
          i = i + 1

     4. Return u32str(L-1) || signed_pub_key[0] || ...
                                 || signed_pub_key[L-2] || sig[L-1]

   In the specific case of L=1, the format of an HSS signature is

     u32str(0) || sig[0]

   In the general case, the format of an HSS signature is

     u32str(Nspk) || signed_pub_key[0] || ...
                              || signed_pub_key[Nspk-1] || sig[Nspk]

   which is equivalent to

     u32str(Nspk) || sig[0] || pub[1] || ...
                              || sig[Nspk-1] || pub[Nspk] || sig[Nspk]

McGrew, et al.                Informational                    [Page 31]

RFC 8554                LMS Hash-Based Signatures             April 2019

6.3.  Signature Verification

   To verify a signature S and message using the public key pub, perform
   the following steps:

     The signature S is parsed into its components as follows:

     Nspk = strTou32(first four bytes of S)
     if Nspk+1 is not equal to the number of levels L in pub:
       return INVALID
     for (i = 0; i < Nspk; i = i + 1) {
       siglist[i] = next LMS signature parsed from S
       publist[i] = next LMS public key parsed from S
     siglist[Nspk] = next LMS signature parsed from S

     key = pub
     for (i = 0; i < Nspk; i = i + 1) {
       sig = siglist[i]
       msg = publist[i]
       if (lms_verify(msg, key, sig) != VALID):
         return INVALID
       key = msg
     return lms_verify(message, key, siglist[Nspk])

   Since the length of an LMS signature cannot be known without parsing
   it, the HSS signature verification algorithm makes use of an LMS
   signature parsing routine that takes as input a string consisting of
   an LMS signature with an arbitrary string appended to it and returns
   both the LMS signature and the appended string.  The latter is passed
   on for further processing.

6.4.  Parameter Set Recommendations

   As for guidance as to the number of LMS levels and the size of each,
   any discussion of performance is implementation specific.  In
   general, the sole drawback for a single LMS tree is the time it takes
   to generate the public key; as every LM-OTS public key needs to be
   generated, the time this takes can be substantial.  For a two-level
   tree, only the top-level LMS tree and the initial bottom-level LMS
   tree need to be generated initially (before the first signature is
   generated); this will in general be significantly quicker.

   To give a general idea of the trade-offs available, we include some
   measurements taken with the LMS implementation available at
   <https://github.com/cisco/hash-sigs>, taken on a 3.3 GHz Xeon
   processor with threading enabled.  We tried various parameter sets,

McGrew, et al.                Informational                    [Page 32]

RFC 8554                LMS Hash-Based Signatures             April 2019

   all with W=8 (which minimizes signature size, while increasing time).
   These are here to give a guideline as to what's possible; for the
   computational time, your mileage may vary, depending on the computing
   resources you have.  The machine these tests were performed on does
   not have the SHA-256 extensions; you could possibly do significantly

             | ParmSet | KeyGenTime | SigSize | KeyLifetime |
             | 15      | 6 sec      | 1616    | 30 seconds  |
             |         |            |         |             |
             | 20      | 3 min      | 1776    | 16 minutes  |
             |         |            |         |             |
             | 25      | 1.5 hour   | 1936    | 9 hours     |
             |         |            |         |             |
             | 15/10   | 6 sec      | 3172    | 9 hours     |
             |         |            |         |             |
             | 15/15   | 6 sec      | 3332    | 12 days     |
             |         |            |         |             |
             | 20/10   | 3 min      | 3332    | 12 days     |
             |         |            |         |             |
             | 20/15   | 3 min      | 3492    | 1 year      |
             |         |            |         |             |
             | 25/10   | 1.5 hour   | 3492    | 1 year      |
             |         |            |         |             |
             | 25/15   | 1.5 hour   | 3652    | 34 years    |

                                  Table 3

   ParmSet:  this is the height of the Merkle tree(s); parameter sets
      listed as a single integer have L=1 and consist of a single Merkle
      tree of that height; parameter sets with L=2 are listed as x/y,
      with x being the height of the top-level Merkle tree and y being
      the bottom level.

   KeyGenTime:  the measured key-generation time; that is, the time
      needed to generate the public/private key pair.

   SigSize:  the size of a signature (in bytes)

   KeyLifetime:  the lifetime of a key, assuming we generated 1000
      signatures per second.  In practice, we're not likely to get
      anywhere close to 1000 signatures per second sustained; if you
      have a more appropriate figure for your scenario, this column is
      easy to recompute.

McGrew, et al.                Informational                    [Page 33]

RFC 8554                LMS Hash-Based Signatures             April 2019

   As for signature generation or verification times, those are
   moderately insensitive to the above parameter settings (except for
   the Winternitz setting and the number of Merkle trees for
   verification).  Tests on the same machine (without multithreading)
   gave approximately 4 msec to sign a short message, 2.6 msec to
   verify; these tests used a two-level ParmSet; a single level would
   approximately halve the verification time.  All times can be
   significantly improved (by perhaps a factor of 8) by using a
   parameter set with W=4; however, that also about doubles the
   signature size.

7.  Rationale

   The goal of this note is to describe the LM-OTS, LMS, and HSS
   algorithms following the original references and present the modern
   security analysis of those algorithms.  Other signature methods are
   out of scope and may be interesting follow-on work.

   We adopt the techniques described by Leighton and Micali to mitigate
   attacks that amortize their work over multiple invocations of the
   hash function.

   The values taken by the identifier I across different LMS public/
   private key pairs are chosen randomly in order to improve security.
   The analysis of this method in [Fluhrer17] shows that we do not need
   uniqueness to ensure security; we do need to ensure that we don't
   have a large number of private keys that use the same I value.  By
   randomly selecting 16-byte I values, the chance that, out of 2^64
   private keys, 4 or more of them will use the same I value is
   negligible (that is, has probability less than 2^-128).

   The reason 16-byte I values were selected was to optimize the
   Winternitz hash-chain operation.  With the current settings, the
   value being hashed is exactly 55 bytes long (for a 32-byte hash
   function), which SHA-256 can hash in a single hash-compression
   operation.  Other hash functions may be used in future
   specifications; all the ones that we will be likely to support
   (SHA-512/256 and the various SHA-3 hashes) would work well with a
   16-byte I value.

   The signature and public key formats are designed so that they are
   relatively easy to parse.  Each format starts with a 32-bit
   enumeration value that indicates the details of the signature
   algorithm and provides all of the information that is needed in order
   to parse the format.

McGrew, et al.                Informational                    [Page 34]

RFC 8554                LMS Hash-Based Signatures             April 2019

   The Checksum (Section 4.4) is calculated using a nonnegative integer
   "sum" whose width was chosen to be an integer number of w-bit fields
   such that it is capable of holding the difference of the total
   possible number of applications of the function H (as defined in the
   signing algorithm of Section 4.5) and the total actual number.  In
   the case that the number of times H is applied is 0, the sum is (2^w
   - 1) * (8*n/w).  Thus, for the purposes of this document, which
   describes signature methods based on H = SHA256 (n = 32 bytes) and w
   = { 1, 2, 4, 8 }, the sum variable is a 16-bit nonnegative integer
   for all combinations of n and w.  The calculation uses the parameter
   ls defined in Section 4.1 and calculated in Appendix B, which
   indicates the number of bits used in the left-shift operation.

7.1.  Security String

   To improve security against attacks that amortize their effort
   against multiple invocations of the hash function, Leighton and
   Micali introduced a "security string" that is distinct for each
   invocation of that function.  Whenever this process computes a hash,
   the string being hashed will start with a string formed from the
   fields below.  These fields will appear in fixed locations in the
   value we compute the hash of, and so we list where in the hash these
   fields would be present.  The fields that make up this string are as

   I     A 16-byte identifier for the LMS public/private key pair.  It
         MUST be chosen uniformly at random, or via a pseudorandom
         process, at the time that a key pair is generated, in order to
         minimize the probability that any specific value of I be used
         for a large number of different LMS private keys.  This is
         always bytes 0-15 of the value being hashed.

   r     In the LMS N-time signature scheme, the node number r
         associated with a particular node of a hash tree is used as an
         input to the hash used to compute that node.  This value is
         represented as a 32-bit (four byte) unsigned integer in network
         byte order.  Either r or q (depending on the domain-separation
         parameter) will be bytes 16-19 of the value being hashed.

   q     In the LMS N-time signature scheme, each LM-OTS signature is
         associated with the leaf of a hash tree, and q is set to the
         leaf number.  This ensures that a distinct value of q is used
         for each distinct LM-OTS public/private key pair.  This value
         is represented as a 32-bit (four byte) unsigned integer in
         network byte order.  Either r or q (depending on the domain-
         separation parameter) will be bytes 16-19 of the value being

McGrew, et al.                Informational                    [Page 35]

RFC 8554                LMS Hash-Based Signatures             April 2019

   D     A domain-separation parameter, which is a two-byte identifier
         that takes on different values in the different contexts in
         which the hash function is invoked.  D occurs in bytes 20 and
         21 of the value being hashed and takes on the following values:

            D_PBLC = 0x8080 when computing the hash of all of the
            iterates in the LM-OTS algorithm

            D_MESG = 0x8181 when computing the hash of the message in
            the LM-OTS algorithms

            D_LEAF = 0x8282 when computing the hash of the leaf of an
            LMS tree

            D_INTR = 0x8383 when computing the hash of an interior node
            of an LMS tree

   i     A value between 0 and 264; this is used in the LM-OTS scheme
         when either computing the iterations of the Winternitz chain or
         using the suggested LM-OTS private key generation process.  It
         is represented as a 16-bit (two-byte) unsigned integer in
         network byte order.  If present, it occurs at bytes 20 and 21
         of the value being hashed.

   j     In the LM-OTS scheme, j is the iteration number used when the
         private key element is being iteratively hashed.  It is
         represented as an 8-bit (one byte) unsigned integer and is
         present if i is a value between 0 and 264.  If present, it
         occurs at bytes 22 to 21+n of the value being hashed.

   C     An n-byte randomizer that is included with the message whenever
         it is being hashed to improve security.  C MUST be chosen
         uniformly at random or via another unpredictable process.  It
         is present if D=D_MESG, and it occurs at bytes 22 to 21+n of
         the value being hashed.

8.  IANA Considerations

   IANA has created two registries: "LM-OTS Signatures", which includes
   all of the LM-OTS signatures as defined in Section 4, and "Leighton-
   Micali Signatures (LMS)" for LMS as defined in Section 5.

   Additions to these registries require that a specification be
   documented in an RFC or another permanent and readily available
   reference in sufficient detail that interoperability between
   independent implementations is possible [RFC8126].  IANA MUST verify
   that all applications for additions to these registries have first
   been reviewed by the IRTF Crypto Forum Research Group (CFRG).

McGrew, et al.                Informational                    [Page 36]

RFC 8554                LMS Hash-Based Signatures             April 2019

   Each entry in either of the registries contains the following

      a short name (Name), such as "LMS_SHA256_M32_H10",

      a positive number (Numeric Identifier), and

      a Reference to a specification that completely defines the
      signature-method test cases that can be used to verify the
      correctness of an implementation.

   The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF
   (decimal 4,294,967,295), inclusive, will not be assigned by IANA and
   are reserved for private use; no attempt will be made to prevent
   multiple sites from using the same value in different (and
   incompatible) ways [RFC8126].

   The initial contents of the "LM-OTS Signatures" registry are as

    | Name                     | Reference |    Numeric Identifier    |
    | Reserved                 |           |        0x00000000        |
    |                          |           |                          |
    | LMOTS_SHA256_N32_W1      | Section 4 |        0x00000001        |
    |                          |           |                          |
    | LMOTS_SHA256_N32_W2      | Section 4 |        0x00000002        |
    |                          |           |                          |
    | LMOTS_SHA256_N32_W4      | Section 4 |        0x00000003        |
    |                          |           |                          |
    | LMOTS_SHA256_N32_W8      | Section 4 |        0x00000004        |
    |                          |           |                          |
    | Unassigned               |           | 0x00000005 - 0xDDDDDDDC  |
    |                          |           |                          |
    | Reserved for Private Use |           | 0xDDDDDDDD - 0xFFFFFFFF  |

                                  Table 4

McGrew, et al.                Informational                    [Page 37]

RFC 8554                LMS Hash-Based Signatures             April 2019

   The initial contents of the "Leighton Micali Signatures (LMS)"
   registry are as follows.

    | Name                     | Reference |    Numeric Identifier    |
    | Reserved                 |           |        0x0 - 0x4         |
    |                          |           |                          |
    | LMS_SHA256_M32_H5        | Section 5 |        0x00000005        |
    |                          |           |                          |
    | LMS_SHA256_M32_H10       | Section 5 |        0x00000006        |
    |                          |           |                          |
    | LMS_SHA256_M32_H15       | Section 5 |        0x00000007        |
    |                          |           |                          |
    | LMS_SHA256_M32_H20       | Section 5 |        0x00000008        |
    |                          |           |                          |
    | LMS_SHA256_M32_H25       | Section 5 |        0x00000009        |
    |                          |           |                          |
    | Unassigned               |           | 0x0000000A - 0xDDDDDDDC  |
    |                          |           |                          |
    | Reserved for Private Use |           | 0xDDDDDDDD - 0xFFFFFFFF  |

                                  Table 5

   An IANA registration of a signature system does not constitute an
   endorsement of that system or its security.

   Currently, the two registries assign a disjoint set of values to the
   defined parameter sets.  This coincidence is a historical accident;
   the correctness of the system does not depend on this.  IANA is not
   required to maintain this situation.

9.  Security Considerations

   The hash function H MUST have second preimage resistance: it must be
   computationally infeasible for an attacker that is given one message
   M to be able to find a second message M' such that H(M) = H(M').

   The security goal of a signature system is to prevent forgeries.  A
   successful forgery occurs when an attacker who does not know the
   private key associated with a public key can find a message (distinct
   from all previously signed ones) and signature that is valid with
   that public key (that is, the Signature Verification algorithm
   applied to that signature and message and public key will return
   VALID).  Such an attacker, in the strongest case, may have the
   ability to forge valid signatures for an arbitrary number of other

McGrew, et al.                Informational                    [Page 38]

RFC 8554                LMS Hash-Based Signatures             April 2019

   LMS is provably secure in the random oracle model, as shown by
   [Katz16].  In addition, further analysis is done by [Fluhrer17],
   where the hash compression function (rather than the entire hash
   function) is considered to be a random oracle.  Corollary 1 of the
   latter paper states:

      If we have no more than 2^64 randomly chosen LMS private keys,
      allow the attacker access to a signing oracle and a SHA-256 hash
      compression oracle, and allow a maximum of 2^120 hash compression
      computations, then the probability of an attacker being able to
      generate a single forgery against any of those LMS keys is less
      than 2^-129.

   Many of the objects within the public key and the signature start
   with a typecode.  A verifier MUST check each of these typecodes, and
   a verification operation on a signature with an unknown type, or a
   type that does not correspond to the type within the public key, MUST
   return INVALID.  The expected length of a variable-length object can
   be determined from its typecode; if an object has a different length,
   then any signature computed from the object is INVALID.

9.1.  Hash Formats

   The format of the inputs to the hash function H has the property that
   each invocation of that function has an input that is repeated by a
   small bounded number of other inputs (due to potential repeats of the
   I value).  In particular, it will vary somewhere in the first 23
   bytes of the value being hashed.  This property is important for a
   proof of security in the random oracle model.

   The formats used during key generation and signing (including the
   recommended pseudorandom key-generation procedure in Appendix A) are
   as follows:

      I || u32str(q) || u16str(i) || u8str(j) || tmp
      I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]
      I || u32str(q) || u16str(D_MESG) || C || message
      I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h]
      I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1]
      I || u32str(q) || u16str(i) || u8str(0xff) || SEED

   Each hash type listed is distinct; at locations 20 and 21 of the
   value being hashed, there exists either a fixed value D_PBLC, D_MESG,
   D_LEAF, D_INTR, or a 16-bit value i.  These fixed values are distinct
   from each other and are large (over 32768), while the 16-bit values
   of i are small (currently no more than 265; possibly being slightly
   larger if larger hash functions are supported); hence, the range of
   possible values of i will not collide any of the D_PBLC, D_MESG,

McGrew, et al.                Informational                    [Page 39]

RFC 8554                LMS Hash-Based Signatures             April 2019

   D_LEAF, D_INTR identifiers.  The only other collision possibility is
   the Winternitz chain hash colliding with the recommended pseudorandom
   key-generation process; here, at location 22 of the value being
   hashed, the Winternitz chain function has the value u8str(j), where j
   is a value between 0 and 254, while location 22 of the recommended
   pseudorandom key-generation process has value 255.

   For the Winternitz chaining function, D_PBLC, and D_MESG, the value
   of I || u32str(q) is distinct for each LMS leaf (or equivalently, for
   each q value).  For the Winternitz chaining function, the value of
   u16str(i) || u8str(j) is distinct for each invocation of H for a
   given leaf.  For D_PBLC and D_MESG, the input format is used only
   once for each value of q and, thus, distinctness is assured.  The
   formats for D_INTR and D_LEAF are used exactly once for each value of
   r, which ensures their distinctness.  For the recommended
   pseudorandom key-generation process, for a given value of I, q and j
   are distinct for each invocation of H.

   The value of I is chosen uniformly at random from the set of all
   128-bit strings.  If 2^64 public keys are generated (and, hence, 2^64
   random I values), there is a nontrivial probability of a duplicate
   (which would imply duplicate prefixes).  However, there will be an
   extremely high probability there will not be a four-way collision
   (that is, any I value used for four distinct LMS keys; probability <
   2^-132), and, hence, the number of repeats for any specific prefix
   will be limited to at most three.  This is shown (in [Fluhrer17]) to
   have only a limited effect on the security of the system.

9.2.  Stateful Signature Algorithm

   The LMS signature system, like all N-time signature systems, requires
   that the signer maintain state across different invocations of the
   signing algorithm to ensure that none of the component one-time
   signature systems are used more than once.  This section calls out
   some important practical considerations around this statefulness.
   These issues are discussed in greater detail in [STMGMT].

   In a typical computing environment, a private key will be stored in
   nonvolatile media such as on a hard drive.  Before it is used to sign
   a message, it will be read into an application's Random-Access Memory
   (RAM).  After a signature is generated, the value of the private key
   will need to be updated by writing the new value of the private key
   into nonvolatile storage.  It is essential for security that the
   application ensures that this value is actually written into that
   storage, yet there may be one or more memory caches between it and
   the application.  Memory caching is commonly done in the file system
   and in a physical memory unit on the hard disk that is dedicated to
   that purpose.  To ensure that the updated value is written to

McGrew, et al.                Informational                    [Page 40]

RFC 8554                LMS Hash-Based Signatures             April 2019

   physical media, the application may need to take several special
   steps.  In a POSIX environment, for instance, the O_SYNC flag (for
   the open() system call) will cause invocations of the write() system
   call to block the calling process until the data has been written to
   the underlying hardware.  However, if that hardware has its own
   memory cache, it must be separately dealt with using an operating
   system or device-specific tool such as hdparm to flush the on-drive
   cache or turn off write caching for that drive.  Because these
   details vary across different operating systems and devices, this
   note does not attempt to provide complete guidance; instead, we call
   the implementer's attention to these issues.

   When hierarchical signatures are used, an easy way to minimize the
   private key synchronization issues is to have the private key for the
   second-level resident in RAM only and never write that value into
   nonvolatile memory.  A new second-level public/private key pair will
   be generated whenever the application (re)starts; thus, failures such
   as a power outage or application crash are automatically
   accommodated.  Implementations SHOULD use this approach wherever

9.3.  Security of LM-OTS Checksum

   To show the security of LM-OTS checksum, we consider the signature y
   of a message with a private key x and let h = H(message) and
   c = Cksm(H(message)) (see Section 4.5).  To attempt a forgery, an
   attacker may try to change the values of h and c.  Let h' and c'
   denote the values used in the forgery attempt.  If for some integer j
   in the range 0 to u, where u = ceil(8*n/w) is the size of the range
   that the checksum value can cover, inclusive,

      a' = coef(h', j, w),

      a = coef(h, j, w), and

      a' > a

McGrew, et al.                Informational                    [Page 41]

RFC 8554                LMS Hash-Based Signatures             April 2019

   then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by
   iteratively applying function F to the j-th term of the signature an
   additional (a' - a) times.  However, as a result of the increased
   number of hashing iterations, the checksum value c' will decrease
   from its original value of c.  Thus, a valid signature's checksum
   will have, for some number k in the range u to (p-1), inclusive,

      b' = coef(c', k, w),

      b = coef(c, k, w), and

      b' < b

   Due to the one-way property of F, the attacker cannot easily compute
   F^b'(x[k]) from F^b(x[k]) = y[k].

10.  Comparison with Other Work

   The eXtended Merkle Signature Scheme (XMSS) is similar to HSS in
   several ways [XMSS][RFC8391].  Both are stateful hash-based signature
   schemes, and both use a hierarchical approach, with a Merkle tree at
   each level of the hierarchy.  XMSS signatures are slightly shorter
   than HSS signatures, for equivalent security and an equal number of

   HSS has several advantages over XMSS.  HSS operations are roughly
   four times faster than the comparable XMSS ones, when SHA256 is used
   as the underlying hash.  This occurs because the hash operation done
   as a part of the Winternitz iterations dominates performance, and
   XMSS performs four compression-function invocations (two for the PRF,
   two for the F function) where HSS only needs to perform one.
   Additionally, HSS is somewhat simpler (as each hash invocation is
   just a prefix followed by the data being hashed).

McGrew, et al.                Informational                    [Page 42]

RFC 8554                LMS Hash-Based Signatures             April 2019

11.  References

11.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, March 2012.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,

   [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,

   [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>.

   [RFC8179]  Bradner, S. and J. Contreras, "Intellectual Property
              Rights in IETF Technology", BCP 79, RFC 8179,
              DOI 10.17487/RFC8179, May 2017,

              Leighton, T. and S. Micali, "Large provably fast and
              secure digital signature schemes based on secure hash
              functions", U.S. Patent 5,432,852, July 1995.

11.2.  Informative References

              Merkle, R., "A Digital Signature Based on a Conventional
              Encryption Function", in Advances in Cryptology -- CRYPTO
              '87 Proceedings, Lecture Notes in Computer Science Vol.
              293, DOI 10.1007/3-540-48184-2_32, 1988.

McGrew, et al.                Informational                    [Page 43]

RFC 8554                LMS Hash-Based Signatures             April 2019

              Merkle, R., "A Certified Digital Signature", in Advances
              in Cryptology -- CRYPTO '89 Proceedings, Lecture Notes in
              Computer Science Vol. 435, DOI 10.1007/0-387-34805-0_21,

              Merkle, R., "One Way Hash Functions and DES", in Advances
              in Cryptology -- CRYPTO '89 Proceedings, Lecture Notes in
              Computer Science Vol. 435, DOI 10.1007/0-387-34805-0_40,

              Fluhrer, S., "Further Analysis of a Proposed Hash-Based
              Signature Standard", Cryptology ePrint Archive Report
              2017/553, 2017, <https://eprint.iacr.org/2017/553>.

   [Katz16]   Katz, J., "Analysis of a Proposed Hash-Based Signature
              Standard", in SSR 2016: Security Standardisation Research
              (SSR) pp. 261-273, Lecture Notes in Computer Science Vol.
              10074, DOI 10.1007/978-3-319-49100-4_12, 2016.

              Merkle, R., "Secrecy, Authentication, and Public Key
              Systems", Technical Report No. 1979-1, Information Systems
              Laboratory, Stanford University, 1979,

   [RFC8391]  Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A.
              Mohaisen, "XMSS: eXtended Merkle Signature Scheme",
              RFC 8391, DOI 10.17487/RFC8391, May 2018,

   [STMGMT]   McGrew, D., Kampanakis, P., Fluhrer, S., Gazdag, S.,
              Butin, D., and J. Buchmann, "State Management for Hash-
              Based Signatures.", in SSR 2016: Security Standardisation
              Research (SSR) pp. 244-260, Lecture Notes in Computer
              Science Vol. 10074, DOI 10.1007/978-3-319-49100-4_11,

   [XMSS]     Buchmann, J., Dahmen, E., and , "XMSS -- A Practical
              Forward Secure Signature Scheme Based on Minimal Security
              Assumptions.", in PQCrypto 2011: Post-Quantum Cryptography
              pp. 117-129, Lecture Notes in Computer Science Vol. 7071,
              DOI 10.1007/978-3-642-25405-5_8, 2011.

McGrew, et al.                Informational                    [Page 44]

RFC 8554                LMS Hash-Based Signatures             April 2019

Appendix A.  Pseudorandom Key Generation

   An implementation MAY use the following pseudorandom process for
   generating an LMS private key.

      SEED is an m-byte value that is generated uniformly at random at
      the start of the process,

      I is the LMS key pair identifier,

      q denotes the LMS leaf number of an LM-OTS private key,

      x_q denotes the x array of private elements in the LM-OTS private
      key with leaf number q,

      i is the index of the private key element, and

      H is the hash function used in LM-OTS.

   The elements of the LM-OTS private keys are computed as:

   x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED).

   This process stretches the m-byte random value SEED into a (much
   larger) set of pseudorandom values, using a unique counter in each
   invocation of H.  The format of the inputs to H are chosen so that
   they are distinct from all other uses of H in LMS and LM-OTS.  A
   careful reader will note that this is similar to the hash we perform
   when iterating through the Winternitz chain; however, in that chain,
   the iteration index will vary between 0 and 254 maximum (for W=8),
   while the corresponding value in this formula is 255.  This algorithm
   is included in the proof of security in [Fluhrer17] and hence this
   method is safe when used within the LMS system; however, any other
   cryptographically secure method of generating private keys would also
   be safe.

Appendix B.  LM-OTS Parameter Options

   The LM-OTS one-time signature method uses several internal
   parameters, which are a function of the selected parameter set.
   These internal parameters include the following:

   p     This is the number of independent Winternitz chains used in the
         signature; it will be the number of w-bit digits needed to hold
         the n-bit hash (u in the below equations), along with the
         number of digits needed to hold the checksum (v in the below

McGrew, et al.                Informational                    [Page 45]

RFC 8554                LMS Hash-Based Signatures             April 2019

   ls    This is the size of the shift needed to move the checksum so
         that it appears in the checksum digits

   ls is needed because, while we express the checksum internally as a
   16-bit value, we don't always express all 16 bits in the signature;
   for example, if w=4, we might use only the top 12 bits.  Because we
   read the checksum in network order, this means that, without the
   shift, we'll use the higher-order bits (which may be always 0) and
   omit the lower-order bits (where the checksum value actually
   resides).  This shift is here to ensure that the parts of the
   checksum we need to express (for security) actually contribute to the
   signature; when multiple such shifts are possible, we take the
   minimal value.

   The parameters ls and p are computed as follows:

     u = ceil(8*n/w)
     v = ceil((floor(lg((2^w - 1) * u)) + 1) / w)
     ls = 16 - (v * w)
     p = u + v

   Here, u and v represent the number of w-bit fields required to
   contain the hash of the message and the checksum byte strings,
   respectively.  And as the value of p is the number of w-bit elements
   of ( H(message) || Cksm(H(message)) ), it is also equivalently the
   number of byte strings that form the private key and the number of
   byte strings in the signature.  The value 16 in the ls computation of
   ls corresponds to the 16-bit value used for the sum variable in
   Algorithm 2 in Section 4.4

   A table illustrating various combinations of n and w with the
   associated values of u, v, ls, and p is provided in Table 6.

McGrew, et al.                Informational                    [Page 46]

RFC 8554                LMS Hash-Based Signatures             April 2019

   |   Hash  | Winternitz |   w-bit   |   w-bit   |  Left |   Total    |
   |  Length | Parameter  |  Elements |  Elements | Shift | Number of  |
   |    in   |    (w)     |  in Hash  |     in    |  (ls) |   w-bit    |
   |  Bytes  |            |    (u)    |  Checksum |       |  Elements  |
   |   (n)   |            |           |    (v)    |       |    (p)     |
   |    32   |     1      |    256    |     9     |   7   |    265     |
   |         |            |           |           |       |            |
   |    32   |     2      |    128    |     5     |   6   |    133     |
   |         |            |           |           |       |            |
   |    32   |     4      |     64    |     3     |   4   |     67     |
   |         |            |           |           |       |            |
   |    32   |     8      |     32    |     2     |   0   |     34     |

                                  Table 6

Appendix C.  An Iterative Algorithm for Computing an LMS Public Key

   The LMS public key can be computed using the following algorithm or
   any equivalent method.  The algorithm uses a stack of hashes for
   data.  It also makes use of a hash function with the typical
   init/update/final interface to hash functions; the result of the
   invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... ,
   hash_update(N[n]), v = hash_final(), in that order, is identical to
   that of the invocation of H(N[1] || N[2] || ... || N[n]).

   Generating an LMS Public Key from an LMS Private Key

     for ( i = 0; i < 2^h; i = i + 1 ) {
       r = i + num_lmots_keys;
       temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i])
       j = i;
       while (j % 2 == 1) {
         r = (r - 1)/2;
         j = (j-1) / 2;
         left_side = pop(data stack);
         temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
       push temp onto the data stack
    public_key = pop(data stack)

McGrew, et al.                Informational                    [Page 47]

RFC 8554                LMS Hash-Based Signatures             April 2019

   Note that this pseudocode expects that all 2^h leaves of the tree
   have equal depth -- that is, it expects num_lmots_keys to be a power
   of 2.  The maximum depth of the stack will be h-1 elements -- that
   is, a total of (h-1)*n bytes; for the currently defined parameter
   sets, this will never be more than 768 bytes of data.

Appendix D.  Method for Deriving Authentication Path for a Signature

   The LMS signature consists of u32str(q) || lmots_signature ||
   u32str(type) || path[0] || path[1] || ... || path[h-1].  This
   appendix shows one method of constructing this signature, assuming
   that the implementation has stored the T[] array that was used to
   construct the public key.  Note that this is not the only possible
   method; other methods exist that don't assume that you have the
   entire T[] array in memory.  To construct a signature, you perform
   the following algorithm:

   Generating an LMS Signature

     1. Set type to the typecode of the LMS algorithm.

     2. Extract h from the typecode, according to Table 2.

     3. Create the LM-OTS signature for the message:
        ots_signature = lmots_sign(message, LMS_PRIV[q])

     4. Compute the array path as follows:
        i = 0
        r = 2^h + q
        while (i < h) {
          temp = (r / 2^i) xor 1
          path[i] = T[temp]
          i = i + 1

     5. S = u32str(q) || ots_signature || u32str(type) ||
                             path[0] || path[1] || ... || path[h-1]

     6. q = q + 1

     7. Return S.

   Here "xor" is the bitwise exclusive-or operation, and / is integer
   division (that is, rounded down to an integer value).

McGrew, et al.                Informational                    [Page 48]

RFC 8554                LMS Hash-Based Signatures             April 2019

Appendix E.  Example Implementation

   An example implementation can be found online at

Appendix F.  Test Cases

   This section provides test cases that can be used to verify or debug
   an implementation.  This data is formatted with the name of the
   elements on the left and the hexadecimal value of the elements on the
   right.  The concatenation of all of the values within a public key or
   signature produces that public key or signature, and values that do
   not fit within a single line are listed across successive lines.

   Test Case 1 Public Key

   HSS public key
   levels      00000002
   LMS type    00000005                         # LM_SHA256_M32_H5
   LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
   I           61a5d57d37f5e46bfb7520806b07a1b8
   K           50650e3b31fe4a773ea29a07f09cf2ea

   Test Case 1 Message

   Message     54686520706f77657273206e6f742064  |The powers not d|
               656c65676174656420746f2074686520  |elegated to the |
               556e6974656420537461746573206279  |United States by|
               2074686520436f6e737469747574696f  | the Constitutio|
               6e2c206e6f722070726f686962697465  |n, nor prohibite|
               6420627920697420746f207468652053  |d by it to the S|
               74617465732c20617265207265736572  |tates, are reser|
               76656420746f20746865205374617465  |ved to the State|
               7320726573706563746976656c792c20  |s respectively, |
               6f7220746f207468652070656f706c65  |or to the people|
               2e0a                              |..|

McGrew, et al.                Informational                    [Page 49]

RFC 8554                LMS Hash-Based Signatures             April 2019

   Test Case 1 Signature

   HSS signature
   Nspk        00000001
   LMS signature
   q           00000005
   LMOTS signature
   LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
   C           d32b56671d7eb98833c49b433c272586
   y[0]        965a25bfd37f196b9073f3d4a232feb6
   y[1]        a64c7f60f6261a62043f86c70324b770
   y[2]        e05fd5c6509a6e61d559cf1a77a970de
   y[3]        582e8ff1b10cd99d4e8e413ef469559f
   y[4]        81d84b15357ff48ca579f19f5e71f184
   y[5]        14784269d7d876f5d35d3fbfc7039a46
   y[6]        60b960e7777c52f060492f2d7c660e14
   y[7]        c3943c6b9c4f2405a3cb8bf8a691ca51
   y[8]        f0a75ee390e385e3ae0b906961ecf41a
   y[9]        35b167b28ce8dc988a3748255230cef9
   y[10]       e783ed04516de012498682212b078105
   y[11]       aaf65de7620dabec29eb82a17fde35af
   y[12]       1099762b37f43c4a3c20010a3d72e2f6
   y[13]       a1a40281cc5a7ea98d2adc7c7400c2fe
   y[14]       9cbbc68fee0c3efe4ec22b83a2caa3e4
   y[15]       4f8a58f7f24335eec5c5eb5e0cf01dcf
   y[16]       c5b9f64a2a9af2f07c05e99e5cf80f00

McGrew, et al.                Informational                    [Page 50]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[17]       26857713afd2ca6bb85cd8c107347552
   y[18]       c413e7d0acd8bdd81352b2471fc1bc4f
   y[19]       cf7cc62fb92be14f18c2192384ebceaf
   y[20]       e87b0144417e8d7baf25eb5f70f09f01
   y[21]       da67571f5dd546fc22cb1f97e0ebd1a6
   y[22]       115cce6f792cc84e36da58960c5f1d76
   y[23]       1efc72d60ca5e908b3a7dd69fef02491
   y[24]       c75e13527b7a581a556168783dc1e975
   y[25]       8d3ee2062445dfb85ef8c35f8e1f3371
   y[26]       ab8f5c612ead0b729a1d059d02bfe18e
   y[27]       eec0f3f3f13039a17f88b0cf808f4884
   y[28]       4f1f4ab949b9feefadcb71ab50ef27d6
   y[29]       9b6066f09c37280d59128d2f0f637c7d
   y[30]       b7c878c9411cafc5071a34a00f4cf077
   y[31]       d76f7ce973e9367095ba7e9a3649b7f4
   y[32]       401b64457c54d65fef6500c59cdfb69a
   y[33]       b0f3f79cd893d314168648499898fbc0
   LMS type    00000005                         # LM_SHA256_M32_H5
   path[0]     d8b8112f9200a5e50c4a262165bd342c
   path[1]     129ac6eda839a6f357b5a04387c5ce97
   path[2]     12f5dbe400bd49e4501e859f885bf073
   path[3]     b5971115aa39efd8d564a6b90282c316
   path[4]     4cca1848cf7da59cc2b3d9d0692dd2a2

McGrew, et al.                Informational                    [Page 51]

RFC 8554                LMS Hash-Based Signatures             April 2019

   LMS public key
   LMS type    00000005                         # LM_SHA256_M32_H5
   LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
   I           d2f14ff6346af964569f7d6cb880a1b6
   K           6c5004917da6eafe4d9ef6c6407b3db0
   LMS signature
   q           0000000a
   LMOTS signature
   LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
   C           0703c491e7558b35011ece3592eaa5da
   y[0]        95cae05b899e35dffd71705470620998
   y[1]        9bc042da4b4525650485c66d0ce19b31
   y[2]        6a120c5612344258b85efdb7db1db9e1
   y[3]        9eeddb03a1d2374af7bf771855774562
   y[4]        a698994c0827d90e86d43e0df7f4bfcd
   y[5]        100e4f2c5fc38c003c1ab6fea479eb2f
   y[6]        969f6aecbfe44cf356888a7b15a3ff07
   y[7]        e61af23aee7fa5d4d9a5dfcf43c4c26c
   y[8]        beadb2b25b3cacc1ac0cef346cbb90fb
   y[9]        319c9944b1586e899d431c7f91bcccc8
   y[10]       f30b2b51f48b71b003dfb08249484201
   y[11]       0081262a00000480dcbc9a3da6fbef5c
   y[12]       9db268f6fe50032a363c9801306837fa
   y[13]       dfd836a28b354023924b6fb7e48bc0b3
   y[14]       91825daef01eae3c38e3328d00a77dc6
   y[15]       205e4737b84b58376551d44c12c3c215

McGrew, et al.                Informational                    [Page 52]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[16]       327f0a5fbb6b5907dec02c9a90934af5
   y[17]       b45696689f2eb382007497557692caac
   y[18]       664fcb6db4971f5b3e07aceda9ac130e
   y[19]       f3fe00812589b7a7ce51544045643301
   y[20]       f2d8b584410ceda8025f5d2d8dd0d217
   y[21]       ce780fd025bd41ec34ebff9d4270a322
   y[22]       89cc10cd600abb54c47ede93e08c114e
   y[23]       929d15462b939ff3f52f2252da2ed64d
   y[24]       aa233db3162833141ea4383f1a6f120b
   y[25]       234d475e2f79cbf05e4db6a9407d72c6
   y[26]       715a0182c7dc8089e32c8531deed4f74
   y[27]       ae0c066babc69369700e1dd26eddc0d2
   y[28]       49ef23be2aa4dbf25206fe45c20dd888
   y[29]       12858792bf8e74cba49dee5e8812e019
   y[30]       82f880a278f682c2bd0ad6887cb59f65
   y[31]       656d9ccbaae3d655852e38deb3a2dcf8
   y[32]       1091d05eb6e2f297774fe6053598457c
   y[33]       e865aa805009cc2918d9c2f840c4da43
   LMS type    00000005                         # LM_SHA256_M32_H5
   path[0]     d5c0d1bebb06048ed6fe2ef2c6cef305
   path[1]     e1920ada52f43d055b5031cee6192520
   path[2]     2335b525f484e9b40d6a4a969394843b
   path[3]     f90b65a7a6201689999f32bfd368e5e3
   path[4]     09ab3034911fe125631051df0408b394

McGrew, et al.                Informational                    [Page 53]

RFC 8554                LMS Hash-Based Signatures             April 2019

   Test Case 2 Private Key

   (note: procedure in Appendix A is used)
   Top level LMS tree
   SEED        558b8966c48ae9cb898b423c83443aae
   I           d08fabd4a2091ff0a8cb4ed834e74534
   Second level LMS tree
   SEED        a1c4696e2608035a886100d05cd99945
   I           215f83b7ccb9acbcd08db97b0d04dc2b

   Test Case 2 Public Key

   HSS public key
   levels      00000002
   LMS type    00000006                         # LM_SHA256_M32_H10
   LMOTS type  00000003                         # LMOTS_SHA256_N32_W4
   I           d08fabd4a2091ff0a8cb4ed834e74534
   K           32a58885cd9ba0431235466bff9651c6

   Test Case 2 Message

   Message     54686520656e756d65726174696f6e20  |The enumeration |
               696e2074686520436f6e737469747574  |in the Constitut|
               696f6e2c206f66206365727461696e20  |ion, of certain |
               7269676874732c207368616c6c206e6f  |rights, shall no|
               7420626520636f6e7374727565642074  |t be construed t|
               6f2064656e79206f7220646973706172  |o deny or dispar|
               616765206f7468657273207265746169  |age others retai|
               6e6564206279207468652070656f706c  |ned by the peopl|
               652e0a                            |e..|

McGrew, et al.                Informational                    [Page 54]

RFC 8554                LMS Hash-Based Signatures             April 2019

   Test Case 2 Signature

   HSS signature
   Nspk        00000001
   LMS signature
   q           00000003
   LMOTS signature
   LMOTS type  00000003                         # LMOTS_SHA256_N32_W4
   C           3d46bee8660f8f215d3f96408a7a64cf
   y[0]        0674e8cb7a55f0c48d484f31f3aa4af9
   y[1]        bb71226d279700ec81c9e95fb11a0d10
   y[2]        4508e126a9a7870bf4360820bdeb9a01
   y[3]        0ac8ba39810909d445f44cb5bb58de73
   y[4]        9edeaa3bfcfe8baa6621ce88480df237
   y[5]        49a18d39a50788f4652987f226a1d481
   y[6]        90da8aa5e5f7671773e941d805536021
   y[7]        54e7b1e1bf494d0d1a28c0d31acc7516
   y[8]        ed30872e07f2b8bd0374eb57d22c614e
   y[9]        2988ab46eaca9ec597fb18b4936e66ef
   y[10]       0c7b345434f72d65314328bbb030d0f0
   y[11]       be3b2adb83c60a54f9d1d1b2f476f9e3
   y[12]       dcc21033f9453d49c8e5a6387f588b1e
   y[13]       56a326a32f9cba1fbe1c07bb49fa04ce
   y[14]       238e5ea986b53e087045723ce16187ed
   y[15]       45fc8c0693e97763928f00b2e3c75af3
   y[16]       11873b59137f67800b35e81b01563d18

McGrew, et al.                Informational                    [Page 55]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[17]       05d357ef4678de0c57ff9f1b2da61dfd
   y[18]       40dd7739ca3ef66f1930026f47d9ebaa
   y[19]       375dbfb83d719b1635a7d8a138919579
   y[20]       a6c0a555c9026b256a6860f4866bd6d0
   y[21]       622442443d5eca959d6c14ca8389d12c
   y[22]       558f249c9661c0427d2e489ca5b5dde2
   y[23]       8266c12c50ea28b2c438e7a379eb106e
   y[24]       b76e8027992e60de01e9094fddeb3349
   y[25]       8278c14b032bcab02bd15692d21b6c5c
   y[26]       5d33b10d518a61e15ed0f092c3222628
   y[27]       a375cebda1dc6bb9a1a01dae6c7aba8e
   y[28]       2949dcc198fb77c7e5cdf6040b0f84fa
   y[29]       ae8a270e951743ff23e0b2dd12e9c3c8
   y[30]       20c4591f71c088f96e095dd98beae456
   y[31]       73217ac5962b5f3147b492e8831597fd
   y[32]       435eb3109350756b9fdabe1c6f368081
   y[33]       b1bab705a4b7e37125186339464ad8fa
   y[34]       0eb1fcbfcc25acb5f718ce4f7c2182fb
   y[35]       6e90d4c9b0cc38608a6cef5eb153af08
   y[36]       9313d28d41a5c6fe6cf3595dd5ee63f0
   y[37]       f88dd73720708c6c6c0ecf1f43bbaada
   y[38]       42761c70c186bfdafafc444834bd3418
   y[39]       ffd5960b0336981795721426803599ed
   y[40]       9e3fa152d9adeca36020fdeeee1b7395

McGrew, et al.                Informational                    [Page 56]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[41]       94a873670b8d93bcca2ae47e64424b74
   y[42]       fa5b9510beb39ccf4b4e1d9c0f19d5e1
   y[43]       7af256a8491671f1f2f22af253bcff54
   y[44]       d0be7919684b23da8d42ff3effdb7ca0
   y[45]       c0a614d31cc7487f52de8664916af79c
   y[46]       2250274a1de2584fec975fb09536792c
   y[47]       301ddff26ec1b23de2d188c999166c74
   y[48]       50f4d646fc6278e8fe7eb6cb5c94100f
   y[49]       7fa7d5cc861c5bdac98e7495eb0a2cee
   y[50]       1287d978b8df064219bc5679f7d7b264
   y[51]       8240027afd9d52a79b647c90c2709e06
   y[52]       d839f851f98f67840b964ebe73f8cec4
   y[53]       da93d9f5f6fa6f6c0f03ce43362b8414
   y[54]       bc85a3ff51efeea3bc2cf27e1658f178
   y[55]       beeecaa04dccea9f97786001475e0294
   y[56]       4a662ecae37ede27e9d6eadfdeb8f8b2
   y[57]       29c2f4dcd153a2742574126e5eaccc77
   y[58]       05ff5453ec99897b56bc55dd49b99114
   y[59]       cc5a8a335d3619d781e7454826df720e
   y[60]       057fa3419b5bb0e25d30981e41cb1361
   y[61]       8bfc3d20a2148861b2afc14562ddd27f
   y[62]       46a24bf77e383c7aacab1ab692b29ed8
   y[63]       b1c78725c1f8f922f6009787b1964247
   y[64]       d4a8b6f04d95c581279a139be09fcf6e

McGrew, et al.                Informational                    [Page 57]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[65]       c05518a7efd35d89d8577c990a5e1996
   y[66]       294546454fa5388a23a22e805a5ca35f
   LMS type    00000006                         # LM_SHA256_M32_H10
   path[0]     b326493313053ced3876db9d23714818
   path[1]     a769db4657a103279ba8ef3a629ca84e
   path[2]     0b491cb4ecbbabec128e7c81a46e62a6
   path[3]     686d16621a80816bfdb5bdc56211d72c
   path[4]     7028a48538ecdd3b38d3d5d62d262465
   path[5]     2e0c19bc4977c6898ff95fd3d310b0ba
   path[6]     83bb7543c675842bafbfc7cdb88483b3
   path[7]     d045851acf6a0a0ea9c710b805cced46
   path[8]     6703d26d14752f34c1c0d2c4247581c1
   path[9]     a415e291fd107d21dc1f084b11582082
   LMS public key
   LMS type    00000005                         # LM_SHA256_M32_H5
   LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
   I           215f83b7ccb9acbcd08db97b0d04dc2b
   K           a1cd035833e0e90059603f26e07ad2aa
   LMS signature
   q           00000004
   LMOTS signature
   LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
   C           0eb1ed54a2460d512388cad533138d24
   y[0]        11b3649023696f85150b189e50c00e98
   y[1]        3b7714fa406b8c35b021d54d4fdada7b

McGrew, et al.                Informational                    [Page 58]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[2]        057aa0e2e74e7dcfd17a0823429db629
   y[3]        83cac8b4d61aacc457f336e6a10b6632
   y[4]        c6bf59daa82afd2b5ebb2a9ca6572a60
   y[5]        df927aade10c1c9f2d5ff446450d2a39
   y[6]        8190643978d7a7f4d64e97e3f1c4a08a
   y[7]        2f190143475a6043d5e6d5263471f4ee
   y[8]        f797fd5a3cd53a066700f45863f04b6c
   y[9]        8b636ae547c1771368d9f317835c9b0e
   y[10]       bc7a5cf8a5abdb12dc718b559b74cab9
   y[11]       67df540890a062fe40dba8b2c1c548ce
   y[12]       862f4a24ebd376d288fd4e6fb06ed870
   y[13]       767b14ce88409eaebb601a93559aae89
   y[14]       fbe549147f71c092f4f3ac522b5cc572
   y[15]       1ead87ac01985268521222fb9057df7e
   y[16]       c2ce956c365ed38e893ce7b2fae15d36
   y[17]       a8ade980ad0f93f6787075c3f680a2ba
   y[18]       8d64c3d3d8582968c2839902229f85ae
   y[19]       7bf0f4ff3ffd8fba5e383a48574802ed
   y[20]       135a7ce517279cd683039747d218647c
   y[21]       9547b830d8118161b65079fe7bc59a99
   y[22]       2b698d09ae193972f27d40f38dea264a
   y[23]       eb0d4029ac712bfc7a5eacbdd7518d6d
   y[24]       4fd7214dc617c150544e423f450c99ce
   y[25]       a3bb86da7eba80b101e15cb79de9a207

McGrew, et al.                Informational                    [Page 59]

RFC 8554                LMS Hash-Based Signatures             April 2019

   y[26]       25d1faa94cbb0a03a906f683b3f47a97
   y[27]       496152a91c2bf9da76ebe089f4654877
   y[28]       2429b9e8cb4834c83464f079995332e4
   y[29]       952c0b7420df525e37c15377b5f09843
   y[30]       3de3afad5733cbe7703c5296263f7734
   y[31]       aa2de3ffdcd297baaaacd7ae646e44b5
   y[32]       982fb2e370c078edb042c84db34ce36b
   y[33]       97ec8075e82b393d542075134e2a17ee
   LMS type    00000005                         # LM_SHA256_M32_H5
   path[0]     4de1f6965bdabc676c5a4dc7c35f97f8
   path[1]     e96aeee300d1f68bf1bca9fc58e40323
   path[2]     04d341aa0a337b19fe4bc43c2e79964d
   path[3]     b0f75be80ea3af098c9752420a8ac0ea
   path[4]     e4041d95398a6f7f3e0ee97cc1591849


   Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric
   Osterweil, Ahmed Kosba, Russ Housley, Philip Lafrance, Alexander
   Truskovsky, Mark Peruzel, and Jim Schaad for constructive suggestions
   and valuable detailed review.  We especially acknowledge Jerry
   Solinas, Laurie Law, and Kevin Igoe, who pointed out the security
   benefits of the approach of Leighton and Micali [USPTO5432852],
   Jonathan Katz, who gave us security guidance, and Bruno Couillard and
   Jim Goodman for an especially thorough review.

McGrew, et al.                Informational                    [Page 60]

RFC 8554                LMS Hash-Based Signatures             April 2019

Authors' Addresses

   David McGrew
   Cisco Systems
   13600 Dulles Technology Drive
   Herndon, VA  20171
   United States of America

   Email: mcgrew@cisco.com

   Michael Curcio
   Cisco Systems
   7025-2 Kit Creek Road
   Research Triangle Park, NC  27709-4987
   United States of America

   Email: micurcio@cisco.com

   Scott Fluhrer
   Cisco Systems
   170 West Tasman Drive
   San Jose, CA
   United States of America

   Email: sfluhrer@cisco.com

McGrew, et al.                Informational                    [Page 61]