Tech-invite3GPPspaceIETF RFCsSIP
in Index   Prev   Next

RFC 8554

Leighton-Micali Hash-Based Signatures

Pages: 61
Part 3 of 4 – Pages 34 to 44
First   Prev   Next

Top   ToC   RFC8554 - Page 34   prevText

7. Rationale

The goal of this note is to describe the LM-OTS, LMS, and HSS algorithms following the original references and present the modern security analysis of those algorithms. Other signature methods are out of scope and may be interesting follow-on work. We adopt the techniques described by Leighton and Micali to mitigate attacks that amortize their work over multiple invocations of the hash function. The values taken by the identifier I across different LMS public/ private key pairs are chosen randomly in order to improve security. The analysis of this method in [Fluhrer17] shows that we do not need uniqueness to ensure security; we do need to ensure that we don't have a large number of private keys that use the same I value. By randomly selecting 16-byte I values, the chance that, out of 2^64 private keys, 4 or more of them will use the same I value is negligible (that is, has probability less than 2^-128). The reason 16-byte I values were selected was to optimize the Winternitz hash-chain operation. With the current settings, the value being hashed is exactly 55 bytes long (for a 32-byte hash function), which SHA-256 can hash in a single hash-compression operation. Other hash functions may be used in future specifications; all the ones that we will be likely to support (SHA-512/256 and the various SHA-3 hashes) would work well with a 16-byte I value. The signature and public key formats are designed so that they are relatively easy to parse. Each format starts with a 32-bit enumeration value that indicates the details of the signature algorithm and provides all of the information that is needed in order to parse the format.
Top   ToC   RFC8554 - Page 35
   The Checksum (Section 4.4) is calculated using a nonnegative integer
   "sum" whose width was chosen to be an integer number of w-bit fields
   such that it is capable of holding the difference of the total
   possible number of applications of the function H (as defined in the
   signing algorithm of Section 4.5) and the total actual number.  In
   the case that the number of times H is applied is 0, the sum is (2^w
   - 1) * (8*n/w).  Thus, for the purposes of this document, which
   describes signature methods based on H = SHA256 (n = 32 bytes) and w
   = { 1, 2, 4, 8 }, the sum variable is a 16-bit nonnegative integer
   for all combinations of n and w.  The calculation uses the parameter
   ls defined in Section 4.1 and calculated in Appendix B, which
   indicates the number of bits used in the left-shift operation.

7.1. Security String

To improve security against attacks that amortize their effort against multiple invocations of the hash function, Leighton and Micali introduced a "security string" that is distinct for each invocation of that function. Whenever this process computes a hash, the string being hashed will start with a string formed from the fields below. These fields will appear in fixed locations in the value we compute the hash of, and so we list where in the hash these fields would be present. The fields that make up this string are as follows: I A 16-byte identifier for the LMS public/private key pair. It MUST be chosen uniformly at random, or via a pseudorandom process, at the time that a key pair is generated, in order to minimize the probability that any specific value of I be used for a large number of different LMS private keys. This is always bytes 0-15 of the value being hashed. r In the LMS N-time signature scheme, the node number r associated with a particular node of a hash tree is used as an input to the hash used to compute that node. This value is represented as a 32-bit (four byte) unsigned integer in network byte order. Either r or q (depending on the domain-separation parameter) will be bytes 16-19 of the value being hashed. q In the LMS N-time signature scheme, each LM-OTS signature is associated with the leaf of a hash tree, and q is set to the leaf number. This ensures that a distinct value of q is used for each distinct LM-OTS public/private key pair. This value is represented as a 32-bit (four byte) unsigned integer in network byte order. Either r or q (depending on the domain- separation parameter) will be bytes 16-19 of the value being hashed.
Top   ToC   RFC8554 - Page 36
   D     A domain-separation parameter, which is a two-byte identifier
         that takes on different values in the different contexts in
         which the hash function is invoked.  D occurs in bytes 20 and
         21 of the value being hashed and takes on the following values:

            D_PBLC = 0x8080 when computing the hash of all of the
            iterates in the LM-OTS algorithm

            D_MESG = 0x8181 when computing the hash of the message in
            the LM-OTS algorithms

            D_LEAF = 0x8282 when computing the hash of the leaf of an
            LMS tree

            D_INTR = 0x8383 when computing the hash of an interior node
            of an LMS tree

   i     A value between 0 and 264; this is used in the LM-OTS scheme
         when either computing the iterations of the Winternitz chain or
         using the suggested LM-OTS private key generation process.  It
         is represented as a 16-bit (two-byte) unsigned integer in
         network byte order.  If present, it occurs at bytes 20 and 21
         of the value being hashed.

   j     In the LM-OTS scheme, j is the iteration number used when the
         private key element is being iteratively hashed.  It is
         represented as an 8-bit (one byte) unsigned integer and is
         present if i is a value between 0 and 264.  If present, it
         occurs at bytes 22 to 21+n of the value being hashed.

   C     An n-byte randomizer that is included with the message whenever
         it is being hashed to improve security.  C MUST be chosen
         uniformly at random or via another unpredictable process.  It
         is present if D=D_MESG, and it occurs at bytes 22 to 21+n of
         the value being hashed.

