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.