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

Stephen Farrell <stephen.farrell@cs.tcd.ie> Mon, 24 July 2017 14:43 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 086B9131D70; Mon, 24 Jul 2017 07:43:58 -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=ham 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 EP-2XQSRrrWk; Mon, 24 Jul 2017 07:43:55 -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 94C32131D6F; Mon, 24 Jul 2017 07:43:55 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id CFF06BE50; Mon, 24 Jul 2017 15:43:53 +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 KerVh1aHaFrG; Mon, 24 Jul 2017 15:43:53 +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 8FCF3BE4D; Mon, 24 Jul 2017 15:43:53 +0100 (IST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cs.tcd.ie; s=mail; t=1500907433; bh=2S9ypQrn2gggphyOnbhoL92EDLT7WOFZT3HuSd5RxeI=; h=Subject:To:Cc:References:From:Date:In-Reply-To:From; b=H3BqAYKuBFGwGM4YkQVifu1hiEzQSUiF3w+Zwj8TOhVIBKhaDBD7f3oGmthmF/M2R uUVpR9PCIRI5xFjZ1jonjNoHxV40HmfTmtCVu+NQvHxnfzCK9nL3wHSrTWFGfzppgf F7GomCDKN8qf/BsSgEWrmu9ySlZK+ZdQ7G+RVSYI=
To: "A. Huelsing" <ietf@huelsing.net>, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>, Alexey Melnikov <alexey.melnikov@isode.com>, "irsg@irtf.org" <irsg@irtf.org>, "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> <27cc7000-7fd5-27dd-b8b5-9b9518a9f3ad@huelsing.net> <1785b9ed-fb53-889a-9d34-311c7ea5c762@cs.tcd.ie> <4699f3d2-40ce-9c40-d29a-d24ecb3b6cab@huelsing.net>
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
Openpgp: id=D66EA7906F0B897FB2E97D582F3C8736805F8DA2; url=
Message-ID: <92dbf402-be6b-cf6d-40da-983f6faa5e8c@cs.tcd.ie>
Date: Mon, 24 Jul 2017 15:43:52 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1
MIME-Version: 1.0
In-Reply-To: <4699f3d2-40ce-9c40-d29a-d24ecb3b6cab@huelsing.net>
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Q2k6mEjaTdQ1bhwHJ55DK04ULXQssufU0"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/VB41J987wmMGIgsqBolZsoqTdqc>
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: Mon, 24 Jul 2017 14:43:58 -0000

Hi Andreas,

I took a look at the diff vs. -09 and all the changes
that I reckon were needed are covered nicely. I also
think that the set of changes as a whole are good
improvements, thanks.

So fwiw, I think this is ready for publication.

Cheers,
S.

PS: I'd still prefer fewer options, but we talked
about that already:-) That oughtn't delay publication
I reckon.

On 24/07/17 15:30, A. Huelsing wrote:
> Dear Stephen,
> 
> we tried to make the required changes. Please have a look if you are fine
> with the changes (especially regarding section 5 and the reference
> implementation).
> 
> You find our answers to your review below and the new draft version attached.
> 
> Thanks again for your time,
> 
> Andreas, Aziz, Denis, Joost & Stefan
> 
> 
> ################# Answers ####################
> 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.
> 
> #Done
> 
> - 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.
> 
> #Done
> 
> 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.)
> 
> ####
> #   We significantly changed section 5, please check if this
> #   satisfies your remarks
> ####
> 
> - 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.
> 
> # Added section on reference implementation
> 
> 
> nits, near-nits and other ignorable things:
> -------------------------------------------
> 
> - abstract: I'd suggest s/can withstand attacks/ can withstand
>   so-far known attacks/
>  
> # Done
> 
> - 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.
> 
> # Done
> 
> - 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.
> 
> # Done
> 
> - 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.
> 
> # Done: Removed the left shift as it is never used for single bytes
> 
> - 2.5: having the "type word" as octet 15 of a 32 byte address
>   seems odd. Is there a reason why? (Just wondering.)
> 
> # Yes: We got the space and think that it simlifies implementation if
> one always has to manipulate whole words (and can treat the address as
> uint32_t[8])
>  
> - 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.)
> 
> # Done
> 
> - 3.1.3: maybe note that "/" means nothing? Which I assume it
>   does? Better might be to just say that.
>  
> # Done
> 
> - 3.1.5: "a maximum value of len_1 * (w - 1) * 2^8" is missing
>   units
>  
> # Done: value -> Integer value
> 
> - 3.1.5: "the variable" - which one?
> 
> # Done: Added explanation
> 
> - 3.1.5: "For the parameter sets given in Section 5 a 32-bit
>   unsigned integer is sufficient." Sufficient for what?
> 
> # Done: Added " to hold the checksum"
>  
> - 3.1.5: The ascii art at the end of p16 doesn't help much.
> 
> # while the art does not contain new information, we think it's
> a handy reminder. Would prefer to keep it like this.
> 
> - 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.
> 
> # Ok, so what should we do? I agree that key handling cannot be
> verified. Still, it seems necessary to emphasize this.
> If it is just about the use of the 2119 term,
> how about:
> "but it is crucial for security that the cryptographic strength
> matches that of the used WOTS+ parameters."?
> 
> - 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.
> 
> # We adressed this in a new sentence at the end of the
> # paragraph.
> 
> - 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.
> # That is exactly what it means. There are far more efficient
> # algorithms to compute that output (but also far more complex)
> 
> - 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.
> 
> # Done
>