Subject: Re: [Cfrg] [irsg] IRSG review of draft-irtf-cfrg-xmss-hash-based-signatures-08

From: Stephen Farrell <[email-masked]>
Date: Fri, 16 Jun 2017 01:56:01 +0100

Hi all,

Apologies for being slow in reviewing this. My comments are below.
I have two things that I think really ought be checked before this
is ready for publication. When that's done, then I think this will
be ready to publish.

I also have two further comments/suggestions that I think would
be significant and relatively easy improvements to the document.
Those don't affect the IRSG review process though, considering the
RG were presumably happy enough as-is. (I'd still argue for those
changes though:-)

And I've a bunch of mostly editorial comments that the authors can
choose to take on board or not as they see fit.

Cheers,
S.

possible errors:
----------------

- 3.1.2: Algorithm 2: "if ( (i + s) > w - 1 )..." seems to be
missing parenthesis around the "(w-1)" to me.  Without those
brackets I could interpret that test to always result in false.

- 4.1.9: should the call to setIdx in alg 12 be after treeSig?
  as-is you seem to have incremented the index too soon so
that when alg 11 does getIdx it'd presumably get the
incremented index and cause verification failure. I think
the same is true of alg 16 as well, in section 4.2.4.

significant comments, but likely fixable:
-----------------------------------------

- section 5: there are waaaay too many options defined here.
  As-is, this will damage potential deployment of xmss. I
would strongly suggest deleting all of the options except the
minimum, that being one (and only one) set of parameters for
XMSS and one for XMSS^MT. If others are needed later, those
can be defined later. (Note that the damage done here includes
the hours of developer time that would be wasted debating
which of these choices to implement/use. Consider the case of
pre-hash variants of eddsa for an ongoing example.)

- section 5 (or an appendix) should contain some test vectors
  (including intermediate values). Without those, implementers
have a much harder time of getting their code right.

nits, near-nits and other ignorable things:
-------------------------------------------

- abstract: I'd suggest s/can withstand attacks/ can withstand
  so-far known attacks/

- 1.1: You say if used >1 time "no cryptographic security
  guarantees remain." It might be clearer to give some
examples of consequences, e.g. that the attacker can forge new
signatures or whatever.

- 1.1: I think you might mention that XMSS and other OTS ideas
  require some new crypto APIs. I'm not aware if anyone has
developed proposals for such, but would be interested if
someone has.

- 2.3, 2nd last para: you might want to say what happens with
  e.g.  B<<2 where B=0xf0. I assume the result is 0xc0 but
someone might think it's 0x3c0 or even 0xc3.

- 2.5: having the "type word" as octet 15 of a 32 byte address
  seems odd. Is there a reason why? (Just wondering.)

- 2.6: It seems odd to given an example where the input and
  output of base_w() are the same. A different example may be
more useful. (More examples generally would be great.)

- 3.1.3: maybe note that "/" means nothing? Which I assume it
  does? Better might be to just say that.

- 3.1.5: "a maximum value of len_1 * (w - 1) * 2^8" is missing
  units

- 3.1.5: "the variable" - which one?

- 3.1.5: "For the parameter sets given in Section 5 a 32-bit
  unsigned integer is sufficient." Sufficient for what?

- 3.1.5: The ascii art at the end of p16 doesn't help much.

- 3.1.7: The "MUST match" statement doesn't seem enforceable
  nor testable so I'm not sure it's a good idea to include.
OTOH, I do get the idea of using 2119 terms for emphasis.

- 3.1.7: I think it might be useful to point out any specific
  problems associated with using a low entropy human memorable
secret (password) for the value S. No matter what you say,
people will do that, so better if you can say you told them
specifically about downsides of doing that.

- 4.1.12: I'm not sure if the MAY there is correct or not.  If
  it means "you MAY use a different algorithm to get the same
output as alg 12" then that'd be fine. If something else is
meant I'm not sure what you're saying, and it'd probably be
better to not even mention it.

