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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

Now, I am just about ready to push out the latest version of the draft; I thought I'd give you some responses before I do so.

> -----Original Message-----
> From: Stephen Farrell <[e-mail]>
> Sent: Tuesday, September 04, 2018 8:04 PM
> To: Scott Fluhrer (sfluhrer) <[e-mail]>; [e-mail]
> Cc: [e-mail]
> Subject: Re: [Cfrg] irsg review of draft-mcgrew-hash-sigs-12
> 
> 
> Hiya,
> 
> >
> >>
> >> (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:
...
> 
> That'd have helped me as a reader yes.

Rereading it, I saw that the beginning organized the levels backwards compared to the rest of the document, so I reworded it.  I believe that the revised text is equally helpful.

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

Hmmm, H=20 takes a bit of time to do key generation.  Now, I do know of a trick that allows you to do an effectively smaller H (while still using that parameter set); the verifier doesn't need to know about it.  However, that trick is not currently described in the draft.

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

I don't believe "key roll over" can work in general (because verifiers might not hear about the key change).  I would recommend HSS with L=2 (with two H=20 trees, that's literally a trillion signatures, which should be enough for almost any application)

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

That is the problem with a single MTI; there are a number of different possible applications, each with different requirements.

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

The draft mandates that 1 <= L <= 8.

> What about API issues for a library that implements
> private key handling, how would an application ask for a 20/15 private key?

For my implementation, the application passes two arrays, one of the LM-OTS parameter sets, and one of the LMS parameter sets.

> How about if someone defines a SHA3 based LMS - do verifiers have to
> decode into the signature to find that out?

That'd be encoded in the LM-OTS and the LMS parameter sets.

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

The will mention that, however it's more a note to IANA ("you don't have to keep the values disjoint") more than a note to an implementer (which I wouldn't expect to be confused; we never just a code point in a context which makes it unclear which one it is).