Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

Michael Hamburg <> Tue, 15 July 2014 01:47 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 6D00E1B27C8 for <>; Mon, 14 Jul 2014 18:47:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 1.557
X-Spam-Level: *
X-Spam-Status: No, score=1.557 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id VbAJAv_pVG_e for <>; Mon, 14 Jul 2014 18:47:14 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 475881B27C4 for <>; Mon, 14 Jul 2014 18:47:14 -0700 (PDT)
Received: from [] ( []) by (Postfix) with ESMTPSA id 3DCC33AA13; Mon, 14 Jul 2014 18:45:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1405388753; bh=nJ3N9dZg9ZQCivpld0UP4LIqmeqX9tvqGOCzKjK9VJU=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=CaKuhPgxCCQfEPfHMPTiwOv0bRwZIyXw1jq7Y3S9QFUNLo60cQsEqD2G6iB9wM7ja sMVfM7ns1ChUf07v+PuirDM3aSGwCIu3MiQ0Oe57CD7T7yVBCVwaRct7/V6AINp+iD D0Oj8EXQHZvPAAhxtAGbduBEUC9seD4EPnoog2Rk=
Content-Type: multipart/alternative; boundary="Apple-Mail=_19620A0D-B2EF-43BA-8B01-7484BCB723D4"
Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
From: Michael Hamburg <>
In-Reply-To: <>
Date: Mon, 14 Jul 2014 18:47:10 -0700
Message-Id: <>
References: <> <>
To: Watson Ladd <>
X-Mailer: Apple Mail (2.1878.6)
Cc: "" <>
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves
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: Tue, 15 Jul 2014 01:47:15 -0000

On Jul 14, 2014, at 6:11 PM, Watson Ladd <> wrote:

> On Jul 14, 2014 12:49 PM, "Paterson, Kenny" <> wrote:
>> Dear CFRG,
>> CFRG has received a formal request from the TLS Working Group for
>> recommendations for new elliptic curves. Specifically, the TLS WG would
>> like CFRG to recommend:
>> - Curves suitable for both key establishment and digital signature
>>  (though the same curves need not be used for both purposes).
>> - One proposed curve or set of curves at the following security
>>  levels: 128-bit (~256-bit curve) and 256-bit (~512 bit curve).
>>  192-bit security is optional.
> I would like these to be taken as minimums. There is no reason
> Curve4417 should not be used for 192 bit security
> or Goldilocks448 if performance is acceptable.
> I am not sure that 512 bits is needed: the NSA only uses P-384 for Top
> Secret data. Perhaps this is an area where the
> TLS WG can do some more thinking about what they want to see.

I agree, but I’m biased since Ed448-Goldilocks is my proposal.

>>   R9.  Required: resist twist attacks [2]
> I don't like R9: twist attacks are only an issue with algorithms that
> work on the compressed form. It just feels different.
> Perhaps the requirement should be that implementations that miss
> checks avoid being completely insecure.

I agree.  That said, I expect every proposal except Brainpool to have the obvious
interpretation of this property: that the twist’s order is not smooth.

>>   R11.  Desired for key exchange: resist invalid curve attacks [2];
>>   note that complete addition laws help and are thus desirable [2].
>>   (Note that the use of ephemeral keys also resist such attacks.)
> I feel this should be folded into an edited R9.

In general invalid curve attacks are a property of an implementation, not a curve.
But complete addition laws should probably be on the list as nice-to-have.

>>   R12.  Required for PAKE: indistinguishability of curve points from
>>   random strings [2]
> Mike Hamburg will know better than I, but my vague recollection is
> that Elligator 2 worked for everything.

“Elligator squared” works for everything.  Elligator 2 works (in DJB’s proposed PAKE)
for every prime-field curve of even order.

Also, this isn’t required for every PAKE, just for EKE.  The alternatives SPAKE2 and
JPAKE don’t need this.  SPEKE, SPAKE2EE and Dragonfly want an encoding, but
it just has to map to the curve and doesn’t have to be uniform.  This means that
SWU will suffice if Elligator 2 isn’t available (i.e. they work on most or all curves).

I propose that R12 should be nixed.  And I’m not biased in this direction, since I’m an
author on the Elligator paper, and my proposal has this indistinguishability property.

— Mike Hamburg