Crypto Forum Research Group D. McGrew
Internet-Draft M. Curcio
Intended status: Informational S. Fluhrer
Expires: April 9, 2018 Cisco Systems
October 6, 2017

Hash-Based Signatures


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

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on April 9, 2018.

Copyright Notice

Copyright (c) 2017 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 ( 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. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

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 moderatley slow key generation (in comparison with RSA and ECDSA). 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 cannot securely sign more than one. 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 this note we describe the Leighton-Micali Signature (LMS) system, which is a variant of the Merkle scheme, and a Hierarchical Signature System (HSS) built on top of it that can efficiently scale to larger numbers of signatures. We denote the one-time signature scheme incorporate in LMS as LM-OTS. This note is structured as follows. Notation is introduced in Section 3. The LM-OTS signature system is described in Section 4, and the LMS and HSS N-time signature systems are described in Section 5 and Section 6, respectively. Sufficient detail is provided to ensure interoperability. The public formats are described in Section 7. The rationale for design decisions are given in Section 8. The changes made to this document over previous versions is listed in Section 9. The IANA registry for these signature systems is described in Section 10. Intellectual Property issues are discussed in Section 11. Security considerations are presented in Section 12.

1.1. Conventions Used In This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

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.

A message/signature pair are 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 are 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 non-negative 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 non-negative 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:

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. 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 non-negative real number, then we define the following functions:

3.1.3. Strings of w-bit elements

If S is a byte string, then byte(S, i) denotes its i^th byte, where byte(S, 0) is the leftmost byte. 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)) )

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 should raise an error.

3.2. Security string

To improve security against attacks that amortize their effort against multiple invocations of the hash function, Leighton and Micali introduce 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 below fields. 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. These fields are:

3.3. 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 XDR enumerations (see Section 7).

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 a diversification parameter q (which is used as part of the security string, as listed in Section 3.2. When the LM-OTS signature system is used outside of an N-time signature system, this value SHOULD be set to the all-zero value.

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:

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

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. A table illustrating various combinations of n, w, p, and ls is provided in Table 1.

4.2. Parameter Sets

To fully describe a LM-OTS signature method, the parameters n and w, as well as the function H, MUST be specified. This section defines several LM-OTS methods, each of which is identified by a name. The values for p and ls are provided as a convenience; the formal method of computing them is given in Appendix B.

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, generate and verify the signature); in general, the LM-OTS signature is n*p bytes long, and public key generation will take p*(2^w-1)+1 hash computations (and signature generation and verification will take about half that on average).

Name H n w p ls
LMOTS_SHA256_N32_W1 SHA256 32 1 265 7
LMOTS_SHA256_N32_W2 SHA256 32 2 133 6
LMOTS_SHA256_N32_W4 SHA256 32 4 67 4
LMOTS_SHA256_N32_W8 SHA256 32 8 34 0

Here SHA256 denotes the NIST standard hash function [FIPS180].

4.3. 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 value p from the type, and the value I the 16 byte
     identifier of the LMS public/private keypair 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 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.4. 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

The public key is the value returned by Algorithm 1.

4.5. Checksum

A checksum is used to ensure that any forgery attempt that manipulates the elements of an existing signature will be detected. The security property that it provides is detailed in Section 12. 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)

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.6. Signature Generation

The LM-OTS signature of a message is generated by first prepending the LM key identifier I, the LM leaf identifier q, the value D_MESG and the randomizer C to the message, then computing the hash, and then concatenating the checksum of the hash to the hash itself, then 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 

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

The signature is the string returned by Algorithm 3. Section 7 specifies the typecode and more formally defines the encoding and decoding of the string.

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

  3. compute the public key candidate Kc from the signature,
     message, 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 Type , 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

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 size 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, 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 L has node number 2^L + 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:

There are 2^h leaves in the tree. The hash function used within the LMS system SHOULD be the same as the hash function used within the LM-OTS system used to generate the leaves.

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

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

   3. q = 0

An LMS private key MAY be generated pseudorandomly from a secret value, in which case the secret value MUST be at least m bytes long, be 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.

5.3. LMS Public Key

An LMS public key is defined as follows, where we denote the public key associated with the i^th LM-OTS private key as OTS_PUB[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, and the string for the r^th node is denoted as T[r] and is defined as

  T[r]=/ H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB[r-2^h])   if r >= 2^h,
       \ H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1]) otherwise.        

