Re: [Cfrg] Comparing ECC curves

Phillip Hallam-Baker <phill@hallambaker.com> Thu, 24 July 2014 17:24 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 8DB5B1A0AF8 for <cfrg@ietfa.amsl.com>; Thu, 24 Jul 2014 10:24:09 -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 KUrNyMuGXXpl for <cfrg@ietfa.amsl.com>; Thu, 24 Jul 2014 10:24:08 -0700 (PDT)
Received: from mail-wg0-x230.google.com (mail-wg0-x230.google.com [IPv6:2a00:1450:400c:c00::230]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3C5BD1A03AA for <Cfrg@irtf.org>; Thu, 24 Jul 2014 10:23:15 -0700 (PDT)
Received: by mail-wg0-f48.google.com with SMTP id x13so3063717wgg.19 for <Cfrg@irtf.org>; Thu, 24 Jul 2014 10:23:13 -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=NHYY5kRgDfUwj4egvnLCwxwA3CojkD33M+PHTsZHkQk=; b=LaN7ZIUx9JK9G8l9AU8r2H7Us4Mqb54mLF2hiFBfdhrAbSBk3HzSSPlH6zxkpzoDhE R39RDvLcW5I8wB3RjAbTFKz/8rWm5fClyVIx3vd835osS7fSjqrynR4Uh7XuN6JP9GDL kwY8J5Xs0gK1ams6DGvVehCp7wNYiSS2onQPWox8AI7F+qcC6G+7EVWmkUL8Fo2HZH8D TQ7Nzeg9UcYSK5iG8uQ855jkotbCGnmiUQoUQHtI0FaGgYSgyuvllNsH7p2iAeW7Sn5V iphFTI9uMKvKn45ANR9UA6RnzBX/VIpi9f9Y+IfUgN1KuJJJ+BuroAi0WO4807c65rjQ QKIA==
MIME-Version: 1.0
X-Received: by 10.194.191.131 with SMTP id gy3mr14597709wjc.108.1406222593803; Thu, 24 Jul 2014 10:23:13 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.194.123.167 with HTTP; Thu, 24 Jul 2014 10:23:13 -0700 (PDT)
In-Reply-To: <53D139EF.1020002@shiftleft.org>
References: <CAMm+Lwj9EPJ9v92xrkM1ceAbkWYe22fpOOBObUbUJjkk8X0dng@mail.gmail.com> <bf68fd7300e14fb58330b094f4795f30@BY2PR03MB474.namprd03.prod.outlook.com> <53D117AD.8060506@sbcglobal.net> <CAMm+LwiJbkr3z5DxDtVMqjrzt0bz=5+4MRkwBMSScoLh_K=k0Q@mail.gmail.com> <53D139EF.1020002@shiftleft.org>
Date: Thu, 24 Jul 2014 13:23:13 -0400
X-Google-Sender-Auth: A1SRILu7RBP8WdUABkBuNMw_cZo
Message-ID: <CAMm+LwhEC8Cqfv1Z+qiyNYEDU4t-mXwirCU9TY+d_XQEhXDvUw@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Mike Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/b4ypSrGjIc7DkzexahDmEOBvfUU
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 17:24:09 -0000

On Thu, Jul 24, 2014 at 12:53 PM, Mike Hamburg <mike@shiftleft.org> wrote:
> On 7/24/2014 8:11 AM, Phillip Hallam-Baker wrote:
>
> 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.
>
> It may interest you to know that that the prime 2^480 - 2^240 - 1 is about
> 40% faster than 2^512 - 569 on modern 64-bit Intel processors, meaning that
> each field operation takes about 60% of the time.  For example, on Haswell a
> field multiply mod 2^480 - 2^240 - 1 costs about 121 cycles, and addition
> (with no reduce, because of reduced radix) takes fewer cycles than the
> pipeline (it's just two AVX2 add instructions).
>
> I believe it is also about that much faster on than 2^521 - 1 on Sandy
> Bridge, but only by 20% or so on Haswell due to an implementation of
> multiplication mod 2^521-1 using 3-way Karatsuba/Chung-Hasan with AVX2.  It
> uses 9 limbs of 58 bits each organized as (Z[w]/(w^3-2))[t]/(t^3-w), and
> needs AVX2 for all the adding.

Hmm, that is good for performance I guess. But doesn't help making a decision.

Talking to folk, I see the current concerns raised:

1) Nothing up my sleeves.
2) Key size.
3) Ability to support encryption and signature with one set of code.
4) Performance.
5) Work factor

My point here is meeting a work factor precisely is much less
important to me than performance.

But the other argument raised is that if you drop the requirement for
hitting the work factor exactly and allow a tradeoff between work
factor and performance this clouds the argument for 'nothing up my
sleeves'.

I think that is actually a good argument. If the requirement is for
256 and nothing less, that is completely defensible. Opening the door
to performance/work factor tradeoffs makes the decision subjective and
we get back to the problem of the proposers proving that there is
nothing up their sleeves.


The objective here is not to decide which algorithms are good, it is
deciding which to reject. I am arguing for each of those criteria as
criteria for reducing the search space.