8. IANA Considerations

IANA has created two registries: "LM-OTS Signatures", which includes all of the LM-OTS signatures as defined in Section 4, and "Leighton- Micali Signatures (LMS)" for LMS as defined in Section 5. Additions to these registries require that a specification be documented in an RFC or another permanent and readily available reference in sufficient detail that interoperability between independent implementations is possible [RFC8126]. IANA MUST verify that all applications for additions to these registries have first been reviewed by the IRTF Crypto Forum Research Group (CFRG).
Top   ToC   RFC8554 - Page 37
   Each entry in either of the registries contains the following

      a short name (Name), such as "LMS_SHA256_M32_H10",

      a positive number (Numeric Identifier), and

      a Reference to a specification that completely defines the
      signature-method test cases that can be used to verify the
      correctness of an implementation.

   The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF
   (decimal 4,294,967,295), inclusive, will not be assigned by IANA and
   are reserved for private use; no attempt will be made to prevent
   multiple sites from using the same value in different (and
   incompatible) ways [RFC8126].

   The initial contents of the "LM-OTS Signatures" registry are as

    | 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
Top   ToC   RFC8554 - Page 38
   The initial contents of the "Leighton Micali Signatures (LMS)"
   registry are as follows.

    | Name                     | Reference |    Numeric Identifier    |
    | Reserved                 |           |        0x0 - 0x4         |
    |                          |           |                          |
    | LMS_SHA256_M32_H5        | Section 5 |        0x00000005        |
    |                          |           |                          |
    | LMS_SHA256_M32_H10       | Section 5 |        0x00000006        |
    |                          |           |                          |
    | LMS_SHA256_M32_H15       | Section 5 |        0x00000007        |
    |                          |           |                          |
    | LMS_SHA256_M32_H20       | Section 5 |        0x00000008        |
    |                          |           |                          |
    | LMS_SHA256_M32_H25       | Section 5 |        0x00000009        |
    |                          |           |                          |
    | Unassigned               |           | 0x0000000A - 0xDDDDDDDC  |
    |                          |           |                          |
    | Reserved for Private Use |           | 0xDDDDDDDD - 0xFFFFFFFF  |

                                  Table 5

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

   Currently, the two registries assign a disjoint set of values to the
   defined parameter sets.  This coincidence is a historical accident;
   the correctness of the system does not depend on this.  IANA is not
   required to maintain this situation.

9. Security Considerations

The hash function H MUST have second preimage resistance: it must be computationally infeasible for an attacker that is given one message M to be able to find a second message M' such that H(M) = H(M'). The security goal of a signature system is to prevent forgeries. A successful forgery occurs when an attacker who does not know the private key associated with a public key can find a message (distinct from all previously signed ones) and signature that is valid with that public key (that is, the Signature Verification algorithm applied to that signature and message and public key will return VALID). Such an attacker, in the strongest case, may have the ability to forge valid signatures for an arbitrary number of other messages.
Top   ToC   RFC8554 - Page 39
   LMS is provably secure in the random oracle model, as shown by
   [Katz16].  In addition, further analysis is done by [Fluhrer17],
   where the hash compression function (rather than the entire hash
   function) is considered to be a random oracle.  Corollary 1 of the
   latter paper states:

      If we have no more than 2^64 randomly chosen LMS private keys,
      allow the attacker access to a signing oracle and a SHA-256 hash
      compression oracle, and allow a maximum of 2^120 hash compression
      computations, then the probability of an attacker being able to
      generate a single forgery against any of those LMS keys is less
      than 2^-129.

   Many of the objects within the public key and the signature start
   with a typecode.  A verifier MUST check each of these typecodes, and
   a verification operation on a signature with an unknown type, or a
   type that does not correspond to the type within the public key, MUST
   return INVALID.  The expected length of a variable-length object can
   be determined from its typecode; if an object has a different length,
   then any signature computed from the object is INVALID.

9.1. Hash Formats

The format of the inputs to the hash function H has the property that each invocation of that function has an input that is repeated by a small bounded number of other inputs (due to potential repeats of the I value). In particular, it will vary somewhere in the first 23 bytes of the value being hashed. This property is important for a proof of security in the random oracle model. The formats used during key generation and signing (including the recommended pseudorandom key-generation procedure in Appendix A) are as follows: I || u32str(q) || u16str(i) || u8str(j) || tmp I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1] I || u32str(q) || u16str(D_MESG) || C || message I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h] I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1] I || u32str(q) || u16str(i) || u8str(0xff) || SEED Each hash type listed is distinct; at locations 20 and 21 of the value being hashed, there exists either a fixed value D_PBLC, D_MESG, D_LEAF, D_INTR, or a 16-bit value i. These fixed values are distinct from each other and are large (over 32768), while the 16-bit values of i are small (currently no more than 265; possibly being slightly larger if larger hash functions are supported); hence, the range of possible values of i will not collide any of the D_PBLC, D_MESG,
Top   ToC   RFC8554 - Page 40
   D_LEAF, D_INTR identifiers.  The only other collision possibility is
   the Winternitz chain hash colliding with the recommended pseudorandom
   key-generation process; here, at location 22 of the value being
   hashed, the Winternitz chain function has the value u8str(j), where j
   is a value between 0 and 254, while location 22 of the recommended
   pseudorandom key-generation process has value 255.

   For the Winternitz chaining function, D_PBLC, and D_MESG, the value
   of I || u32str(q) is distinct for each LMS leaf (or equivalently, for
   each q value).  For the Winternitz chaining function, the value of
   u16str(i) || u8str(j) is distinct for each invocation of H for a
   given leaf.  For D_PBLC and D_MESG, the input format is used only
   once for each value of q and, thus, distinctness is assured.  The
   formats for D_INTR and D_LEAF are used exactly once for each value of
   r, which ensures their distinctness.  For the recommended
   pseudorandom key-generation process, for a given value of I, q and j
   are distinct for each invocation of H.

   The value of I is chosen uniformly at random from the set of all
   128-bit strings.  If 2^64 public keys are generated (and, hence, 2^64
   random I values), there is a nontrivial probability of a duplicate
   (which would imply duplicate prefixes).  However, there will be an
   extremely high probability there will not be a four-way collision
   (that is, any I value used for four distinct LMS keys; probability <
   2^-132), and, hence, the number of repeats for any specific prefix
   will be limited to at most three.  This is shown (in [Fluhrer17]) to
   have only a limited effect on the security of the system.

9.2. Stateful Signature Algorithm

