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

[Stephen Farrell <[e-mail]>]

Hi Andreas,

On 20/06/17 08:58, A. Huelsing wrote:
> 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.

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

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

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.

> 
> What do you think?
> 
> Andreas
> 
> 
> Am 19-06-17 um 18:48 schrieb Stephen Farrell:
>> Hiya,
>>
>> On 19/06/17 17:37, Paterson, Kenny wrote:
>>> @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.
>> 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.
>>
>>> Cheers,
>>>
>>> Kenny 
>>>
>>>
>>> On 16/06/2017 01:56, "Stephen Farrell" <[e-mail]> wrote:
>>>
>>>> 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.
>>>>
>>>>
>>>>
> 
>