Re: [Cfrg] Comparing ECC curves
Phillip Hallam-Baker <phill@hallambaker.com> Thu, 24 July 2014 15:14 UTC
Return-Path: <hallam@gmail.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 89C851A02D5 for <cfrg@ietfa.amsl.com>; Thu, 24 Jul 2014 08:14:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, 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 6zRqfIsxoXzm for <cfrg@ietfa.amsl.com>; Thu, 24 Jul 2014 08:14:07 -0700 (PDT)
Received: from mail-wi0-x22a.google.com (mail-wi0-x22a.google.com [IPv6:2a00:1450:400c:c05::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 49FD51A03EB for <Cfrg@irtf.org>; Thu, 24 Jul 2014 08:11:10 -0700 (PDT)
Received: by mail-wi0-f170.google.com with SMTP id f8so9399548wiw.3 for <Cfrg@irtf.org>; Thu, 24 Jul 2014 08:11:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=Nz0n+4YexCfxpF/cJF+A/0Gjiq21b3RTWBFwjSvKhok=; b=cLvy1049kgrmxzn3IvzbB7qz0I5PXBKw0zQQyWxN4EM37q4Us+QvInxvJ/bxn5zyeG XBj69E4wbXqd9XtEtbjsXSN7HNxGzi+U8zeoB4zS2N1RzurinNhxODAPg5dikMJT32R6 fqoJKDENSJshCJe+MhenU/m/r3OhtItUj7g34VSiiumaC03JGUXmluRjFD1ieJSAiSin /uDmRXyhCoA3MavOJlod+1Tp3kvRLb4GtmQmuLXJzk0zUU2d2RSyEmt6PwH/L+5p1Zh8 Jxcs4M6htUTKX8bkwTLrskR18+AG7N0KaMt1/9McR4rQozmtJTx89fKgrhtiEstPADF4 Ni/g==
MIME-Version: 1.0
X-Received: by 10.194.71.12 with SMTP id q12mr13279689wju.5.1406214667931; Thu, 24 Jul 2014 08:11:07 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.194.123.167 with HTTP; Thu, 24 Jul 2014 08:11:07 -0700 (PDT)
In-Reply-To: <53D117AD.8060506@sbcglobal.net>
References: <CAMm+Lwj9EPJ9v92xrkM1ceAbkWYe22fpOOBObUbUJjkk8X0dng@mail.gmail.com> <bf68fd7300e14fb58330b094f4795f30@BY2PR03MB474.namprd03.prod.outlook.com> <53D117AD.8060506@sbcglobal.net>
Date: Thu, 24 Jul 2014 11:11:07 -0400
X-Google-Sender-Auth: fiUcXMkrxG-gbJ6xWkH6y7IEFbM
Message-ID: <CAMm+LwiJbkr3z5DxDtVMqjrzt0bz=5+4MRkwBMSScoLh_K=k0Q@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: David Jacobson <dmjacobson@sbcglobal.net>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/j9vFhHExjqVNHAl7NpY9fwmtAW8
Cc: "Cfrg@irtf.org" <Cfrg@irtf.org>
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 15:14:13 -0000
On Thu, Jul 24, 2014 at 10:26 AM, David Jacobson <dmjacobson@sbcglobal.net> wrote: > On 7/23/14 11:36 PM, Patrick Longa Pierola wrote: > [snip] > >> 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 > > [snip] > > You are addressing performance. But what about the ease of making a > constant time implementation? The security value of 256 over 255 or 254 is > not much. It is just that 256 is a nice round number, and might be a > checkbox item. If we can accept 255 or 254, it might make constant time > implementations easier. Perhaps people who have done constant time > implementations can comment. My understanding here is that DJB has a curve with 255 bits that he claims operates a lot faster than the 256 bit alternatives. I do not know how that affects the work factor but what I do know is that I really don't care. E-521 seems to have been chosen as the fastest prime giving a work factor of at least 2^256. If someone finds a prime that gives a work factor of 2^240 and is 30% faster, I would have to think about which I preferred. Comparing performance of symmetric algorithms is easier in some ways as every strong 128 bit cipher has the exact same work factor. So we are arguing over whether they are strong and which is faster (which can of course be complex as it might be architecture dependent). The problem I am trying to explore here is how we compare two different proposals that deliver slightly different work factors. Another point to consider here is that the whole PKIX world is currently using 2048 bit keys and we have infrastructure built out to support them. Any of these choices is going to be dramatically faster and have shorter keys. We use public keys with an effective work factor of 2^120 because that is the best compromise of strength versus inconvenience, not because that is a work factor we are happy with. From an architectural point of view I would like my long term public keys that I use repeatedly to be a lot stronger than my ephemeral keys and session keys. So people implementing just one curve should probably be looking at the curves giving a work factor of approx 2^256 rather than the shorter ones. There are certainly people who think they need the absolute best performance and go for the shorter ones. But thats most likely to be driven by key size constraints trying to shoehorn into UDP packets and twitter packets.
- [Cfrg] Comparing ECC curves Phillip Hallam-Baker
- Re: [Cfrg] Comparing ECC curves Benjamin Black
- Re: [Cfrg] Comparing ECC curves Michael Hamburg
- Re: [Cfrg] Comparing ECC curves Phillip Hallam-Baker
- Re: [Cfrg] Comparing ECC curves Watson Ladd
- Re: [Cfrg] Comparing ECC curves Phillip Hallam-Baker
- Re: [Cfrg] Comparing ECC curves Watson Ladd
- Re: [Cfrg] Comparing ECC curves Patrick Longa Pierola
- Re: [Cfrg] Comparing ECC curves Phillip Hallam-Baker
- Re: [Cfrg] Comparing ECC curves David Jacobson
- Re: [Cfrg] Comparing ECC curves Phillip Hallam-Baker
- Re: [Cfrg] Comparing ECC curves Patrick Longa Pierola
- Re: [Cfrg] Comparing ECC curves Mike Hamburg
- Re: [Cfrg] Comparing ECC curves Phillip Hallam-Baker
- Re: [Cfrg] Comparing ECC curves Mike Jones
- Re: [Cfrg] Comparing ECC curves Yoav Nir
- Re: [Cfrg] Comparing ECC curves Michael Hamburg