RFC 8554
Leighton-Micali Hash-Based Signatures
Leighton-Micali Hash-Based Signatures 🎀
- Stream: Internet Research Task Force (IRTF) 🌈
- Request for Comments: 8554
- Authors: D. McGrew, M. Curcio, S. Fluhrer (all from Cisco Systems) 💜
- Category: Informational 📚
- ISSN: 2070-1721
- Date: April 2019 🗓️
- Obsoletes / Updates: This header doesn't list anything it obsoletes or updates 🧚
Abstract
okay bestie, this note describes a digital-signature system built on cryptographic hash functions 🔥. It follows the seminal work 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 💅. The big deal is that these systems give you asymmetric authentication without any large integer mathematics, and they can hit a high security level 😭. They're compact, relatively simple to implement, and naturally resistant to side-channel attacks 🫶. And here's the iconic part: unlike a lot of other signature systems, hash-based signatures would still be secure even if an attacker managed to build a quantum computer 👑.
This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF 🌸. It's been reviewed by lots of researchers, both inside the research group and outside it, and the Acknowledgements section lists many of them 💖.
Status of This Memo
This document is not an Internet Standards Track specification. It's published for informational purposes 📖.
It's a product of the Internet Research Task Force (IRTF), which publishes the results of Internet-related research and development activities 🔬. These results might not be suitable for deployment, so read that part carefully ⚠️. This RFC represents the consensus of the Crypto Forum Research Group of the IRTF. Documents approved for publication by the IRSG are not candidates for any level of Internet Standard, see Section 2 of RFC 7841 🦋.
For the current status of this document, any errata, and how to give feedback on it, head to https://www.rfc-editor.org/info/rfc8554 🧚.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved 💜.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication. Please review those documents carefully, because they describe your rights and restrictions with respect to this document 🙈.
Table of Contents 🍓
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. CFRG Note on Post-Quantum Cryptography . . . . . . . . . 5
1.2. Intellectual Property . . . . . . . . . . . . . . . . . . 6
1.2.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . 6
1.3. Conventions Used in This Document . . . . . . . . . . . . 6
2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 7
3.1.2. Functions . . . . . . . . . . . . . . . . . . . . . . 8
3.1.3. Strings of w-Bit Elements . . . . . . . . . . . . . . 8
3.2. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3. Notation and Formats . . . . . . . . . . . . . . . . . . 9
4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 12
4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 13
4.2. Private Key . . . . . . . . . . . . . . . . . . . . . . . 14
4.3. Public Key . . . . . . . . . . . . . . . . . . . . . . . 15
4.4. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 15
4.5. Signature Generation . . . . . . . . . . . . . . . . . . 16
4.6. Signature Verification . . . . . . . . . . . . . . . . . 17
5. Leighton-Micali Signatures . . . . . . . . . . . . . . . . . 19
5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 19
5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 20
5.3. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 21
5.4. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 22
5.4.1. LMS Signature Generation . . . . . . . . . . . . . . 23
5.4.2. LMS Signature Verification . . . . . . . . . . . . . 24
6. Hierarchical Signatures . . . . . . . . . . . . . . . . . . . 26
6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 29
6.2. Signature Generation . . . . . . . . . . . . . . . . . . 30
6.3. Signature Verification . . . . . . . . . . . . . . . . . 32
6.4. Parameter Set Recommendations . . . . . . . . . . . . . . 32
7. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.1. Security String . . . . . . . . . . . . . . . . . . . . . 35
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36
9. Security Considerations . . . . . . . . . . . . . . . . . . . 38
9.1. Hash Formats . . . . . . . . . . . . . . . . . . . . . . 39
9.2. Stateful Signature Algorithm . . . . . . . . . . . . . . 40
9.3. Security of LM-OTS Checksum . . . . . . . . . . . . . . . 41
10. Comparison with Other Work . . . . . . . . . . . . . . . . . 42
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 43
11.1. Normative References . . . . . . . . . . . . . . . . . . 43
11.2. Informative References . . . . . . . . . . . . . . . . . 43
Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 45
Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 45
Appendix C. An Iterative Algorithm for Computing an LMS Public
Key . . . . . . . . . . . . . . . . . . . . . . . . 47
Appendix D. Method for Deriving Authentication Path for a
Signature . . . . . . . . . . . . . . . . . . . . . 48
Appendix E. Example Implementation . . . . . . . . . . . . . . . 49
Appendix F. Test Cases . . . . . . . . . . . . . . . . . . . . . 49
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 60
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 611. Introduction ✨
okay so one-time signature systems, and general-purpose signature systems built out of them, have been around since 1979 [Merkle79] 🕰️. They were well studied in the 1990s [USPTO5432852] and got renewed attention in the last decade 📈. The vibe of these systems is: small private and public keys, fast signature generation and verification 💨, but large signatures and moderately slow key generation (compared to RSA and ECDSA (Elliptic Curve Digital Signature Algorithm)) 🐢. Private keys can be made super small with the right key generation, like the approach in Appendix A 🤏. Lately everyone's obsessed with them because of their post-quantum security and how well they suit 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 their general signature system [Merkle79]. It goes into enough detail to make sure implementations can actually talk to each other 🫶💖.
Here's the basic idea 💅. A signature system gives you asymmetric message authentication. The key-generation algorithm makes a public/private key pair 🗝️. You sign a message with the private key to get a signature, and then anyone with the public key can verify that message/signature pair ✅. A One-Time Signature (OTS) system can sign one message securely, but it becomes insecure if you sign more than one message with the same public/private key pair 💀. An N-time signature system can sign N messages (or fewer) securely 🔥. A Merkle-tree signature scheme is an N-time signature system that uses an OTS system as one of its components 🌳.
In the Merkle scheme, a binary tree of height h holds 2^h OTS key pairs 🌲. Every interior node holds the hash of the values of its two child nodes 🧩. The public key of the tree is the value of the root node (a recursive hash of the OTS public keys) 👑. The private key of the tree is the collection of all the OTS private keys, plus the index of the next OTS private key to sign the next message with 🔑. Keep that index safe, bestie, it's literally the main character of the whole thing 🙈.
Now here's where it gets iconic 🦋. In this note we describe the Leighton-Micali Signature (LMS) system, which is a variant of the Merkle scheme, along with the Hierarchical Signature System (HSS) built on top of it. HSS lets it scale efficiently to larger numbers of signatures 📈. To sign a big pile of messages on resource-constrained systems, the Merkle tree can be split into a bunch of smaller trees 🧸. Only the bottommost tree is used to sign messages, and the trees above it are used to sign the public keys of their children 🪜.
Let's do an example 🧁. Take the simplest case, two levels, where both levels are height h trees. The root tree signs 2^h trees, each with 2^h OTS key pairs. Each second-level tree has 2^h OTS key pairs too, so you get a total of 2^(2h) bottom-level key pairs, and the whole thing can sign 2^(2h) messages 🤯. The perk is that only the active trees need to be instantiated, which saves both time (for key generation) and space (for key storage) 💜. The tradeoff? A multilevel signature scheme makes the signature bigger and makes verification take longer 🐌.
Here's how the rest of this note is laid out 🗺️. Notes on post-quantum cryptography are in Section 1.1, and intellectual property issues are in Section 1.2 💫. The notation is defined in Section 3, and the public formats are described in Section 3.3 📐. The Leighton-Micali One-Time Signature (LM-OTS) system is in Section 4, and the LMS and HSS N-time signature systems are in Sections 5 and 6 respectively 🎀. There's enough detail to make sure things interoperate 🤝. The rationale for the design decisions is in Section 7, the IANA registry for these signature systems is in Section 8, and security considerations are in Section 9 🛡️. Comparison with another hash-based signature algorithm, the eXtended Merkle Signature Scheme (XMSS), is in Section 10 🌸.
This document represents the rough consensus of the CFRG 🫶✨.
1.1. CFRG Note on Post-Quantum Cryptography
okay so the CFRG (Crypto Forum Research Group) says all their post-quantum algorithms are ready for experimenting and more engineering 🧪✨. the goal is to figure out how the performance and sizes affect IETF protocols. but ngl, we don't have much real-world deployment experience with them yet 🙈
a lot of these algorithms come with specific restrictions 💀. for example, they might need a change to the classical interface, or their proposed parameters have gotten less cryptanalysis than established schemes. the CFRG agreed that every document about post-quantum tech should include the paragraph above, plus a clear extra warning about any specific restrictions. that's especially important if the restrictions could affect how the scheme gets used or deployed 📣. this guidance can change over time through document updates 🔄
now for LMS specifically 🌈
the CFRG consensus is that they're confident in the cryptographic security of the signature schemes in this document against quantum computers, based on what the research community currently knows about quantum algorithms 🛡️. honestly, they're confident that a big chunk of the Internet could depend on these signature schemes, as long as developers take care of the following 🫶
here's the plot twist 😭. unlike traditional signature schemes, these ones are stateful, which means the secret key changes over time 🔑. if a secret key state gets used twice, there are no cryptographic security guarantees left. that means it becomes feasible to forge a signature on a new message 💀. this is a brand new property that most developers won't be familiar with, so the secret keys need really careful handling 🧐. developers should not use the schemes described here, except in systems that prevent the reuse of secret key states.
Heads up: because these schemes are stateful, classical digital signature APIs can't be used without modification 🚨.
the API MUST be able to handle a dynamic secret key state. in other words, the API MUST allow the signature-generation algorithm to update the secret key state 🔄✨.
1.2. Intellectual Property
this document is based on U.S. Patent 5,432,852, which was issued over twenty years ago, so it's expired now 🎉.
1.2.1. Disclaimer
this document is not legal advice, so if you want a legal interpretation of your rights, please talk to your own legal advisers 🧑⚖️.
the IETF's policies and processes about intellectual property and patents are outlined in [RFC8179] and at <https://datatracker.ietf.org/ipr/about> 📚.
1.3. Conventions Used in This Document
the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🎀.
2. Interface 🔌
the LMS signing algorithm is stateful 🧠. it modifies and updates the private key as a side effect of generating a signature. once a particular value of the private key has been used to sign one message, it MUST NOT be used to sign another 🚫.
the key-generation algorithm takes an indication of the parameters for the signature system as input. if it succeeds, it returns both a private key and a public key 🗝️. otherwise, it returns an indication of failure 😩.
the signing algorithm takes the message to be signed and the current value of the private key as input. if it succeeds, it returns a signature and the next value of the private key, if there is one 📝. after the private key of an N-time signature system has signed N messages, the signing algorithm returns the signature plus an indication that there's no next value of the private key that can be used for signing 🏁. if it fails, it returns an indication of failure 💔.
the verification algorithm takes the public key, a message, and a signature as input. it returns an indication of whether or not the signature-and-message pair is valid ✅.
a message/signature pair is valid if the signature was returned by the signing algorithm on input of the message and the private key corresponding to the public key. otherwise, the signature and message pair is not valid, with a probability very close to one 🙃.
3. Notation ✍️
3.1. Data Types 🍓
bytes and byte strings are the fundamental data types 💜. a single byte is written as a pair of hexadecimal digits with a leading 0x. a byte string is an ordered sequence of zero or more bytes, written 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, where all the 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). these take a nonnegative integer X as input and return one-, two-, and four-byte strings, respectively 🎯. we also use the function strTou32(S), which takes a four-byte string S as input and returns a nonnegative integer. the identity u32str(strTou32(S)) = S holds for any four-byte string S 🪄.
3.1.1. Operators 🧮
when a and b are real numbers, the mathematical operators are defined like this 💖:
^: a ^ b denotes the result of a raised to the power of b*: a * b denotes the product of a multiplied by b/: a / b denotes the quotient of a divided by b%: a % b denotes the remainder of the integer division of a by b (with a and b being restricted to integers in this case)+: a + b denotes the sum of a and b-: a - b denotes the difference of a and bAND: a AND b denotes the bitwise AND of the two nonnegative integers a and b (represented in binary notation)
the standard order of operations is used when evaluating arithmetic expressions 📐.
when B is a byte and i is an integer, then B >> i denotes the logical right-shift operation by i bit positions. similarly, B << i denotes the logical left-shift operation ➡️⬅️.
if S and T are byte strings, then S || T denotes the concatenation of S and T. if S and T are equal-length byte strings, then S AND T denotes the bitwise logical AND operation 🔗.
the i-th element in an array A is denoted as A[i] 🔢.
3.1.2. Functions 🎀
if r is a nonnegative real number, then we define the following functions:
ceil(r): returns the smallest integer greater than or equal to rfloor(r): returns the largest integer less than or equal to rlg(r): returns the base-2 logarithm of r
3.1.3. Strings of w-Bit Elements 🧵
if S is a byte string, then byte(S, i) denotes its i-th byte, where the index starts at 0 from the left. so byte(S, 0) is the leftmost byte of S, byte(S, 1) is the second byte from the left, and (assuming S is n bytes long) byte(S, n-1) is the rightmost byte of S 👀. in addition, bytes(S, i, j) denotes the range of bytes from the i-th to the j-th byte, inclusive. for example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 2) is 0x0406 🌸.
a byte string can be considered 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 MUST raise an error 🚨.
3.2. Typecodes 🏷️
a typecode is an unsigned integer that's associated with a particular data format 💅. the format of the LM-OTS, LMS, and HSS signatures and public keys all begin with a typecode that indicates the precise details used in that format. these typecodes are represented as four-byte unsigned integers in network byte order. equivalently, they are External Data Representation (XDR) enumerations (see Section 3.3) 🦋.
3.3. Notation and Formats 📐✨
okay so the signature and public key formats are written in XDR, which is basically a super strict, machine-readable recipe so nobody can misread them 💅 [RFC4506]. The private key format is not included because it isn't needed for interoperability, and an implementation MAY use any private key format 🔐. For clarity though, we include an example of private key data in Test Case 2 of Appendix F. XDR is used, but these formats are honestly simple and easy to parse without any special tools 🫶. Here's the layout, and the definitions go like this:
/* one-time signatures */
enum lmots_algorithm_type {
lmots_reserved = 0,
lmots_sha256_n32_w1 = 1,
lmots_sha256_n32_w2 = 2,
lmots_sha256_n32_w4 = 3,
lmots_sha256_n32_w8 = 4
};
typedef opaque bytestring32[32];
struct lmots_signature_n32_p265 {
bytestring32 C;
bytestring32 y[265];
};
struct lmots_signature_n32_p133 {
bytestring32 C;
bytestring32 y[133];
};
struct lmots_signature_n32_p67 {
bytestring32 C;
bytestring32 y[67];
};
struct lmots_signature_n32_p34 {
bytestring32 C;
bytestring32 y[34];
};
union lmots_signature switch (lmots_algorithm_type type) {
case lmots_sha256_n32_w1:
lmots_signature_n32_p265 sig_n32_p265;
case lmots_sha256_n32_w2:
lmots_signature_n32_p133 sig_n32_p133;
case lmots_sha256_n32_w4:
lmots_signature_n32_p67 sig_n32_p67;
case lmots_sha256_n32_w8:
lmots_signature_n32_p34 sig_n32_p34;
default:
void; /* error condition */
};/* hash-based signatures (hbs) */
enum lms_algorithm_type {
lms_reserved = 0,
lms_sha256_n32_h5 = 5,
lms_sha256_n32_h10 = 6,
lms_sha256_n32_h15 = 7,
lms_sha256_n32_h20 = 8,
lms_sha256_n32_h25 = 9
};
/* leighton-micali signatures (lms) */
union lms_path switch (lms_algorithm_type type) {
case lms_sha256_n32_h5:
bytestring32 path_n32_h5[5];
case lms_sha256_n32_h10:
bytestring32 path_n32_h10[10];
case lms_sha256_n32_h15:
bytestring32 path_n32_h15[15];
case lms_sha256_n32_h20:
bytestring32 path_n32_h20[20];
case lms_sha256_n32_h25:
bytestring32 path_n32_h25[25];
default:
void; /* error condition */
};
struct lms_signature {
unsigned int q;
lmots_signature lmots_sig;
lms_path nodes;
};
struct lms_key_n32 {
lmots_algorithm_type ots_alg_type;
opaque I[16];
opaque K[32];
};
union lms_public_key switch (lms_algorithm_type type) {
case lms_sha256_n32_h5:
case lms_sha256_n32_h10:
case lms_sha256_n32_h15:
case lms_sha256_n32_h20:
case lms_sha256_n32_h25:
lms_key_n32 z_n32;
default:
void; /* error condition */
};
/* hierarchical signature system (hss) */
struct hss_public_key {
unsigned int L;
lms_public_key pub;
};
struct signed_public_key {
lms_signature sig;
lms_public_key pub;
};
struct hss_signature {
signed_public_key signed_keys<7>;
lms_signature sig_of_message;
};4. LM-OTS One-Time Signatures 🦋
this section defines LM-OTS signatures 🔏. The signature is used to validate the authenticity of a message by associating a secret private key with a shared public key. These are one-time signatures, so 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.
so to make this work in an N-time signature system, the LM-OTS key generation, signing, and verification algorithms all take I and q as input parameters 🧩. I is a 16-byte string that indicates which Merkle tree this LM-OTS is used with. q is a 32-bit integer that indicates the leaf of the Merkle tree where the OTS public key appears. These parameters are used as part of the security string, as listed in Section 7.1. When the LM-OTS signature system is used outside of an N-time signature system, I MAY be used to differentiate this one-time signature from others; however, q MUST 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 depend on n and w. These parameters are summarized as follows:
n: the number of bytes of the output of the hash function.w: the width (in bits) of the Winternitz coefficients; that is, the number of bits from the hash or checksum that is used with a single Winternitz chain. It is a member of the set { 1, 2, 4, 8 }.p: the number of n-byte string elements that make up the LM-OTS signature. This is a function of n and w; the values for the defined parameter sets are listed in Table 1; it can also be computed by the algorithm given in Appendix B.ls: the number of left-shift bits used in the checksum function Cksm (defined in Section 4.4).H: a second-preimage-resistant cryptographic hash function that accepts byte strings of any length and returns an n-byte string.
For more background on the cryptographic security requirements for H, see Section 9 🔐.
the value of n is determined by the hash function selected for use as part of the LM-OTS algorithm, and this choice 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 depend on the choices of the parameters n and w, as described in Appendix B. Table 1 illustrates various combinations of n, w, p and ls, along with the resulting signature length 📊.
The value of w describes a space/time trade-off ⚖️. Increasing the value of w will cause the signature to shrink (by decreasing the value of p) while increasing the amount of time needed to perform operations with it: generating the public key and generating and verifying the signature. In general, the LM-OTS signature is 4+n*(p+1) bytes long, and public key generation will take p*(2^w - 1) + 1 hash computations (and signature generation and verification will take approximately half that on average) ⏱️.
+---------------------+--------+----+---+-----+----+---------+
| Parameter Set Name | H | n | w | p | ls | sig_len |
+---------------------+--------+----+---+-----+----+---------+
| LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 8516 |
| | | | | | | |
| LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 4292 |
| | | | | | | |
| LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 2180 |
| | | | | | | |
| LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 1124 |
+---------------------+--------+----+---+-----+----+---------+
Table 1Here SHA256 denotes the SHA-256 hash function defined in NIST standard [FIPS180].
4.2. Private Key 🗝️
The format of the LM-OTS private key is an internal matter to the implementation, and this document does not attempt to define it. One possibility is that the private key may consist of a typecode indicating the particular LM-OTS algorithm, an array x[] containing p n-byte strings, and the 16-byte string I and the 4-byte string q. This private key MUST be used to sign (at most) one message 🚫. The following algorithm shows pseudocode for generating a private key.
Algorithm 0: Generating a Private Key
1. Retrieve the values of q and I (the 16-byte identifier of the
LMS public/private key pair) from the LMS tree that this LM-OTS
private key will be used with
2. Set type to the typecode of the algorithm
3. Set n and p according to the typecode and Table 1
4. Compute the array x as follows:
for ( i = 0; i < p; i = i + 1 ) {
set x[i] to a uniformly random n-byte string
}
5. Return u32str(type) || I || u32str(q) || x[0] || x[1] || ...
|| x[p-1]An implementation MAY use a pseudorandom method to compute x[i], as suggested in [Merkle79], page 46. The details of the pseudorandom method do not affect interoperability, but the cryptographic strength MUST match that of the LM-OTS algorithm 💖. Appendix A provides an example of a pseudorandom method for computing the LM-OTS private key.
4.3. Public Key 🔑
The LM-OTS public key is generated from the private key by iteratively applying the function H to each individual element of x, for 2^w - 1 iterations, then hashing all of the resulting values 🌀.
The public key is generated from the private key using the following algorithm, or any equivalent process.
Algorithm 1: Generating a One-Time Signature Public Key From a Private Key
1. Set type to the typecode of the algorithm
2. Set the integers n, p, and w according to the typecode and
Table 1
3. Determine x, I, and q from the private key
4. Compute the string K as follows:
for ( i = 0; i < p; i = i + 1 ) {
tmp = x[i]
for ( j = 0; j < 2^w - 1; j = j + 1 ) {
tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
}
y[i] = tmp
}
K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])
5. Return u32str(type) || I || u32str(q) || Kwhere D_PBLC is the fixed two-byte value 0x8080, which is used to distinguish the last hash from every other hash in this system 🧁.
The public key is the value returned by Algorithm 1 ✨.
4.4. Checksum 🧮
A checksum is used to ensure that any forgery attempt that manipulates the elements of an existing signature will be detected 🕵️♀️. This checksum is needed because an attacker can freely advance any of the Winternitz chains. That is, if this checksum were not present, then an attacker who could find a hash that has every digit larger than the valid hash could replace it (and adjust the Winternitz chains) 😤. The security property that the checksum provides is detailed in Section 9. The checksum function Cksm is defined as follows, where S denotes the n-byte string that is input to that function, and the value sum is a 16-bit unsigned integer:
Algorithm 2: Checksum Calculation
sum = 0
for ( i = 0; i < (n*8/w); i = i + 1 ) {
sum = sum + (2^w - 1) - coef(S, i, w)
}
return (sum << ls)ls is the parameter that shifts the significant bits of the checksum into the positions that will actually be used by the coef function when encoding the digits of the checksum. The actual ls parameter is a function of the n and w parameters; the values for the currently defined parameter sets are shown in Table 1. It is calculated by the algorithm given in Appendix B.
Because of the left-shift operation, the rightmost bits of the result of Cksm will often be zeros. Due to the value of p, these bits will not be used during signature generation or verification 🌷.
4.5. Signature Generation 💅
okay so making an LM-OTS signature is a whole mood 🦋 You go in order: stick the LMS key identifier I, the LMS leaf identifier q, the value D_MESG (0x8181), and the randomizer C onto the front of the message, then hash the whole thing. Next you tack the checksum of that hash onto the hash itself and read the result as a bunch of w-bit values. Each value tells you how many times to run H on the matching piece of your private key. Finally you concatenate all the H outputs and that's your signature 🎀 Here's the pseudocode, bestie:
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]The lowkey coolest part is that the signature pieces are intermediate values of the elements computed by the public key algorithm in Section 4.3 🧚 So the signature is basically the public key math caught halfway through. The signature is whatever Algorithm 3 returns, and Section 3.3 is where the formal structure, the lmots_signature union, gets defined 📜
4.6. Signature Verification 🔍
ngl this is where the receiver does the detective work 🕵️♀️ To verify a message with its signature (an array of n-byte strings, denoted as y), the receiver has to "complete" the chain of H iterations using the w-bit coefficients from the message hash plus its checksum. That computation should end up matching the provided public key. Here are the steps:
Algorithm 4a: Verifying a Signature and Message Using a Public Key
1. If the public key is not at least four bytes long,
return INVALID.
2. Parse pubtype, I, q, and K from the public key as follows:
a. pubtype = strTou32(first 4 bytes of public key)
b. Set n according to the pubkey and Table 1; if the public key
is not exactly 24 + n bytes long, return INVALID.
c. I = next 16 bytes of public key
d. q = strTou32(next 4 bytes of public key)
e. K = next n bytes of public key
3. Compute the public key candidate Kc from the signature,
message, pubtype, and the identifiers I and q obtained from the
public key, using Algorithm 4b. If Algorithm 4b returns
INVALID, then return INVALID.
4. If Kc is equal to K, return VALID; otherwise, return INVALID.Algorithm 4b: Computing a Public Key Candidate Kc from a Signature,
Message, Signature Typecode pubtype, and Identifiers I, q
1. If the signature is not at least four bytes long,
return INVALID.
2. Parse sigtype, C, and y from the signature as follows:
a. sigtype = strTou32(first 4 bytes of signature)
b. If sigtype is not equal to pubtype, return INVALID.
c. Set n and p according to the pubtype and Table 1; if the
signature is not exactly 4 + n * (p+1) bytes long,
return INVALID.
d. C = next n bytes of signature
e. y[0] = next n bytes of signature
y[1] = next n bytes of signature
...
y[p-1] = next n bytes of signature
3. Compute the string Kc as follows:
Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
for ( i = 0; i < p; i = i + 1 ) {
a = coef(Q || Cksm(Q), i, w)
tmp = y[i]
for ( j = a; j < 2^w - 1; j = j + 1 ) {
tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
}
z[i] = tmp
}
Kc = H(I || u32str(q) || u16str(D_PBLC) ||
z[0] || z[1] || ... || z[p-1])
4. Return Kc.5. Leighton-Micali Signatures 🌈
The Leighton-Micali Signature (LMS) method can sign a potentially large but fixed number of messages, which is so iconic 👑 An LMS system uses two cryptographic components: a one-time signature method and a hash function. Each LMS public/private key pair is tied to a perfect binary tree, and every node holds an m-byte value, where m is the output length of the hash function. Each leaf holds the public key value of an LM-OTS public/private key pair. The root's value is the LMS public key, and each interior node is computed by hashing the concatenation of its children's values 🍓
Each node gets a node number, an unsigned integer called node_num in the algorithms below. Here's how it's computed: the root is node 1. For each node with node number N < 2^h (where h is the height of the tree), its left child is node 2*N and its right child is node 2*N + 1. So every node gets a unique number, and the leaves are numbered 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 be computed conveniently whenever the LMS algorithms need it, as those algorithms describe 🧮
5.1. Parameters 🎀
An LMS system has the following parameters:
h: the height of the treem: the number of bytes associated with each nodeH: 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. To minimize the risk, these two hash functions SHOULD be the same, so an attacker can't take advantage of a 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 for the implementation, and this document doesn't try to define it. One possibility is an array OTS_PRIV[] of 2^h LM-OTS private keys, plus the leaf number q of the next LM-OTS private key that hasn't been used yet. The q-th element of OTS_PRIV[] is generated using Algorithm 0 with the identifiers I, q. The leaf number q starts at zero when the LMS private key is created. Here's the process:
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 = 0An LMS private key MAY be generated pseudorandomly from a secret value. In that case, the secret value MUST be at least m bytes long and uniformly random, and it MUST NOT be used for any purpose other than generating the LMS private key. How this process is done doesn't affect interoperability, because the public key verification operation doesn't depend on these details. Appendix A gives an example of a pseudorandom method for computing an LMS private key ✨
The signature-generation logic uses q as the next leaf to use, so step 4 starts it at the leftmost leaf. Since 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. 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 tied to 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 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])Here D_LEAF is the fixed two-byte value 0x8282, and D_INTR is the fixed two-byte value 0x8383. Both are used to tell this hash apart from every other hash in the system 🙈
When r >= 2^h, we're processing a leaf node, so we only hash a single LM-OTS public key. When r < 2^h, we're processing an internal node, meaning 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 in use. 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 by recursively applying the equation above, or by any equivalent method. Appendix C has an iterative procedure for it 🧚
5.4. LMS Signature ✨
okay so an LMS signature is basically a little bundle with four pieces 🎀:
- the number q of the leaf that goes with the LM-OTS signature, as a four-byte unsigned integer in network byte order
- an LM-OTS signature
- a typecode saying which LMS algorithm is being used
- an array of h m-byte values, which is the path through the tree from that leaf up to the root 🌳
Written out symbolically, it looks like this 💅:
u32str(q) || lmots_signature || u32str(type) ||
path[0] || path[1] || path[2] || ... || path[h-1]Section 3.3 is where the format gets formally pinned down as the lms_signature structure 🧚. The array for a tree of height h has h values, and each one is the sibling of a node on the path from the leaf up to the root. A sibling is just the other node that shares the same parent. Counting starts at the bottom of the tree at 0, so path[0] is the value of the node right next to leaf q. path[1] is the second-level node next to leaf q's parent, and it keeps going like that up the tree until path[h-1], which is the next-to-top node on the side that leaf q is not sitting under 🦋.
Here's a tiny example with h=3 and q=2 so you can actually picture it. The leaf marked OTS is the one-time signature that signs the real message. The nodes on the path from the OTS public key up to the root are marked with a , and the nodes that end up in the path array are marked with . So path[0] is the leaf sitting next to the OTS public key (that's where the path starts 🌸), path[1] is the T[4]* node, which is the sibling of the second path node T[5], and path[2] is the T[3]* node, the sibling of the third path node T[2]*.
Root
|
---------------------------------
| |
T[2]* T[3]**
| |
------------------ -----------------
| | | |
T[4]** T[5]* T[6] T[7]
| | | |
--------- ---------- -------- ---------
| | | | | | | |
leaf leaf OTS leaf** leaf leaf leaf leafThe whole point of this authentication path is that you can check the OTS hash using just h path values and a bunch of hash computations 🔥. The verifier rebuilds the hashes going up the path. First it hashes the OTS value together with path[0], which gives a tentative T[5]' value. Then it hashes path[1] with that T[5]' value to get a tentative T[2]' value. Then it hashes that with path[2] to get a tentative Root' value. If that matches the known public key of the Merkle tree, then the T[2]' it computed must be the correct T[2] from the original tree. That means the T[5]' it got must be the correct T[5] too, so the OTS public key is the same one from the original tree and therefore it's legit 😭🙌.
5.4.1. LMS Signature Generation
okay so to make an LMS signature for a message using 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 gets set to the leaf number of the LMS private key that was actually used. Now here's the big one: before the signature gets released, the leaf number q in the LMS private key MUST be incremented, so that the same LM-OTS private key never gets used again 🚫. If the LMS private key lives in nonvolatile memory, then the implementation MUST ensure that the incremented value has been stored before the signature is released. This is super important, so let me spell out the disaster it prevents 💀:
- a) we generate a signature with one LM-OTS private key and hand it off to the application
- b) before we update the nonvolatile memory, we crash
- c) we reboot and generate a second signature using that same LM-OTS private key
Two different signatures from the same LM-OTS private key is a huge problem, because an attacker could potentially forge a signature on a third message 😱.
The array of node values in the signature MAY be computed in any way you like. There are loads of time/storage trade-offs you can play with 🍓. The fastest option is to store every node of the tree and just copy the needed ones into the array, and pseudocode for that shows up in Appendix D. The least storage-hungry option is to recompute all the nodes for every single signature. The details of this procedure don't matter for interoperability, and you don't need to know any of them to verify a signature. The internal nodes of the tree don't need to be secret, so a node-caching scheme that only stores internal nodes can skip 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
okay so verifying an LMS signature goes like this 🫶. First you run the LM-OTS signature verification algorithm (Algorithm 4b) to get the LM-OTS public key from the LM-OTS signature and the message. That public key value gets assigned to the matching leaf of the LMS tree. Then you compute the root of the tree from that leaf value and the path[] array, using Algorithm 6 below. If the root matches the public key, the signature is valid. If not, the verification fails 🥀.
Here's Algorithm 6 and its helper, Algorithm 6a, exactly as written 💖:
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 ✨
okay so bestie, this part is my absolute favourite 😭🫶 when the public key generation time is making you cry, HSS comes in to save the day 🦋. It's a hierarchical scheme and it uses LMS as a building block. So in HSS we've got a sequence of L LMS trees 🌳. The public key of the first LMS tree gets included in the HSS public key 💖, each LMS private key signs the next LMS public key, and the very last LMS private key signs the actual message 💅. It's giving chain of trust, and I'm obsessed 🔥.
Let's say we've got a three-level hierarchy (L=3) 🎀. To sign a message, we'd 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 sitting inside the HSS public key 👑.
To verify the LMS signature, we check all of the signatures, one by one 🧚:
- We verify that the level 1 LMS public key is correctly signed by the level 0 signature.
- We verify that the level 2 LMS public key is correctly signed by the level 1 signature.
- We verify that the message is correctly signed by the level 2 signature.
We only accept the HSS signature if all the signatures validated 🙈. No exceptions, no vibes-based acceptance, periodt 💀.
During signature generation, we sign messages with the lowest (level L-1) LMS tree 🍓. Once we've used all the leafs in that tree to sign messages, we toss it, generate a fresh LMS tree, and sign it with the next (level L-2) LMS tree. And when that one is used up too, we recursively generate and sign a fresh level L-2 LMS tree 🌸. It's like a cycle of renewal, ngl so iconic ✨.
HSS, in essence, is a tree of LMS trees 🌳🌳. There's a single LMS tree at level 0 (the root). Each LMS tree (well, really the private key that goes with it) at level i is used to sign 2^h objects, where h is the height of the trees at level i 🦋. If i < L-1, then each object is another LMS tree (really the public key) at level i+1. If i = L-1, we've hit the bottom of the HSS tree, so each object is a message from the application 💜. The HSS public key holds the public key of the root LMS tree, and an HSS signature is tied to a path from the root of the HSS tree down to the leaf 🧚♀️.
Now here's why this is so worth it 🤩. Compared to LMS, HSS has a way reduced public key generation time, because only the root tree has to be generated before the HSS public key gets distributed 💖. 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 (each level 1 public key is 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, since you only need to compute the level 0 LMS tree to get that value. You can, of course, decide to compute the initial level 1 and level 2 LMS trees too 🫶. And the 2^20 level 2 LMS trees can jointly sign a total of over a billion messages 😭✨. Compare that to a single LMS tree that could sign a billion messages, which would need a billion OTS public keys computed first (if h=30 were allowed in a supported parameter set) 💀.
Each LMS tree in the hierarchy has its own distinct LMS public key, private key, signature, and identifier 🌈. The number of levels is denoted L and is between one and eight, inclusive 🍓. We use the following notation, 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 keypub[i+1], generated using the private keyprv[i].
These arrays are maintained for the whole life of the HSS key 🔥. The contents of the prv[] array MUST be kept private 🔒. The pub[] and sig[] arrays MAY be revealed if the implementation finds that convenient 💅.
In this section, a N-time private key counts as exhausted once it has generated N signatures, so it can't be used for signing anymore 🙈.
For i > 0, the values prv[i], pub[i], and (for all values of i) sig[i] get 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), the LMS key generation processes in Sections 5.2 and 5.3 are performed 🧚. If the generated key pairs are for level i of the HSS hierarchy, we store the public key in pub[i] and the private key in prv[i] 🌸. Also, if i > 0, we sign the generated public key with the LMS private key at level i-1, and put the signature into sig[i-1] 💜. When an LMS key pair is generated, the key pair and its identifier MUST be generated independently of all other key pairs ✨.
HSS allows L=1 🎀. In that case, the HSS public key and signature formats are basically the LMS public key and signature formats, just with a fixed field stuck on the front. Since HSS with L=1 has very little overhead compared to LMS, all implementations MUST support HSS 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 for this 🧠. For one, the signer may decide to store parts of the 0-th LMS tree (the bits it needs to construct while computing the public key) to speed up later operations. Since the 0-th tree is never updated, those internal nodes will never need to be recomputed 💖. Also, during signature generation, almost all the work involved in updating the authentication path happens at the bottom (L-1th) LMS public key 🍓. So it can be useful to pick a parameter set for that key that gives it a shorter LMS tree 🦋.
A close reading of the HSS verification pseudocode shows that it would allow the parameters of the non-top LMS public keys to change over time 👀. For example, the signer might initially have the 1-th LMS public key use LMS_SHA256_M32_H10, but when that tree is exhausted, swap it for an LMS public key that uses LMS_SHA256_M32_H15. Honestly this would work with the example verification pseudocode 🤷♀️, but the signer MUST NOT change the parameter sets for a specific level 🚫. This prohibition exists to support verifiers that may keep state across several signature verifications 🙈.
6.1. Key Generation
The HSS public key is the number of levels L, followed by pub[0], the public key of the top level 🎀.
The HSS private key is prv[0], ... , prv[L-1], along with the associated pub[0], ... pub[L-1] and sig[0], ..., sig[L-2] values 🌸. As mentioned earlier, the values of the pub[] and sig[] arrays don't need to be kept secret and may be revealed 💅. The value of pub[0] never changes (and, except for the index q, prv[0] doesn't need to change either) 🧚. The values of pub[i] and prv[i] are dynamic for i > 0, though, and they get changed by the signature-generation algorithm 🔥.
During key generation, the public and private keys get initialized 🦋. Here's 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 keyIn the above algorithm, each LMS public/private key pair generated MUST be generated independently 🔒.
Note that the value of the public key doesn't depend on step 2 being run 🤯. So an implementation can totally 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, these steps happen 💅:
- If
prv[L-1]is exhausted, determine the smallest integer d such that all of the private keysprv[d],prv[d+1], ... ,prv[L-1]are exhausted. If d is equal to zero, 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 signature generation, 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]andprv[i]are set to those values, then the public keypub[i]is signed withprv[i-1], andsig[i-1]is set to the resulting value 🦋. - The message is signed with
prv[L-1], and the valuesig[L-1]is set to that result ✨. - The value of the HSS signature is set as follows. We let
signed_pub_keydenote an array of octet strings, wheresigned_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk-1 inclusive, where Nspk = L-1 is the number of signed public keys. Then the HSS signature isu32str(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's 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, you run through these 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])Okay so here's the tricky bit 👀 An LMS signature doesn't come with a length label, so you can't know how long it is until you actually parse it. That's why the HSS verification algorithm uses an LMS signature parsing routine. You give it an LMS signature with some extra string stuck on the end, and it hands back both the LMS signature and the leftover string. That leftover gets passed along for more processing. It's giving careful parsing, honestly 🧚
6.4. Parameter Set Recommendations 🎀
Okay, so when it comes to picking how many LMS levels to use and how big each one should be, performance talk is totally implementation specific 🙈 Generally speaking, the only real downside of a single LMS tree is how long it takes to generate the public key. Every LM-OTS public key has to be generated, so that wait can get seriously long. With a two-level tree, only the top-level LMS tree and the first bottom-level LMS tree need to be generated up front (before you make your first signature), and that's usually way quicker. Iconic 💅
To give you a vibe check on the trade-offs, we included some measurements from the LMS implementation at <https://github.com/cisco/hash-sigs>. They were taken on a 3.3 GHz Xeon processor with threading turned on. We tried a bunch of parameter sets, all with W=8, since that one keeps signatures smallest while taking more time. Treat these as a guideline for what's possible, not gospel: your mileage on computing time may vary depending on what hardware you have. The machine used for these tests doesn't have the SHA-256 extensions, so you could probably 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 3Here's what the columns mean, bestie 📝
- ParmSet: this is the height of the Merkle tree(s). Parameter sets written as a single integer have L=1 and are just one Merkle tree of that height. Parameter sets with L=2 are written as x/y, where x is the height of the top-level Merkle tree and y is the bottom level.
- KeyGenTime: the measured key-generation time, meaning how long it takes to generate the public/private key pair.
- SigSize: the size of a signature, in bytes.
- KeyLifetime: the lifetime of a key, assuming you generate 1000 signatures per second. Real talk though, you're not gonna sustain anything close to 1000 signatures per second 💀 If you've got a better number for your situation, this column is super easy to recompute.
Signature generation and verification times are pretty much unbothered by the parameter settings above. The exceptions are the Winternitz setting and the number of Merkle trees, which do matter for verification. On the same machine without multithreading, signing a short message took about 4 msec and verifying took about 2.6 msec. Those tests used a two-level ParmSet, and a single level would roughly halve the verification time. You can speed everything up a lot (maybe by a factor of 8!) by using a parameter set with W=4, but heads up, that also roughly doubles the signature size 🍓
7. Rationale 🌈
Okay, the whole point of this note is to describe the LM-OTS, LMS, and HSS algorithms, following the original references, and to present the modern security analysis of those algorithms. Other signature methods are out of scope, but they could be super interesting follow-on work 👑
We borrow the techniques Leighton and Micali described to deal with attacks that spread their work out over multiple calls to the hash function 🧠
The values the identifier I takes across different LMS public/private key pairs are picked randomly, which helps security. The analysis of this method in [Fluhrer17] shows that we don't actually need uniqueness to be secure. What we do need is to make sure we don't end up with a huge number of private keys sharing the same I value. By randomly choosing 16-byte I values, the chance that, out of 2^64 private keys, 4 or more of them use the same I value is negligible (in other words, the probability is less than 2^-128). Smart, right? 🦋
The reason we went with 16-byte I values 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), and SHA-256 can hash that in a single hash-compression operation. Other hash functions may show up in future specifications. All the ones we're 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 to be relatively easy to parse. Each format starts with a 32-bit enumeration value. That value tells you the details of the signature algorithm and gives you everything you need to parse the rest of the format ✨
The Checksum (Section 4.4) is calculated using a nonnegative integer called "sum." Its width was picked to be an integer number of w-bit fields, so it can hold the difference between 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. If H is applied 0 times, the sum is (2^w - 1) * (8*n/w). So for 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 every combination of n and w. The calculation uses the parameter ls defined in Section 4.1 and calculated in Appendix B, which tells you how many bits to use in the left-shift operation 💅
7.1. Security String 🔐
To make things safer against attacks that spread their effort across multiple calls to the hash function, Leighton and Micali introduced a "security string" that's different for every single invocation of that function. Whenever this process computes a hash, the string being hashed starts with a string built from the fields below. These fields always sit in fixed spots inside the value being hashed, so we list where each one lives in the hash. The fields are:
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 treei: 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 📜✨
okay so IANA keeps two registries bestie 🗂️💖. First up is "LM-OTS Signatures", which holds all the LM-OTS signatures from Section 4. Then there's "Leighton-Micali Signatures (LMS)", which holds LMS from Section 5. 🌸
Adding something new to either one needs a specification in an RFC, or in another permanent and readily available reference, detailed enough that independent implementations can actually interoperate [RFC8126]. And the vibe check: IANA MUST verify that every application to add to these registries has first been reviewed by the IRTF Crypto Forum Research Group (CFRG). 🕵️♀️ CFRG gets the first look, always. Iconic.
Every entry in either registry has three 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.
Now the private-use zone 🔒: the numbers from 0xDDDDDDDD (decimal 3,722,304,989) through 0xFFFFFFFF (decimal 4,294,967,295), inclusive, are not going to be assigned by IANA. They're reserved for private use, and nobody is going to stop multiple sites from using the same value in different, incompatible ways [RFC8126]. Chaotic but that's the deal 🙈.
The initial contents of the "LM-OTS Signatures" registry look like this:
+--------------------------+-----------+--------------------------+
| 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 next 🦋:
+--------------------------+-----------+--------------------------+
| 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
Real talk: an IANA registration of a signature system does not count as an endorsement of that system or its security. Being listed is not a stamp of approval 🙅♀️✨.
Last bit of this section 💅: right now the two registries assign a disjoint set of values to the defined parameter sets. That overlap-free situation is a historical accident, and the correctness of the system does not depend on it. IANA is not required to keep it that way, so don't build your life around it, bestie 🫶.
9. Security Considerations 🚨🔐
this section is serious, and I'm not gonna pretend it isn't 😭. Read it all.
The hash function H MUST have second preimage resistance. In plain terms, it must be computationally infeasible for an attacker who is given one message M to find a second message M' such that H(M) = H(M') 🧨.
The whole point of a signature system is to stop forgeries 🛑. A successful forgery happens when an attacker who doesn't know the private key tied to a public key can find a message (one that's distinct from every message already signed) plus a signature that's valid under that public key. "Valid" here means the Signature Verification algorithm, run on that signature, message, and public key, returns VALID. In the strongest case, that attacker might even be able to forge valid signatures for a bunch of other messages too. Scary stuff 👀.
LMS is provably secure in the random oracle model, as shown by [Katz16]. There's also more analysis in [Fluhrer17], where the hash compression function (instead of the entire hash function) is treated as a random oracle. Corollary 1 of that second paper says:
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.
Okay, the typecode situation 🏷️: lots of the objects inside the public key and the signature begin with a typecode. A verifier MUST check each of these typecodes. A verification operation on a signature with an unknown type, or with a type that doesn't match the type inside the public key, MUST return INVALID. The expected length of a variable-length object can be figured out from its typecode, and if an object has a different length, then any signature computed from that object is INVALID. Length check, no exceptions 🙅♀️.
9.1. Hash Formats 🧁
The inputs to the hash function H have a property that's super important for the proof: each invocation has an input that gets repeated by a small, bounded number of other inputs, because of potential repeats of the I value. Specifically, the input varies somewhere in the first 23 bytes of the value being hashed. This is essential for the proof of security in the random oracle model 🧠✨.
These are the formats used during key generation and signing, including the recommended pseudorandom key-generation procedure in Appendix A:
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) || SEEDEach hash type on that list is distinct. At locations 20 and 21 of the value being hashed, you'll find either a fixed value (D_PBLC, D_MESG, D_LEAF, or D_INTR) or a 16-bit value i. The fixed values are different from each other and they're large (over 32768), while the 16-bit values of i are small (currently no more than 265, possibly a bit larger if larger hash functions are supported). So the range of possible i values can't collide with the D_PBLC, D_MESG, D_LEAF, or D_INTR identifiers 💜. The only other possible collision is between the Winternitz chain hash and 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 between 0 and 254, while the recommended pseudorandom key-generation process has the value 255 at location 22. Clever, right? 🍓
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 gets used only once for each value of q, so distinctness is guaranteed. The formats for D_INTR and D_LEAF are used exactly once for each value of r, which keeps them distinct too. For the recommended pseudorandom key-generation process, for a given value of I, q and j are distinct for each invocation of H 🎀.
Now the I value itself 🎲. It's chosen uniformly at random from the set of all 128-bit strings. If 2^64 public keys are generated (and so 2^64 random I values), there's a nontrivial probability of a duplicate, which would imply duplicate prefixes. But there is an extremely high probability that there won't be a four-way collision (meaning any I value used for four distinct LMS keys, with probability < 2^-132). So the number of repeats for any specific prefix will be limited to at most three. [Fluhrer17] shows this has only a limited effect on the security of the system, so we're giving it a big thumbs up 👍🦋.
9.2. Stateful Signature Algorithm 💅
okay so the LMS signature system, like ALL N-time signature systems, needs the signer to keep track of state between every single signing call 🙈 That way none of the component one-time signature systems ever gets used twice. This section flags some important practical stuff about that statefulness. There's a deeper dive in [STMGMT] if you're obsessed (same) 📚
In a typical computing setup, the private key lives on nonvolatile media, like a hard drive 💾 Before signing, it gets read into the application's Random-Access Memory (RAM). After a signature is made, the new private key value has to be written back into nonvolatile storage. It is essential for security that the app actually makes sure that value gets written, but there may be one or more memory caches sitting between the app and the disk 😭 Caching usually lives in the file system and in a physical memory unit on the hard disk that's dedicated to that job. To make sure the updated value really hits the physical media, the application may need to take a few special steps.
In a POSIX environment, for example, the O_SYNC flag (for the open() system call) makes calls to write() block the calling process until the data has been written to the underlying hardware ✨ But if that hardware has its own memory cache, it must be handled separately with an operating system or device-specific tool like hdparm, which can flush the on-drive cache or turn off write caching for that drive. These details vary across operating systems and devices, so this note doesn't try to give complete guidance. Instead, we're just pointing implementers toward these issues 🫶
When hierarchical signatures are used, an easy way to dodge the private key synchronization issues is to keep the private key for the second level in RAM only and never write that value into nonvolatile memory 🧚 A new second-level public/private key pair gets generated whenever the application (re)starts. So failures like a power outage or an application crash are automatically handled 🔥 Implementations SHOULD use this approach wherever possible.
9.3. Security of LM-OTS Checksum 🔐
To show the security of the LM-OTS checksum, we look at 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 try a forgery, an attacker might attempt 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, inclusive, where u = ceil(8*n/w) is the size of the range that the checksum value can cover:
a' = coef(h', j, w),
a = coef(h, j, w), and
a' > athen 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, because of the increased number of hashing iterations, the checksum value c' will decrease from its original value of c. So 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' < bThanks to the one-way property of F, the attacker can't 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 happens because the hash operation done as 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. Plus, HSS is somewhat simpler, since each hash invocation is just a prefix followed by the data being hashed. Iconic, honestly 👑
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.
Appendix A. Pseudorandom Key Generation ✨
An implementation MAY use the following pseudorandom process for generating an LMS private key 🌈 It's totally optional, but here's how it goes:
SEEDis an m-byte value that is generated uniformly at random at the start of the process,Iis the LMS key pair identifier,qdenotes the LMS leaf number of an LM-OTS private key,x_qdenotes the x array of private elements in the LM-OTS private key with leaf numberq,iis the index of the private key element, andHis the hash function used in LM-OTS.
The elements of the LM-OTS private keys are computed as:
x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED).This process stretches the m-byte random value SEED into a (much larger) set of pseudorandom values, using a unique counter in each invocation of H 🦋 The format of the inputs to H is chosen so they're distinct from all other uses of H in LMS and LM-OTS. A careful reader will notice this is similar to the hash we perform when iterating through the Winternitz chain. The difference is that in that chain, the iteration index varies 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], so this method is safe when used within the LMS system. Any other cryptographically secure method of generating private keys would also be safe 💜
Appendix B. LM-OTS Parameter Options ✨
okay so the LM-OTS one-time signature method has a bunch of internal parameters 🤓 and they all depend on which parameter set you picked. bestie, these are the ones:
pis the number of independent Winternitz chains used in the signature. It's the number of w-bit digits needed to hold the n-bit hash (uin the equations below) plus the number of digits needed to hold the checksum (vin the equations below) 🦋lsis the size of the shift needed to move the checksum so that it lands in the checksum digits 💅
ok, the reason ls exists is kinda iconic 👑 We store the checksum internally as a 16-bit value, but we don't always put all 16 bits into the signature. If w=4, for example, we might only use the top 12 bits. We read the checksum in network order, so without the shift we'd grab the higher-order bits (which might always be 0) and skip the lower-order bits, which is where the checksum value actually lives 😭 The shift makes sure the parts of the checksum we need for security really do contribute to the signature. If more than one shift would work, we take the smallest one 🫶
Here's how ls and p get computed:
u = ceil(8*n/w)
v = ceil((floor(lg((2^w - 1) * u)) + 1) / w)
ls = 16 - (v * w)
p = u + vSo u and v are the number of w-bit fields needed to hold the message hash and the checksum byte strings, respectively. And since p counts the w-bit elements of ( H(message) || Cksm(H(message)) ), it's also the number of byte strings in the private key AND the number of byte strings in the signature. Two for one, periodt ✨ The 16 in the ls computation is the 16-bit value used for the sum variable in Algorithm 2 in Section 4.4 🧚
Here's a table with a bunch of n and w combos and their matching u, v, ls, and p values (it's Table 6) 🌈
+---------+------------+-----------+-----------+-------+------------+
| Hash | Winternitz | w-bit | w-bit | Left | Total |
| Length | Parameter | Elements | Elements | Shift | Number of |
| in | (w) | in Hash | in | (ls) | w-bit |
| Bytes | | (u) | Checksum | | Elements |
| (n) | | | (v) | | (p) |
+---------+------------+-----------+-----------+-------+------------+
| 32 | 1 | 256 | 9 | 7 | 265 |
| | | | | | |
| 32 | 2 | 128 | 5 | 6 | 133 |
| | | | | | |
| 32 | 4 | 64 | 3 | 4 | 67 |
| | | | | | |
| 32 | 8 | 32 | 2 | 0 | 34 |
+---------+------------+-----------+-----------+-------+------------+Table 6
Appendix C. An Iterative Algorithm for Computing an LMS Public Key 🌸
You can compute the LMS public key with the algorithm below or with any equivalent method, bestie 💖 This one uses a stack of hashes for its data. It also uses a hash function with the usual init/update/final interface. Calling hash_init(), then hash_update(N[1]), hash_update(N[2]), ... , hash_update(N[n]), and then v = hash_final(), in that order, gives you the same result as H(N[1] || N[2] || ... || N[n]) 🧠
Generating an LMS Public Key from an LMS Private Key 🔥
for ( i = 0; i < 2^h; i = i + 1 ) {
r = i + num_lmots_keys;
temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i])
j = i;
while (j % 2 == 1) {
r = (r - 1)/2;
j = (j-1) / 2;
left_side = pop(data stack);
temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
}
push temp onto the data stack
}
public_key = pop(data stack)Heads up: this pseudocode assumes all 2^h leaves of the tree have equal depth. Basically, it expects num_lmots_keys to be a power of 2 🙈 The maximum depth of the stack is h-1 elements, which is (h-1)*n bytes total. For the parameter sets that are currently defined, that's never more than 768 bytes of data 💜
Appendix D. Method for Deriving Authentication Path for a Signature 🦋
An LMS signature is made up of u32str(q) || lmots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1]. This appendix shows ONE method for building it, assuming the implementation has stored the T[] array that was used to build the public key. It's not the only way, though. Other methods exist that don't need the whole T[] array sitting in memory 🫶 To build a signature, you run this algorithm:
Generating an LMS Signature ✨
1. Set type to the typecode of the LMS algorithm.
2. Extract h from the typecode, according to Table 2.
3. Create the LM-OTS signature for the message:
ots_signature = lmots_sign(message, LMS_PRIV[q])
4. Compute the array path as follows:
i = 0
r = 2^h + q
while (i < h) {
temp = (r / 2^i) xor 1
path[i] = T[temp]
i = i + 1
}
5. S = u32str(q) || ots_signature || u32str(type) ||
path[0] || path[1] || ... || path[h-1]
6. q = q + 1
7. Return S.Quick decoder ring: "xor" is the bitwise exclusive-or, and / is integer division, which means rounded down to a whole number 🧚
Appendix E. Example Implementation 💅
There's an example implementation you can check out online at https://github.com/cisco/hash-sigs 🌈
Appendix F. Test Cases 🎀
This section has test cases you can use to verify or debug your implementation, bestie 🔍 The data is laid out with the element name on the left and its hexadecimal value on the right. Concatenating all the values inside a public key or signature gives you that public key or signature. Values too long for one line just continue on the next lines 😭
Test Case 1 Public Key 🔑
--------------------------------------------
HSS public key
levels 00000002
--------------------------------------------
LMS type 00000005 # LM_SHA256_M32_H5
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
I 61a5d57d37f5e46bfb7520806b07a1b8
K 50650e3b31fe4a773ea29a07f09cf2ea
30e579f0df58ef8e298da0434cb2b878
--------------------------------------------
--------------------------------------------Test Case 1 Message 💌
--------------------------------------------
Message 54686520706f77657273206e6f742064 |The powers not d|
656c65676174656420746f2074686520 |elegated to the |
556e6974656420537461746573206279 |United States by|
2074686520436f6e737469747574696f | the Constitutio|
6e2c206e6f722070726f686962697465 |n, nor prohibite|
6420627920697420746f207468652053 |d by it to the S|
74617465732c20617265207265736572 |tates, are reser|
76656420746f20746865205374617465 |ved to the State|
7320726573706563746976656c792c20 |s respectively, |
6f7220746f207468652070656f706c65 |or to the people|
2e0a |..|
--------------------------------------------Test Case 1 Signature 🦋
--------------------------------------------
HSS signature
Nspk 00000001
sig[0]:
--------------------------------------------
LMS signature
q 00000005
--------------------------------------------
LMOTS signature
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
C d32b56671d7eb98833c49b433c272586
bc4a1c8a8970528ffa04b966f9426eb9
y[0] 965a25bfd37f196b9073f3d4a232feb6
9128ec45146f86292f9dff9610a7bf95
y[1] a64c7f60f6261a62043f86c70324b770
7f5b4a8a6e19c114c7be866d488778a0
y[2] e05fd5c6509a6e61d559cf1a77a970de
927d60c70d3de31a7fa0100994e162a2
y[3] 582e8ff1b10cd99d4e8e413ef469559f
7d7ed12c838342f9b9c96b83a4943d16
y[4] 81d84b15357ff48ca579f19f5e71f184
66f2bbef4bf660c2518eb20de2f66e3b
y[5] 14784269d7d876f5d35d3fbfc7039a46
2c716bb9f6891a7f41ad133e9e1f6d95
y[6] 60b960e7777c52f060492f2d7c660e14
71e07e72655562035abc9a701b473ecb
y[7] c3943c6b9c4f2405a3cb8bf8a691ca51
d3f6ad2f428bab6f3a30f55dd9625563
y[8] f0a75ee390e385e3ae0b906961ecf41a
e073a0590c2eb6204f44831c26dd768c
y[9] 35b167b28ce8dc988a3748255230cef9
9ebf14e730632f27414489808afab1d1
y[10] e783ed04516de012498682212b078105
79b250365941bcc98142da13609e9768
y[11] aaf65de7620dabec29eb82a17fde35af
15ad238c73f81bdb8dec2fc0e7f93270
y[12] 1099762b37f43c4a3c20010a3d72e2f6
06be108d310e639f09ce7286800d9ef8
y[13] a1a40281cc5a7ea98d2adc7c7400c2fe
5a101552df4e3cccfd0cbf2ddf5dc677
y[14] 9cbbc68fee0c3efe4ec22b83a2caa3e4
8e0809a0a750b73ccdcf3c79e6580c15
y[15] 4f8a58f7f24335eec5c5eb5e0cf01dcf
4439424095fceb077f66ded5bec73b27
y[16] c5b9f64a2a9af2f07c05e99e5cf80f00
252e39db32f6c19674f190c9fbc506d8That's the whole test-case set for this part, bestie! 🌈✨
y[17] 26857713afd2ca6bb85cd8c107347552 f30575a5417816ab4db3f603f2df56fb y[18] c413e7d0acd8bdd81352b2471fc1bc4f 1ef296fea1220403466b1afe78b94f7e y[19] cf7cc62fb92be14f18c2192384ebceaf 8801afdf947f698ce9c6ceb696ed70e9 y[20] e87b0144417e8d7baf25eb5f70f09f01 6fc925b4db048ab8d8cb2a661ce3b57a y[21] da67571f5dd546fc22cb1f97e0ebd1a6 5926b1234fd04f171cf469c76b884cf3 y[22] 115cce6f792cc84e36da58960c5f1d76 0f32c12faef477e94c92eb75625b6a37 y[23] 1efc72d60ca5e908b3a7dd69fef02491 50e3eebdfed39cbdc3ce9704882a2072 y[24] c75e13527b7a581a556168783dc1e975 45e31865ddc46b3c957835da252bb732 y[25] 8d3ee2062445dfb85ef8c35f8e1f3371 af34023cef626e0af1e0bc017351aae2 y[26] ab8f5c612ead0b729a1d059d02bfe18e fa971b7300e882360a93b025ff97e9e0 y[27] eec0f3f3f13039a17f88b0cf808f4884 31606cb13f9241f40f44e537d302c64a y[28] 4f1f4ab949b9feefadcb71ab50ef27d6 d6ca8510f150c85fb525bf25703df720 y[29] 9b6066f09c37280d59128d2f0f637c7d 7d7fad4ed1c1ea04e628d221e3d8db77 y[30] b7c878c9411cafc5071a34a00f4cf077 38912753dfce48f07576f0d4f94f42c6 y[31] d76f7ce973e9367095ba7e9a3649b7f4 61d9f9ac1332a4d1044c96aefee67676 y[32] 401b64457c54d65fef6500c59cdfb69a f7b6dddfcb0f086278dd8ad0686078df y[33] b0f3f79cd893d314168648499898fbc0 ced5f95b74e8ff14d735cdea968bee74
LMS type 00000005 # LM_SHA256_M32_H5 path[0] d8b8112f9200a5e50c4a262165bd342c d800b8496810bc716277435ac376728d path[1] 129ac6eda839a6f357b5a04387c5ce97 382a78f2a4372917eefcbf93f63bb591 path[2] 12f5dbe400bd49e4501e859f885bf073 6e90a509b30a26bfac8c17b5991c157e path[3] b5971115aa39efd8d564a6b90282c316 8af2d30ef89d51bf14654510a12b8a14 path[4] 4cca1848cf7da59cc2b3d9d0692dd2a2 0ba3863480e25b1b85ee860c62bf5136
LMS public key LMS type 00000005 # LM_SHA256_M32_H5 LMOTS type 00000004 # LMOTS_SHA256_N32_W8 I d2f14ff6346af964569f7d6cb880a1b6 K 6c5004917da6eafe4d9ef6c6407b3db0 e5485b122d9ebe15cda93cfec582d7ab
final_signature:
LMS signature q 0000000a
LMOTS signature LMOTS type 00000004 # LMOTS_SHA256_N32_W8 C 0703c491e7558b35011ece3592eaa5da 4d918786771233e8353bc4f62323185c y[0] 95cae05b899e35dffd71705470620998 8ebfdf6e37960bb5c38d7657e8bffeef y[1] 9bc042da4b4525650485c66d0ce19b31 7587c6ba4bffcc428e25d08931e72dfb y[2] 6a120c5612344258b85efdb7db1db9e1 865a73caf96557eb39ed3e3f426933ac y[3] 9eeddb03a1d2374af7bf771855774562 37f9de2d60113c23f846df26fa942008 y[4] a698994c0827d90e86d43e0df7f4bfcd b09b86a373b98288b7094ad81a0185ac y[5] 100e4f2c5fc38c003c1ab6fea479eb2f 5ebe48f584d7159b8ada03586e65ad9c y[6] 969f6aecbfe44cf356888a7b15a3ff07 4f771760b26f9c04884ee1faa329fbf4 y[7] e61af23aee7fa5d4d9a5dfcf43c4c26c e8aea2ce8a2990d7ba7b57108b47dabf y[8] beadb2b25b3cacc1ac0cef346cbb90fb 044beee4fac2603a442bdf7e507243b7 y[9] 319c9944b1586e899d431c7f91bcccc8 690dbf59b28386b2315f3d36ef2eaa3c y[10] f30b2b51f48b71b003dfb08249484201 043f65f5a3ef6bbd61ddfee81aca9ce6 y[11] 0081262a00000480dcbc9a3da6fbef5c 1c0a55e48a0e729f9184fcb1407c3152 y[12] 9db268f6fe50032a363c9801306837fa fabdf957fd97eafc80dbd165e435d0e2 y[13] dfd836a28b354023924b6fb7e48bc0b3 ed95eea64c2d402f4d734c8dc26f3ac5 y[14] 91825daef01eae3c38e3328d00a77dc6 57034f287ccb0f0e1c9a7cbdc828f627 y[15] 205e4737b84b58376551d44c12c3c215 c812a0970789c83de51d6ad787271963
y[16] 327f0a5fbb6b5907dec02c9a90934af5 a1c63b72c82653605d1dcce51596b3c2 y[17] b45696689f2eb382007497557692caac 4d57b5de9f5569bc2ad0137fd47fb47e y[18] 664fcb6db4971f5b3e07aceda9ac130e 9f38182de994cff192ec0e82fd6d4cb7 y[19] f3fe00812589b7a7ce51544045643301 6b84a59bec6619a1c6c0b37dd1450ed4 y[20] f2d8b584410ceda8025f5d2d8dd0d217 6fc1cf2cc06fa8c82bed4d944e71339e y[21] ce780fd025bd41ec34ebff9d4270a322 4e019fcb444474d482fd2dbe75efb203 y[22] 89cc10cd600abb54c47ede93e08c114e db04117d714dc1d525e11bed8756192f y[23] 929d15462b939ff3f52f2252da2ed64d 8fae88818b1efa2c7b08c8794fb1b214 y[24] aa233db3162833141ea4383f1a6f120b e1db82ce3630b3429114463157a64e91 y[25] 234d475e2f79cbf05e4db6a9407d72c6 bff7d1198b5c4d6aad2831db61274993 y[26] 715a0182c7dc8089e32c8531deed4f74 31c07c02195eba2ef91efb5613c37af7 y[27] ae0c066babc69369700e1dd26eddc0d2 16c781d56e4ce47e3303fa73007ff7b9 y[28] 49ef23be2aa4dbf25206fe45c20dd888 395b2526391a724996a44156beac8082 y[29] 12858792bf8e74cba49dee5e8812e019 da87454bff9e847ed83db07af3137430 y[30] 82f880a278f682c2bd0ad6887cb59f65 2e155987d61bbf6a88d36ee93b6072e6 y[31] 656d9ccbaae3d655852e38deb3a2dcf8 058dc9fb6f2ab3d3b3539eb77b248a66 y[32] 1091d05eb6e2f297774fe6053598457c c61908318de4b826f0fc86d4bb117d33 y[33] e865aa805009cc2918d9c2f840c4da43 a703ad9f5b5806163d7161696b5a0adc
LMS type 00000005 # LM_SHA256_M32_H5 path[0] d5c0d1bebb06048ed6fe2ef2c6cef305 b3ed633941ebc8b3bec9738754cddd60 path[1] e1920ada52f43d055b5031cee6192520 d6a5115514851ce7fd448d4a39fae2ab path[2] 2335b525f484e9b40d6a4a969394843b dcf6d14c48e8015e08ab92662c05c6e9 path[3] f90b65a7a6201689999f32bfd368e5e3 ec9cb70ac7b8399003f175c40885081a path[4] 09ab3034911fe125631051df0408b394 6b0bde790911e8978ba07dd56c73e7ee
Test Case 2 Private Key
(note: procedure in Appendix A is used) Top level LMS tree SEED 558b8966c48ae9cb898b423c83443aae 014a72f1b1ab5cc85cf1d892903b5439 I d08fabd4a2091ff0a8cb4ed834e74534 Second level LMS tree SEED a1c4696e2608035a886100d05cd99945 eb3370731884a8235e2fb3d4d71f2547 I 215f83b7ccb9acbcd08db97b0d04dc2b
Test Case 2 Public Key
HSS public key levels 00000002
LMS type 00000006 # LM_SHA256_M32_H10 LMOTS type 00000003 # LMOTS_SHA256_N32_W4 I d08fabd4a2091ff0a8cb4ed834e74534 K 32a58885cd9ba0431235466bff9651c6 c92124404d45fa53cf161c28f1ad5a8e
Test Case 2 Message
Message 54686520656e756d65726174696f6e20 |The enumeration | 696e2074686520436f6e737469747574 |in the Constitut| 696f6e2c206f66206365727461696e20 |ion, of certain | 7269676874732c207368616c6c206e6f |rights, shall no| 7420626520636f6e7374727565642074 |t be construed t| 6f2064656e79206f7220646973706172 |o deny or dispar| 616765206f7468657273207265746169 |age others retai| 6e6564206279207468652070656f706c |ned by the peopl| 652e0a |e..|
Test Case 2 Signature
HSS signature Nspk 00000001 sig[0]:
LMS signature q 00000003
LMOTS signature LMOTS type 00000003 # LMOTS_SHA256_N32_W4 C 3d46bee8660f8f215d3f96408a7a64cf 1c4da02b63a55f62c666ef5707a914ce y[0] 0674e8cb7a55f0c48d484f31f3aa4af9 719a74f22cf823b94431d01c926e2a76 y[1] bb71226d279700ec81c9e95fb11a0d10 d065279a5796e265ae17737c44eb8c59 y[2] 4508e126a9a7870bf4360820bdeb9a01 d9693779e416828e75bddd7d8c70d50a y[3] 0ac8ba39810909d445f44cb5bb58de73 7e60cb4345302786ef2c6b14af212ca1 y[4] 9edeaa3bfcfe8baa6621ce88480df237 1dd37add732c9de4ea2ce0dffa53c926 y[5] 49a18d39a50788f4652987f226a1d481 68205df6ae7c58e049a25d4907edc1aa y[6] 90da8aa5e5f7671773e941d805536021 5c6b60dd35463cf2240a9c06d694e9cb y[7] 54e7b1e1bf494d0d1a28c0d31acc7516 1f4f485dfd3cb9578e836ec2dc722f37 y[8] ed30872e07f2b8bd0374eb57d22c614e 09150f6c0d8774a39a6e168211035dc5 y[9] 2988ab46eaca9ec597fb18b4936e66ef 2f0df26e8d1e34da28cbb3af75231372 y[10] 0c7b345434f72d65314328bbb030d0f0 f6d5e47b28ea91008fb11b05017705a8 y[11] be3b2adb83c60a54f9d1d1b2f476f9e3 93eb5695203d2ba6ad815e6a111ea293 y[12] dcc21033f9453d49c8e5a6387f588b1e a4f706217c151e05f55a6eb7997be09d y[13] 56a326a32f9cba1fbe1c07bb49fa04ce cf9df1a1b815483c75d7a27cc88ad1b1 y[14] 238e5ea986b53e087045723ce16187ed a22e33b2c70709e53251025abde89396 y[15] 45fc8c0693e97763928f00b2e3c75af3 942d8ddaee81b59a6f1f67efda0ef81d y[16] 11873b59137f67800b35e81b01563d18 7c4a1575a1acb92d087b517a8833383f
y[17] 05d357ef4678de0c57ff9f1b2da61dfd
e5d88318bcdde4d9061cc75c2de3cd47
y[18] 40dd7739ca3ef66f1930026f47d9ebaa
713b07176f76f953e1c2e7f8f271a6ca
y[19] 375dbfb83d719b1635a7d8a138919579
44b1c29bb101913e166e11bd5f34186f
y[20] a6c0a555c9026b256a6860f4866bd6d0
b5bf90627086c6149133f8282ce6c9b3
y[21] 622442443d5eca959d6c14ca8389d12c
4068b503e4e3c39b635bea245d9d05a2
y[22] 558f249c9661c0427d2e489ca5b5dde2
20a90333f4862aec793223c781997da9
y[23] 8266c12c50ea28b2c438e7a379eb106e
ca0c7fd6006e9bf612f3ea0a454ba3bd
y[24] b76e8027992e60de01e9094fddeb3349
883914fb17a9621ab929d970d101e45f
y[25] 8278c14b032bcab02bd15692d21b6c5c
204abbf077d465553bd6eda645e6c306
y[26] 5d33b10d518a61e15ed0f092c3222628
1a29c8a0f50cde0a8c66236e29c2f310
y[27] a375cebda1dc6bb9a1a01dae6c7aba8e
bedc6371a7d52aacb955f83bd6e4f84d
y[28] 2949dcc198fb77c7e5cdf6040b0f84fa
f82808bf985577f0a2acf2ec7ed7c0b0
y[29] ae8a270e951743ff23e0b2dd12e9c3c8
28fb5598a22461af94d568f29240ba28
y[30] 20c4591f71c088f96e095dd98beae456
579ebbba36f6d9ca2613d1c26eee4d8c
y[31] 73217ac5962b5f3147b492e8831597fd
89b64aa7fde82e1974d2f6779504dc21
y[32] 435eb3109350756b9fdabe1c6f368081
bd40b27ebcb9819a75d7df8bb07bb05d
y[33] b1bab705a4b7e37125186339464ad8fa
aa4f052cc1272919fde3e025bb64aa8e
y[34] 0eb1fcbfcc25acb5f718ce4f7c2182fb
393a1814b0e942490e52d3bca817b2b2
y[35] 6e90d4c9b0cc38608a6cef5eb153af08
58acc867c9922aed43bb67d7b33acc51
y[36] 9313d28d41a5c6fe6cf3595dd5ee63f0
a4c4065a083590b275788bee7ad875a7
y[37] f88dd73720708c6c6c0ecf1f43bbaada
e6f208557fdc07bd4ed91f88ce4c0de8
y[38] 42761c70c186bfdafafc444834bd3418
be4253a71eaf41d718753ad07754ca3e
y[39] ffd5960b0336981795721426803599ed
5b2b7516920efcbe32ada4bcf6c73bd2
y[40] 9e3fa152d9adeca36020fdeeee1b7395
21d3ea8c0da497003df1513897b0f547
y[41] 94a873670b8d93bcca2ae47e64424b74
23e1f078d9554bb5232cc6de8aae9b83
y[42] fa5b9510beb39ccf4b4e1d9c0f19d5e1
7f58e5b8705d9a6837a7d9bf99cd1338
y[43] 7af256a8491671f1f2f22af253bcff54
b673199bdb7d05d81064ef05f80f0153
y[44] d0be7919684b23da8d42ff3effdb7ca0
985033f389181f47659138003d712b5e
y[45] c0a614d31cc7487f52de8664916af79c
98456b2c94a8038083db55391e347586
y[46] 2250274a1de2584fec975fb09536792c
fbfcf6192856cc76eb5b13dc4709e2f7
y[47] 301ddff26ec1b23de2d188c999166c74
e1e14bbc15f457cf4e471ae13dcbdd9c
y[48] 50f4d646fc6278e8fe7eb6cb5c94100f
a870187380b777ed19d7868fd8ca7ceb
y[49] 7fa7d5cc861c5bdac98e7495eb0a2cee
c1924ae979f44c5390ebedddc65d6ec1
y[50] 1287d978b8df064219bc5679f7d7b264
a76ff272b2ac9f2f7cfc9fdcfb6a5142
y[51] 8240027afd9d52a79b647c90c2709e06
0ed70f87299dd798d68f4fadd3da6c51
y[52] d839f851f98f67840b964ebe73f8cec4
1572538ec6bc131034ca2894eb736b3b
y[53] da93d9f5f6fa6f6c0f03ce43362b8414
940355fb54d3dfdd03633ae108f3de3e
y[54] bc85a3ff51efeea3bc2cf27e1658f178
9ee612c83d0f5fd56f7cd071930e2946
y[55] beeecaa04dccea9f97786001475e0294
bc2852f62eb5d39bb9fbeef75916efe4
y[56] 4a662ecae37ede27e9d6eadfdeb8f8b2
b2dbccbf96fa6dbaf7321fb0e701f4d4
y[57] 29c2f4dcd153a2742574126e5eaccc77
686acf6e3ee48f423766e0fc466810a9
y[58] 05ff5453ec99897b56bc55dd49b99114
2f65043f2d744eeb935ba7f4ef23cf80
y[59] cc5a8a335d3619d781e7454826df720e
ec82e06034c44699b5f0c44a8787752e
y[60] 057fa3419b5bb0e25d30981e41cb1361
322dba8f69931cf42fad3f3bce6ded5b
y[61] 8bfc3d20a2148861b2afc14562ddd27f
12897abf0685288dcc5c4982f8260268
y[62] 46a24bf77e383c7aacab1ab692b29ed8
c018a65f3dc2b87ff619a633c41b4fad
y[63] b1c78725c1f8f922f6009787b1964247
df0136b1bc614ab575c59a16d089917b
y[64] d4a8b6f04d95c581279a139be09fcf6e
98a470a0bceca191fce476f9370021cb
y[65] c05518a7efd35d89d8577c990a5e1996
1ba16203c959c91829ba7497cffcbb4b
y[66] 294546454fa5388a23a22e805a5ca35f
956598848bda678615fec28afd5da61a
--------------------------------------------
LMS type 00000006 # LM_SHA256_M32_H10
path[0] b326493313053ced3876db9d23714818
1b7173bc7d042cefb4dbe94d2e58cd21
path[1] a769db4657a103279ba8ef3a629ca84e
e836172a9c50e51f45581741cf808315
path[2] 0b491cb4ecbbabec128e7c81a46e62a6
7b57640a0a78be1cbf7dd9d419a10cd8
path[3] 686d16621a80816bfdb5bdc56211d72c
a70b81f1117d129529a7570cf79cf52a
path[4] 7028a48538ecdd3b38d3d5d62d262465
95c4fb73a525a5ed2c30524ebb1d8cc8
path[5] 2e0c19bc4977c6898ff95fd3d310b0ba
e71696cef93c6a552456bf96e9d075e3
path[6] 83bb7543c675842bafbfc7cdb88483b3
276c29d4f0a341c2d406e40d4653b7e4
path[7] d045851acf6a0a0ea9c710b805cced46
35ee8c107362f0fc8d80c14d0ac49c51
path[8] 6703d26d14752f34c1c0d2c4247581c1
8c2cf4de48e9ce949be7c888e9caebe4
path[9] a415e291fd107d21dc1f084b11582082
49f28f4f7c7e931ba7b3bd0d824a4570
--------------------------------------------
LMS public key
LMS type 00000005 # LM_SHA256_M32_H5
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
I 215f83b7ccb9acbcd08db97b0d04dc2b
K a1cd035833e0e90059603f26e07ad2aa
d152338e7a5e5984bcd5f7bb4eba40b7
--------------------------------------------
final_signature:
--------------------------------------------
LMS signature
q 00000004
--------------------------------------------
LMOTS signature
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
C 0eb1ed54a2460d512388cad533138d24
0534e97b1e82d33bd927d201dfc24ebb
y[0] 11b3649023696f85150b189e50c00e98
850ac343a77b3638319c347d7310269d
y[1] 3b7714fa406b8c35b021d54d4fdada7b
9ce5d4ba5b06719e72aaf58c5aae7aca
y[2] 057aa0e2e74e7dcfd17a0823429db629
65b7d563c57b4cec942cc865e29c1dad
y[3] 83cac8b4d61aacc457f336e6a10b6632
3f5887bf3523dfcadee158503bfaa89d
y[4] c6bf59daa82afd2b5ebb2a9ca6572a60
67cee7c327e9039b3b6ea6a1edc7fdc3
y[5] df927aade10c1c9f2d5ff446450d2a39
98d0f9f6202b5e07c3f97d2458c69d3c
y[6] 8190643978d7a7f4d64e97e3f1c4a08a
7c5bc03fd55682c017e2907eab07e5bb
y[7] 2f190143475a6043d5e6d5263471f4ee
cf6e2575fbc6ff37edfa249d6cda1a09
y[8] f797fd5a3cd53a066700f45863f04b6c
8a58cfd341241e002d0d2c0217472bf1
y[9] 8b636ae547c1771368d9f317835c9b0e
f430b3df4034f6af00d0da44f4af7800
y[10] bc7a5cf8a5abdb12dc718b559b74cab9
090e33cc58a955300981c420c4da8ffd
y[11] 67df540890a062fe40dba8b2c1c548ce
d22473219c534911d48ccaabfb71bc71
y[12] 862f4a24ebd376d288fd4e6fb06ed870
5787c5fedc813cd2697e5b1aac1ced45
y[13] 767b14ce88409eaebb601a93559aae89
3e143d1c395bc326da821d79a9ed41dc
y[14] fbe549147f71c092f4f3ac522b5cc572
90706650487bae9bb5671ecc9ccc2ce5
y[15] 1ead87ac01985268521222fb9057df7e
d41810b5ef0d4f7cc67368c90f573b1a
y[16] c2ce956c365ed38e893ce7b2fae15d36
85a3df2fa3d4cc098fa57dd60d2c9754
y[17] a8ade980ad0f93f6787075c3f680a2ba
1936a8c61d1af52ab7e21f416be09d2a
y[18] 8d64c3d3d8582968c2839902229f85ae
e297e717c094c8df4a23bb5db658dd37
y[19] 7bf0f4ff3ffd8fba5e383a48574802ed
545bbe7a6b4753533353d73706067640
y[20] 135a7ce517279cd683039747d218647c
86e097b0daa2872d54b8f3e508598762
y[21] 9547b830d8118161b65079fe7bc59a99
e9c3c7380e3e70b7138fe5d9be255150
y[22] 2b698d09ae193972f27d40f38dea264a
0126e637d74ae4c92a6249fa103436d3
y[23] eb0d4029ac712bfc7a5eacbdd7518d6d
4fe903a5ae65527cd65bb0d4e9925ca2
y[24] 4fd7214dc617c150544e423f450c99ce
51ac8005d33acd74f1bed3b17b7266a4
y[25] a3bb86da7eba80b101e15cb79de9a207
852cf91249ef480619ff2af8cabca831
y[26] 25d1faa94cbb0a03a906f683b3f47a97
c871fd513e510a7a25f283b196075778
y[27] 496152a91c2bf9da76ebe089f4654877
f2d586ae7149c406e663eadeb2b5c7e8
y[28] 2429b9e8cb4834c83464f079995332e4
b3c8f5a72bb4b8c6f74b0d45dc6c1f79
y[29] 952c0b7420df525e37c15377b5f09843
19c3993921e5ccd97e097592064530d3
y[30] 3de3afad5733cbe7703c5296263f7734
2efbf5a04755b0b3c997c4328463e84c
y[31] aa2de3ffdcd297baaaacd7ae646e44b5
c0f16044df38fabd296a47b3a838a913
y[32] 982fb2e370c078edb042c84db34ce36b
46ccb76460a690cc86c302457dd1cde1
y[33] 97ec8075e82b393d542075134e2a17ee
70a5e187075d03ae3c853cff60729ba4
--------------------------------------------
LMS type 00000005 # LM_SHA256_M32_H5
path[0] 4de1f6965bdabc676c5a4dc7c35f97f8
2cb0e31c68d04f1dad96314ff09e6b3d
path[1] e96aeee300d1f68bf1bca9fc58e40323
36cd819aaf578744e50d1357a0e42867
path[2] 04d341aa0a337b19fe4bc43c2e79964d
4f351089f2e0e41c7c43ae0d49e7f404
path[3] b0f75be80ea3af098c9752420a8ac0ea
2bbb1f4eeba05238aef0d8ce63f0c6e5
path[4] e4041d95398a6f7f3e0ee97cc1591849
d4ed236338b147abde9f51ef9fd4e1c1Acknowledgements ✨
okay bestie, time for the shoutouts 🫶 Huge thanks to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric Osterweil, Ahmed Kosba, Russ Housley, Philip Lafrance, Alexander Truskovsky, Mark Peruzel, and Jim Schaad for helpful suggestions and really detailed reviews 💖
We especially want to acknowledge Jerry Solinas, Laurie Law, and Kevin Igoe, who spotted the security benefits of the approach of Leighton and Micali [USPTO5432852] 🙌 Jonathan Katz gave us security guidance 🔐, and Bruno Couillard and Jim Goodman did an especially thorough review 💅 iconic behaviour, honestly.
Authors' Addresses 🎀
- David McGrew
- Cisco Systems
- 13600 Dulles Technology Drive
- Herndon, VA 20171
- United States of America
- Email: mcgrew@cisco.com
- Michael Curcio
- Cisco Systems
- 7025-2 Kit Creek Road
- Research Triangle Park, NC 27709-4987
- United States of America
- Email: micurcio@cisco.com
- Scott Fluhrer
- Cisco Systems
- 170 West Tasman Drive
- San Jose, CA
- United States of America
- Email: sfluhrer@cisco.com
That's the whole RFC, bestie 🌈✨ Hash-based signatures, fully served. Periodt 💅👑
📦 where this page comes from
- ietf: rfc8554 2019-04
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms