Tech-invite   3GPPspecs   RFCs   Search in Tech-invite

868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100IETF‑orgGroupsStats
in Index   Prev   Next

RFC 8554

Leighton-Micali Hash-Based Signatures

Pages: 61
Group: IRTF
Informational
Part 1 of 4 – Pages 1 to 18
None   None   Next

Top   ToC   RFC8554 - Page 1
Internet Research Task Force (IRTF)                            D. McGrew
Request for Comments: 8554                                     M. Curcio
Category: Informational                                       S. Fluhrer
ISSN: 2070-1721                                            Cisco Systems
                                                              April 2019


                 Leighton-Micali Hash-Based Signatures

Abstract

   This note describes a digital-signature system based on cryptographic
   hash functions, following the seminal work in this area 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.  These systems provide asymmetric authentication
   without using large integer mathematics and can achieve a high
   security level.  They are suitable for compact implementations, are
   relatively simple to implement, and are naturally resistant to side-
   channel attacks.  Unlike many other signature systems, hash-based
   signatures would still be secure even if it proves feasible for an
   attacker to build a quantum computer.

   This document is a product of the Crypto Forum Research Group (CFRG)
   in the IRTF.  This has been reviewed by many researchers, both in the
   research group and outside of it.  The Acknowledgements section lists
   many of them.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Research Task Force
   (IRTF).  The IRTF publishes the results of Internet-related research
   and development activities.  These results might not be suitable for
   deployment.  This RFC represents the consensus of the Crypto Forum
   Research Group of the Internet Research Task Force (IRTF).  Documents
   approved for publication by the IRSG are not candidates for any level
   of Internet Standard; see Section 2 of RFC 7841.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   https://www.rfc-editor.org/info/rfc8554.
Top   ToC   RFC8554 - Page 2
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 of this document.  Please review these documents
   carefully, as 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
Top   ToC   RFC8554 - Page 3
   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  . . . . . . . . . . . . . . . . . . . . . . .  61

1.  Introduction

   One-time signature systems, and general-purpose signature systems
   built out of one-time signature systems, have been known since 1979
   [Merkle79], were well studied in the 1990s [USPTO5432852], and have
   benefited from renewed attention in the last decade.  The
   characteristics of these signature systems are small private and
   public keys and fast signature generation and verification, but large
   signatures and moderately slow key generation (in comparison with RSA
   and ECDSA (Elliptic Curve Digital Signature Algorithm)).  Private
   keys can be made very small by appropriate key generation, for
   example, as described in Appendix A.  In recent years, there has been
   interest in these systems because of their post-quantum security and
   their suitability for 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
   general signature system [Merkle79] with enough specificity to ensure
   interoperability between implementations.

   A signature system provides asymmetric message authentication.  The
   key-generation algorithm produces a public/private key pair.  A
   message is signed by a private key, producing a signature, and a
   message/signature pair can be verified by a public key.  A One-Time
   Signature (OTS) system can be used to sign one message securely but
   will become insecure if more than one is signed with the same public/
