Re: [Cfrg] irsg review of draft-mcgrew-hash-sigs-12

[Stephen Farrell <[e-mail]>]

Hiya,

To be clear: the responses below are such that I'm happy
for my IRSG review to be ready-to-publish. (That said, I'm
even happier to chat more about points below.)

On 04/09/18 04:43, Scott Fluhrer (sfluhrer) wrote:
>> -----Original Message----- From: Cfrg <[e-mail]> On
>> Behalf Of Stephen Farrell Sent: Wednesday, August 29, 2018 9:20 AM 
>> To: [e-mail] Cc: [e-mail] Subject: [Cfrg] irsg review
>> of draft-mcgrew-hash-sigs-12
>> 
>> 
>> Hiya,
>> 
>> This is a nice piece of work, thanks.
> Thank you.
> 
>> I've a few comments and a bunch of nitty things below. From the
>> comments, I'd say that only #1 and #5 really need to be resolved
>> before publication, the others (and the nits) aren't the kind of 
>> thing that ought block progress. (And it could well be that neither
>> #1 nor #5 really need changes too of course - I do often get things
>> wrong:-)
>> 
>> Cheers, S.
>> 
>> (1) Shouldn't there be a section like the one in XMSS? [1] If the
>> authors were ok with adding something like that, I think that'd be
>> good. Given the earlier discussion on the CFRG list that resulted
>> in [1], I'd say the RG ought be asked if they no longer think that
>> kind of thing is needed, if the draft is to be published as-is.
>> 
>> [1] https://tools.ietf.org/html/rfc8391#section-1.1
> 
> Ok, I put it in there.  As LMS shares the same strengths and
> weaknesses as XMSS, everything in the XMSS section is applicable to
> LMS; I just copied and pasted.

Cool.

> 
>> 
>> (2) Is defining a separate one-time LM-OTS mechainism, as if it
>> could be used in isolation, (in section 4) really worthwhile? I'm
>> not sure there are applications for that.  If we're really only
>> interested in signature schemes that can emit multiple signatures,
>> then I think not presenting this as if it could be used alone could
>> be a good idea. (Even if exactly the same thing is defined as an
>> internal mechanism.) That said, I do really like the presentation
>> in 4.1 so am not asking to change that much, just to say that it's
>> not independently useful.  I guess what I dislike is the 1st column
>> of table 1 that gives the impression these are usable signature
>> mechanisms, and the IANA registry for OTS signature schemes (table
>> 3). This needn't get in the way of publication though.
> 
> Whether LM-OTS is an independently usable mechanism is something that
> has changed over time; in the earlier versions of the drafts, it was.
> Currently, we don't specify that it is (largely because, just like
> you, we don't see that as a very useful primitive outside of LMS);
> the current text attempts to reflect that.
> 
> On the other hand, we do need the IANA registry for it, because it
> does occur within LMS, and it does have multiple possible settings.

Not sure I agree really but see #5 below.

> Now, we could have an integrated space that specified both the LM-OTS
> and LMS settings; however, that'd be an non-interoperable change, and
> as there are multiple implementations now, I would not like to do
> that.

Understood. OTOH, if we're dealing with a few implementations
and not much deployment, now is a fine time to fix things that
may cause bugs or confusion later.

