RFC 8554
Leighton-Micali Hash-Based Signatures
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).
+--------------------+--------+----+----+ | 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 25.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.
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.
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.
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.
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
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
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.
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.
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.
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.
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.
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]
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,
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.
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.
(page 34 continued on part 3)
