[Cfrg] fwd: Re: [Cryptography] IETF discussion on new ECC curves.

=JeffH <Jeff.Hodges@KingsMountain.com> Sun, 27 July 2014 14:21 UTC

Return-Path: <Jeff.Hodges@kingsmountain.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 1B2F11A0280 for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 07:21:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.066
X-Spam-Level:
X-Spam-Status: No, score=-1.066 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, IP_NOT_FRIENDLY=0.334, J_CHICKENPOX_31=0.6, LOTS_OF_MONEY=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 pEAQQEeP0vz1 for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 07:21:31 -0700 (PDT)
Received: from gproxy6-pub.mail.unifiedlayer.com (gproxy6-pub.mail.unifiedlayer.com [67.222.39.168]) by ietfa.amsl.com (Postfix) with SMTP id 9F1C71A0276 for <cfrg@irtf.org>; Sun, 27 Jul 2014 07:21:30 -0700 (PDT)
Received: (qmail 2868 invoked by uid 0); 27 Jul 2014 14:21:30 -0000
Received: from unknown (HELO cmgw4) (10.0.90.85) by gproxy6.mail.unifiedlayer.com with SMTP; 27 Jul 2014 14:21:30 -0000
Received: from box514.bluehost.com ([74.220.219.114]) by cmgw4 with id XYMF1o00L2UhLwi01YMJlV; Sun, 27 Jul 2014 14:21:28 -0600
X-Authority-Analysis: v=2.1 cv=OcELUHjY c=1 sm=1 tr=0 a=9W6Fsu4pMcyimqnCr1W0/w==:117 a=9W6Fsu4pMcyimqnCr1W0/w==:17 a=cNaOj0WVAAAA:8 a=f5113yIGAAAA:8 a=ekOJvlQLSnQA:10 a=NDtjRgbWLu4A:10 a=3NT3xRclEPMA:10 a=8nJEP1OIZ-IA:10 a=ieNpE_y6AAAA:8 a=XYUc-DgfXtMA:10 a=aQyOShshic0A:10 a=A_MYNcKfAAAA:8 a=WOIJDy4HAAAA:8 a=dEDnwm5mAAAA:8 a=VvWRDUFFAAAA:8 a=FP58Ms26AAAA:8 a=RcrKDrMYAAAA:20 a=yMTatn1YAAAA:8 a=s90BdVvJAAAA:8 a=rxypbISzv3UYxv2DE7wA:9 a=pgQiit2yM-kAejvf:21 a=lskClPdghSBjhIJz:21 a=wPNLvfGTeEIA:10 a=2MUaMXdx0lEA:10 a=XuD5i-D3J3cA:10 a=gz4j-12ivIwA:10 a=hU4wx-L-dZAA:10 a=sj9yjA9kNZIA:10 a=uy88i352CyQA:10 a=nS7hf6rJOiYA:10
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=kingsmountain.com; s=default; h=Content-Transfer-Encoding:Content-Type:Subject:To:MIME-Version:From:Date:Message-ID; bh=sQZPAwuRvJukNbj96mzEevwdL8uLhnFRutde4hTbPJs=; b=AGuZcWeFofhDXhQd2oLXU2HVTr0e7oQEsgFXoQNKxsmEpEnxpdw9EobiDT25syMEIWC2CC5LVmY/RQb5sLflfBK7sjhPCoAska/XKP+HNngRjoWaRFO8YmoyrVEVHOOJ;
Received: from [98.248.231.21] (port=49506 helo=[192.168.11.14]) by box514.bluehost.com with esmtpsa (TLSv1:DHE-RSA-AES128-SHA:128) (Exim 4.82) (envelope-from <Jeff.Hodges@KingsMountain.com>) id 1XBPK8-0004X3-KA for cfrg@irtf.org; Sun, 27 Jul 2014 08:21:16 -0600
Message-ID: <53D50ADA.20901@KingsMountain.com>
Date: Sun, 27 Jul 2014 07:21:14 -0700
From: =JeffH <Jeff.Hodges@KingsMountain.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: IRTF Crypto Forum Research Group <cfrg@irtf.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Identified-User: {11025:box514.bluehost.com:kingsmou:kingsmountain.com} {sentby:smtp auth 98.248.231.21 authed with jeff.hodges+kingsmountain.com}
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Ytg5JLtZxbUE20VXLJAQ_mgm1IA
Subject: [Cfrg] fwd: Re: [Cryptography] IETF discussion on new ECC 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: Sun, 27 Jul 2014 14:21:33 -0000