Top   ToC   RFC8554 - Page 4
   private key pair.  An N-time signature system can be used to sign N
   or fewer messages securely.  A Merkle-tree signature scheme is an
   N-time signature system that uses an OTS system as a component.

   In the Merkle scheme, a binary tree of height h is used to hold 2^h
   OTS key pairs.  Each interior node of the tree holds a value that is
   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), while the private key of the tree is the collection of
   all the OTS private keys, together with the index of the next OTS
   private key to sign the next message with.

   In this note, we describe the Leighton-Micali Signature (LMS) system
   (a variant of the Merkle scheme) with the Hierarchical Signature
   System (HSS) built on top of it that allows it to efficiently scale
   to larger numbers of signatures.  In order to support signing a large
   number of messages on resource-constrained systems, the Merkle tree
   can be subdivided into a number of smaller trees.  Only the
   bottommost tree is used to sign messages, while trees above that are
   used to sign the public keys of their children.  For example, in the
   simplest case with two levels with both levels consisting of height h
   trees, the root tree is used to sign 2^h trees with 2^h OTS key
   pairs, and each second-level tree has 2^h OTS key pairs, for a total
   of 2^(2h) bottom-level key pairs, and so can sign 2^(2h) messages.
   The advantage of this scheme is that only the active trees need to be
   instantiated, which saves both time (for key generation) and space
   (for key storage).  On the other hand, using a multilevel signature
   scheme increases the size of the signature as well as the signature
   verification time.

   This note is structured as follows.  Notes on post-quantum
   cryptography are discussed in Section 1.1.  Intellectual property
   issues are discussed in Section 1.2.  The notation used within this
   note 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 described in Section 4, and the LMS and HSS N-time signature
   systems are described in Sections 5 and 6, respectively.  Sufficient
   detail is provided to ensure interoperability.  The rationale for the
   design decisions is given in Section 7.  The IANA registry for these
   signature systems is described in Section 8.  Security considerations
   are presented in Section 9.  Comparison with another hash-based
   signature algorithm (eXtended Merkle Signature Scheme (XMSS)) is in
   Section 10.

   This document represents the rough consensus of the CFRG.
Top   ToC   RFC8554 - Page 5
1.1.  CFRG Note on Post-Quantum Cryptography

   All post-quantum algorithms documented by the Crypto Forum Research
   Group (CFRG) are today considered ready for experimentation and
   further engineering development (e.g., to establish the impact of
   performance and sizes on IETF protocols).  However, at the time of
   writing, we do not have significant deployment experience with such
   algorithms.

   Many of these algorithms come with specific restrictions, e.g.,
   change of classical interface or less cryptanalysis of proposed
   parameters than established schemes.  The CFRG has consensus that all
   documents describing post-quantum technologies include the above
   paragraph and a clear additional warning about any specific
   restrictions, especially as those might affect use or deployment of
   the specific scheme.  That guidance may be changed over time via
   document updates.

   Additionally, for LMS:

   CFRG consensus is that we are confident in the cryptographic security
   of the signature schemes described in this document against quantum
   computers, given the current state of the research community's
   knowledge about quantum algorithms.  Indeed, we are confident that
   the security of a significant part of the Internet could be made
   dependent on the signature schemes defined in this document, if
   developers take care of the following.

   In contrast to traditional signature schemes, the signature schemes
   described in this document are stateful, meaning the secret key
   changes over time.  If a secret key state is used twice, no
   cryptographic security guarantees remain.  In consequence, it becomes
   feasible to forge a signature on a new message.  This is a new
   property that most developers will not be familiar with and requires
   careful handling of secret keys.  Developers should not use the
   schemes described here except in systems that prevent the reuse of
   secret key states.

   Note that the fact that the schemes described in this document are
   stateful also implies that classical APIs for digital signatures
   cannot be used without modification.  The API MUST be able to handle
   a dynamic secret key state; that is, the API MUST allow the
   signature-generation algorithm to update the secret key state.
Top   ToC   RFC8554 - Page 6
1.2.  Intellectual Property

   This document is based on U.S. Patent 5,432,852, which was issued
   over twenty years ago and is thus expired.

1.2.1.  Disclaimer

   This document is not intended as legal advice.  Readers are advised
   to consult with their own legal advisers if they would like a legal
   interpretation of their rights.

   The IETF policies and processes regarding 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 is used to sign one message, it
   MUST NOT be used to sign another.

   The key-generation algorithm takes as input an indication of the
   parameters for the signature system.  If it is successful, it returns
   both a private key and a public key.  Otherwise, it returns an
   indication of failure.

   The signing algorithm takes as input the message to be signed and the
   current value of the private key.  If successful, it returns a
   signature and the next value of the private key, if there is such a
   value.  After the private key of an N-time signature system has
   signed N messages, the signing algorithm returns the signature and an
   indication that there is no next value of the private key that can be
   used for signing.  If unsuccessful, it returns an indication of
   failure.

   The verification algorithm takes as input the public key, a message,
   and a signature; it returns an indication of whether or not the
   signature-and-message pair is valid.
