Re: [Cfrg] Chopping out curves

David McGrew <mcgrew@cisco.com> Fri, 17 January 2014 12:41 UTC

Return-Path: <mcgrew@cisco.com>
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 633B91AE0A2 for <cfrg@ietfa.amsl.com>; Fri, 17 Jan 2014 04:41:06 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Level:
X-Spam-Status: No, score=-15.039 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_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
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 g5Y5q6qe3nJc for <cfrg@ietfa.amsl.com>; Fri, 17 Jan 2014 04:41:04 -0800 (PST)
Received: from rcdn-iport-4.cisco.com (rcdn-iport-4.cisco.com [173.37.86.75]) by ietfa.amsl.com (Postfix) with ESMTP id 1A7861AE08B for <cfrg@irtf.org>; Fri, 17 Jan 2014 04:41:04 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=4874; q=dns/txt; s=iport; t=1389962452; x=1391172052; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=QVr1MFZdOZmXwxyU2FEYWFjgeR/rRHc4orJGVfbExXA=; b=g6JoPbPwFfAZuCYI2pTxyUdMgBi6kLAurCkHwLgbLKA5Bmidgj8zMDkw Rjp+p9Cvf9EQQFyNL4XVEjBDsVQr5zhLEaAA/xkacvy1NXXkEsr37u+bI L/hT+2u1yp7S8S3slF99MpMNC5pkzcyphcwPlTNPUQ/Va510pUSMMBvT1 M=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AjEFAJFf2FKtJXHA/2dsb2JhbABZgws4u2eBDxZ0giUBAQEDAQEBAS8BBTYKARALDgoJFg8JAwIBAgEPBjAGAQwBBQICBQsHBIdRAwkIDb9RDYVWF4xcD4EyCwYBUAeEOAEDiUeKdIF6gWyGRoYWhTuDSx6BLAEIFwQ
X-IronPort-AV: E=Sophos;i="4.95,670,1384300800"; d="scan'208";a="298076002"
Received: from rcdn-core2-5.cisco.com ([173.37.113.192]) by rcdn-iport-4.cisco.com with ESMTP; 17 Jan 2014 12:40:50 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core2-5.cisco.com (8.14.5/8.14.5) with ESMTP id s0HCemX8017140; Fri, 17 Jan 2014 12:40:49 GMT
Message-ID: <52D924D2.2070308@cisco.com>
Date: Fri, 17 Jan 2014 07:40:50 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Michael Hamburg <mike@shiftleft.org>, Watson Ladd <watsonbladd@gmail.com>
References: <CACsn0cmJX2begH0q8vOUZhP2t3CFo_2Ad71Neke4EKejoYCPRg@mail.gmail.com> <CAGZ8ZG1qF4ba3ogjHQnMwgXV+0Fj7eR44QdvuSw3GYBvNVFZBA@mail.gmail.com> <c406386b6fc67d11332141423f2f0f40.squirrel@www.trepanning.net> <CACsn0c=Eh1J81JHq=u8WsTtVK4HAJDghyisTZnM6U61jdr2KUQ@mail.gmail.com> <E283FD8C-1716-4540-B71F-D28F49DA2AD7@shiftleft.org>
In-Reply-To: <E283FD8C-1716-4540-B71F-D28F49DA2AD7@shiftleft.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
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: Fri, 17 Jan 2014 12:41:06 -0000

Hi Michael, and Watson,

On 01/16/2014 05:53 PM, Michael Hamburg wrote:
> 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.

I agree that people need more time to understand and think about the 
issues.  Let me suggest an approach:

- add a placeholder section to the draft stating that "This draft 
identifies one curve at each important security level, in order to 
promote interoperability.   These curves will be described in a future 
version of this draft.  Feedback should be directed to the authors and 
to cfr@ietf.org."

- in the draft, outline the pros and cons for each curve type (this 
could be as simple as Michael's text in this email)

- collect feedback from reviewers and implementers during the lifetime 
of the draft

- before RFC publication, choose the curves and fill in the section.   
Leave all the text about the curves that were chosen, and move the text 
about the other curves either to an appendix or to the rationale.   Edit 
the rationale section so that it explains why the particular curves were 
chosen as mandatory-to-implement, and why the others were not.

This approach would make sure that the draft gets a broad review, which 
is really important, and it allows us to postpone making choices that 
might limit the solution space that gets considered. Our goal should be 
to create a well-considered RFC that provides value for the broadest 
possible community.

regards,

David

>
> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
> .
>