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

[Stephen Farrell <[e-mail]>]

(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:
> 
> 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.
>>>>>
>>>>>
>>>>>
>>
>>
> 
> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>