The LMS signature system, like all N-time signature systems, requires that the signer maintain state across different invocations of the signing algorithm to ensure that none of the component one-time signature systems are used more than once. This section calls out some important practical considerations around this statefulness. These issues are discussed in greater detail in [STMGMT]. In a typical computing environment, a private key will be stored in nonvolatile media such as on a hard drive. Before it is used to sign a message, it will be read into an application's Random-Access Memory (RAM). After a signature is generated, the value of the private key will need to be updated by writing the new value of the private key into nonvolatile storage. It is essential for security that the application ensures that this value is actually written into that storage, yet there may be one or more memory caches between it and the application. Memory caching is commonly done in the file system and in a physical memory unit on the hard disk that is dedicated to that purpose. To ensure that the updated value is written to
Top   ToC   RFC8554 - Page 41
   physical media, the application may need to take several special
   steps.  In a POSIX environment, for instance, the O_SYNC flag (for
   the open() system call) will cause invocations of the write() system
   call to block the calling process until the data has been written to
   the underlying hardware.  However, if that hardware has its own
   memory cache, it must be separately dealt with using an operating
   system or device-specific tool such as hdparm to flush the on-drive
   cache or turn off write caching for that drive.  Because these
   details vary across different operating systems and devices, this
   note does not attempt to provide complete guidance; instead, we call
   the implementer's attention to these issues.

   When hierarchical signatures are used, an easy way to minimize the
   private key synchronization issues is to have the private key for the
   second-level resident in RAM only and never write that value into
   nonvolatile memory.  A new second-level public/private key pair will
   be generated whenever the application (re)starts; thus, failures such
   as a power outage or application crash are automatically
   accommodated.  Implementations SHOULD use this approach wherever

9.3. Security of LM-OTS Checksum

To show the security of LM-OTS checksum, we consider the signature y of a message with a private key x and let h = H(message) and c = Cksm(H(message)) (see Section 4.5). To attempt a forgery, an attacker may try to change the values of h and c. Let h' and c' denote the values used in the forgery attempt. If for some integer j in the range 0 to u, where u = ceil(8*n/w) is the size of the range that the checksum value can cover, inclusive, a' = coef(h', j, w), a = coef(h, j, w), and a' > a
Top   ToC   RFC8554 - Page 42
   then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by
   iteratively applying function F to the j-th term of the signature an
   additional (a' - a) times.  However, as a result of the increased
   number of hashing iterations, the checksum value c' will decrease
   from its original value of c.  Thus, a valid signature's checksum
   will have, for some number k in the range u to (p-1), inclusive,

      b' = coef(c', k, w),

      b = coef(c, k, w), and

      b' < b

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

10. Comparison with Other Work

The eXtended Merkle Signature Scheme (XMSS) is similar to HSS in several ways [XMSS][RFC8391]. Both are stateful hash-based signature schemes, and both use a hierarchical approach, with a Merkle tree at each level of the hierarchy. XMSS signatures are slightly shorter than HSS signatures, for equivalent security and an equal number of signatures. HSS has several advantages over XMSS. HSS operations are roughly four times faster than the comparable XMSS ones, when SHA256 is used as the underlying hash. This occurs because the hash operation done as a part of the Winternitz iterations dominates performance, and XMSS performs four compression-function invocations (two for the PRF, two for the F function) where HSS only needs to perform one. Additionally, HSS is somewhat simpler (as each hash invocation is just a prefix followed by the data being hashed).
Top   ToC   RFC8554 - Page 43

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, <>. [RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, <>. [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, <>. [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <>. [RFC8179] Bradner, S. and J. Contreras, "Intellectual Property Rights in IETF Technology", BCP 79, RFC 8179, DOI 10.17487/RFC8179, May 2017, <>. [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.
Top   ToC   RFC8554 - Page 44
              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,

              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,

              Fluhrer, S., "Further Analysis of a Proposed Hash-Based
              Signature Standard", Cryptology ePrint Archive Report
              2017/553, 2017, <>.

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

              Merkle, R., "Secrecy, Authentication, and Public Key
              Systems", Technical Report No. 1979-1, Information Systems
              Laboratory, Stanford University, 1979,

   [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,

   [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,

   [XMSS]     Buchmann, J., Dahmen, E., and , "XMSS -- A Practical
              Forward Secure Signature Scheme Based on Minimal Security
              Assumptions.", in PQCrypto 2011: Post-Quantum Cryptography
              pp. 117-129, Lecture Notes in Computer Science Vol. 7071,
              DOI 10.1007/978-3-642-25405-5_8, 2011.

(next page on part 4)

Next Section