5.2. LMS Private Key

An LMS private key consists 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 qth element of OTS_PRIV[] is generated using Algorithm 0 with the security string S = 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) {
         S = I || q
         OTS_PRIV[q] = LM-OTS private key with security string S
       }

   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 perfect 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 rth node is denoted as T[r] and is defined as

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

The LMS public key is the string u32str(type) || I || T[1]. Section 7 specifies the format of the type variable. The value I is the private key identifier (whose length is denoted by the parameter set), 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.

• a typecode indicating the particular LMS algorithm,
• 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, and
• 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(type) || u32str(q) || ots_signature || 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 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 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 
     INVALID

  2. parse pubtype, I, and T[1] from the public key as follows:
     a. pubtype = strTou32(first 4 bytes of public key)

     b. if the public key is not exactly 4 + LenI + m bytes 
        long, return INVALID

     c. I = next LenI bytes of the public key

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

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

  7. 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
     follows: 
    a. sigtype = strTou32(first 4 bytes of signature)

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

    c. set m, h, and LenI according to sigtype and Table 2; 

    d. q = strTou32(next 4 bytes of signature)

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

    f. set n and p according to otssigtype and Table 1; if the
    signature does string is not at least 12 + n * (p + 1) + m * h
    bytes long, return INVALID

    g. ots_signature = bytes 8 through 8 + n * (p + 1) of signature

    h. 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
 
  5. Kc = candidate public key computed by applying Algorithm 4b 
     to the signature ots_signature, the message, and the 
     security string S = I || q

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

  7. 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. It also makes use of an hbs_key_info structure, which contains the typecode of the LMS algorithm and the typecode of the LM-OTS algorithm.

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 two 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 LMS private key of the ith level,
• pub[i] is the LMS public key of the ith level (which includes the identifier I as well as the key value K),
• sig[i] is the LMS signature of the ith level,

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.

6.1. Key Generation

When an HSS keypair is generated, the keypair for each level has its own identifier.

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. All of the information of the leaf level L-1, including the private key, MUST NOT be stored in nonvolatile memory. Letting nv denote the lowest level for which prv[nv] is stored in nonvolatile memory, there are nv nonvolatile levels, and L-nv volatile levels. For security, nv should be as close to zero as possible (see Section 12.1).

The public key of the HSS scheme is pub[1], the public key of the first level, followed by an array info[] containing the hbs_key_info structures for the remaining levels 1, ..., L-1.

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 > 1, 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:

• 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 one, then the HSS keypair is exhausted, and it MUST NOT generate any more signatures. Otherwise, the keypairs 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 strings, where signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and L-2, inclusive. Then the HSS signature is u32str(L-1) || signed_pub_key[0] || ... || signed_pub_key[L-2] || sig[L-1].
• Note that the number of signed_pub_key elements in the signature is indicated by the value L-1 that appears in the initial four bytes of the signature.

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:

   L' = strToU32(first four bytes of S)
   for (i = 0; i < L'; i = i + 1) {
      siglist[0] = next LMS signature parsed from S
      publist[1] = next LMS public key parsed from S
   }
   siglist[L-1] = next LMS signature parsed from S

   key = pub
   for (i =0; i < L'; 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[L-1])        

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 futher 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 {
  ots_reserved         = 0,
  lmots_sha256_n32_w1  = 1,
  lmots_sha256_n32_w2  = 2,
  lmots_sha256_n32_w4  = 3,
  lmots_sha256_n32_w8  = 4
};

typedef opaque bytestring16[16];
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;
 default:
   void;   /* error condition */
}; 

union ots_private_key switch (ots_algorithm_type type) {
 case lmots_sha256_n32_w1:
 case lmots_sha256_n32_w2:
 case lmots_sha256_n32_w4:
 case lmots_sha256_n32_w8:
      bytestring32 x32;
 default:
   void;   /* error condition */
};

/* hash based signatures (hbs) */ 

enum hbs_algorithm_type {
  hbs_reserved       = 0,
  lms_sha256_n32_h20 = 1,
  lms_sha256_n32_h10 = 2,
  lms_sha256_n32_h5  = 3,
};

/* leighton mical signatures (lms) */