[ discussions wrt CFRG curve selection process seems to be spread over a 
variety of lists. fwd'g fyi/fwiw/ftr/ymmv.. ]


Subject: Re: [Cryptography] IETF discussion on new ECC curves.
From: Trevor Perrin <trevp@trevp.net>
Date: Sat, 26 Jul 2014 22:16:06 -0700
To: Phillip Hallam-Baker <phill@hallambaker.com>
Cc: "cryptography@metzdowd.com" <cryptography@metzdowd.com>

On Sat, Jul 26, 2014 at 11:32 AM, Phillip Hallam-Baker
<phill@hallambaker.com> wrote:
 > There was much discussion on new curves for ECC. The discussion looks
 > like it is down to choosing curves that are close to powers of 2 which
 > can be computed twice as fast as the traditional random curves in a
 > constant time implementation.
 >
 > The choices on the table right now are the NUMS curves proposed by
 > Brian LaMacchia and co at Microsoft and Dan Bernstein's Curve 25519
 > (2^255-19).

There should be more on the table.  Curve4417 (DJB et al) and
Ed448-Goldilocks (Mike Hamburg) are also good curves, at ~207 and ~224
bits of security.

https://eprint.iacr.org/2014/526.pdf
http://sourceforge.net/projects/ed448goldilocks/


 > One point of comparison of course is performance but it is actually
 > quite difficult to compare like with like. There does not seem to be
 > more than a 15% difference between any of them.

Here are some efficiency scores based on extrapolating performance vs
security for Microsoft NUMS (w-*-mers and ed-*mers), Curve25519,
Goldilocks, and others:

https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0

The differences are larger than 15%.  For example, Microsoft's fastest
512-bit curve takes close to twice the time of 448-bit Goldilocks.
But you would expect a 512-bit curve to be only ~40% slower than a
448-bit curve.


 > Most of the other
 > differences fall away when the point compression patent expires which
 > I am told is a matter of weeks.

US 6141420 expires Tuesday.


 > Another point that is important for me is consistency. I want as few
 > choices as possible. Given that the CA industry is going from RSA2048
 > with a putative work factor of 2^120 and all of these alternatives are
 > much faster and with much shorter keys, I can't see why I would go for
 > a 2^128 work factor. So I am only really looking for 2^256 work
 > factor.

It's reasonable to ask for a work factor significantly greater than
2^128 as a hedge against cryptanalysis.  But people like Adam Langley,
myself, and Mike Hamburg have argued that demanding the work factor
match a precise number (like 2^256) is over-prescriptive.

https://www.imperialviolet.org/2014/05/25/strengthmatching.html
https://moderncrypto.org/mail-archive/curves/2014/000140.html

Curve size has a significant effect on efficiency due to availability
of primes and options for dividing field elements into processor
words.

(Dan Bernstein has a great discussion of this:
https://moderncrypto.org/mail-archive/curves/2014/000237.html
)

So instead of fixing an exact security level (and thus curve size) in
advance, it makes more sense to consider a range of acceptable
security levels, and then choose a particularly efficient curve within
that range, as Curve4147, Goldilocks, and the 2^521-1 curves have
done.

 > What do folks think here? I see a bunch of possibilities
 >
 > 1) We choose the NUMS curve for the 2^256 work factor curve and Curve
 > 25519 for 2^128
 >
 > 2) We choose NUMS for both
 >
 > 3) We choose Curve25519 and E521
 >
 > 4) We spend several years arguing to no point

I think the world should move towards Curve25519 for a fast
"regular-strength" curve, and choose one efficient "extra-strength"
curve in the 384-512ish range.  Curve41417, Goldilocks, and E-521 seem
like prime contenders.

FWIW, there's a "curves" list where this and other topics in elliptic
curve crypto are discussed:

https://moderncrypto.org


Trevor
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography