LMS algorithm testing

[bfussell]

Is LMS still on the roadmap ?
If so, any timeframe we might see it ?

Thanks,

Barry

[celic]

I'm actively working on it. It's a bit challenging. The schemes don't fit well within our style of testing. I don't have a timetable for when this will be completed. It would be great if we could open up some discussions on how to approach this. I know Cisco worked with the CAVP (Matt Watson) in the past on this. I've got his code working along with contributions from Russ before he left the team.

[celic]

Let me clarify on what I'm looking for... I can write all the tests I want but if they don't exercise the algorithm in a way that's practical and useful for a real-world crypto module, there isn't much purpose. I'm missing some of that knowledge on how SP800-208 algorithms are used in the real world. How often are new trees generated? Do you keep larger trees in memory or re-generate them on-demand? Are there any assurances we can collect around knowing when a tree is depleted?

[zugzwang]

Hello @celic, Fortanix DSM supports LMS signatures (see our Algorithm Support page), so perhaps I can describe a real-world usage.

There is no need to keep whole trees in memory. Recall that leaves are One-Time LMS keys used to sign data, and each one of these leaves is indexed by a counter q increased after every signature (see sec 4.2 and 5.2 of RFC8554). Therefore, the representation of the state of a (one-level) LMS depends on a counter q, and the tree is depleted (or "the key is exhausted") whenever q exceeds the amount of leaves in this tree. Note that I say 'counter' since we implement it incrementally, but this approach is not mandatory.

If follows that in the two-level setting (such is the case of Fortanix DSM), one LMS key can be represented succintly by two private keys (as per sec. 5.2) with its respective counters, and one signature. The first key represents the upper tree (leaf q₁ currently in operation) and the second tree represents the lower tree attached to (and signed by) that particular leaf. When the lower tree is out of leaves (e.g. q₂ reaches threshold), it is replaced by another tree, signed by the upper leaf q₁ + 1, and q₂ ← 0 is set. The process continues until the upper tree runs out of leaves.

(I would be happy to discuss further in a live call, as there are more details intentionally left out. Feel free to reach me at [email protected])

[celic]

Thanks. I don't have a set list of questions to warrant a call, but with how unique these algorithms are, I appreciate the help in understanding how industry uses them. By the "two-level setting", do you mean HSS?

[zugzwang]

Yes, I mean HSS.

[jethrogb]

https://pages.nist.gov/ACVP/draft-celi-acvp-lms.html

[ashman-p]

Hi Folks, Just wondering if things could be simplified by adding the number of levels in the public key (L) and signature (L-1) as done in RFC 8554? That would give a consistent interface and simplified code for LMS/HSS?
e.g publicKey": "0000000B00000005D3933B303FD...." would become
publicKey": "**00000001**0000000B00000005D3933B303FD...."

signature": "0000000F00000006D789CF..."
signature": "**000000**0000000F00000006D789CF...",

Thanks.

[celic]

We will have separate HSS testing where that element will be prepended to the LMS key as specified in RFC 8554 Section 6. For specifically LMS testing, the prepended field is not part of the standard.