Internet-Draft Additional LMS Signatures April 2021
Fluhrer & Dang Expires 4 October 2021 [Page]
Crypto Forum Research Group
Intended Status:
S. Fluhrer
Cisco Systems
Q. Dang

Additional Parameter sets for LMS Hash-Based Signatures


This note extends LMS (RFC 8554) by defining parameter sets by including additional hash functions. Hese include hash functions that result in signatures with significantly smaller than the signatures using the current parameter sets, and should have sufficient security.

This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 3 October 2021.

Table of Contents

1. Introduction

Stateful hash based signatures have small private and public keys, are efficient to compute, and are believed to have excellent security. One disadvantage is that the signatures they produce tend to be somewhat large (possibly 1k - 4kbytes). What this draft explores are a set of parameter sets to the LMS (RFC8554) stateful hash based signature method that reduce the size of the signature significantly.

1.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 [RFC3979] and [RFC4879] and at

2. Conventions Used In This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

3. Additional Hash Function Definitions

3.1. 192 bit Hash Function based on SHA256

This document defines a SHA-2 based hash function with a 192 bit output. As such, we define SHA256-192 as a truncated version of SHA256 [FIPS180]. That is, it is the result of performing a SHA256 operation to a message, and then omitting the final 64 bits of the output. It is the same procedure used to define SHA224, except that we use the SHA256 IV (rather than using one dedicated to SHA256-192), and you truncate 64 bits, rather than 32.

The following test vector may illustrate this:

  SHA256("abc")     = ba7816bf 8f01cfea 414140de 5dae2223
                      b00361a3 96177a9c b410ff61 f20015ad
  SHA256-192("abc") = ba7816bf 8f01cfea 414140de 5dae2223
                      b00361a3 96177a9c

We use the same IV as the untruncated SHA256, rather than defining a distinct one, so that we can use a standard SHA256 hash implementation without modification. In addition, the fact that you get partial knowledge of the SHA256 hash of a message by examining the SHA256-192 hash of the same message is not a concern for this application. Each message that is hashed is randomized. Any message being signed includes the C randomizer which varies per message; in addition, all hashes include the I identifier, which varies depending on the public key. Therefore, signing the same message by SHA256 and by SHA256-192 will not result in the same value being hashed, and so the latter hash value is not a prefix of the former one.

3.2. 256 bit Hash Function based on SHAKE256

This document defines a SHAKE-based hash function with a 256 bit output. As such, we define SHAKE256-256 as a hash where you submit the preimage to the SHAKE256 XOF, with the output being 256 bits, see FIPS 202 [FIPS202] for more detail.

3.3. 192 bit Hash Function based on SHAKE256

This document defines a SHAKE-based hash function with a 192 bit output. As such, we define SHAKE256-192 as a hash where you submit the preimage to the SHAKE256 XOF, with the output being 192 bits, see FIPS 202 [FIPS202] for more detail.

4. Additional LM-OTS Parameter Sets

Here is a table with the LM-OTS parameters defined that use the above hashes:

Table 1
Parameter Set Name H n w p ls id
LMOTS_SHA256_N24_W1 SHA256-192 24 1 200 8 TBD1
LMOTS_SHA256_N24_W2 SHA256-192 24 2 101 6 TBD2
LMOTS_SHA256_N24_W4 SHA256-192 24 4 51 4 TBD3
LMOTS_SHA256_N24_W8 SHA256-192 24 8 26 0 TBD4
LMOTS_SHAKE_N32_W1 SHAKE256-256 32 1 265 7 TBD5
LMOTS_SHAKE_N32_W2 SHAKE256-256 32 2 133 6 TBD6
LMOTS_SHAKE_N32_W4 SHAKE256-256 32 4 67 4 TBD7
LMOTS_SHAKE_N32_W8 SHAKE256-256 32 8 34 0 TBD8
LMOTS_SHAKE_N24_W1 SHAKE256-192 24 1 200 8 TBD9
LMOTS_SHAKE_N24_W2 SHAKE256-192 24 2 101 6 TBD10
LMOTS_SHAKE_N24_W4 SHAKE256-192 24 4 51 4 TBD11
LMOTS_SHAKE_N24_W8 SHAKE256-192 24 8 26 0 TBD12

The id is the IANA-defined identifier used to denote this specific parameter set, and which appears in both public keys and signatures.

The SHA256_N24, SHAKE_N32, SHAKE_N24 in the parameter set name denote the SHA256-192, SHAKE256-256 and SHAKE256-192 hash functions defined in Section 3.

Remember that the C message randomizer (which is included in the signature) is the size of the hash n, and so it shrinks from 32 bytes to 24 bytes for those the parameter sets that use either SHA256-192 or SHAKE256-192.

5. Additional LM Parameter Sets

Here is a table with the LM parameters defined that use SHA256-192, SHAKE256-256 and SHAKE256-192 hash functions:

Table 2
Parameter Set Name H m h id
LMS_SHA256_M24_H5 SHA256-192 24 5 TBD13
LMS_SHA256_M24_H10 SHA256-192 24 10 TBD14
LMS_SHA256_M24_H15 SHA256-192 24 15 TBD15
LMS_SHA256_M24_H20 SHA256-192 24 20 TBD16
LMS_SHA256_M24_H25 SHA256-192 24 25 TBD17
LMS_SHAKE_M32_H5 SHAKE256-256 32 5 TBD18
LMS_SHAKE_M32_H10 SHAKE256-256 32 10 TBD19
LMS_SHAKE_M32_H15 SHAKE256-256 32 15 TBD20
LMS_SHAKE_M32_H20 SHAKE256-256 32 20 TBD21
LMS_SHAKE_M32_H25 SHAKE256-256 32 25 TBD22
LMS_SHAKE_M24_H5 SHAKE256-192 24 5 TBD23
LMS_SHAKE_M24_H10 SHAKE256-192 24 10 TBD24
LMS_SHAKE_M24_H15 SHAKE256-192 24 15 TBD25
LMS_SHAKE_M24_H20 SHAKE256-192 24 20 TBD26
LMS_SHAKE_M24_H25 SHAKE256-192 24 25 TBD27

The id is the IANA-defined identifier used to denote this specific parameter set, and which appears in both public keys and signatures.

The SHA256_M24, SHAKE_M32, SHAKE_M24 in the parameter set name denote the SHA256-192, SHAKE256-256 and SHAKE256-192 hash functions defined in Section 3.

6. Comparisons of 192 bit and 256 bit parameter sets

Switching to a 192 bit hash affects the signature size, the computation time, and the security strength.

The major reason for considering these truncated parameter sets is that they cause the signatures to shrink considerably.

Here is a table that gives the space used by both the 256 bit parameter sets and the 192 bit parameter sets, for a range of plausible Winternitz parameters and tree heights

Table 3
ParmSet Winternitz 256 bit hash 192 bit hash
15 4 2672 1624
15 8 1616 1024
20 4 2832 1744
20 8 1776 1144
15/10 4 5236 3172
15/10 8 3124 1972
15/15 4 5396 3292
15/15 8 3284 2092
20/10 4 5396 3292
20/10 8 3284 2092
20/15 4 5556 3412
20/15 8 3444 2212

ParmSet: this is the height of the Merkle tree(s); parameter sets listed as a single integer have L=1, and consist a single Merkle tree of that height; parameter sets with L=2 are listed as x/y, with x being the height of the top level Merkle tree, and y being the bottom level.

Winternitz: this is the Winternitz parameter used (for the tests that use multiple trees, this applies to all of them).

256 bit hash: the size in bytes of a signature, assuming that a 256 bit hash is used in the signature (either SHA256 or SHAKE256-256).

192 bit hash: the size in bytes of a signature, assuming that a 192 bit hash is used in the signature (either SHA256-192 or SHAKE256-192).

An examination of the signature sizes show that the 192 bit parameters consistently give a 35% - 40% reduction in the size of the signature in comparison with the 256 bit parameters.

In addition, for SHA256-192, there is a smaller (circa 20%) reduction in the amount of computation required for a signature operation with a 192 bit hash. The SHAKE256-192 signatures may have either a faster or slower computation, depending on the implementation speed of SHAKE versus SHA256 hashes.

The SHAKE256-256 based parameter sets give no space advantage (or disadvantage) over the existing SHA256-based parameter sets; any performance delta would depend solely on the implementation and whether they can generate SHAKE hashes faster than SHA256 ones.

7. IANA Considerations

[TO BE REMOVED: The entries from Section 4, namely LMOTS_SHA256_N24_W1 through LMOTS_SHAKE_N24_W8 , should be inserted into ]

[TO BE REMOVED: The entries from Section 5, namely LMS_SHA256_M24_H5 through LMS_SHAKE_M24_H25 should be inserted into ]

Until IANA assigns the codepoints, we will (for testing purposes only) use the following private use code points to do any necessary interoperability testing. Such an implementation must change to the IANA-assigned code points when they become available.

Table 4
Parameter Set Name Temporary Codepoint
LMOTS_SHA256_N24_W1 0xE0000001
LMOTS_SHA256_N24_W2 0xE0000002
LMOTS_SHA256_N24_W4 0xE0000003
LMOTS_SHA256_N24_W8 0xE0000004
LMOTS_SHAKE_N32_W1 0xE0000005
LMOTS_SHAKE_N32_W2 0xE0000006
LMOTS_SHAKE_N32_W4 0xE0000007
LMOTS_SHAKE_N32_W8 0xE0000008
LMOTS_SHAKE_N24_W1 0xE0000009
LMOTS_SHAKE_N24_W2 0xE000000A
LMOTS_SHAKE_N24_W4 0xE000000B
LMOTS_SHAKE_N24_W8 0xE000000C
LMS_SHA256_M24_H5 0xE0000001
LMS_SHA256_M24_H10 0xE0000002
LMS_SHA256_M24_H15 0xE0000003
LMS_SHA256_M24_H20 0xE0000004
LMS_SHA256_M24_H25 0xE0000005
LMS_SHAKE_M32_H5 0xE0000006
LMS_SHAKE_M32_H10 0xE0000007
LMS_SHAKE_M32_H15 0xE0000008
LMS_SHAKE_M32_H20 0xE0000009
LMS_SHAKE_M32_H25 0xE000000A
LMS_SHAKE_M24_H5 0xE000000B
LMS_SHAKE_M24_H10 0xE000000C
LMS_SHAKE_M24_H15 0xE000000D
LMS_SHAKE_M24_H20 0xE000000E
LMS_SHAKE_M24_H25 0xE000000F

8. Security Considerations

The strength of a signature that uses the SHA256-192, SHAKE256-256 and SHAKE256-192 hash functions is based on the difficultly in finding preimages or second preimages to those hash functions.

The case of SHAKE256-256 is essentially the same as the existing SHA256 based signatures; the difficultly of finding preimages is essentially the same, and so they have (barring unexpected cryptographical advances) essentially the same level of security.

The case of SHA256-192 and SHAKE256-192 requires closer analysis.

For a classical (nonquantum) computer, they have no known attack better than performing hashes of a large number of distinct preimages; as a successful attack has a high probability of requiring nearly 2**192 hash computations (for either SHA256-192 or SHAKE256-192). These can be taken as the expected work effort, and would appear to be completely infeasible in practice.

For a Quantum Computer, they could in theory use a Grover's algorithm to reduce the expected complexity required to circa 2**96 hash computations (for N=24). On the other hand, to implement Grover's algorithm with this number of hash computations would require performing circa 2**96 hash computations in succession, which will take more time than is likely to be acceptable to any attacker. To speed this up, the attacker would need to run a number of instances of Grover's algorithm in parallel. This would necessarily increase the total work effort required, and to an extent that makes it likely to be infeasible.

Hence, we expect that LMS based on these hash functions is secure against both classical and quantum computers, even though, in both cases, the expected work effort is less (for the N=24 case) than against either SHA256 or SHAKE256-256.

8.1. Note on the version of SHAKE

FIPS 202 defines both SHAKE128 and SHAKE256. This specification selects SHAKE256, even though it is, for large messages, less efficient. The reason is that SHAKE128 has a low upper bound on the difficulty of finding preimages (due to the invertibility of its internal permutation), which would limit the strength of LMS (whose strength is based on the difficulty of finding preimages). Hence, we specify the use of SHAKE256, which has a considerably stronger preimage resistance.

9. References

9.1. Normative References

National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS 180-4, .
National Institute of Standards and Technology, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS 202, .
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <>.
Bradner, S., Ed., "Intellectual Property Rights in IETF Technology", RFC 3979, DOI 10.17487/RFC3979, , <>.
Narten, T., "Clarification of the Third Party Disclosure Procedure in RFC 3979", RFC 4879, DOI 10.17487/RFC4879, , <>.
Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 5226, DOI 10.17487/RFC5226, , <>.
McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487/RFC8554, , <>.

9.2. Informative References

Grover, L.K., "A fast quantum mechanical algorithm for database search", 28th ACM Symposium on the Theory of Computing p. 212, .

Appendix A. Test Cases

This section provides three test cases that can be used to verify or debug an implementation, one for each hash function. This data is formatted with the name of the elements on the left, and the value of the elements on the right, in hexadecimal. The concatenation of all of the values within a public key or signature produces that public key or signature, and values that do not fit within a single line are listed across successive lines.

Test Case 1 Private Key for SHA256-192

(note: procedure in Appendix A of RFC8554 is used)
SEED        000102030405060708090a0b0c0d0e0f
I           202122232425262728292a2b2c2d2e2f

Test Case 1 Public Key for SHA256-192

HSS public key
levels      00000001
LMS type    0e000001                         # LMS_SHA256_M24_H5
LMOTS type  0e000004                         # LMOTS_SHA256_N24_W8
I           202122232425262728292a2b2c2d2e2f
K           2c571450aed99cfb4f4ac285da148827

Test Case 1 Message for SHA256-192

Message     54657374206d657361676520666f7220  |Test mesage for |
            5348413235362f3139320a            |SHA256-192.|

Test Case 1 Signature for SHA256-192

HSS signature
Nspk        00000000
LMS signature
q           00000005
LMOTS signature
LMOTS type  e0000004                         # LMOTS_SHA256_N24_W8
C           0b5040a18c1b5cabcbc85b047402ec62
y[0]        dcc7fa8c8d2d2a8cb41b4fb080443d82
y[1]        6dfc604ac2510910dd8e289eb0b43986
y[2]        25a6220a0b38dc3e518afe5b1b9b2525
y[3]        1a1136b7c7263f5c64babe117bf808e4
y[4]        134667b731876d2b36170f4b4bf1dae8
y[5]        d17d25948a09526225e1a40a55212fac
y[6]        13f4edcb07e401ba4fd42625b573e2b1
y[7]        ffbc1e12acfb9bf0c2fac322bbfaf292
y[8]        1e9ad5bc6fac2e2f3c3dbd92a46c6187
y[9]        cfea0868d59cf329d0633ba5b5ae3202
y[10]       b8d9ec380b05f629ae878e6265de29bc
y[11]       29ba727d4ec2e2fade202fc84737a9d8
y[12]       6eaccbfb4d5f2faacd4066aa93818533
y[13]       c9bfa602e3e973fe08c8ee35713d8580
y[14]       e937f14d3ae25f6f99c307bb66d2b0da
y[15]       696ed00415b5437628f76d11040b061f
y[16]       06d19d6870145e9b1a746673de15a02c
y[17]       9dccadd828483b74251d571ddec71585
y[18]       420641e1a7793544e48cab9818fb6156
y[19]       f1247ed1da9ee87da408fffa366b4f2c
y[20]       e9c9626aedebd1c3f8d6a2c5a9e514f7
y[21]       ecae4ad57b9de6cc58df826552bdd9d8
y[22]       e7bb777d2cf0fedf0c31e7aee973fe18
y[23]       d41802eece0e8d583ab0ae1729913a1a
y[24]       d562dc2abcc212ab163bd29a2c13dae8
y[25]       b85121440c1a6993ee2396eff407e50e
LMS type    e0000001                         # LMS_SHA256_M24_H5
path[0]     e9ca10eaa811b22ae07fb195e3590a33
path[1]     38d19f152182c807d3c40b189d3fcbea
path[2]     332d33ae0b761a2a8f984b56b2ac2fd4
path[3]     19c7aa7e9eee96504b0e60c6bb5c942d
path[4]     5871cffd131d0e04ffe5065bc7875e82

