Re: [Cfrg] [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement

Alyssa Rowan <> Sun, 12 January 2014 12:58 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 36C971ADFA2 for <>; Sun, 12 Jan 2014 04:58:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.798
X-Spam-Status: No, score=0.798 tagged_above=-999 required=5 tests=[BAYES_50=0.8, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PhyDiB-Ti_IN for <>; Sun, 12 Jan 2014 04:58:08 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id D6ECD1AD738 for <>; Sun, 12 Jan 2014 04:58:07 -0800 (PST)
Received: from [] ( []) by (Postfix) with ESMTPSA id 711C7602B3 for <>; Sun, 12 Jan 2014 12:57:55 +0000 (GMT)
Message-ID: <>
Date: Sun, 12 Jan 2014 12:57:55 +0000
From: Alyssa Rowan <>
MIME-Version: 1.0
References: <> <> <20140112062942.GA32437@LK-Perkele-VII>
In-Reply-To: <20140112062942.GA32437@LK-Perkele-VII>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Subject: Re: [Cfrg] [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sun, 12 Jan 2014 12:58:11 -0000

Hash: SHA512

On 12/01/2014 06:29, Ilari Liusvaara wrote:
>> One problem with defining EdDSA for larger curves is that the 
>> needed hashes are large.

On 12/01/2014 06:40, Peter Gutmann wrote:
> Are they? [...]

EdDSA uses a hash to generate deterministic secret random exponents, to
avoid eating entropy when signing (like ECDSA does in its natural
habitat). That will need to be a big enough hash to cover the size we
need: 512 bits covers 2^255 - 19, but to cover Curve3617 or E521, we're
going to need a bigger boat.

On 12/01/2014 06:29, Ilari Liusvaara wrote:
> [...] And there are very few hashes with serious analysis that can 
> do >512 bits.

That's why I observed in the OP that Keccak (the eventual SHA-3) may
have some useful properties in this arena: the sponge function's
flexible output size, I think, makes it a natural fit.

However, there may be disagreement in the wider arena as to whether
NIST's endorsement of it counts as a positive, a NOP, or a negative,
in light of the wider situation.

I recognise that, and empathise with it: it deserves careful, open
consideration, and a discussion weighing up which hash we use, why, and
how, I think. Bullet tree time, to explore my thoughts on the matter:

• Suitability:
  - Keccak's output size (and parameters) are flexible.
    · This is _very_ handy for the curves bigger than 25519!
    · We could even if we wished set our own parameters to suit.
    · Of course, if we did that, it wouldn't be SHA-3, but we might be
      able to hardware-accelerate it anyway.
    · Possible suitable parameter selections? Positives & negatives.
  - This is less true of some other competitors.

• NIST wanted to reduce the capacity after the competition.
  - Keccak authors defended that choice as safe.
    · Many SHA-3 entries were deliberately conservative.
    · It does reduce the margin of safety against second-preimage.
    · But we _wanted_ SHA-3 very conservative, 'just in case'.
    · BLAKE team reduced rounds of BLAKE2 for speed => still OK.
    · Is it an issue if it's still better than ρ?
  - Well, that escalated quickly. They couldn't have timed it worse.
    · Snowden revelations.
    · Coinciding with NIST proposing safety margin reduction in SHA-3.
    · Looked bad! Much grumbling.
    · NIST quickly backed down: didn't want to be seen poisoning the
  - SHA-3 will be Keccak, as submitted in final round, no changes,
    no nasty surprises, apparently.
    · Except the padding [10…1] might be swapped for Sakura's.
    · Which also seems sensible: pretty straightforward Merkle root.

• Why did NIST (and/or NSA, therefore) like it?
  - Stated reason: because it's nothing like SHA-2.
    · An attack weakening Merkle-Dåmgard constructs is unlikely to be
      directly relevant to sponge functions.
    · Fair enough. Seems legit.
  - Either they like strong, or they like secretly weak.
    · We aren't mindreaders, and have no way of knowing which.
    · C'est la vie!
  - Its software performance is... okay. It's not great.
    · Skein and BLAKE were twice the speed, and left it in the dust.
    · BLAKE2 is even faster!
    · Keccak lies around the middle of the pack, a little slower than
  - It's very fast in hardware.
    · Now _this_ is a _very_ consistent thing NIST/NSA like: because
      basically all their crypto implementations are hardware.
    · This is therefore fairly likely to have been a dominant factor.
    · Fast hardware performance is a negative in a PBKDF or a Hashcash,
      which we actually want to be slow to measure out workfactor of
    · But it's a positive in a signature scheme, as long as the hash is
      strong enough to resist any plausible second-preimage attack.
    · And it is.
    · A collision would not suffice here.

• Is there anything wrong with Keccak?
  - As far as we know: nope.
  - It looked very strong during the competition: it still does.
  - I don't know anything to suggest it's weak. Theoretically it
    looks pretty good.
  - None of the other SHA-3 final round candidates look bad either.
  - Even SHA-2 still doesn't look bad, exactly.
    · Except for the length-extension, which isn't a threat here.
    · I do not think we want to use an NSA-designed algorithm in a new
      signature scheme, when we have new ones that were designed as
      part of an open competition and have been widely discussed.

• Speed?
  - As above, software: ...okay, but not great; hardware: excellent.
  - Will we get hardware?
    · Crystal ball time!
    · Eventually, probably yes, due to it being SHA-3. NIST pulls a lot
      of weight in that area.
    · If we use it in this signature scheme, that actually may make a
      small difference. TLS, etc, certainly wouldn't hurt adoption.
    · Would we be able to use any such hardware?
    · Without doubt, if the hardware exposes the sponge function
      itself. Otherwise, most probably; depends on what we choose.
  - How does hash performance impact?
    · Probably relatively little. Signatures usually cover small
      things; key exchanges, etc, and the EC code will dominate time.
    · The case where it does: signing larger files. Code signing, etc.
    · If that's a problem, there's a tried-and-true solution already:
      a detached signature covering a manifest of hashes, which could
      be anything we like, e.g., tree hash mode of Skein, whatever.
    · I/O however remains the firm bottleneck on anything big.
    · Keccak isn't _that_ slow.

So. Thoughts?

- --