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

[Stephen Farrell <[e-mail]>]

Hiya,

This is a nice piece of work, thanks. 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

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

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

	[2]
https://csrc.nist.gov/csrc/media/events/ssr-2016-security-standardisation-research/documents/presentation-tue-gazdag.pdf

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

(5) The IANA registries seem a bit odd: why no HSS registry? Why
are the code points for the two registries contiguous? What if
IANA are asked to register a value of 0x00000005 for the LM-OTS
registry? (See point (2) where I also suggest that you drop the
LM-OTS registry entirely, which'd solve that latter issue nicely:-)

nits

- 3.1.1 - "When a and b are real numbers" what is "a % b"? would
  s/real numbers/integers/ not be ok here?

- 3.1.3 uses "AND" which isn't in 3.1

- 3.3 - too many options, as always :-(

- section 4: typo: "is used which."

- 4.1: uses the term "Winternitz coeffecients" which hasn't yet
  been explained.  Migth be good to do that earlier. (But I expect
it's ok, an implementer will figure it out.)

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

- Alg 4b, step 2b - the type values weren't really described
  earlier, but had forward refs, so this reader at this point
isn't sure that I understand the need for this check. I guess
it'll be clear as I read further so not sure if any change is
needed, just calling out that it's not yet clear, and when to
use identifiers like rsaEncryption vs. rsaWithSHA256 has caused
confusion/bugs/interop issues in the past.

- section 5: could say that h is the height of the tree before (or
  just after) "N < 2^h"

- 5.1: m and H aren't really independent parameters - I don't
  think it'd be ok for m to not be the length of the output of H
would it?

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

- 5.2: I was briefly confused by I being 16 bytes of random and
  the mention of the secret value that MUST be m bytes long.
Probably no need to change but you could refer back to alg 0 maybe
when mentioning the secret value.

- 5.2: I could see some implementer being unsure whether q=0 or
  q=1 is used for the first signature. Maybe say here that q is
incremented after signing, and that the first signature has q=0 in
it's encoding?

- 5.3: "if r >= 2^h: " you could add a comment after that saying
  that means r is a leaf node.

- 5.4: typo: "bthe"

- 5.4: The description here is very clear, thanks!

- 5.4.1: I dunno if anyone has considered APIs for this that'd
  allow working in parallel e.g. for different threads/processes.
It's probably fine to leave that for another day, but if there
were e.g. a reference to something about that, it might be good to
add. If not, it might be worth saying somewhere to be careful
about thread-safety? (Which could be in the security
considerations.) I see some mention of threading in the github.com
code so maybe there is something to say here?

- section 5 generally - it'd have been nice to see an equivalent
  of table 1 here.

- Algs 6 and 6a, step 1: same comment as before about length
  checks:-)

- section 6: N was used in section 5 in a slightly different way,
  maybe choose another letter for one of those? L is not
introduced properly.

- section 6: "tree of LMS trees" is a bit ambiguous - are the
  lower level trees only attached to the leaves of a higher level
tree, or could the root of lower level tree (somehow) be (mixed
with) an interior node in it's parent? IOW, if the level 0 tree
has h=3, are there 8 level 1 trees or 17 or 18? I guess you
mean 8.

- section 6: a picture would help a lot but I understand that may
  be hard in ascii-art.

- section 6: why start calling things objects here? Talking about
  the LMS tree being "used to sign" is also confusing - I think
you mean the private keys in the leaves are used to sign the roots
of the child trees.

- section 6: it'd be nicer if you had a different term for the
  trees at l=L-1, e.g. maybe call those message signing trees or
something?

- section 6: What's "an individual message" here?

- section 6: Can trees at different levels have different depths?
  I guess so.  It'd be good to be explicit about that. Can trees
at the same level have different depths?

- 6.1: "When an HSS key pair is generated, the key pair for each
  level MUST have its own identifier I." I think you mean the
"current key pair" there? If so be good to say that maybe.

- 6.1: typo "The values of pub[0] does not change..."
  s/values/value/

- 6.4: be better if the table on p31 was an actual table, also be
  good to list the value of N for each.

- 6.4: ParmSet is not clear to me - are all the examples of L=1 or
  L=2?  If so, saying that'd help.

- section 7: "The reason this size... " you mean the size of I
  here I guess?  Just checking.

- 9.2: I think a reference to [2] above here (or the related
  paper) would be good - there's lots in the paper that's not here
that'd be good for an implementer to consider. (Sorry, I've lost
the URL for the paper, but I'm sure the authors know it:-)

- Appendix E: why not use a https URL?

- Appendix F: I'm lazy - I didn't check the test vectors:-)