0
$\begingroup$

I am working with the RFC for Leighton-Micali Hash-Based Signatures: RFC-8554. The question is if I understood it correctly and my calculations of the key sizes are correct.

Basically, LMS uses several Winternitz-One-Time-Signature keys.

Winternitz-OTS

In chapter 4.1 of the RFC the parameter sets of the OTS keys are mentioned:

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

Where n is the number of bytes of the output of the hash function and p is the number of n-byte string elements. This means basically for the OTS private key we have n * p keys (+ 4 bytes for the typecode). This would also fit for the given signature length sig_len (n * p + 4 + 32 bytes for the checksum). The OTS public key is of equal length of the private key.

LMS

In chapter 5.1 of the RFC the parameter sets of the LMS keys are mentioned.

+--------------------+--------+----+----+
| 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 |
+--------------------+--------+----+----+

Where m is the number of bytes associated with each node and h is the height of the Merkle tree. One LMS private key consists of 2^h OTS private keys.

Questions

  1. Is it correct that any LMS parameter set can be used with any OTS parameter set? e.g. LMS_SHA256_M32_H25 for the Merkle tree and LMOTS_SHA_256_N32_W2 for the OTS keys.

  2. Are those calculations of LMS private key sizes correct: Formula: 2^h * ((n * p) + 4)

    • LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W8: 2^5 * ((32 * 34) + 4) = 34 944 bytes ~ 34 KB
    • LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W1: 2^5 * ((32 * 265) + 4) = 271 488 bytes ~ 271 KB
    • LMS_SHA256_M32_H20 & LMOTS_SHA256_N32_W8: 2^20 * ((32 * 34) + 4) ~ 1.1 GB
    • LMS_SHA256_M32_H20 & LMOTS_SHA256_N32_W1: 2^20 * ((32 * 265) + 4) ~ 9 GB
    • LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W8: 2^25 * ((32 * 34) + 4) ~ 37 GB
    • LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1: 2^25 * ((32 * 265) + 4) ~ 285 GB

If those key sizes are correct then how would someone store them securely? Are those deep Merkle trees realistic? I guess calculating the corresponding public key can be done on demand.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$
  1. Yes, each LMS parameter sets can be used with any OTS parameter set. In the final NIST Recommendation for Stateful Hash-Based Signature Schemes there are even more parameters defined.
  1. Those calculations are correct but we do not need to store the entire LMS tree in memory. The solution is to store the seed for the RNG in the private key and calculate the tree on demand. Requires more work but requires much less memory.

Calculations

LMOTS private key:

Size = 4 byte LMOTS typecode + 16 byte identifier + 4 byte q + n byte seed

Example: LMOTS_SHA256_N32_W8 = 4 + 16 + 4 + 32 = 56 byte

LMS private key:

Size = 4 byte LMOTS typecode + 4 byte LMS typecode + 4 byte q + 16 byte identifier + 2^h LMOTS private key size

Examples:

LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W8: 4 + 4 + 4 + 16 + 2^5 * 56 = 1 820 byte

LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1: 4 + 4 + 4 + 16 + 2^25 * 56 = 1 879 048 220 byte ~ 1.9 GB

Improve this answer
$\endgroup$
5
  • $\begingroup$ For the LMS private key, we can use the same RNG trick to use a single n byte seed to determine all the private OTS values; appendix A of the RFC gives one suggested way. $\endgroup$
    – poncho
    Apr 8, 2021 at 21:45
  • $\begingroup$ @poncho That's what I wanted to say or did I understand you wrong? $\endgroup$
    – AndiCover
    Apr 9, 2021 at 5:09
  • $\begingroup$ Well, when you say that LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1 requires a 1.9GB private key, well, it can be implemented with a considerably shorter private key than that... $\endgroup$
    – poncho
    Apr 9, 2021 at 12:55
  • $\begingroup$ @poncho Ah you mean if I do not store the seed in the LMOTS keys I could decrease the size by about 1GB? I will consider that in my implementation. $\endgroup$
    – AndiCover
    Apr 10, 2021 at 8:23
  • $\begingroup$ Yes, you can generate all the private OTS values from one seed, hence you need to store only that seed $\endgroup$
    – poncho
    Apr 10, 2021 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.