RFC 8554
Leighton-Micali Hash-Based Signatures
7. Rationale
The goal of this note is to describe the LM-OTS, LMS, and HSS algorithms following the original references and present the modern security analysis of those algorithms. Other signature methods are out of scope and may be interesting follow-on work. We adopt the techniques described by Leighton and Micali to mitigate attacks that amortize their work over multiple invocations of the hash function. The values taken by the identifier I across different LMS public/ private key pairs are chosen randomly in order to improve security. The analysis of this method in [Fluhrer17] shows that we do not need uniqueness to ensure security; we do need to ensure that we don't have a large number of private keys that use the same I value. By randomly selecting 16-byte I values, the chance that, out of 2^64 private keys, 4 or more of them will use the same I value is negligible (that is, has probability less than 2^-128). The reason 16-byte I values were selected was to optimize the Winternitz hash-chain operation. With the current settings, the value being hashed is exactly 55 bytes long (for a 32-byte hash function), which SHA-256 can hash in a single hash-compression operation. Other hash functions may be used in future specifications; all the ones that we will be likely to support (SHA-512/256 and the various SHA-3 hashes) would work well with a 16-byte I value. The signature and public key formats are designed so that they are relatively easy to parse. Each format starts with a 32-bit enumeration value that indicates the details of the signature algorithm and provides all of the information that is needed in order to parse the format.
The Checksum (Section 4.4) is calculated using a nonnegative integer "sum" whose width was chosen to be an integer number of w-bit fields such that it is capable of holding the difference of the total possible number of applications of the function H (as defined in the signing algorithm of Section 4.5) and the total actual number. In the case that the number of times H is applied is 0, the sum is (2^w - 1) * (8*n/w). Thus, for the purposes of this document, which describes signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 4, 8 }, the sum variable is a 16-bit nonnegative integer for all combinations of n and w. The calculation uses the parameter ls defined in Section 4.1 and calculated in Appendix B, which indicates the number of bits used in the left-shift operation.7.1. Security String
To improve security against attacks that amortize their effort against multiple invocations of the hash function, Leighton and Micali introduced a "security string" that is distinct for each invocation of that function. Whenever this process computes a hash, the string being hashed will start with a string formed from the fields below. These fields will appear in fixed locations in the value we compute the hash of, and so we list where in the hash these fields would be present. The fields that make up this string are as follows: I A 16-byte identifier for the LMS public/private key pair. It MUST be chosen uniformly at random, or via a pseudorandom process, at the time that a key pair is generated, in order to minimize the probability that any specific value of I be used for a large number of different LMS private keys. This is always bytes 0-15 of the value being hashed. r In the LMS N-time signature scheme, the node number r associated with a particular node of a hash tree is used as an input to the hash used to compute that node. This value is represented as a 32-bit (four byte) unsigned integer in network byte order. Either r or q (depending on the domain-separation parameter) will be bytes 16-19 of the value being hashed. q In the LMS N-time signature scheme, each LM-OTS signature is associated with the leaf of a hash tree, and q is set to the leaf number. This ensures that a distinct value of q is used for each distinct LM-OTS public/private key pair. This value is represented as a 32-bit (four byte) unsigned integer in network byte order. Either r or q (depending on the domain- separation parameter) will be bytes 16-19 of the value being hashed.
D A domain-separation parameter, which is a two-byte identifier
that takes on different values in the different contexts in
which the hash function is invoked. D occurs in bytes 20 and
21 of the value being hashed and takes on the following values:
D_PBLC = 0x8080 when computing the hash of all of the
iterates in the LM-OTS algorithm
D_MESG = 0x8181 when computing the hash of the message in
the LM-OTS algorithms
D_LEAF = 0x8282 when computing the hash of the leaf of an
LMS tree
D_INTR = 0x8383 when computing the hash of an interior node
of an LMS tree
i A value between 0 and 264; this is used in the LM-OTS scheme
when either computing the iterations of the Winternitz chain or
using the suggested LM-OTS private key generation process. It
is represented as a 16-bit (two-byte) unsigned integer in
network byte order. If present, it occurs at bytes 20 and 21
of the value being hashed.
j In the LM-OTS scheme, j is the iteration number used when the
private key element is being iteratively hashed. It is
represented as an 8-bit (one byte) unsigned integer and is
present if i is a value between 0 and 264. If present, it
occurs at bytes 22 to 21+n of the value being hashed.
C An n-byte randomizer that is included with the message whenever
it is being hashed to improve security. C MUST be chosen
uniformly at random or via another unpredictable process. It
is present if D=D_MESG, and it occurs at bytes 22 to 21+n of
the value being hashed.
8. IANA Considerations
IANA has created two registries: "LM-OTS Signatures", which includes
all of the LM-OTS signatures as defined in Section 4, and "Leighton-
Micali Signatures (LMS)" for LMS as defined in Section 5.
Additions to these registries require that a specification be
documented in an RFC or another permanent and readily available
reference in sufficient detail that interoperability between
independent implementations is possible [RFC8126]. IANA MUST verify
that all applications for additions to these registries have first
been reviewed by the IRTF Crypto Forum Research Group (CFRG).
Each entry in either of the registries contains the following
elements:
a short name (Name), such as "LMS_SHA256_M32_H10",
a positive number (Numeric Identifier), and
a Reference to a specification that completely defines the
signature-method test cases that can be used to verify the
correctness of an implementation.
The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF
(decimal 4,294,967,295), inclusive, will not be assigned by IANA and
are reserved for private use; no attempt will be made to prevent
multiple sites from using the same value in different (and
incompatible) ways [RFC8126].
The initial contents of the "LM-OTS Signatures" registry are as
follows.
+--------------------------+-----------+--------------------------+
| Name | Reference | Numeric Identifier |
+--------------------------+-----------+--------------------------+
| Reserved | | 0x00000000 |
| | | |
| LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 |
| | | |
| LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 |
| | | |
| LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 |
| | | |
| LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 |
| | | |
| Unassigned | | 0x00000005 - 0xDDDDDDDC |
| | | |
| Reserved for Private Use | | 0xDDDDDDDD - 0xFFFFFFFF |
+--------------------------+-----------+--------------------------+
Table 4
The initial contents of the "Leighton Micali Signatures (LMS)" registry are as follows. +--------------------------+-----------+--------------------------+ | Name | Reference | Numeric Identifier | +--------------------------+-----------+--------------------------+ | Reserved | | 0x0 - 0x4 | | | | | | LMS_SHA256_M32_H5 | Section 5 | 0x00000005 | | | | | | LMS_SHA256_M32_H10 | Section 5 | 0x00000006 | | | | | | LMS_SHA256_M32_H15 | Section 5 | 0x00000007 | | | | | | LMS_SHA256_M32_H20 | Section 5 | 0x00000008 | | | | | | LMS_SHA256_M32_H25 | Section 5 | 0x00000009 | | | | | | Unassigned | | 0x0000000A - 0xDDDDDDDC | | | | | | Reserved for Private Use | | 0xDDDDDDDD - 0xFFFFFFFF | +--------------------------+-----------+--------------------------+ Table 5 An IANA registration of a signature system does not constitute an endorsement of that system or its security. Currently, the two registries assign a disjoint set of values to the defined parameter sets. This coincidence is a historical accident; the correctness of the system does not depend on this. IANA is not required to maintain this situation.9. Security Considerations
The hash function H MUST have second preimage resistance: it must be computationally infeasible for an attacker that is given one message M to be able to find a second message M' such that H(M) = H(M'). The security goal of a signature system is to prevent forgeries. A successful forgery occurs when an attacker who does not know the private key associated with a public key can find a message (distinct from all previously signed ones) and signature that is valid with that public key (that is, the Signature Verification algorithm applied to that signature and message and public key will return VALID). Such an attacker, in the strongest case, may have the ability to forge valid signatures for an arbitrary number of other messages.
LMS is provably secure in the random oracle model, as shown by [Katz16]. In addition, further analysis is done by [Fluhrer17], where the hash compression function (rather than the entire hash function) is considered to be a random oracle. Corollary 1 of the latter paper states: If we have no more than 2^64 randomly chosen LMS private keys, allow the attacker access to a signing oracle and a SHA-256 hash compression oracle, and allow a maximum of 2^120 hash compression computations, then the probability of an attacker being able to generate a single forgery against any of those LMS keys is less than 2^-129. Many of the objects within the public key and the signature start with a typecode. A verifier MUST check each of these typecodes, and a verification operation on a signature with an unknown type, or a type that does not correspond to the type within the public key, MUST return INVALID. The expected length of a variable-length object can be determined from its typecode; if an object has a different length, then any signature computed from the object is INVALID.9.1. Hash Formats
The format of the inputs to the hash function H has the property that each invocation of that function has an input that is repeated by a small bounded number of other inputs (due to potential repeats of the I value). In particular, it will vary somewhere in the first 23 bytes of the value being hashed. This property is important for a proof of security in the random oracle model. The formats used during key generation and signing (including the recommended pseudorandom key-generation procedure in Appendix A) are as follows: I || u32str(q) || u16str(i) || u8str(j) || tmp I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1] I || u32str(q) || u16str(D_MESG) || C || message I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h] I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1] I || u32str(q) || u16str(i) || u8str(0xff) || SEED Each hash type listed is distinct; at locations 20 and 21 of the value being hashed, there exists either a fixed value D_PBLC, D_MESG, D_LEAF, D_INTR, or a 16-bit value i. These fixed values are distinct from each other and are large (over 32768), while the 16-bit values of i are small (currently no more than 265; possibly being slightly larger if larger hash functions are supported); hence, the range of possible values of i will not collide any of the D_PBLC, D_MESG,
D_LEAF, D_INTR identifiers. The only other collision possibility is the Winternitz chain hash colliding with the recommended pseudorandom key-generation process; here, at location 22 of the value being hashed, the Winternitz chain function has the value u8str(j), where j is a value between 0 and 254, while location 22 of the recommended pseudorandom key-generation process has value 255. For the Winternitz chaining function, D_PBLC, and D_MESG, the value of I || u32str(q) is distinct for each LMS leaf (or equivalently, for each q value). For the Winternitz chaining function, the value of u16str(i) || u8str(j) is distinct for each invocation of H for a given leaf. For D_PBLC and D_MESG, the input format is used only once for each value of q and, thus, distinctness is assured. The formats for D_INTR and D_LEAF are used exactly once for each value of r, which ensures their distinctness. For the recommended pseudorandom key-generation process, for a given value of I, q and j are distinct for each invocation of H. The value of I is chosen uniformly at random from the set of all 128-bit strings. If 2^64 public keys are generated (and, hence, 2^64 random I values), there is a nontrivial probability of a duplicate (which would imply duplicate prefixes). However, there will be an extremely high probability there will not be a four-way collision (that is, any I value used for four distinct LMS keys; probability < 2^-132), and, hence, the number of repeats for any specific prefix will be limited to at most three. This is shown (in [Fluhrer17]) to have only a limited effect on the security of the system.9.2. Stateful Signature Algorithm
The LMS signature system, like all N-time signature systems, requires that the signer maintain state across different invocations of the signing algorithm to ensure that none of the component one-time signature systems are used more than once. This section calls out some important practical considerations around this statefulness. These issues are discussed in greater detail in [STMGMT]. In a typical computing environment, a private key will be stored in nonvolatile media such as on a hard drive. Before it is used to sign a message, it will be read into an application's Random-Access Memory (RAM). After a signature is generated, the value of the private key will need to be updated by writing the new value of the private key into nonvolatile storage. It is essential for security that the application ensures that this value is actually written into that storage, yet there may be one or more memory caches between it and the application. Memory caching is commonly done in the file system and in a physical memory unit on the hard disk that is dedicated to that purpose. To ensure that the updated value is written to
physical media, the application may need to take several special steps. In a POSIX environment, for instance, the O_SYNC flag (for the open() system call) will cause invocations of the write() system call to block the calling process until the data has been written to the underlying hardware. However, if that hardware has its own memory cache, it must be separately dealt with using an operating system or device-specific tool such as hdparm to flush the on-drive cache or turn off write caching for that drive. Because these details vary across different operating systems and devices, this note does not attempt to provide complete guidance; instead, we call the implementer's attention to these issues. When hierarchical signatures are used, an easy way to minimize the private key synchronization issues is to have the private key for the second-level resident in RAM only and never write that value into nonvolatile memory. A new second-level public/private key pair will be generated whenever the application (re)starts; thus, failures such as a power outage or application crash are automatically accommodated. Implementations SHOULD use this approach wherever possible.9.3. Security of LM-OTS Checksum
To show the security of LM-OTS checksum, we consider the signature y of a message with a private key x and let h = H(message) and c = Cksm(H(message)) (see Section 4.5). To attempt a forgery, an attacker may try to change the values of h and c. Let h' and c' denote the values used in the forgery attempt. If for some integer j in the range 0 to u, where u = ceil(8*n/w) is the size of the range that the checksum value can cover, inclusive, a' = coef(h', j, w), a = coef(h, j, w), and a' > a
then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by
iteratively applying function F to the j-th term of the signature an
additional (a' - a) times. However, as a result of the increased
number of hashing iterations, the checksum value c' will decrease
from its original value of c. Thus, a valid signature's checksum
will have, for some number k in the range u to (p-1), inclusive,
b' = coef(c', k, w),
b = coef(c, k, w), and
b' < b
Due to the one-way property of F, the attacker cannot easily compute
F^b'(x[k]) from F^b(x[k]) = y[k].
10. Comparison with Other Work
The eXtended Merkle Signature Scheme (XMSS) is similar to HSS in
several ways [XMSS][RFC8391]. Both are stateful hash-based signature
schemes, and both use a hierarchical approach, with a Merkle tree at
each level of the hierarchy. XMSS signatures are slightly shorter
than HSS signatures, for equivalent security and an equal number of
signatures.
HSS has several advantages over XMSS. HSS operations are roughly
four times faster than the comparable XMSS ones, when SHA256 is used
as the underlying hash. This occurs because the hash operation done
as a part of the Winternitz iterations dominates performance, and
XMSS performs four compression-function invocations (two for the PRF,
two for the F function) where HSS only needs to perform one.
Additionally, HSS is somewhat simpler (as each hash invocation is
just a prefix followed by the data being hashed).
11. References
11.1. Normative References
[FIPS180] National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS PUB 180-4, DOI 10.6028/NIST.FIPS.180-4, March 2012. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>. [RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, <https://www.rfc-editor.org/info/rfc4506>. [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, <https://www.rfc-editor.org/info/rfc8126>. [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>. [RFC8179] Bradner, S. and J. Contreras, "Intellectual Property Rights in IETF Technology", BCP 79, RFC 8179, DOI 10.17487/RFC8179, May 2017, <https://www.rfc-editor.org/info/rfc8179>. [USPTO5432852] Leighton, T. and S. Micali, "Large provably fast and secure digital signature schemes based on secure hash functions", U.S. Patent 5,432,852, July 1995.11.2. Informative References
[C:Merkle87] Merkle, R., "A Digital Signature Based on a Conventional Encryption Function", in Advances in Cryptology -- CRYPTO '87 Proceedings, Lecture Notes in Computer Science Vol. 293, DOI 10.1007/3-540-48184-2_32, 1988.
[C:Merkle89a] Merkle, R., "A Certified Digital Signature", in Advances in Cryptology -- CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, DOI 10.1007/0-387-34805-0_21, 1990. [C:Merkle89b] Merkle, R., "One Way Hash Functions and DES", in Advances in Cryptology -- CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, DOI 10.1007/0-387-34805-0_40, 1990. [Fluhrer17] Fluhrer, S., "Further Analysis of a Proposed Hash-Based Signature Standard", Cryptology ePrint Archive Report 2017/553, 2017, <https://eprint.iacr.org/2017/553>. [Katz16] Katz, J., "Analysis of a Proposed Hash-Based Signature Standard", in SSR 2016: Security Standardisation Research (SSR) pp. 261-273, Lecture Notes in Computer Science Vol. 10074, DOI 10.1007/978-3-319-49100-4_12, 2016. [Merkle79] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Technical Report No. 1979-1, Information Systems Laboratory, Stanford University, 1979, <http://www.merkle.com/papers/Thesis1979.pdf>. [RFC8391] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, May 2018, <https://www.rfc-editor.org/info/rfc8391>. [STMGMT] McGrew, D., Kampanakis, P., Fluhrer, S., Gazdag, S., Butin, D., and J. Buchmann, "State Management for Hash- Based Signatures.", in SSR 2016: Security Standardisation Research (SSR) pp. 244-260, Lecture Notes in Computer Science Vol. 10074, DOI 10.1007/978-3-319-49100-4_11, 2016. [XMSS] Buchmann, J., Dahmen, E., and , "XMSS -- A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions.", in PQCrypto 2011: Post-Quantum Cryptography pp. 117-129, Lecture Notes in Computer Science Vol. 7071, DOI 10.1007/978-3-642-25405-5_8, 2011.
(next page on part 4)
