Re: [Cfrg] Comparing ECC curves

Patrick Longa Pierola <plonga@microsoft.com> Thu, 24 July 2014 06:36 UTC

Return-Path: <plonga@microsoft.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 E4F711A00C9 for <cfrg@ietfa.amsl.com>; Wed, 23 Jul 2014 23:36:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 yz5cVrbD9WR1 for <cfrg@ietfa.amsl.com>; Wed, 23 Jul 2014 23:36:13 -0700 (PDT)
Received: from na01-bn1-obe.outbound.protection.outlook.com (mail-bn1lp0142.outbound.protection.outlook.com [207.46.163.142]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A405B1A0010 for <Cfrg@irtf.org>; Wed, 23 Jul 2014 23:36:12 -0700 (PDT)
Received: from BY2PR03MB474.namprd03.prod.outlook.com (10.141.141.149) by BY2PR03MB476.namprd03.prod.outlook.com (10.141.141.153) with Microsoft SMTP Server (TLS) id 15.0.990.7; Thu, 24 Jul 2014 06:36:10 +0000
Received: from BY2PR03MB474.namprd03.prod.outlook.com ([10.141.141.149]) by BY2PR03MB474.namprd03.prod.outlook.com ([10.141.141.149]) with mapi id 15.00.0990.007; Thu, 24 Jul 2014 06:36:10 +0000
From: Patrick Longa Pierola <plonga@microsoft.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>, "Cfrg@irtf.org" <Cfrg@irtf.org>
Thread-Topic: [Cfrg] Comparing ECC curves
Thread-Index: AQHPpsVlokHtIBVyPkOedmRlQCZAupuurLaA
Date: Thu, 24 Jul 2014 06:36:09 +0000
Message-ID: <bf68fd7300e14fb58330b094f4795f30@BY2PR03MB474.namprd03.prod.outlook.com>
References: <CAMm+Lwj9EPJ9v92xrkM1ceAbkWYe22fpOOBObUbUJjkk8X0dng@mail.gmail.com>
In-Reply-To: <CAMm+Lwj9EPJ9v92xrkM1ceAbkWYe22fpOOBObUbUJjkk8X0dng@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [50.47.83.223]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:
x-forefront-prvs: 028256169F
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(243025005)(24454002)(51704005)(189002)(57704003)(199002)(50986999)(81542001)(106116001)(74662001)(79102001)(86362001)(83322001)(66066001)(15975445006)(33646002)(54356999)(76176999)(86612001)(77982001)(81342001)(15202345003)(105586002)(101416001)(99396002)(2656002)(80022001)(99286002)(19580395003)(74316001)(46102001)(19580405001)(21056001)(76576001)(20776003)(83072002)(31966008)(85852003)(107046002)(74502001)(76482001)(106356001)(95666004)(85306003)(107886001)(92566001)(64706001)(87936001)(4396001)(108616002)(24736002); DIR:OUT; SFP:; SCL:1; SRVR:BY2PR03MB476; H:BY2PR03MB474.namprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; LANG:en;
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: microsoft.onmicrosoft.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/lJfBqKUmV1OG5VVQcbQ3ae5PJ_c
Subject: Re: [Cfrg] Comparing 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: Thu, 24 Jul 2014 06:36:15 -0000

> Phillip Hallam-Baker wrote:
> 2) Should the security levels be maximums or minimums?
>
> Looking through the Microsoft presentation I see that they have chosen work factors of 128, 192 and 256 bits. This is reasonable of course but maybe not the best  
> way to compare like with like. Because the real limitations here are the machine resources which nowadays come in units of 64 bits.

> What I am really interested in is how much security you can provide for an n*64 bits wide datapath. I do not want to have to mess about with a129 bits to achieve 128
> bits security. If someone can do the math significantly faster then I'll take 127 bits. But I certainly don't want to go below 120 bits unless the advantages were
> phenomenal.

An important related point: I haven't seen any result in the literature demonstrating any meaningful performance advantage when dropping one bit from 256 to 
255 bits, or from 384 to 383, or from 512 to 511 (case of primes with the form 2^m - c). Our experiments [1] reveal that one bit less injects less than 4% of performance 
improvement. Under this light, we prefer the conservative approach: keep a traditional 2 x s bitlength, which is multiple of a computer word of 64 bits (for a bit-security
level s = {128,192,256}), maximize ECDLP security and make the curve generation process as simple and rigid as possible. This also helps to keep curve design at different
security levels consistent. And, arguably, all this together avoids some potential errors and ease the work of implementers. At the other side of the spectrum, I haven't seen
any performance advantage of increasing the prime bitlength beyond 2 x s. It is actually potentially counterproductive: in [1] we show that increasing the field
representation by one word (which happens when moving from 512 bits to 521 bits for example) degrades performance by a factor 1.2. In this case, the performance
issues make the conservative approach even more attractive, taking as a bonus all the benefits mentioned above. 

[1] http://eprint.iacr.org/2014/130.pdf    
     
> 3) Do we need to consider 2^192 work factor?

> I can't see any case where I am interested in a work factor of 2^192.
> Either I am willing to make some concession to performance or I want it gold plated and 2^256. I would quite like to see the 2^192 work factor nuked.

> The only reason for going above 2^128 is that I don't trust the algorithm. Its not about increasing the work factor by 2^64, its about increasing the safety margin in the
> case of a cryptanalytic attack. I have seen attacks that reduce the work factor to the root of the intended one (i.e. 2^n becomes 2^(n/2)). I can't think of a better one
> that has been discovered offhand (most are not that good of course).
> So 2^256 makes me feel like I am sufficiently protected against algorithm compromise while 2^192 is kinda marginal.

Totally agreed. We should give preference to 128 and 256-bit sec levels.

Patrick 

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
http://www.irtf.org/mailman/listinfo/cfrg