Test Case 2 Private Key for SHAKE256-192

(note: procedure in Appendix A of RFC8554 is used)
SEED        303132333435363738393a3b3c3d3e3f
I           505152535455565758595a5b5c5d5e5f

Test Case 2 Public Key for SHAKE256-192

HSS public key
levels      00000001
LMS type    0e00000b                         # LMS_SHAKE_M24_H5
LMOTS type  0e00000c                         # LMOTS_SHAKE_N24_W8
I           505152535455565758595a5b5c5d5e5f
K           db54a4509901051c01e26d9990e55034

Test Case 2 Message for SHAKE256-192

Message     54657374206d657361676520666f7220  |Test mesage for |
            5348414b453235362d3139320a        |SHAKE256-192.|

Test Case 2 Signature for SHAKE256-192

HSS signature
Nspk        00000000
LMS signature
q           00000006
LMOTS signature
LMOTS type  e000000c                         # LMOTS_SHAKE_N24_W8
C           bbf8b68bac9e1d2fa970a094bc4fedb7
y[0]        124f566f03b8949c17d8bb078b16c8cf
y[1]        98d8ee389efd08795a2864c51e267e7f
y[2]        0490e090b0295f97faa80f322a77d839
y[3]        ec8bbe764563d7099be23bc155a809de
y[4]        b5f07e1c7b389f0eb0e26d6b61c4228e
y[5]        76c45c4f9e0c10adf0af1f54715c8254
y[6]        e7c17c1455e55754f32e7bebf6b17a18
y[7]        fa3dc68df1b3ae000a30722ced785e53
y[8]        37afbf185f61cf86bb688965c736e359
y[9]        0017a5ae6f891b59f41c94e5b217b621
y[10]       1ecb389899d17ee22b2e5112846855db
y[11]       bb36d30da85bcbfd25b6d45d6820cbff
y[12]       3340cbcf9ccf1dd756f75c250460467a
y[13]       20172d8ebab81ee66c415dc9d226f193
y[14]       154cbea8e3bb0e37f0cee83e8a1a4492
y[15]       54b48a63c8f1c8ae9460039423942e10
y[16]       59baabff86aa9d26e361da998b0924cc
y[17]       11d1843b74c7a8151c32125f46bd61d5
y[18]       3b7e82c150a738cffdb6a537ba60fcd5
y[19]       d8726006e96fb89c429e975129870650
y[20]       3dfea6e2f369b79fa746ac77d09c54e6
y[21]       fe58d8442eba0ae8a9b3bd5d4c6a564e
y[22]       2c2dd72df1144b8b1ceff9f6ff84a547
y[23]       78d309c632432e1f7f16a6cd15057327
y[24]       82825de35a40e9aa8711b305306fc3ce
y[25]       eaabd5ebf6edbe5bf50978507489d66d
LMS type    e000000b                         # MS_SHAKE_M24_H5
path[0]     f756d0b3277dbcecfa7c007eaef9c068
path[1]     478f397cf71f7859d406aa93129d6448
path[2]     5589b9893128c82ad6d2299eebfdb038
path[3]     29e03883c0df124495ac5ede5d53da77
path[4]     6b8892b7556f7ab3831f528e80bf6b95

Test Case 3 Private Key for SHAKE256-256

(note: procedure in Appendix A of RFC8554 is used)
SEED        606162636465666768696a6b6c6d6e6f
I           808182838485868788898a8b8c8d8e8f

Test Case 3 Public Key for SHAKE256-256

HSS public key
levels      00000001
LMS type    0e000006                         # LMS_SHAKE_M32_H5
LMOTS type  0e000008                         # LMOTS_SHAKE_N32_W8
I           808182838485868788898a8b8c8d8e8f
K           9bb7faee411cae806c16a466c3191a8b

Test Case 3 Message for SHAKE256-256

Message     54657374206d657361676520666f7220  |Test mesage for |
            5348414b453235362d3235360a        |SHAKE256-256.|

Test Case 2 Signature for SHAKE256-256

HSS signature
Nspk        00000000
LMS signature
q           00000007
LMOTS signature
LMOTS type  e0000008                         # LMOTS_SHAKE_N32_W8
C           b82709f0f00e83759190996233d1ee4f
y[0]        16b228118c62b96c9c77678b33183730
y[1]        1d69c00129680b67e75b3bd7d8aa5c8b
y[2]        864b302ff321f9c4b8354408d0676050
y[3]        1403160fb45450d61a9c8c81f6bd69bd
y[4]        34ecc66dc88e10c6e0142942d4843f70
y[5]        caeef21303f8ac58b9f200371dc9e41a
y[6]        5b3ed19d847bd0a737177263cbc1a226
y[7]        ceb3bbcbd25228dda8306536376f8793
y[8]        7352919995b74404cc69a6f3b469445c
y[9]        3da3571ef70f805c9cc54b8e501a98b9
y[10]       769a9d422786def59700eef3278017ba
y[11]       36fbec4178d2bda3ad31e1644a2bcce2
y[12]       0d5beab0fb805e1945c41834dd6085e6
y[13]       ff123abe64dae8dabb2e84ca705309c2
y[14]       6f5e3bb8813997881b6a33cac0714e4b
y[15]       e773139ae377f5ba19ac86198d485fca
y[16]       bfe2d86b12778164436ab2659ba86676
y[17]       f72c5cb31f5a0b1d926324c26e67d4c3
y[18]       cf440f52ca9b5b9b99aba8a6754aae2b
y[19]       c36131c8991f0cc2ba57a15d35c91cf8
y[20]       bd4792b924b839332a64788a7701a300
y[21]       4fa87920b645e42aa2fecc9e21e000ca
y[22]       9376430f355aaf96a0a13d13f2419141
y[23]       0ea7255214ce11238605de2f000d2001
y[24]       49217cdf52f307172e2f6c7a2a4543e1
y[25]       14ed22483f2889f61e62b6fb78f5645b
y[26]       b61958786c97bd52fa199c27f6bb4d68
y[27]       d6e852cf6bc773ffd4c07ee2d6cc55f5
y[28]       cab1cc285faf6793ffad7a8c341a49c5
y[29]       81a68e21d748a7e7b1df8a593f3894b2
y[30]       1db33bbd390d2c04401c39b253b78ce2
y[31]       de256890804d83d6ec5ca3286f1fca9c
y[32]       9bbc69e2fd8618e9db3bdb0af13dda06
y[33]       19f55e9af11ae3d5614b564c642dbfec
LMS type    e0000006                         # MS_SHAKE_M32_H5
path[0]     71d585a35c3a908379f4072d070311db
path[1]     1329978a05d5e815cf4d74c1e547ec4a
path[2]     ae61ba57e5342e9db12caf6f6dbc5253
path[3]     1c12b9ffc3bcb1d3ac8589777655e22c
path[4]     ad6bfc337db69849e54411df8920c228

Authors' Addresses

Scott Fluhrer
Cisco Systems
170 West Tasman Drive
San Jose, CA
United States of America
Quynh Dang
100 Bureau Drive
Gaithersburg, MD
United States of America