The LMS public key is the string u32str(type) || u32str(otstype) || I || T[1]. Section 7 specifies the format of the type variable. The value otstype is the parameter set for the LM-OTS public/private keypairs 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.

5.4. LMS Signature

An LMS signature consists of Section 7 specifies the typecode and more formally defines the format. The array of values contains the siblings of the nodes on the path from the leaf to the root but does not contain the nodes on the path themselves. The array for a tree with height h will have h values. The first value is the sibling of the leaf, the next value is the sibling of the parent of the leaf, and so on up the path to the root.

Symbolically, the signature can be represented as u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1].

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, someone could potentially generate a forged signature of a third message.

The array of node values in the signature MAY be computed in any way. There are many potential time/storage tradeoffs 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. 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 tradeoffs are described in the 'Small-Memory LM Schemes' section of [USPTO5432852].

5.5. 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, 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 fails.

Algorithm 6: LMS Signature Verification

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

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

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

     b. set m according to pubtype, based on Table 2

     c. if the public key is not exactly 20 + m bytes 
        long, return INVALID

     d. I = next 16 bytes of the public key

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

  3. compute the candidate LMS root value Tc from the signature,
     message, identifier and pubtype using Algorithm 6b.

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

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

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

  2. parse sigtype, q, ots_signature, and path from the signature as

    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. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature

    f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1))

    f. if sigtype is not the LM typecode from the public key, return INVALID

    g. set m, h according to sigtype and Table 2

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

    i. 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
  3. Kc = candidate public key computed by applying Algorithm 4b 
     to the signature ots_signature, the message, and the 
     identifiers I, q

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

  5. return Tc

6. Hierarchical signatures

In scenarios where it is necessary to minimize the time taken by the public key generation process, a Hierarchical N-time Signature System (HSS) can be used. Leighton and Micali describe a scheme in which an LMS public key is used to sign a second LMS public key, which is then distributed along with the signatures generated with the second public key [USPTO5432852]. This hierarchical scheme, which we describe in this section, uses an LMS scheme as a component. HSS, in essence, utilizes a tree of LMS trees, in which 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 one of its leaves. 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.

Each level of the hierarchy is associated with a distinct LMS public key, private key, signature, and identifier. The number of levels is denoted 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:

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

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.

6.1. Key Generation

When an HSS key pair is generated, the key pair for each level MUST have its own identifier I.

To generate an HSS private and public key pair, new LMS private and public keys are generated for prv[i] and pub[i] for i=0, ... , L-1. These key pairs, and their identifiers, MUST be generated independently.

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]. The values pub[0] and prv[0] do not change, though the values of pub[i] and prv[i] are dynamic for i > 0, and are changed by the signature generation algorithm.

6.2. Signature Generation

To sign a message using the private key prv, the following steps are performed:

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]

6.3. Signature Verification

To verify a signature sig and message using the public key pub, the following steps are performed:

   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.

7. Formats

