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

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

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

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

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


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

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

> Why are the
> code points for the two registries contiguous?

Combination of coincidence and historic accident.

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.

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

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

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

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

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