union lms_path switch (hbs_algorithm_type type) {
 case lms_sha256_n32_h20:
   bytestring32 path_n32_h20[20]; 
case lms_sha256_n32_h15:
   bytestring32 path_n32_h15[15]; 
 case lms_sha256_n32_h10:
   bytestring32 path_n32_h10[10];
 case lms_sha256_n32_h5:
   bytestring32 path_n32_h5[5];
 default:
   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[64];                    
  opaque K[32];                
};    

union hbs_public_key switch (hbs_algorithm_type type) {
 case lms_sha256_n32_h20:
 case lms_sha256_n32_h10:
 case lms_sha256_n32_h5:
      lms_key_n32 z_n32;
 default:
   void;     /* error condition */
};

/* hierarchical signature system (hss)  */

struct hss_public_key {
  unsigned int levels;
  hbs_public_key pub;
};

struct signed_public_key {
  hbs_signature sig;
  hbs_public_key pub;
}

struct hss_signature {
  signed_public_key signed_keys<L-1>;
  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 and LMS 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 required to be distinct in order to improve security. That distinctness ensures the uniqueness of the inputs to H across all of those public/private key pair instances, which is important for provable security in the random oracle model. The length of I is set at 31 or 64 bytes so that randomly chosen values of I will be distinct with probability at least 1 - 1/2^128 as long as there are 2^60 or fewer instances of LMS public/private key pairs.

The sizes of the parameters in the security string are such that, for n=16, the LM-OTS iterates a 55-byte value (that is, the string that is input to H() during the iteration over j during signature generation and verification is 55 bytes long). Thus, when SHA-256 is used as the function H, only a single invocation of its compression function is needed.

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

A future version of this specification may support hash functions other than SHA-256.

9. History

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

Version 04

• Specified that, in the HSS method, the I value was computed from the I value of the parent LM tree. Previous versions had the I value extracted from the public key (which meant that all LM trees of a particular level and public key used the same I value)
• Changed the length of the I field based on the parameter set. As noted in the Rationale section, this allows an implemetation to compute N=32 based parameter sets significantly faster.
• Modified the XDR of an HSS signature not to use an array of LM signatures; LM signatures are variable length, and XDR doesn't support arrays of variable length structures.
• Changed the LMS registry to be in a consistent order with the LM-OTS paramter sets. Also, added LMS parameter sets with height 15 trees

Previous versions

• In Algorithms 3 and 4, the message was moved from the initial position of the input to the function H to the final position, in the computation of the intermediate variable Q. This was done to improve security by preventing an attacker that can find a collision in H from taking advantage of that fact via the forward chaining property of Merkle-Damgard.
• The Hierarchical Signature Scheme was generalized slightly so that it can use more than two levels.
• Several points of confusion were corrected; these had resulted from incomplete or inconsistent changes from the Merkle approach of the earlier draft to the Leighton-Micali approach.

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:

• a short name, such as "LMS_SHA256_N32_H10",
• a positive number, 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.

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 cfrg@ietf.org. Interested applicants that are unfamiliar with IANA processes should visit http://www.iana.org.

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.

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

x_q[j] = / H(I || u32str(q) || SEED || u16str(j) || D_PRG)     if j = 0,
         \ H(I || u32str(q) || x_q[j-1] || u16str(j) || D_PRG) otherwise

  u = ceil(8*n/w)
  v = ceil((floor(lg((2^w - 1) * u)) + 1) / w)
  ls = (number of bits in sum) - (v * w)
  p = u + v

  for ( i = 0; i < num_lmots_keys; i = i + 2 ) {
    level = 0;
    for ( j = 0; j < 2; j = j + 1 ) {
      r = node_num 
      push H(I || OTS_PUBKEY[i+j] || u32str(r) || D_LEAF) on data stack
      push level onto the integer stack
    }
    while ( height of the integer stack >= 2 ) {
      if level of the top 2 elements on the integer stack are equal {
        hash_init()
        siblings = ""
        repeat ( 2 ) {
          siblings = (pop(data stack) || siblings)
          level = pop(integer stack)
        }
        hash_update(siblings)
        r = node_num 
        hash_update(I || u32str(r) || D_INTR)
        push hash_final() onto the data stack
        push (level + 1) onto the integer stack
      }
    }
  }
  public_key = pop(data stack)

     --- Pending Revision ---