> 
>> 
>> (3) As an editorial comment, section 6 isn't near as clear as
>> section 5 for this reader - 5 was really well described, but I
>> found 6 quite confusing. If it were possible to improve that,
>> that'd be great. I think describing HSS by saying that the private
>> keys from the leaves of the parent tree are used to sign the root 
>> of the child trees would have helped me a lot. (Assuming that the
>> picture on slide 19 of [2] illustrates what's going on with HSS,
>> but without introducing the reservation idea.) See also the
>> specific nitty comments on section 6 below. All that said, while it
>> took me a while to understand the text in section 6, I did
>> eventually, and I guess an implementer would also, so publication 
>> without changing this would be ok.
> 
> Ok, I tried adding this text near the top of section 6:
> 
> In HSS, we have a sequence of L LMS trees, where the public key for
> each LMS tree is signed by one of the leaves of the next LMS tree
> (and the public key of the last tree is effectively the public key
> for the entire HSS system).  For example, if we have a three level
> hierarchy (L=3), then we have:
> 
> One LMS tree (level 2 in the notation we'll use below) that signs the
> message
> 
> A second LMS tree (level 1) that signs the public key for the level 2
> LMS tree
> 
> A third LMS tree (level 0) that signs the publi key for the level 1
> LMS tree
> 
> The root of the level 0 LMS tree is contained in the HSS public key.
> 
> To verify the LMS signature, we would verify all the signatures:
> 
> We would verify that the level 1 LMS public key is correctly signed
> by the level 0 signature.
> 
> We would verify that the level 2 LMS public key is correctly signed
> by the level 1 signature.
> 
> We would verify that the message is correctly signed by the level 2
> signature.
> 
> We would accept the HSS signature only if all the signatures 
> validated.
> 
> During the signature generation process, we sign messages with the 
> lowest (level L-1) LMS tree.  Once we have used all the leafs in
> that tree, we would discard it, generate a fresh LMS tree, and sign
> it with the next (level L-2) LMS tree (and when that is used up, 
> recursively generate and sign a fresh level L-2 LMS tree.
> 
> Do you think that this overview (in addition to the more detailed
> description already in the draft) is a help?

That'd have helped me as a reader yes.

>> (4) There's a lack of guidance as to what is mandatory to
>> implement.  The only thing you really say along those lines is that
>> "implementations MUST support HSS" with L=1. I think it'd be better
>> if you picked (exactly!) one LMS option and said that that was MTI.
>> That's just my opinion and I guess the RG were ok with not being
>> that specific, so this oughtn't hold up publication if the RG are
>> still ok with that and/or the authors really don't wanna pick one. 
>> OTOH, pretty much every CFRG RFC that has more than one choice
>> causes debate in IETF WGs when it comes time to use those, so if
>> picking one was doable, that'd be a fine thing to do I reckon.
> 
> That has not been a topic that's come up, either between us, nor on
> the mailing list.
> 
> I don't personally feel comfortable in mandating something without
> discussing it first.  

Fair point. We should bear in mind though that discussing this
once in CFRG is maybe better than every IETF WG that wants to
use LMS re-doing the discussion but based on less understanding
of the scheme (if, that is, a CFRG discussion results in selecting
one option as MTI).

> Does anyone else what to chime in?  Should we
> mandate that a verifier be able to recognize anything in the draft
> (which isn't all that many options currently)?

I'd argue for a tighter spec than that myself. (Just as one
input.) My take would be to say that LMS_SHA256_M32_H20 with
LMOTS_SHA256_N32_W8 is the only MTI option for signers or
verifiers.

My argument for that is that I think there'll be applications
for which that could work, if one has a key roll-over scheme
(e.g. last N sigs need to sign a new tree root), and that such
roll-over will absolutely be needed by applications so we ought
not allow so many sigs that people decide to not implement any
key roll-over. h=15 might be too shallow but I'd be fine if
that was the one and only MTI; I'd argue against h=25 as the
only MTI as that may be too deep to force implementers to deal
with key roll-over. I picked LMOTS_SHA256_N32_W8 as that has
the shortest sig which I think will be important for getting
any traction but I wouldn't argue against the w=4 variant if
that had some benefits.

And to be clear: picking an MTI here just means that those who
want to use this won't have to, but can if they want, argue
about what's right for their particular situation.

> 
>> 
>> (5) The IANA registries seem a bit odd: why no HSS registry?
> 
> Because there are no HSS-specific opaque values.  The only
> HSS-specific field in the public key/signature is the L value, which
> is a small integer (which obviously needn't be registered with IANA)

Hmm. Not sure I agree there - would it be wise to accept
and try to verify an L=2^32 HSS signature? What about API
issues for a library that implements private key handling,
how would an application ask for a 20/15 private key? How
about if someone defines a SHA3 based LMS - do verifiers
have to decode into the signature to find that out?

All that said, I don't have the HSS signature format in
my head really, so the above may not really argue for having
HSS codepoints. (Or they may:-) Or maybe it's fine to not
expect the same level of interop for HSS as for LMS? (I'm
not clear if that's considered an important goal or not.)

> 
>> Why are the code points for the two registries contiguous?
> 
> Combination of coincidence and historic accident.

Sounds like a potential source of confusion to me.

> 
> Originally, we had both N=32 and N=16 parameter sets; for some
> reason, in the -04 version of the draft, the LM-OTS N=32 parameter
> sets came first (and were assigned values 1 through 4), and in LMS
> the N=16 parameter sets came first (being assigned values 1 through
> 4, with the N=32 parameter sets being assigned values 5 through 8).
> In the next version of the draft, we removed the N=16 parameter sets
> (as they weren't quantum-safe), but left the N=32 assigned values the
> same, giving the structure you see.

Ah, that history wasn't clear. I don't think it needs to be in the
RFC though. It does mean that my comment #5 oughtn't be blocking
though.

> 
>> What if IANA are asked to register a value of 0x00000005 for the
>> LM-OTS registry?
> 
> That would not be an issue at all.  The LMS and LM-OTS registries are
> separate name-spaces; when parsing a public key or signature, we
> always know which we are dealing with, and so there are no issue if
> the same value is given different meanings to the different
> registries.

So maybe make that point in section 8? If for no other reason, it'd
head off a crazy developer with code that branches on just the code
points and not the combo of alg and codepoint?

> 

>> nits

All your answers below seen entirely fine to me, thanks. I do have
an answer for the one where you ask a question.

>> 
>> 
>> - 3.3 - too many options, as always :-(
> 
> Sigh...  However, there is one saving grace that not many other
> cryptoalgorithms share; no matter which set of options the user
> chooses, the security remains the same.  This is not often true in
> crypto (e.g. a 1024 bit RSA key doesn't have the same security as a
> 2048 bit key), however it is true here.  Now, different options given
> different practical tradeoffs (in terms of performance, signature
> size, number of signatures per key), however I believe that
> developers can be trusted to accurately weigh those practical
> concerns.
> 
>> 
>> - Algorithm 4a: why call out the 4 byte min in step 1? I bet there 
>> are other encoding checks an implementer would need to do, and
>> just including this one might lead someone to not think about which
>> other checks are needed to be safe.  I have the same comment on the
>> length checks in other places. (Bear in mind that this is a nit
>> though!)
> 
> Actually, I believe that all necessary length checks are listed in
> the pseudocode.  If you spot a counterexample, please tell me.

Sorry, don't have one. I'd bet a beer though:-)

>> - 5.1: the SHOULD for the hash function being the same for LMS and 
>> LM-OTS is a bit odd. I can't think of a reason for using different
>> hashes - e.g. afaik there's no (and unlikely to be a) legacy LM-OTS
>> implementation that'd be used independently of LMS, so I don't see
>> the reason to not have a MUST here. (And MUSTs are easier:-)
> 
> You aren't the first one to ask.  To quote my answer to the previous
> person:
> 
> As for whether we should allow this [allowing different hash
> functions in LM-OTS and LMS] as an option, well, we've actually
> changed our minds about that (version -06 did not).  On the other
> hand, I do not see any specific reason to forbid it; doing so doesn't
> cause any unexpected cryptographical weaknesses (other than giving
> the attacker his choice of two different hash functions to attack).
> 
>> 
>> - section 5 generally - it'd have been nice to see an equivalent of
>> table 1 here.
> 
> Don't we have table 2 in section 5?  It doesn't give signature
> lengths, but the LMS signature length is a function of both the
> LM-OTS and the LMS parameter set.

Sure. But the sig len is what some readers will want to know.
If you did pick one MTI then you could report on the sig len
for it.

> 
>> 
>> - section 6: Can trees at different levels have different depths?
> 
> Yes, if you look at the parameter set recommendations, we include
> mismatched parameter sets, such as 15/10 (the top tree has h=15, the
> bottom tree has h=10).
> 
> And, yes, they would appear to be a good idea, at least in some
> settings; which the LMS trees are identical from a cryptographical
> standpoint, they aren't from a practical ones.  There are certainly
> valid reasons why someone might want to top-most tree to be larger.
> 
>> I guess so.  It'd be good to be explicit about that. Can trees at
>> the same level have different depths?
> 
> Hmmm, there's nothing that a verifier can do to make sure that a
> signer isn't doing it; would just a simple MUST NOT statement be good
> enough?

If that's even needed? The only bad outcomes I can think of are
1) if a verifier assumes uniformity, non-uniform level-i depths
might trigger some bugs and 2) I guess it'd be harder to get
portability (which is not claimed as a goal here).

>> 
>> - 6.4: be better if the table on p31 was an actual table, also be 
>> good to list the value of N for each.
> 
> I made it into a table; however all current parameter sets have
> N=32.
> 
>> 
>> - Appendix F: I'm lazy - I didn't check the test vectors:-)
> 
> Bad reviewer; no donut :-)

Ah, bummer:-)

Cheers,
S.

>