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

Stephen Farrell <stephen.farrell@cs.tcd.ie> Fri, 16 June 2017 00:56 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 839471270FC; Thu, 15 Jun 2017 17:56:15 -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 OZWIHLwQ6WpR; Thu, 15 Jun 2017 17:56:13 -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 C501A126E3A; Thu, 15 Jun 2017 17:56:09 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id 0E8F6BEB3; Fri, 16 Jun 2017 01:56:07 +0100 (IST)
X-Virus-Scanned: Debian amavisd-new at scss.tcd.ie
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 oe9PZpy9uNMT; Fri, 16 Jun 2017 01:56:05 +0100 (IST)
Received: from [172.28.172.2] (unknown [185.51.73.39]) by mercury.scss.tcd.ie (Postfix) with ESMTPSA id F3EC1BEAA; Fri, 16 Jun 2017 01:56:03 +0100 (IST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cs.tcd.ie; s=mail; t=1497574565; bh=FxsusIsoFCI4VPSp2suiYw3WMyLzS/6eH+hnBI5pPvk=; h=Subject:To:References:From:Date:In-Reply-To:From; b=eXyfdw46UoVyGuS1/qE2kZkidUvTmZZHZu0R2+TCnRcxz6FSPZfM7zNsXXv9X/IOc Mnk/RvSpvrwxwNAmegzWeEfU45szvfaiUgRNcEiKvdLtwLQpS3KeYi1Bx11HUFr0CW HmKahsqluQALFjEOv4VdpnOXo5idNVhy+Bqj8HPQ=
To: "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>
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>
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
Openpgp: id=D66EA7906F0B897FB2E97D582F3C8736805F8DA2; url=
Message-ID: <9e6b6146-e376-86cb-70be-0127a3e72d16@cs.tcd.ie>
Date: Fri, 16 Jun 2017 01:56:01 +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: <D566ADE0.963E4%kenny.paterson@rhul.ac.uk>
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="2HF9T7PvPKFdPS2lNjO5SiD5C3vG6wpXt"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/nV-NpirZfwsbkPjw8FgK5JppgB8>
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: Fri, 16 Jun 2017 00:56:15 -0000

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.