Top   ToC   RFC8554 - Page 7
   A message/signature pair is valid if the signature was returned by
   the signing algorithm upon input of the message and the private key
   corresponding to the public key; otherwise, the signature and message
   pair is not valid with probability very close to one.

3.  Notation

3.1.  Data Types

   Bytes and byte strings are the fundamental data types.  A single byte
   is denoted as a pair of hexadecimal digits with a leading "0x".  A
   byte string is an ordered sequence of zero or more bytes and is
   denoted 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, in which all 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), which take a nonnegative integer X as input and return
   one-, two-, and four-byte strings, respectively.  We also make use of
   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, mathematical operators are defined as
   follows:

      ^ : 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 b

      AND : a AND b denotes the bitwise AND of the two nonnegative
      integers a and b (represented in binary notation)
Top   ToC   RFC8554 - Page 8
   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 r

      floor(r) : returns the largest integer less than or equal to r

      lg(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 at the left.  Hence, 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 to be 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)) )
Top   ToC   RFC8554 - Page 9
   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 is 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

   The signature and public key formats are formally defined in XDR to
   provide an unambiguous, machine-readable definition [RFC4506].  The
   private key format is not included as it is not needed for
   interoperability and an implementation MAY use any private key
   format.  However, for clarity, we include an example of private key
   data in Test Case 2 of Appendix F.  Though XDR is used, these formats
Top   ToC   RFC8554 - Page 10
   are simple and easy to parse without any special tools.  An
   illustration of the layout of data in these objects is provided
   below.  The definitions are as follows:

   /* one-time signatures */

   enum 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 */
   };
Top   ToC   RFC8554 - Page 11
   /* 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;
Top   ToC   RFC8554 - Page 12
    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;
   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.

   In order to facilitate its use in an N-time signature system, the
   LM-OTS key generation, signing, and verification algorithms all take
   as input parameters I and q.  The parameter I is a 16-byte string
   that indicates which Merkle tree this LM-OTS is used with.  The
   parameter 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, the value I MAY be used to differentiate this one-time
   signature from others; however, the value q MUST be set to the all-
   zero value.
Top   ToC   RFC8554 - Page 13
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 are dependent 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; the choice of this value 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 are dependent 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: generate the public key and generate and verify 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).
Top   ToC   RFC8554 - Page 14
      +---------------------+--------+----+---+-----+----+---------+
      | 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 1

   Here 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
Top   ToC   RFC8554 - Page 15
   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) || K

   where 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
Top   ToC   RFC8554 - Page 16
   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

   The LM-OTS signature of a message is generated by doing the following
   in sequence: prepending the LMS key identifier I, the LMS leaf
   identifier q, the value D_MESG (0x8181), and the randomizer C to the
   message; computing the hash; concatenating the checksum of the hash
   to the hash itself; considering the resulting value as a sequence of
   w-bit values; and using each of the w-bit values to determine the
   number of times to apply the function H to the corresponding element
   of the private key.  The outputs of the function H are concatenated
   together and returned as the signature.  The pseudocode for this
   procedure is shown below.

   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
Top   ToC   RFC8554 - Page 17
     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]

   Note that this algorithm results in a signature whose elements are
   intermediate values of the elements computed by the public key
   algorithm in Section 4.3.

   The signature is the string returned by Algorithm 3.  Section 3.3
   formally defines the structure of the string as the lmots_signature
   union.

4.6.  Signature Verification

   In order to verify a message with its signature (an array of n-byte
   strings, denoted as y), the receiver must "complete" the chain of
   iterations of H using the w-bit coefficients of the string resulting
   from the concatenation of the message hash and its checksum.  This
   computation should result in a value that matches the provided public
   key.

   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
Top   ToC   RFC8554 - Page 18
     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.


Next Section