The signature and public key formats are formally defined using the External Data Representation (XDR) [RFC4506] in order to provide an unambiguous, machine readable definition. For clarity, we also include a private key format as well, though consistency is not needed for interoperability and an implementation MAY use any private key format. Though XDR is used, these formats 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 ots_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 ots_signature switch (ots_algorithm_type type) {
 case lmots_sha256_n32_w1:
   lmots_signature_n32_p265 sig_n32_p265;
 case lmots_sha256_n32_w2:
   lmots_signature_n32_p133 sig_n32_p133;
 case lmots_sha256_n32_w4:
   lmots_signature_n32_p67  sig_n32_p67;
 case lmots_sha256_n32_w8:
   lmots_signature_n32_p34  sig_n32_p34;
   void;   /* error condition */

/* hash based signatures (hbs) */ 

enum hbs_algorithm_type {
  hbs_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 (hbs_algorithm_type type) {
 case lms_sha256_n32_h5:
   bytestring32 path_n32_h5[5];
 case lms_sha256_n32_h10:
   bytestring32 path_n32_h10[10];
 case lms_sha256_n32_h15:
   bytestring32 path_n32_h15[15]; 
 case lms_sha256_n32_h20:
   bytestring32 path_n32_h20[20]; 
 case lms_sha256_n32_h25:
   bytestring32 path_n32_h25[25]; 
   void;     /* error condition */

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

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

union hbs_public_key switch (hbs_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;
   void;     /* error condition */

/* hierarchical signature system (hss)  */

struct hss_public_key {
  unsigned int L;
  hbs_public_key pub;

struct signed_public_key {
  hbs_signature sig;
  hbs_public_key pub;

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

Many of the objects 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, and if an object has a different length, then any signature computed from the object is INVALID.

8. 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 this size was 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.

The Checksum Section 4.5 is calculated using a non-negative 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.6 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 non-negative 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.

9. History

This is the eigth version of this draft. It has the following changes from previous versions:

Version 07

Version 06

Version 05

Version 04

Previous versions

This section is to be removed by the RFC editor upon publication.

10. IANA Considerations

The Internet Assigned Numbers Authority (IANA) is requested to create two registries: one for OTS signatures, which includes all of the LM-OTS signatures as defined in Section 3, and one for Leighton-Micali Signatures, as defined in Section 4. 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. Each entry in the registry contains the following elements:

Requests to add an entry to the registry MUST include the name and the reference. The number is assigned by IANA. Submitters SHOULD have their requests reviewed by the IRTF Crypto Forum Research Group (CFRG) at Interested applicants that are unfamiliar with IANA processes should visit

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

The LM-OTS registry is as follows.

Name Reference Numeric Identifier
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

The LMS registry is as follows.

Name Reference Numeric Identifier
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

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

11. Intellectual Property

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

11.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 [RFC3979] and [RFC4879] and at

12. 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 and signature that are 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.

LMS is provably secure in the random oracle model, where the hash compression function is considered the random oracle, as shown by [Fluhrer17]. Corollary 1 of that paper states:

The format of the inputs to the hash function H have 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), and in particular, 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 are

   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[r-2^h]
   I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1]
   I || u32str(q) || u16str(j) || u8str(0xff) || SEED

Each hash type listed is distinct; at locations 20, 21 of each hash, there exists either a fixed value D_PBLC, D_MESG, D_LEAF, D_INTR, or a 16 bit value (i or j). These fixed values are distinct from each other, and large (over 32768), while the 16 bit values are small (currently no more than 265; possibly being slightly larger if larger hash functions are supported; hence the hash invocations with i/j will not collide any of the D_PBLC, D_MESG, D_LEAF, D_INTR hashes. The only other collision possibility is the Winternitz chain hash colliding with the recommended pseudorandom key generation process; here, at location 22, 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 pseuddorandom 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 3. This can be shown (in [Fluhrer17]) to have only a limited effect on the security of the system.

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

In a typical computing environment, a private key will be stored in non-volatile 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 non-volatile storage. It is essential for security that the application ensure 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 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 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 non-volatile 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.

12.2. 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.6). 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,

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,

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

13. Comparison with other work

The eXtended Merkle Signature Scheme (XMSS) [XMSS] is similar to HSS in several ways. 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 need only perform one. Additionally, HSS is somewhat simpler, and it allows a single-level tree in a simple way (as described in Section 6.2).

14. Acknowledgements

Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric Osterweil, Ahmed Kosba, Russ Housley, Philip Lafrance, Alexander Truskovsky, Mark Peruzel 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] and Jonathan Katz, who gave us security guidance, and Bruno Couillard and Jim Goodman for an especially thorough review.

15. References

15.1. Normative References

[FIPS180] National Institute of Standards and Technology, "Secure Hash Standard (SHS)", 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.
[RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 2434, DOI 10.17487/RFC2434, October 1998.
[RFC3979] Bradner, S., "Intellectual Property Rights in IETF Technology", RFC 3979, DOI 10.17487/RFC3979, March 2005.
[RFC4506] Eisler, M., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006.
[RFC4879] Narten, T., "Clarification of the Third Party Disclosure Procedure in RFC 3979", RFC 4879, DOI 10.17487/RFC4879, April 2007.
[USPTO5432852] Leighton, T. and S. Micali, "Large provably fast and secure digital signature schemes from secure hash functions", U.S. Patent 5,432,852, July 1995.

15.2. Informative References

[C:Merkle87] Merkle, R., "A Digital Signature Based on a Conventional Encryption Function", Lecture Notes in Computer Science crypto87vol, 1988.
[C:Merkle89a] Merkle, R., "A Certified Digital Signature", Lecture Notes in Computer Science crypto89vol, 1990.
[C:Merkle89b] Merkle, R., "One Way Hash Functions and DES", Lecture Notes in Computer Science crypto89vol, 1990.
[Fluhrer17] Fluhrer, S., "Further analysis of a proposed hash-based signature standard", EPrint, 2017.
[Grover96] Grover, L., "A fast quantum mechanical algorithm for database search", 28th ACM Symposium on the Theory of Computing p. 212, 1996.
[Katz16] Katz, J., "Analysis of a proposed hash-based signature standard", Security Standardization Research (SSR) Conference, 2016.
[Merkle79] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Stanford University Information Systems Laboratory Technical Report 1979-1, 1979.
[SPHINCS] Bernstein, D., Hopwood, D., Hulsing, A., Lange, T., Niederhagen, R., Papachristadoulou, L., Schneider, M., Schwabe, P. and Z. Wilcox-O'Hearn, "SPHINCS: Practical Stateless Hash-Based Signatures.", Annual International Conference on the Theory and Applications of Cryptographic Techniques Springer., 2015.
[STMGMT] McGrew, D., Fluhrer, S., Kampanakis, P., Gazdag, S., Butin, D. and J. Buchmann, "State Management for Hash-based Signatures.", Security Standardization Resarch (SSR) Conference 224., 2016.
[XMSS] Buchmann, J., Dahmen, E. and . Andreas Hulsing, "XMSS-a practical forward secure signature scheme based on minimal security assumptions.", International Workshop on Post-Quantum Cryptography Springer Berlin., 2011.

Appendix A. Pseudorandom Key Generation

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

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

x_q[j] = H(I || u32str(q) || u16str(j) || 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 cryptographical 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 set:

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 bits value used for the sum variable in Algorithm 2 in Section 4.5

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

Hash Length in Bytes (n) Winternitz Parameter (w) w-bit Elements in Hash (u) w-bit Elements in Checksum (v) Left Shift (ls) Total Number of w-bit Elements (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

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

Note that this pseudocode expects that all 2^h leaves of the tree have equal depth; that is, 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. Example Implementation

Two example implementations can be found online at and at

Appendix E. 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 value of the elements on the right, in hexadecimal. The concatenation of all of the values within a public key or signature produces that public key or signature, and values that do not fit within a single line are listed across successive lines.

Test Case 1 Public Key

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

Test Case 1 Message

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

Test Case 1 Signature

HSS signature
Nspk        00000001
LMS signature
q           00000005
LMOTS signature
LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
C           d32b56671d7eb98833c49b433c272586
y[0]        965a25bfd37f196b9073f3d4a232feb6
y[1]        a64c7f60f6261a62043f86c70324b770
y[2]        e05fd5c6509a6e61d559cf1a77a970de
y[3]        582e8ff1b10cd99d4e8e413ef469559f
y[4]        81d84b15357ff48ca579f19f5e71f184
y[5]        14784269d7d876f5d35d3fbfc7039a46
y[6]        60b960e7777c52f060492f2d7c660e14
y[7]        c3943c6b9c4f2405a3cb8bf8a691ca51
y[8]        f0a75ee390e385e3ae0b906961ecf41a
y[9]        35b167b28ce8dc988a3748255230cef9
y[10]       e783ed04516de012498682212b078105
y[11]       aaf65de7620dabec29eb82a17fde35af
y[12]       1099762b37f43c4a3c20010a3d72e2f6
y[13]       a1a40281cc5a7ea98d2adc7c7400c2fe
y[14]       9cbbc68fee0c3efe4ec22b83a2caa3e4
y[15]       4f8a58f7f24335eec5c5eb5e0cf01dcf
y[16]       c5b9f64a2a9af2f07c05e99e5cf80f00
y[17]       26857713afd2ca6bb85cd8c107347552
y[18]       c413e7d0acd8bdd81352b2471fc1bc4f
y[19]       cf7cc62fb92be14f18c2192384ebceaf
y[20]       e87b0144417e8d7baf25eb5f70f09f01
y[21]       da67571f5dd546fc22cb1f97e0ebd1a6
y[22]       115cce6f792cc84e36da58960c5f1d76
y[23]       1efc72d60ca5e908b3a7dd69fef02491
y[24]       c75e13527b7a581a556168783dc1e975
y[25]       8d3ee2062445dfb85ef8c35f8e1f3371
y[26]       ab8f5c612ead0b729a1d059d02bfe18e
y[27]       eec0f3f3f13039a17f88b0cf808f4884
y[28]       4f1f4ab949b9feefadcb71ab50ef27d6
y[29]       9b6066f09c37280d59128d2f0f637c7d
y[30]       b7c878c9411cafc5071a34a00f4cf077
y[31]       d76f7ce973e9367095ba7e9a3649b7f4
y[32]       401b64457c54d65fef6500c59cdfb69a
y[33]       b0f3f79cd893d314168648499898fbc0
LMS type    00000005                         # LM_SHA256_M32_H5
path[0]     d8b8112f9200a5e50c4a262165bd342c
path[1]     129ac6eda839a6f357b5a04387c5ce97
path[2]     12f5dbe400bd49e4501e859f885bf073
path[3]     b5971115aa39efd8d564a6b90282c316
path[4]     4cca1848cf7da59cc2b3d9d0692dd2a2
LMS public key
LMS type    00000005                         # LM_SHA256_M32_H5
LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
I           d2f14ff6346af964569f7d6cb880a1b6
K           6c5004917da6eafe4d9ef6c6407b3db0
LMS signature
q           0000000a
LMOTS signature
LMOTS type  00000004                         # LMOTS_SHA256_N32_W8
C           0703c491e7558b35011ece3592eaa5da
y[0]        95cae05b899e35dffd71705470620998
y[1]        9bc042da4b4525650485c66d0ce19b31
y[2]        6a120c5612344258b85efdb7db1db9e1
y[3]        9eeddb03a1d2374af7bf771855774562
y[4]        a698994c0827d90e86d43e0df7f4bfcd
y[5]        100e4f2c5fc38c003c1ab6fea479eb2f
y[6]        969f6aecbfe44cf356888a7b15a3ff07
y[7]        e61af23aee7fa5d4d9a5dfcf43c4c26c
y[8]        beadb2b25b3cacc1ac0cef346cbb90fb
y[9]        319c9944b1586e899d431c7f91bcccc8
y[10]       f30b2b51f48b71b003dfb08249484201
y[11]       0081262a00000480dcbc9a3da6fbef5c
y[12]       9db268f6fe50032a363c9801306837fa
y[13]       dfd836a28b354023924b6fb7e48bc0b3
y[14]       91825daef01eae3c38e3328d00a77dc6
y[15]       205e4737b84b58376551d44c12c3c215
y[16]       327f0a5fbb6b5907dec02c9a90934af5
y[17]       b45696689f2eb382007497557692caac
y[18]       664fcb6db4971f5b3e07aceda9ac130e
y[19]       f3fe00812589b7a7ce51544045643301
y[20]       f2d8b584410ceda8025f5d2d8dd0d217
y[21]       ce780fd025bd41ec34ebff9d4270a322
y[22]       89cc10cd600abb54c47ede93e08c114e
y[23]       929d15462b939ff3f52f2252da2ed64d
y[24]       aa233db3162833141ea4383f1a6f120b
y[25]       234d475e2f79cbf05e4db6a9407d72c6
y[26]       715a0182c7dc8089e32c8531deed4f74
y[27]       ae0c066babc69369700e1dd26eddc0d2
y[28]       49ef23be2aa4dbf25206fe45c20dd888
y[29]       12858792bf8e74cba49dee5e8812e019
y[30]       82f880a278f682c2bd0ad6887cb59f65
y[31]       656d9ccbaae3d655852e38deb3a2dcf8
y[32]       1091d05eb6e2f297774fe6053598457c
y[33]       e865aa805009cc2918d9c2f840c4da43
LMS type    00000005                         # LM_SHA256_M32_H5
path[0]     d5c0d1bebb06048ed6fe2ef2c6cef305
path[1]     e1920ada52f43d055b5031cee6192520
path[2]     2335b525f484e9b40d6a4a969394843b
path[3]     f90b65a7a6201689999f32bfd368e5e3
path[4]     09ab3034911fe125631051df0408b394

Authors' Addresses

David McGrew Cisco Systems 13600 Dulles Technology Drive Herndon, VA 20171 USA EMail:
Michael Curcio Cisco Systems 7025-2 Kit Creek Road Research Triangle Park, NC 27709-4987 USA EMail:
Scott Fluhrer Cisco Systems 170 West Tasman Drive San Jose, CA USA EMail: