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

Stephen Farrell <stephen.farrell@cs.tcd.ie> Tue, 27 June 2017 15:50 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 D58A8129ADF; Tue, 27 Jun 2017 08:50:04 -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 prAIf3Mwr6y3; Tue, 27 Jun 2017 08:50:02 -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 C9C04128BA2; Tue, 27 Jun 2017 08:50:01 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id 89108BE55; Tue, 27 Jun 2017 16:49:59 +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 hZFgyzyxa3VN; Tue, 27 Jun 2017 16:49:59 +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 F1108BE50; Tue, 27 Jun 2017 16:49:58 +0100 (IST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cs.tcd.ie; s=mail; t=1498578599; bh=QodNXlmWZwD5Ae6Y2oshtDdWlJvmavhDSm7sYsH/c3s=; h=Subject:To:Cc:References:From:Date:In-Reply-To:From; b=MSKIavTz501j1dzGvTg02gpAUIx6KeLvayMH7e2KEUAAbzikjhItH3pi4sQ3Ruzcq FlzbZPhrmvkj5FULbGRXuCdM2tC34k/+2UksuZ6lznNYWtNJo5dLnc7v1HVMaWtflU qI6SgrjxFeV2TRua7NZ5hIa3TddZMSH0/l9uyrqw=
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>
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
Openpgp: id=D66EA7906F0B897FB2E97D582F3C8736805F8DA2; url=
Message-ID: <1785b9ed-fb53-889a-9d34-311c7ea5c762@cs.tcd.ie>
Date: Tue, 27 Jun 2017 16:49:57 +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: <27cc7000-7fd5-27dd-b8b5-9b9518a9f3ad@huelsing.net>
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="ueEfgrN5Q7W2NvIjnt9uDtnLDV4uRsdVS"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/EZMHnwBB5X8S6v_LkJsxgXAFjqg>
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, 27 Jun 2017 15:50:05 -0000

Hi Andreas,

On 27/06/17 14:01, A. Huelsing wrote:
> 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?

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
> have dependencies to OpenSSL for SHA2.

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.

> 
>>>>> 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.
> Added parenthesis.
>>>>> - 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.
> Indeed, we now give idx_sig as additional input (and don't use the already
> 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.

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

I think those would be fine improvements yes.

Cheers and thanks for considering the review,
S.

>>>>> - 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.
> See above.
> 
> Cheers,
> 
> Stefan & Andreas
>>>>> 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.
>>>>>
>>>>>
>>>>>
> 
>