Subject: [Cfrg] draft-mcgrew-hash-sigs and variable L

From: Geraint Luff <[email-masked]>
Date: Fri, 30 Mar 2018 00:54:39 +0100

Hi folks,

Reading through draft-mcgrew-hash-sigs-10, the HSS structure (section 6)
has a constant number of levels.  I apologise if this has been asked
before, but what's the reason to limit it to finite depths?  Allowing a
variable number of levels seems to me more flexible/scalable, and
performance/size are competitive.

To illustrate what I mean: let's say we are working with N-time LMS keys.
We start with L=1.  After the first N/2 signatures, we increase L to 2.
After the next (N^2)/2 signatures, increase L to 3, and so on.  Or stated
more compatibly with Section 6.2: we increment L every time prv[d] uses the
signature at leaf number (N - 2^i) for any integer i, where d is the lowest
value such that prv[d] is not completely exhausted.

An HSS tree with L levels gives you N^L signatures.  The scheme above would
give you slightly more than (N^L)/2 signatures before the length increases
beyond L - so if a fixed-depth scheme ends up using < 50% of its possible
signatures by the time you rotate the key, the variable-depth scheme would
actually have been more efficient.

I also see that in the HSS verification algorithm, it checks "Nspk" against
the declared level-count of the public key, and I believe I understand
why.  However with the above infinite-depth scheme, it's possible to fairly
simply check/determine the correct number of levels for a particular
signature - for a signature with L levels, the LMS signatures will take
exactly (L - 1) "odd" paths (corresponding to a 1 in the leaf number),
followed by an "even" one.  If we verify this, we can be certain the length
was determined using the algorithm above, so it performs the same role as
the existing length check.

I think a scheme like this would add flexibility, while also no longer
requiring the key owner to guess how many signatures they'll need when
generating a key.

Again, apologies if this has already been discussed and discarded - I
couldn't find a thread about it in the mailing-list archives, though.

All the best,
Geraint

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 30 Mar 2018 18:29:08 +0000

From: Cfrg <[email-masked]> On Behalf Of Geraint Luff
Sent: Thursday, March 29, 2018 7:55 PM
To: [email-masked]
Subject: [Cfrg] draft-mcgrew-hash-sigs and variable L

Hi folks,

Reading through draft-mcgrew-hash-sigs-10, the HSS structure (section 6) has a constant number of levels.  I apologise if this has been asked before, but what's the reason to limit it to finite depths?  Allowing a variable number of levels seems to me more flexible/scalable, and performance/size are competitive.

As far as I know, it hasn’t been suggested.  I personally have a prejudice against it, as I dislike signatures that vary in size.  I suspect that’s not due to any security concerns (your size variations are independent of any secret data, so you’re good there), but rather the concern with how varying sizes would affect the noncryptographical parts; for example, how possible that the protocol we’re using would deal with the initial size just fine, but stop working after they grow somewhat.

To illustrate what I mean: let's say we are working with N-time LMS keys.  We start with L=1.  After the first N/2 signatures, we increase L to 2.  After the next (N^2)/2 signatures, increase L to 3, and so on.

Actually, after (N^2)/2 L2 signatures, you’d run out; that is, the top level tree will have used up all the signatures it’s allowed.  For example, consider the case N=32; for L=1, you’d use up the first 16 top level nodes for the first 16 signatures.  Then, you start with L=2, and generate (N^2)/2 = 512 signatures.  That would be 512/32 = 16 L2 trees, which would require 16 top level nodes to sign.  At this point, you hit the end of the top level tree, which you switch to L=3, there’s no L1 signatures left to use.

I believe things can be modified to make it work; it would appear to be more complex than what you have…

Or stated more compatibly with Section 6.2: we increment L every time prv[d] uses the signature at leaf number (N - 2^i) for any integer i, where d is the lowest value such that prv[d] is not completely exhausted.

An HSS tree with L levels gives you N^L signatures.  The scheme above would give you slightly more than (N^L)/2 signatures before the length increases beyond L - so if a fixed-depth scheme ends up using < 50% of its possible signatures by the time you rotate the key, the variable-depth scheme would actually have been more efficient.

That’d need to be re-evaluated once you replace your scheme with one that actually works.

In any case, I suspect that much of the time, a fixed L=2 would be quite sufficient.  That’s because Merkle walking algorithms exist that allow us to efficiently compute the next authentication path using relatively little time (a handful of OTS public key computations), and not that much memory storage.  This means that relatively tall trees are practical, and so (for example) a hierarchy of 20/15 (that is, the L1 tree has height 20, and the L2 tree has height 15) would be feasible (and have enough signatures to last, at 1000 signatures per second, for an entire year).  That might not be applicable in (say) the Hardware Security Module (HSM) case (where the HSM can’t deal with these fancier algorithms), but they probably can’t deal with varying tree size anyways…

I also see that in the HSS verification algorithm, it checks "Nspk" against the declared level-count of the public key, and I believe I understand why.  However with the above infinite-depth scheme, it's possible to fairly simply check/determine the correct number of levels for a particular signature - for a signature with L levels, the LMS signatures will take exactly (L - 1) "odd" paths (corresponding to a 1 in the leaf number), followed by an "even" one.  If we verify this, we can be certain the length was determined using the algorithm above, so it performs the same role as the existing length check.

Nit: because of these Merkle walking algorithms work, you wouldn’t want to use the odd paths first, and then the even paths.  Instead, you’d want to use the left side of the tree first, and then the right side.  That is a trivial modification to what you said…

I think a scheme like this would add flexibility, while also no longer requiring the key owner to guess how many signatures they'll need when generating a key.

Given how easy it is to guess a huge number, e.g. 2^{35} or 2^{40}, I don’t personally see that as a major concern…

Again, apologies if this has already been discussed and discarded - I couldn't find a thread about it in the mailing-list archives, though.

All the best,
Geraint