Re: [Cfrg] Chopping out curves

Michael Hamburg <mike@shiftleft.org> Thu, 16 January 2014 22:54 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8AAB01AD739 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 14:54:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 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, RDNS_DYNAMIC=0.982, SPF_PASS=-0.001] autolearn=no
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 DWpODd_0G5ZB for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 14:53:59 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id 202171AD672 for <cfrg@irtf.org>; Thu, 16 Jan 2014 14:53:59 -0800 (PST)
Received: from [10.184.148.249] (w035.z205158021.lax-ca.dsl.cnc.net [205.158.21.35]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 7ED563AA03; Thu, 16 Jan 2014 14:51:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1389912717; bh=spGBCvhnLwgU3pZESz/b8uLY8xCchgS9tjcYiLbBDAk=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=HJfsW+VeoHRu8vzlhsN/6KYHMGL9VVlQFU/xUWHcCNidberUr4hISVvj2+a+noJk1 /J7flHmTmtM3ElriJDhLHqRscvwC4xjWZ71y1cDseM+T7wFHRzTSFj0e2qxDoSbUba 3YMEFN32wxqK6Ofw8SRVDgTS0NVFJMrP30JA4AJc=
Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CACsn0c=Eh1J81JHq=u8WsTtVK4HAJDghyisTZnM6U61jdr2KUQ@mail.gmail.com>
Date: Thu, 16 Jan 2014 14:53:42 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <E283FD8C-1716-4540-B71F-D28F49DA2AD7@shiftleft.org>
References: <CACsn0cmJX2begH0q8vOUZhP2t3CFo_2Ad71Neke4EKejoYCPRg@mail.gmail.com> <CAGZ8ZG1qF4ba3ogjHQnMwgXV+0Fj7eR44QdvuSw3GYBvNVFZBA@mail.gmail.com> <c406386b6fc67d11332141423f2f0f40.squirrel@www.trepanning.net> <CACsn0c=Eh1J81JHq=u8WsTtVK4HAJDghyisTZnM6U61jdr2KUQ@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
X-Mailer: Apple Mail (2.1827)
Cc: Trevor Perrin <trevp@trevp.net>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Chopping out curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Jan 2014 22:54:00 -0000

Hey Watson,

Let’s maybe let this sit for a couple of days before declaring the matter settled.  I mean, as the author of Goldilocks, I’d love to see it become the one stronger curve that gets adopted.  But Trevor proposed chopping curves literally one hour ago, and Goldilocks has been on Safecurves for less than a week and isn’t even completely implemented.  I don’t want it to be railroaded into being the one curve in a new RFC, even if just for a couple git revisions.

Defense for why it’s a good curve, though:
* Cofactor 4 is minimal for Edwards.  It could just as easily be a Montgomery curve; Ed vs Mont was mostly an arbitrary choice.
* 448 is a round number (although this can hurt us in point encoding, depending on the options)
* 448 is about the largest bitsize which can fit into a 16-limb reduced-radix multiplier on a 32-bit arch without carry problems.
* 2^448-2^224-1 is Karatsuba multiplier friendly.
* Solinas primes are fast.  Field mul comparable to about 2 muls over 2^255-19 on Intel.

Downsides:
* If you don’t like “special” primes, then you surely won’t like a Solinas trinomial prime.
* If the point encoding is as spec’d, it’s one bit too long.

Cheers,
— Mike



On Jan 16, 2014, at 2:36 PM, Watson Ladd <watsonbladd@gmail.com> wrote:

> On Thu, Jan 16, 2014 at 2:07 PM, Dan Harkins <dharkins@lounge.org> wrote:
>> 
>> On Thu, January 16, 2014 1:50 pm, Trevor Perrin wrote:
>>> On Thu, Jan 16, 2014 at 1:40 PM, Watson Ladd <watsonbladd@gmail.com>
>>> wrote:
>>>> Dear all,
>>>> Trevor Perrin suggests that we only put in Curve25519/T25519 and
>>>> E383/M382 so implementors can focus on 4 curves ala Suite B. Are there
>>>> any protocols in which larger curves would be useful? Anything we
>>>> might be missing with this decision?
>>> 
>>> I didn't quite suggest that.
>>> 
>>> I do feel there should be fewer curves.  Perhaps only curve25519 and
>>> (either Curve3617 or Ed448-Goldilocks).
>>> 
>>> It takes a great deal of effort to do high-speed, const-time
>>> implementations of a different curve, so we should not diffuse that
>>> effort across too many choices.
>>> 
>>> Note that Suite B only has 2 curves (P-256 and P-384).
>> 
>>  I think this is a good idea. Too much choice can lead to confusion
>> and lack of interoperability. When the brainpool curves were added
>> we pared it down from 14 (including twisted variants) to 4.
>> 
>>  Suite B has 2 curves because it defines two security levels. We can
>> define more security levels if needed but we should probably only
>> have 1 Chicago curve at each level.
> 
> So the question is which. I think curve25519 and Ed448-Goldilocks make
> sense, together with an
> isogenous curve for signatures since Montgomery curves are a bit odd
> from that perspective. Does anyone see a need
> for more security levels then that/are these choices terrible for
> reasons we haven't appreciated?
> 
>> 
>>  Dan.
>> 
>> 
>> 
>> 
> 
> 
> 
> -- 
> "Those who would give up Essential Liberty to purchase a little
> Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg