    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

    Abstract

       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
       https://www.rfc-editor.org/info/rfc8554.

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

       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
       <https://datatracker.ietf.org/ipr/about>.

    1.3.  Conventions Used in This Document

       The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
       "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
       "OPTIONAL" in this document are to be interpreted as described in
       BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
       capitals, as shown here.

    2.  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
       failure.

       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
       follows:

          ^ : 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
       expressions.

       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
       functions:

          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;
        default:
          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];
        default:
          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

        default:
          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
       message.

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

    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
       Message

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

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

       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:
              H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h])
         else
              H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])

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

          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

                                    Root
                                     |
                     ---------------------------------
                     |                               |
                   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
            INVALID.

         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)
              else:
                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
          key.

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

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

       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
       tree).

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

       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
            pub[0]

         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
       performed:

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

                 +---------+------------+---------+-------------+
                 | 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
       follows:

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

    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
       elements:

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

        +--------------------------+-----------+--------------------------+
        | 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
       messages.

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

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

       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,
                  <https://www.rfc-editor.org/info/rfc2119>.

       [RFC4506]  Eisler, M., Ed., "XDR: External Data Representation
                  Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May
                  2006, <https://www.rfc-editor.org/info/rfc4506>.

       [RFC8126]  Cotton, M., Leiba, B., and T. Narten, "Guidelines for
                  Writing an IANA Considerations Section in RFCs", BCP 26,
                  RFC 8126, DOI 10.17487/RFC8126, June 2017,
                  <https://www.rfc-editor.org/info/rfc8126>.

       [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
                  2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
                  May 2017, <https://www.rfc-editor.org/info/rfc8174>.

       [RFC8179]  Bradner, S. and J. Contreras, "Intellectual Property
                  Rights in IETF Technology", BCP 79, RFC 8179,
                  DOI 10.17487/RFC8179, May 2017,
                  <https://www.rfc-editor.org/info/rfc8179>.

       [USPTO5432852]
                  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

       [C:Merkle87]
                  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

       [C:Merkle89a]
                  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,
                  1990.

       [C:Merkle89b]
                  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,
                  1990.

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

       [Merkle79]
                  Merkle, R., "Secrecy, Authentication, and Public Key
                  Systems", Technical Report No. 1979-1, Information Systems
                  Laboratory, Stanford University, 1979,
                  <http://www.merkle.com/papers/Thesis1979.pdf>.

       [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,
                  <https://www.rfc-editor.org/info/rfc8391>.

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

       [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
             equations)

    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
       <https://github.com/cisco/hash-sigs>.

    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
                   30e579f0df58ef8e298da0434cb2b878
       --------------------------------------------
       --------------------------------------------

       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
       sig[0]:
       --------------------------------------------
       LMS signature
       q           00000005
       --------------------------------------------
       LMOTS signature
       LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
       C           d32b56671d7eb98833c49b433c272586
                   bc4a1c8a8970528ffa04b966f9426eb9
       y[0]        965a25bfd37f196b9073f3d4a232feb6
                   9128ec45146f86292f9dff9610a7bf95
       y[1]        a64c7f60f6261a62043f86c70324b770
                   7f5b4a8a6e19c114c7be866d488778a0
       y[2]        e05fd5c6509a6e61d559cf1a77a970de
                   927d60c70d3de31a7fa0100994e162a2
       y[3]        582e8ff1b10cd99d4e8e413ef469559f
                   7d7ed12c838342f9b9c96b83a4943d16
       y[4]        81d84b15357ff48ca579f19f5e71f184
                   66f2bbef4bf660c2518eb20de2f66e3b
       y[5]        14784269d7d876f5d35d3fbfc7039a46
                   2c716bb9f6891a7f41ad133e9e1f6d95
       y[6]        60b960e7777c52f060492f2d7c660e14
                   71e07e72655562035abc9a701b473ecb
       y[7]        c3943c6b9c4f2405a3cb8bf8a691ca51
                   d3f6ad2f428bab6f3a30f55dd9625563
       y[8]        f0a75ee390e385e3ae0b906961ecf41a
                   e073a0590c2eb6204f44831c26dd768c
       y[9]        35b167b28ce8dc988a3748255230cef9
                   9ebf14e730632f27414489808afab1d1
       y[10]       e783ed04516de012498682212b078105
                   79b250365941bcc98142da13609e9768
       y[11]       aaf65de7620dabec29eb82a17fde35af
                   15ad238c73f81bdb8dec2fc0e7f93270
       y[12]       1099762b37f43c4a3c20010a3d72e2f6
                   06be108d310e639f09ce7286800d9ef8
       y[13]       a1a40281cc5a7ea98d2adc7c7400c2fe
                   5a101552df4e3cccfd0cbf2ddf5dc677
       y[14]       9cbbc68fee0c3efe4ec22b83a2caa3e4
                   8e0809a0a750b73ccdcf3c79e6580c15
       y[15]       4f8a58f7f24335eec5c5eb5e0cf01dcf
                   4439424095fceb077f66ded5bec73b27
       y[16]       c5b9f64a2a9af2f07c05e99e5cf80f00
                   252e39db32f6c19674f190c9fbc506d8

    McGrew, et al.                Informational                    [Page 50]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[17]       26857713afd2ca6bb85cd8c107347552
                   f30575a5417816ab4db3f603f2df56fb
       y[18]       c413e7d0acd8bdd81352b2471fc1bc4f
                   1ef296fea1220403466b1afe78b94f7e
       y[19]       cf7cc62fb92be14f18c2192384ebceaf
                   8801afdf947f698ce9c6ceb696ed70e9
       y[20]       e87b0144417e8d7baf25eb5f70f09f01
                   6fc925b4db048ab8d8cb2a661ce3b57a
       y[21]       da67571f5dd546fc22cb1f97e0ebd1a6
                   5926b1234fd04f171cf469c76b884cf3
       y[22]       115cce6f792cc84e36da58960c5f1d76
                   0f32c12faef477e94c92eb75625b6a37
       y[23]       1efc72d60ca5e908b3a7dd69fef02491
                   50e3eebdfed39cbdc3ce9704882a2072
       y[24]       c75e13527b7a581a556168783dc1e975
                   45e31865ddc46b3c957835da252bb732
       y[25]       8d3ee2062445dfb85ef8c35f8e1f3371
                   af34023cef626e0af1e0bc017351aae2
       y[26]       ab8f5c612ead0b729a1d059d02bfe18e
                   fa971b7300e882360a93b025ff97e9e0
       y[27]       eec0f3f3f13039a17f88b0cf808f4884
                   31606cb13f9241f40f44e537d302c64a
       y[28]       4f1f4ab949b9feefadcb71ab50ef27d6
                   d6ca8510f150c85fb525bf25703df720
       y[29]       9b6066f09c37280d59128d2f0f637c7d
                   7d7fad4ed1c1ea04e628d221e3d8db77
       y[30]       b7c878c9411cafc5071a34a00f4cf077
                   38912753dfce48f07576f0d4f94f42c6
       y[31]       d76f7ce973e9367095ba7e9a3649b7f4
                   61d9f9ac1332a4d1044c96aefee67676
       y[32]       401b64457c54d65fef6500c59cdfb69a
                   f7b6dddfcb0f086278dd8ad0686078df
       y[33]       b0f3f79cd893d314168648499898fbc0
                   ced5f95b74e8ff14d735cdea968bee74
       --------------------------------------------
       LMS type    00000005                         # LM_SHA256_M32_H5
       path[0]     d8b8112f9200a5e50c4a262165bd342c
                   d800b8496810bc716277435ac376728d
       path[1]     129ac6eda839a6f357b5a04387c5ce97
                   382a78f2a4372917eefcbf93f63bb591
       path[2]     12f5dbe400bd49e4501e859f885bf073
                   6e90a509b30a26bfac8c17b5991c157e
       path[3]     b5971115aa39efd8d564a6b90282c316
                   8af2d30ef89d51bf14654510a12b8a14
       path[4]     4cca1848cf7da59cc2b3d9d0692dd2a2
                   0ba3863480e25b1b85ee860c62bf5136
       --------------------------------------------

    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
                   e5485b122d9ebe15cda93cfec582d7ab
       --------------------------------------------
       final_signature:
       --------------------------------------------
       LMS signature
       q           0000000a
       --------------------------------------------
       LMOTS signature
       LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
       C           0703c491e7558b35011ece3592eaa5da
                   4d918786771233e8353bc4f62323185c
       y[0]        95cae05b899e35dffd71705470620998
                   8ebfdf6e37960bb5c38d7657e8bffeef
       y[1]        9bc042da4b4525650485c66d0ce19b31
                   7587c6ba4bffcc428e25d08931e72dfb
       y[2]        6a120c5612344258b85efdb7db1db9e1
                   865a73caf96557eb39ed3e3f426933ac
       y[3]        9eeddb03a1d2374af7bf771855774562
                   37f9de2d60113c23f846df26fa942008
       y[4]        a698994c0827d90e86d43e0df7f4bfcd
                   b09b86a373b98288b7094ad81a0185ac
       y[5]        100e4f2c5fc38c003c1ab6fea479eb2f
                   5ebe48f584d7159b8ada03586e65ad9c
       y[6]        969f6aecbfe44cf356888a7b15a3ff07
                   4f771760b26f9c04884ee1faa329fbf4
       y[7]        e61af23aee7fa5d4d9a5dfcf43c4c26c
                   e8aea2ce8a2990d7ba7b57108b47dabf
       y[8]        beadb2b25b3cacc1ac0cef346cbb90fb
                   044beee4fac2603a442bdf7e507243b7
       y[9]        319c9944b1586e899d431c7f91bcccc8
                   690dbf59b28386b2315f3d36ef2eaa3c
       y[10]       f30b2b51f48b71b003dfb08249484201
                   043f65f5a3ef6bbd61ddfee81aca9ce6
       y[11]       0081262a00000480dcbc9a3da6fbef5c
                   1c0a55e48a0e729f9184fcb1407c3152
       y[12]       9db268f6fe50032a363c9801306837fa
                   fabdf957fd97eafc80dbd165e435d0e2
       y[13]       dfd836a28b354023924b6fb7e48bc0b3
                   ed95eea64c2d402f4d734c8dc26f3ac5
       y[14]       91825daef01eae3c38e3328d00a77dc6
                   57034f287ccb0f0e1c9a7cbdc828f627
       y[15]       205e4737b84b58376551d44c12c3c215
                   c812a0970789c83de51d6ad787271963

    McGrew, et al.                Informational                    [Page 52]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[16]       327f0a5fbb6b5907dec02c9a90934af5
                   a1c63b72c82653605d1dcce51596b3c2
       y[17]       b45696689f2eb382007497557692caac
                   4d57b5de9f5569bc2ad0137fd47fb47e
       y[18]       664fcb6db4971f5b3e07aceda9ac130e
                   9f38182de994cff192ec0e82fd6d4cb7
       y[19]       f3fe00812589b7a7ce51544045643301
                   6b84a59bec6619a1c6c0b37dd1450ed4
       y[20]       f2d8b584410ceda8025f5d2d8dd0d217
                   6fc1cf2cc06fa8c82bed4d944e71339e
       y[21]       ce780fd025bd41ec34ebff9d4270a322
                   4e019fcb444474d482fd2dbe75efb203
       y[22]       89cc10cd600abb54c47ede93e08c114e
                   db04117d714dc1d525e11bed8756192f
       y[23]       929d15462b939ff3f52f2252da2ed64d
                   8fae88818b1efa2c7b08c8794fb1b214
       y[24]       aa233db3162833141ea4383f1a6f120b
                   e1db82ce3630b3429114463157a64e91
       y[25]       234d475e2f79cbf05e4db6a9407d72c6
                   bff7d1198b5c4d6aad2831db61274993
       y[26]       715a0182c7dc8089e32c8531deed4f74
                   31c07c02195eba2ef91efb5613c37af7
       y[27]       ae0c066babc69369700e1dd26eddc0d2
                   16c781d56e4ce47e3303fa73007ff7b9
       y[28]       49ef23be2aa4dbf25206fe45c20dd888
                   395b2526391a724996a44156beac8082
       y[29]       12858792bf8e74cba49dee5e8812e019
                   da87454bff9e847ed83db07af3137430
       y[30]       82f880a278f682c2bd0ad6887cb59f65
                   2e155987d61bbf6a88d36ee93b6072e6
       y[31]       656d9ccbaae3d655852e38deb3a2dcf8
                   058dc9fb6f2ab3d3b3539eb77b248a66
       y[32]       1091d05eb6e2f297774fe6053598457c
                   c61908318de4b826f0fc86d4bb117d33
       y[33]       e865aa805009cc2918d9c2f840c4da43
                   a703ad9f5b5806163d7161696b5a0adc
       --------------------------------------------
       LMS type    00000005                         # LM_SHA256_M32_H5
       path[0]     d5c0d1bebb06048ed6fe2ef2c6cef305
                   b3ed633941ebc8b3bec9738754cddd60
       path[1]     e1920ada52f43d055b5031cee6192520
                   d6a5115514851ce7fd448d4a39fae2ab
       path[2]     2335b525f484e9b40d6a4a969394843b
                   dcf6d14c48e8015e08ab92662c05c6e9
       path[3]     f90b65a7a6201689999f32bfd368e5e3
                   ec9cb70ac7b8399003f175c40885081a
       path[4]     09ab3034911fe125631051df0408b394
                   6b0bde790911e8978ba07dd56c73e7ee

    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
                   014a72f1b1ab5cc85cf1d892903b5439
       I           d08fabd4a2091ff0a8cb4ed834e74534
       Second level LMS tree
       SEED        a1c4696e2608035a886100d05cd99945
                   eb3370731884a8235e2fb3d4d71f2547
       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
                   c92124404d45fa53cf161c28f1ad5a8e
       --------------------------------------------
       --------------------------------------------

       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
       sig[0]:
       --------------------------------------------
       LMS signature
       q           00000003
       --------------------------------------------
       LMOTS signature
       LMOTS type  00000003                         # LMOTS_SHA256_N32_W4
       C           3d46bee8660f8f215d3f96408a7a64cf
                   1c4da02b63a55f62c666ef5707a914ce
       y[0]        0674e8cb7a55f0c48d484f31f3aa4af9
                   719a74f22cf823b94431d01c926e2a76
       y[1]        bb71226d279700ec81c9e95fb11a0d10
                   d065279a5796e265ae17737c44eb8c59
       y[2]        4508e126a9a7870bf4360820bdeb9a01
                   d9693779e416828e75bddd7d8c70d50a
       y[3]        0ac8ba39810909d445f44cb5bb58de73
                   7e60cb4345302786ef2c6b14af212ca1
       y[4]        9edeaa3bfcfe8baa6621ce88480df237
                   1dd37add732c9de4ea2ce0dffa53c926
       y[5]        49a18d39a50788f4652987f226a1d481
                   68205df6ae7c58e049a25d4907edc1aa
       y[6]        90da8aa5e5f7671773e941d805536021
                   5c6b60dd35463cf2240a9c06d694e9cb
       y[7]        54e7b1e1bf494d0d1a28c0d31acc7516
                   1f4f485dfd3cb9578e836ec2dc722f37
       y[8]        ed30872e07f2b8bd0374eb57d22c614e
                   09150f6c0d8774a39a6e168211035dc5
       y[9]        2988ab46eaca9ec597fb18b4936e66ef
                   2f0df26e8d1e34da28cbb3af75231372
       y[10]       0c7b345434f72d65314328bbb030d0f0
                   f6d5e47b28ea91008fb11b05017705a8
       y[11]       be3b2adb83c60a54f9d1d1b2f476f9e3
                   93eb5695203d2ba6ad815e6a111ea293
       y[12]       dcc21033f9453d49c8e5a6387f588b1e
                   a4f706217c151e05f55a6eb7997be09d
       y[13]       56a326a32f9cba1fbe1c07bb49fa04ce
                   cf9df1a1b815483c75d7a27cc88ad1b1
       y[14]       238e5ea986b53e087045723ce16187ed
                   a22e33b2c70709e53251025abde89396
       y[15]       45fc8c0693e97763928f00b2e3c75af3
                   942d8ddaee81b59a6f1f67efda0ef81d
       y[16]       11873b59137f67800b35e81b01563d18
                   7c4a1575a1acb92d087b517a8833383f

    McGrew, et al.                Informational                    [Page 55]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[17]       05d357ef4678de0c57ff9f1b2da61dfd
                   e5d88318bcdde4d9061cc75c2de3cd47
       y[18]       40dd7739ca3ef66f1930026f47d9ebaa
                   713b07176f76f953e1c2e7f8f271a6ca
       y[19]       375dbfb83d719b1635a7d8a138919579
                   44b1c29bb101913e166e11bd5f34186f
       y[20]       a6c0a555c9026b256a6860f4866bd6d0
                   b5bf90627086c6149133f8282ce6c9b3
       y[21]       622442443d5eca959d6c14ca8389d12c
                   4068b503e4e3c39b635bea245d9d05a2
       y[22]       558f249c9661c0427d2e489ca5b5dde2
                   20a90333f4862aec793223c781997da9
       y[23]       8266c12c50ea28b2c438e7a379eb106e
                   ca0c7fd6006e9bf612f3ea0a454ba3bd
       y[24]       b76e8027992e60de01e9094fddeb3349
                   883914fb17a9621ab929d970d101e45f
       y[25]       8278c14b032bcab02bd15692d21b6c5c
                   204abbf077d465553bd6eda645e6c306
       y[26]       5d33b10d518a61e15ed0f092c3222628
                   1a29c8a0f50cde0a8c66236e29c2f310
       y[27]       a375cebda1dc6bb9a1a01dae6c7aba8e
                   bedc6371a7d52aacb955f83bd6e4f84d
       y[28]       2949dcc198fb77c7e5cdf6040b0f84fa
                   f82808bf985577f0a2acf2ec7ed7c0b0
       y[29]       ae8a270e951743ff23e0b2dd12e9c3c8
                   28fb5598a22461af94d568f29240ba28
       y[30]       20c4591f71c088f96e095dd98beae456
                   579ebbba36f6d9ca2613d1c26eee4d8c
       y[31]       73217ac5962b5f3147b492e8831597fd
                   89b64aa7fde82e1974d2f6779504dc21
       y[32]       435eb3109350756b9fdabe1c6f368081
                   bd40b27ebcb9819a75d7df8bb07bb05d
       y[33]       b1bab705a4b7e37125186339464ad8fa
                   aa4f052cc1272919fde3e025bb64aa8e
       y[34]       0eb1fcbfcc25acb5f718ce4f7c2182fb
                   393a1814b0e942490e52d3bca817b2b2
       y[35]       6e90d4c9b0cc38608a6cef5eb153af08
                   58acc867c9922aed43bb67d7b33acc51
       y[36]       9313d28d41a5c6fe6cf3595dd5ee63f0
                   a4c4065a083590b275788bee7ad875a7
       y[37]       f88dd73720708c6c6c0ecf1f43bbaada
                   e6f208557fdc07bd4ed91f88ce4c0de8
       y[38]       42761c70c186bfdafafc444834bd3418
                   be4253a71eaf41d718753ad07754ca3e
       y[39]       ffd5960b0336981795721426803599ed
                   5b2b7516920efcbe32ada4bcf6c73bd2
       y[40]       9e3fa152d9adeca36020fdeeee1b7395
                   21d3ea8c0da497003df1513897b0f547

    McGrew, et al.                Informational                    [Page 56]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[41]       94a873670b8d93bcca2ae47e64424b74
                   23e1f078d9554bb5232cc6de8aae9b83
       y[42]       fa5b9510beb39ccf4b4e1d9c0f19d5e1
                   7f58e5b8705d9a6837a7d9bf99cd1338
       y[43]       7af256a8491671f1f2f22af253bcff54
                   b673199bdb7d05d81064ef05f80f0153
       y[44]       d0be7919684b23da8d42ff3effdb7ca0
                   985033f389181f47659138003d712b5e
       y[45]       c0a614d31cc7487f52de8664916af79c
                   98456b2c94a8038083db55391e347586
       y[46]       2250274a1de2584fec975fb09536792c
                   fbfcf6192856cc76eb5b13dc4709e2f7
       y[47]       301ddff26ec1b23de2d188c999166c74
                   e1e14bbc15f457cf4e471ae13dcbdd9c
       y[48]       50f4d646fc6278e8fe7eb6cb5c94100f
                   a870187380b777ed19d7868fd8ca7ceb
       y[49]       7fa7d5cc861c5bdac98e7495eb0a2cee
                   c1924ae979f44c5390ebedddc65d6ec1
       y[50]       1287d978b8df064219bc5679f7d7b264
                   a76ff272b2ac9f2f7cfc9fdcfb6a5142
       y[51]       8240027afd9d52a79b647c90c2709e06
                   0ed70f87299dd798d68f4fadd3da6c51
       y[52]       d839f851f98f67840b964ebe73f8cec4
                   1572538ec6bc131034ca2894eb736b3b
       y[53]       da93d9f5f6fa6f6c0f03ce43362b8414
                   940355fb54d3dfdd03633ae108f3de3e
       y[54]       bc85a3ff51efeea3bc2cf27e1658f178
                   9ee612c83d0f5fd56f7cd071930e2946
       y[55]       beeecaa04dccea9f97786001475e0294
                   bc2852f62eb5d39bb9fbeef75916efe4
       y[56]       4a662ecae37ede27e9d6eadfdeb8f8b2
                   b2dbccbf96fa6dbaf7321fb0e701f4d4
       y[57]       29c2f4dcd153a2742574126e5eaccc77
                   686acf6e3ee48f423766e0fc466810a9
       y[58]       05ff5453ec99897b56bc55dd49b99114
                   2f65043f2d744eeb935ba7f4ef23cf80
       y[59]       cc5a8a335d3619d781e7454826df720e
                   ec82e06034c44699b5f0c44a8787752e
       y[60]       057fa3419b5bb0e25d30981e41cb1361
                   322dba8f69931cf42fad3f3bce6ded5b
       y[61]       8bfc3d20a2148861b2afc14562ddd27f
                   12897abf0685288dcc5c4982f8260268
       y[62]       46a24bf77e383c7aacab1ab692b29ed8
                   c018a65f3dc2b87ff619a633c41b4fad
       y[63]       b1c78725c1f8f922f6009787b1964247
                   df0136b1bc614ab575c59a16d089917b
       y[64]       d4a8b6f04d95c581279a139be09fcf6e
                   98a470a0bceca191fce476f9370021cb

    McGrew, et al.                Informational                    [Page 57]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[65]       c05518a7efd35d89d8577c990a5e1996
                   1ba16203c959c91829ba7497cffcbb4b
       y[66]       294546454fa5388a23a22e805a5ca35f
                   956598848bda678615fec28afd5da61a
       --------------------------------------------
       LMS type    00000006                         # LM_SHA256_M32_H10
       path[0]     b326493313053ced3876db9d23714818
                   1b7173bc7d042cefb4dbe94d2e58cd21
       path[1]     a769db4657a103279ba8ef3a629ca84e
                   e836172a9c50e51f45581741cf808315
       path[2]     0b491cb4ecbbabec128e7c81a46e62a6
                   7b57640a0a78be1cbf7dd9d419a10cd8
       path[3]     686d16621a80816bfdb5bdc56211d72c
                   a70b81f1117d129529a7570cf79cf52a
       path[4]     7028a48538ecdd3b38d3d5d62d262465
                   95c4fb73a525a5ed2c30524ebb1d8cc8
       path[5]     2e0c19bc4977c6898ff95fd3d310b0ba
                   e71696cef93c6a552456bf96e9d075e3
       path[6]     83bb7543c675842bafbfc7cdb88483b3
                   276c29d4f0a341c2d406e40d4653b7e4
       path[7]     d045851acf6a0a0ea9c710b805cced46
                   35ee8c107362f0fc8d80c14d0ac49c51
       path[8]     6703d26d14752f34c1c0d2c4247581c1
                   8c2cf4de48e9ce949be7c888e9caebe4
       path[9]     a415e291fd107d21dc1f084b11582082
                   49f28f4f7c7e931ba7b3bd0d824a4570
       --------------------------------------------
       LMS public key
       LMS type    00000005                         # LM_SHA256_M32_H5
       LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
       I           215f83b7ccb9acbcd08db97b0d04dc2b
       K           a1cd035833e0e90059603f26e07ad2aa
                   d152338e7a5e5984bcd5f7bb4eba40b7
       --------------------------------------------
       final_signature:
       --------------------------------------------
       LMS signature
       q           00000004
       --------------------------------------------
       LMOTS signature
       LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
       C           0eb1ed54a2460d512388cad533138d24
                   0534e97b1e82d33bd927d201dfc24ebb
       y[0]        11b3649023696f85150b189e50c00e98
                   850ac343a77b3638319c347d7310269d
       y[1]        3b7714fa406b8c35b021d54d4fdada7b
                   9ce5d4ba5b06719e72aaf58c5aae7aca

    McGrew, et al.                Informational                    [Page 58]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[2]        057aa0e2e74e7dcfd17a0823429db629
                   65b7d563c57b4cec942cc865e29c1dad
       y[3]        83cac8b4d61aacc457f336e6a10b6632
                   3f5887bf3523dfcadee158503bfaa89d
       y[4]        c6bf59daa82afd2b5ebb2a9ca6572a60
                   67cee7c327e9039b3b6ea6a1edc7fdc3
       y[5]        df927aade10c1c9f2d5ff446450d2a39
                   98d0f9f6202b5e07c3f97d2458c69d3c
       y[6]        8190643978d7a7f4d64e97e3f1c4a08a
                   7c5bc03fd55682c017e2907eab07e5bb
       y[7]        2f190143475a6043d5e6d5263471f4ee
                   cf6e2575fbc6ff37edfa249d6cda1a09
       y[8]        f797fd5a3cd53a066700f45863f04b6c
                   8a58cfd341241e002d0d2c0217472bf1
       y[9]        8b636ae547c1771368d9f317835c9b0e
                   f430b3df4034f6af00d0da44f4af7800
       y[10]       bc7a5cf8a5abdb12dc718b559b74cab9
                   090e33cc58a955300981c420c4da8ffd
       y[11]       67df540890a062fe40dba8b2c1c548ce
                   d22473219c534911d48ccaabfb71bc71
       y[12]       862f4a24ebd376d288fd4e6fb06ed870
                   5787c5fedc813cd2697e5b1aac1ced45
       y[13]       767b14ce88409eaebb601a93559aae89
                   3e143d1c395bc326da821d79a9ed41dc
       y[14]       fbe549147f71c092f4f3ac522b5cc572
                   90706650487bae9bb5671ecc9ccc2ce5
       y[15]       1ead87ac01985268521222fb9057df7e
                   d41810b5ef0d4f7cc67368c90f573b1a
       y[16]       c2ce956c365ed38e893ce7b2fae15d36
                   85a3df2fa3d4cc098fa57dd60d2c9754
       y[17]       a8ade980ad0f93f6787075c3f680a2ba
                   1936a8c61d1af52ab7e21f416be09d2a
       y[18]       8d64c3d3d8582968c2839902229f85ae
                   e297e717c094c8df4a23bb5db658dd37
       y[19]       7bf0f4ff3ffd8fba5e383a48574802ed
                   545bbe7a6b4753533353d73706067640
       y[20]       135a7ce517279cd683039747d218647c
                   86e097b0daa2872d54b8f3e508598762
       y[21]       9547b830d8118161b65079fe7bc59a99
                   e9c3c7380e3e70b7138fe5d9be255150
       y[22]       2b698d09ae193972f27d40f38dea264a
                   0126e637d74ae4c92a6249fa103436d3
       y[23]       eb0d4029ac712bfc7a5eacbdd7518d6d
                   4fe903a5ae65527cd65bb0d4e9925ca2
       y[24]       4fd7214dc617c150544e423f450c99ce
                   51ac8005d33acd74f1bed3b17b7266a4
       y[25]       a3bb86da7eba80b101e15cb79de9a207
                   852cf91249ef480619ff2af8cabca831

    McGrew, et al.                Informational                    [Page 59]

    RFC 8554                LMS Hash-Based Signatures             April 2019

       y[26]       25d1faa94cbb0a03a906f683b3f47a97
                   c871fd513e510a7a25f283b196075778
       y[27]       496152a91c2bf9da76ebe089f4654877
                   f2d586ae7149c406e663eadeb2b5c7e8
       y[28]       2429b9e8cb4834c83464f079995332e4
                   b3c8f5a72bb4b8c6f74b0d45dc6c1f79
       y[29]       952c0b7420df525e37c15377b5f09843
                   19c3993921e5ccd97e097592064530d3
       y[30]       3de3afad5733cbe7703c5296263f7734
                   2efbf5a04755b0b3c997c4328463e84c
       y[31]       aa2de3ffdcd297baaaacd7ae646e44b5
                   c0f16044df38fabd296a47b3a838a913
       y[32]       982fb2e370c078edb042c84db34ce36b
                   46ccb76460a690cc86c302457dd1cde1
       y[33]       97ec8075e82b393d542075134e2a17ee
                   70a5e187075d03ae3c853cff60729ba4
       --------------------------------------------
       LMS type    00000005                         # LM_SHA256_M32_H5
       path[0]     4de1f6965bdabc676c5a4dc7c35f97f8
                   2cb0e31c68d04f1dad96314ff09e6b3d
       path[1]     e96aeee300d1f68bf1bca9fc58e40323
                   36cd819aaf578744e50d1357a0e42867
       path[2]     04d341aa0a337b19fe4bc43c2e79964d
                   4f351089f2e0e41c7c43ae0d49e7f404
       path[3]     b0f75be80ea3af098c9752420a8ac0ea
                   2bbb1f4eeba05238aef0d8ce63f0c6e5
       path[4]     e4041d95398a6f7f3e0ee97cc1591849
                   d4ed236338b147abde9f51ef9fd4e1c1

    Acknowledgements

       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]