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

Stephen Farrell <stephen.farrell@cs.tcd.ie> Tue, 20 June 2017 11:45 UTC

Return-Path: <stephen.farrell@cs.tcd.ie>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1AB09128D3E for <cfrg@ietfa.amsl.com>; Tue, 20 Jun 2017 04:45:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.302
X-Spam-Level:
X-Spam-Status: No, score=-4.302 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cs.tcd.ie
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lutVRYCmAph8 for <cfrg@ietfa.amsl.com>; Tue, 20 Jun 2017 04:45:19 -0700 (PDT)
Received: from mercury.scss.tcd.ie (mercury.scss.tcd.ie [134.226.56.6]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 06B19129B2D for <Cfrg@irtf.org>; Tue, 20 Jun 2017 04:45:14 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id BD7ABBE64; Tue, 20 Jun 2017 12:45:12 +0100 (IST)
Received: from mercury.scss.tcd.ie ([127.0.0.1]) by localhost (mercury.scss.tcd.ie [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bZmdc82Nyp9Q; Tue, 20 Jun 2017 12:45:12 +0100 (IST)
Received: from [134.226.36.93] (bilbo.dsg.cs.tcd.ie [134.226.36.93]) by mercury.scss.tcd.ie (Postfix) with ESMTPSA id F36F8BE53; Tue, 20 Jun 2017 12:45:11 +0100 (IST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cs.tcd.ie; s=mail; t=1497959112; bh=+yiMWJ0CnLwJA3Eh3O+UkFFy0XokVLJZ8pDS8vaAX54=; h=Subject:To:Cc:References:From:Date:In-Reply-To:From; b=vIm6TEMx8jsChEqmV3BSeazSeUnbl20+fh9U7hVyMNJJKpNYikTp82fst3Id5YHjr TrHbW3ktzYTZ/swQmB+mNfL2LGi27I43pK0lHRTs3KOZSAsVxwTzC7f9YpjQjuLP5z 75KqZoV6YN3fOnO5CvCkbFDe/he4+E+Azi05dxuM=
To: "A. Huelsing" <ietf@huelsing.net>, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>, Alexey Melnikov <alexey.melnikov@isode.com>, "cfrg@irtf.org" <Cfrg@irtf.org>
Cc: "draft-irtf-cfrg-xmss-hash-based-signatures@ietf.org" <draft-irtf-cfrg-xmss-hash-based-signatures@ietf.org>
References: <D4FDAF9D.8D586%kenny.paterson@rhul.ac.uk> <9a878527-5ab9-5429-7c5d-4f7e4ca4e8db@isode.com> <08944dc3-9086-ed47-cc1b-54248b3dac70@cs.tcd.ie> <D566ADE0.963E4%kenny.paterson@rhul.ac.uk> <9e6b6146-e376-86cb-70be-0127a3e72d16@cs.tcd.ie> <D56DBB2C.96A67%kenny.paterson@rhul.ac.uk> <6f90e485-01f4-5ad8-49ef-e51c52e01a46@cs.tcd.ie> <5e328e85-a8a1-67f1-3853-418309b04a17@huelsing.net> <4180756b-b718-05ce-2ea0-b8bf65fa8711@cs.tcd.ie>
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
Openpgp: id=D66EA7906F0B897FB2E97D582F3C8736805F8DA2; url=
Message-ID: <d5a2ab2b-ac24-6e28-cc1d-b5d3098474da@cs.tcd.ie>
Date: Tue, 20 Jun 2017 12:45:11 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.1
MIME-Version: 1.0
In-Reply-To: <4180756b-b718-05ce-2ea0-b8bf65fa8711@cs.tcd.ie>
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="eNs3IVVKko6GO4o2jdEB1uW6t6bQ613ia"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/tTH1YWr6OHRjHoDDKCLO_gBuA6s>
Subject: Re: [Cfrg] [irsg] IRSG review of draft-irtf-cfrg-xmss-hash-based-signatures-08
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 20 Jun 2017 11:45:22 -0000

(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" <stephen.farrell@cs.tcd.ie> 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
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>