Re: [Cfrg] ECC reboot (Was: When's the decision?)

Phillip Hallam-Baker <phill@hallambaker.com> Fri, 17 October 2014 20:22 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 398411A1AF1 for <cfrg@ietfa.amsl.com>; Fri, 17 Oct 2014 13:22:52 -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 i_8XSVYXOFvd for <cfrg@ietfa.amsl.com>; Fri, 17 Oct 2014 13:22:50 -0700 (PDT)
Received: from mail-la0-x22b.google.com (mail-la0-x22b.google.com [IPv6:2a00:1450:4010:c03::22b]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2C26D1A1B09 for <cfrg@irtf.org>; Fri, 17 Oct 2014 13:22:49 -0700 (PDT)
Received: by mail-la0-f43.google.com with SMTP id mc6so1331245lab.16 for <cfrg@irtf.org>; Fri, 17 Oct 2014 13:22:48 -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:content-transfer-encoding; bh=fSiKXyb+AubIuSd+X64EBAptUx3pdXq93E0NCmY/CpU=; b=Cm05vrr7ZyiGjdgfCDkXIbQS7YUEg1vsvRy7LPuRw0PKRHpQRn3g3N733KhoBUNp3B c6zxuA0GzjBbMwoTIu+O30OK4T/Qc7icoE+SNoR9M2IWtN4vnRBl0e/kjNfWYLr7oxhR iS4viMmV5WCfXJWJ/NGzeRhaohwQ897fmpmNKvIfvNBsjBFxQ6JKh1P/eJhgOCPyLD/Z BYnlDu+4aB5H7POobGQAxnCs9Aqag/thQYSrTGYu0ng2fuz3AZ1qhKZWGP2UX1Djk4Cf +b7lXxk5zh0j79UlZRZcrvdW8fRIKB1T6MUKqpGhvNHWabGF0Bfx0vOfwWsZ+W93LipE npJA==
MIME-Version: 1.0
X-Received: by 10.152.1.42 with SMTP id 10mr11488108laj.4.1413577368216; Fri, 17 Oct 2014 13:22:48 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.112.66.196 with HTTP; Fri, 17 Oct 2014 13:22:47 -0700 (PDT)
In-Reply-To: <54400E9F.5020905@akr.io>
References: <D065A817.30406%kenny.paterson@rhul.ac.uk> <54400E9F.5020905@akr.io>
Date: Fri, 17 Oct 2014 16:22:47 -0400
X-Google-Sender-Auth: NaI_WzSEMrlAwJGdt8typ5znmYA
Message-ID: <CAMm+LwhVKBfcfrXUKmVXKsiAMRSTV+ws+u07grmxkfnR2oYJoQ@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Alyssa Rowan <akr@akr.io>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/nN_PuHVzs1d8ZfXuswMsiLzscxo
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] ECC reboot (Was: When's the decision?)
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: Fri, 17 Oct 2014 20:22:52 -0000

On Thu, Oct 16, 2014 at 2:29 PM, Alyssa Rowan <akr@akr.io> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> On 16/10/2014 17:08, Paterson, Kenny wrote:
>
>> Our first task should be to finalise the requirements that we will
>> use to guide the selection process. I think we are close, with a
>> couple of outstanding issues:
>
> Alright, so let's try to get things in high gear and argue those out…?
>
>> 1. Amount of "wiggle room" that should be permitted.
>
> Broadly: I think what we're aiming for is probably one faster/strong
> curve, and one stronger/fast curve.
>
> Given the strong preferences of some to minimise the number of curves,
> it looks to me like ­≈384 is almost-definitely dropped, leaving us
> with something near ≈256 and something near ≈512.
>
> We seem to be in agreement that wiggle room on ≈256 would include
> fields of 2^255-19 as well as 2^256-189 in scope.
>
> For the paranoid-strong, performance-second ≈512, 2^512-569 very
> obviously falls within scope.

Agree so far.


> I put forth that 2^521-1 also falls within scope. It's not very far
> away, and it's a true Mersenne prime rather than a pseudo-Mersenne,
> and they do not grow on trees - no others fall near our criteria (the
> next lowest is 2^127-1 which is way too small, and the next biggest is
> 2^607-1). They are very attractive - attractive enough for 4 (?)
> independent research groups to independently arrive on E-521, and
> SECG/NIST to have independently picked the same prime years ago for
> secp521r1.

It is a Mersenne but the performance advantage is compromised by it
being larger than 512 bits. That means every memory operation is going
to break stride. Which is a really bad tradeoff for the marginal
improvement in speed.


> [Previous discussion countering this point: Sean Parkinson @ RSA
> suggested stepping over a power of 2 is "only going to hurt
> performance in the future". Phillip Hallam-Baker also thought anything
> that is not less than a clean multiple of a power of two "may cause
> severe performance hits on future architectures", mentioning 512-bit
> memory buses on graphics cards?!

There is a good reason for that. What we call 'graphics cards' are
really just what we used to call a vector unit.

Getting someone to build purpose built ECC accelerators is hard and
expensive. I can buy an nvida card that with a ridiculous number of
cores that I can pretty much program to do anything I like.


Its not just a question of speed, its a question of the amount of
microcode required to implement ECC math as a native function of the
GPU.


> although I'm not convinced that's
> actually primarily relevant to an implementation of a high-strength
> curve. We will, of course, evaluate performance of contenders in Phase
> II, future architectures can be more-or-less anything that works well,
> and performance implications usually aren't anything like so obvious…
> Aren't Mersennes actually particularly _good_ performance-wise?]

That depends on whether you are looking for a reason to include or exclude.

At the ~512 level, what I am looking for is a curve that absolutely
nobody is going to be able to suggest is suspect as being bongoed.
2^512 is a round number that needs no explanation. 2^521 isn't.

The Web PKI will almost certainly be based exclusively on the ~512
level curve. The roots certainly will. So the performance advantage of
issuing end entity ~256 certs would be very small.

Where I think ~256 keys will be used is for ephemeral mix ins. So I
exchange a master session key M with the ~512 bit key, use an
ephemeral ~256 to create a second session key E and then derive my
encryption and authentication keys using a one way function on M and
E. That preserves the ~512 work factor for confidentiality and adds a
~256 work factor for forward secrecy.


So I am willing to be more flexible on ~256 than ~512 because for my
applications the attacker always has to break the ~512.


> I put forth that 2^414-17 and 2^448-2^224-1 might fall outside "wiggle
> room" there, although I do so very reluctantly as I think it's a shame
> to exclude them on that basis if they have otherwise nice properties,
> and they do seem to have very good performance for their strength.

I agree. They are a little faster but we have to give up a lot of
security to get that speed. Its not 64 bits, its a 2^20 reduction in
work factor. I want them bits.


>> 31/10/14 (2 weeks from now): we agree on whatever benchmarking
>> system we're going to use for performance measurements. (Right now,
>> supercop seems like the front runner to me.)

I think a significant performance difference is a tie breaker but not
the best determinant. What I see as being convincing are:

1) Difficulty of screwing up the implementation (see Watson Ladd's post).

2) Legacy deployment.


Given the way that I think we are likely to use ~256 and given the
fact that DJB has established a large user base for the curve already.
I am willing to suggest we just let him win on that one unless there
is at least a 10%, maybe a 20% speed advantage he missed.

For ~512 I want the Platinum level security, whatever it takes.