- section 5 should also spell out the signature and
public key sizes in bytes and ideally, if you keep multiple
options, (but please don't:-) describe relative or measured
timings.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 19 Jun 2017 16:37:28 +0000

@Stephen: thanks for making this thorough study of the draft.

@draft authors: can you please go through this feedback carefully and
implement the necessary changes?

The toughest part will likely be selecting one set of parameters. If
Stephen is amenable (but maybe he is not), I'd suggest highlighting one
set amongst the several listed as being your "preferred" set (rather than
including just one set as Stephen suggests) - that'd be a halfway house
between what you currently have and what Stephen suggests.

Cheers,

Kenny

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 19 Jun 2017 17:48:17 +0100

Hiya,

> between what you currently have and what Stephen suggests.

I'm always amenable:-)

For me, the key thing is to avoid folks using the RFC feeling
the need to debate which set(s) of parameters to choose to use.
Such debates are really wasteful, so reducing the set to the
minimum is very helpful. If there's really a need for loads
of parameters to be defined, (and I don't think there is for
this), then that creates a need to explain when to use which,
in sufficient detail for developers.

So I do think it's easier to just delete options, and since
there's an IANA registry, if it turns out more variants are
needed later then those can be added as needed. So, absent
someone saying that they need loads of options for their code,
I'd say just one XMSS and one XMSS^MT option would be best.

Cheers,
S.

---

From: "A. Huelsing" <[email-masked]>
Date: Tue, 20 Jun 2017 09:58:53 +0200

Hi,

thanks a lot for your review Stephen.

Let me comment on the parameter criticism. There is a crucial difference between
XMSS and "traditional" signature schemes which influenced our decision.
Unlike "traditional" signature schemes, XMSS (and all other Merkle-tree based,
stateful schemes) the number of signatures one can generate using a key pair
is controlled by the parameter h, the total tree hight, which also influences
performance significantly (increasing h increases number of signatures but makes
the scheme slower and signatures larger).

What we tried to do was to reduce all parameters that really influence
implementations (used hash function, hash function output length, Winternitz
parameter) to a single mandatory parameter set (SHA2-256, 256, 16). This also
fixes a single security level of 256 bit classical / 128 bit quantum. We only
gave different mandatory options for the total tree height and - for XMSS^MT -
different options for the number of layers d which controls the height of trees
in a hypertree. I am not aware of an implementation that really relies on these
two parameters being fixed. Low-level optimized implementations are rather
vectorizing the hash-function implementation as there is not too much
exploitable parallelism in the signature and verification algorithm as most
operations are sequential (different story for stateless schemes).

Now the selection really depends on what are your requirements, i.e., how many
signatures should be possible with one key pair. I agree that we should support
this highlighting the number of signatures as well as the signature size for
each of these parameter sets.

Finally, regarding the test vectors: I think it makes more sense to think of
hash-based signatures as a protocol rather than a basic primitive. We have
cross-verified reference implementations available. Is there an option to
provide an implementation instead of test vectors? Then developers can test
their implementation by verifying their signatures with the reference code and
check their verification algorithm with signatures from the reference
implementation. I am happy to add test cases (we already got those from the
cross testing).

What do you think?

Andreas

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 20 Jun 2017 12:41:54 +0100

Hi Andreas,

> each of these parameter sets.

So 5.2 has 3 required variants with h=10,16 and 20. And you
have 9 optional variants there too. (In case folks reading
this forget h=10 allows for 2^10 signatures.)

And 5.3 has 8 required variants with h=20,40,60 and d varying
between 2 and 12. And you have 24 optional variants.

That's a total of 36 options, which I still maintain isn't
useful. The probability that a verifier doesn't support a
variant chosen by a signer seems like it'd be too high to
me. And given what I imagine are the range of different
implementation strategies, I'd also guess that a verifier
could see performance vary in unexpected ways if it tries
to support all 36, i.e. I'm guessing a verifier that can
handle all 36 won't see best performance for all variants
and might experience really bad performance for some.

Considering 5.2 - I think I'd argue to only define the h=10
one for now (or only make that REQUIRED). My argument would
be that any real application has to handle running out of
signatures, and experience (mine anyway:-) says that hitting
that sooner is better. (Sort of similar to how LE issues
90-day certificates as a way to ensure renewal gets done and
gets automated - I think they got that right.)

For 5.3 I'd also argue to just go with about the same number
of signatures on the same basis, and to only make one variant
REQUIRED, so h=20,d=2 I guess.

I agree that adding more about the signature-count and maybe
time/memory trade-offs would be good regardless. (Though that
could be done in another draft if publishing now is a priority.)

All that said, please note that I don't consider that this
ought be blocking in terms of publication. (While still not
liking that there's 36 options:-)

> implementation. I am happy to add test cases (we already got those from the

It's maybe a bit late in the day but you could add an RFC7942
section to the draft describing implementations. That text is
usually deleted from the RFC (an approach of which I'm not fond)
but the I-D will still exist, so it'd not get lost. Or you
could add a reference to wiki page or similar that has that
kind of information. Either would be a fine thing to do. I guess
at the stage we're at the latter would make more sense. (I did
a quick search and didn't find such a page though, so I guess
you'd have to make one with the names of implementations and
links to code/docs.)

And to be clear, if you don't have an implementation that can
spit out test vectors and intermediate values, then I'm not
asking that you make one now.

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 20 Jun 2017 12:45:11 +0100

(Dropping irsg)

Oops, my arithmetic was wrong: it's 44 options, not 36:-)
I left out the mandatory ones from 5.3. Doesn't affect the
argument though.

S.

On 20/06/17 12:41, Stephen Farrell wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "A. Huelsing" <[email-masked]>
Date: Tue, 27 Jun 2017 15:01:00 +0200

Hi Stephen, hi Kenny, hi Alexey,

We are currently going through the review. While we didn't handle the nits yet,
we made up our mind about the first four points (see below). Regarding the last
point of test vectors.
We think it is better to add a reference implementation. We would now just add
the C code as appendix. Would that be fine? Are there any conditions on code? We
have dependencies to OpenSSL for SHA2.

>>>> possible errors:
Added parenthesis.
>>>> the same is true of alg 16 as well, in section 4.2.4.
Indeed, we now give idx_sig as additional input (and don't use the already
updated index from SK anymore).
>>>> significant comments, but likely fixable:
Got your point Our noted todos are:
####
#   1.) Select 1 XMSS & 1 XMSS^MT parameter set as default options
#   2.) Explain that all other h / d combis are fine but we can only give
limited number
#   3.) Add sizes & #sigs for parameter sets
#   4.) Explain trade-offs
#   5.) Make implementation of verification for all parameters mandatory / sign
just a para suggestion
####
Do you agree?
>>>> have a much harder time of getting their code right.
See above.

Cheers,

Stefan & Andreas

---

From: Watson Ladd <[email-masked]>
Date: Tue, 27 Jun 2017 07:28:57 -0700

> have dependencies to OpenSSL for SHA2.

I would prefer just calls to sha256(unsigned char *out, unsigned char
*in, size_t inlen). OpenSS's API  is a mess.
Sincerely,
Watson

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 27 Jun 2017 15:41:00 +0000

I would prefer calls to sha-3-256. SHA-2 is not a randomizer by design.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 27 Jun 2017 16:49:57 +0100

Hi Andreas,

On 27/06/17 14:01, A. Huelsing wrote:
> the C code as appendix. Would that be fine?

Your call entirely IMO. An appendix is just fine, or a reference
to a git repo could be as good, if test vectors aren't the right
thing to do.

> Are there any conditions on code? We

If you include code directly in the RFC, there's a license
issue - it needs to be BSD basically and marked out as such
(via "CODE_BEGINS" or some such, I forget the detail;-). If
your current code doesn't use the BSD license, then it'll be
easier to just add a URL referring to it somewhere.

> updated index from SK anymore).

Ok great - those were the only two changes that I think should
have been blocking for publication. All the rest is just my
opinion that you (and/or the RG chairs) should take into
account however you see fit.

> #   5.) Make implementation of verification for all parameters mandatory / sign

I think those would be fine improvements yes.

Cheers and thanks for considering the review,
S.