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

Phillip Hallam-Baker <phill@hallambaker.com> Fri, 17 October 2014 23:31 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 2BB6F1A1A03 for <cfrg@ietfa.amsl.com>; Fri, 17 Oct 2014 16:31:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.277
X-Spam-Level:
X-Spam-Status: No, score=-1.277 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, HTML_MESSAGE=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 JYC1gUD-ap_g for <cfrg@ietfa.amsl.com>; Fri, 17 Oct 2014 16:31:07 -0700 (PDT)
Received: from mail-lb0-x234.google.com (mail-lb0-x234.google.com [IPv6:2a00:1450:4010:c04::234]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1AE251A1A02 for <cfrg@irtf.org>; Fri, 17 Oct 2014 16:31:06 -0700 (PDT)
Received: by mail-lb0-f180.google.com with SMTP id n15so1421010lbi.39 for <cfrg@irtf.org>; Fri, 17 Oct 2014 16:31:05 -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=/2KC+wgKPXnrUEcs3jd9BhZXqxvUzBmIHU2PcwaMFVc=; b=w+4lzgNxE9tXCT9OkDSOHhnEIlNuedSzObqaOYJfGu9Y4iy38kOYC0BHEjCUOA/6Xr X1XiB7TtLt8aFtCzd3XeqJCBnyiiR6GygRA5FdPcWzWDLJEc6vRjrNEl1Y7QWXqpUk2Z j+ba1dPJXN+3FHY/mUJC1/jeg+19J5+RFpt0k3YeZgWEoi/okxrEugak9mqdQnsFJbuY rxmNlRKyqygoNAD/KpsaQg3uDsVGQp6Agr/a1tLP60auwdj3GJLPZSwybznmztiYBn+4 Ad0DwQ3T8gq9RMJ6GfzoTbdeu9k72WC3JjRq9+cTknmIroXNlrrPC2k9UQfRFRm9SRWN +PDw==
MIME-Version: 1.0
X-Received: by 10.153.7.170 with SMTP id dd10mr11934436lad.45.1413588665365; Fri, 17 Oct 2014 16:31:05 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.112.66.196 with HTTP; Fri, 17 Oct 2014 16:31:05 -0700 (PDT)
In-Reply-To: <5218FD35-E00A-413F-ACCB-AA9B99DEF48B@shiftleft.org>
References: <D065A817.30406%kenny.paterson@rhul.ac.uk> <54400E9F.5020905@akr.io> <CAMm+LwhVKBfcfrXUKmVXKsiAMRSTV+ws+u07grmxkfnR2oYJoQ@mail.gmail.com> <5218FD35-E00A-413F-ACCB-AA9B99DEF48B@shiftleft.org>
Date: Fri, 17 Oct 2014 19:31:05 -0400
X-Google-Sender-Auth: n6YSxfpEFJljKFo0lRADHDmheWY
Message-ID: <CAMm+LwjrSVn=T4uqJsQ00Jp0H3-AL7-pk0RSJ_gyGrJgKGpuSg@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: multipart/alternative; boundary=001a113483ae41fb390505a6c23c
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/p8mHpYFXEtsj61HpPJxMTzl5xXA
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 23:31:10 -0000

On Fri, Oct 17, 2014 at 5:27 PM, Michael Hamburg <mike@shiftleft.org> wrote:

>
> > 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.
>
> Discrete graphics probably won’t be be a common crypto platform, though I
> agree that AVX-512F will be in a few years.


I think that we will find the CPU choices will end up being limited to CPU
cores and GPU cores long term because those are the areas where all the big
R&D bucks are going.

Its like when I try to buy motors for my robots. There are no motors made
for the purpose of driving a dalek or an R2D2. There are motors made for
scooters and wheelchairs because those are the markets with the big enough
markets.

AVX-512F looks tasty though.




> > 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.
>
> I’m not sure what you mean by “bongoed”.  I do not believe that 2^521-1
> has been struck rhythmically by hands, or has been played as a melody on
> bongos.
>

Got at by the NSA.


> It is possible, if unlikely, that some mathematical property of Mersenne
> primes would make elliptic curves mod them weaker than mod other primes.
> But at least 4 groups thought 2^521-1 was an obvious choice, and at least 3
> of them came up with the same curve.  That’s about as unsuspicious as
> you’re going to get without some VPR performance art.
>
> > 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.
>
> Just the way they use ~15kbit RSA keys now, eschewing ~3072-bit keys as
> too weak, right?
>

The only reason we are interested in ECC is that RSA stops giving
meaningful increases in work factor at 2048 bits. 4096 bits is a lot more
work for the defender for a rather modest improvement in work factor.


I looked at Mozilla’s included CAs.  There are four ECC certs there, all of
> them on the NIST secp384r1 curve.  So they apparently do not consider ~512
> bits necessary, but if the only choices are 256 and 512 I suppose they will
> go with 512.
>
> The RSA-based roots are mostly 2048 bits long, equivalent to about a
> 224-bit ECC.  If the CAs consider this an acceptable level of security for
> hosts, I suspect that webmasters will be OK with ~256-bit curves.  That’s
> what Cloudflare uses for their universal SSL, for example.


The only reason to deploy ECC is if we are unsatisfied with RSA. It is not
the case that RSA2048 is satisfactory. It is merely 'adequate'.


> 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.
>
> Maybe for your applications, but that’s not how TLS’s ECDHE works.


Not relevant because we have to cut a new OID set anyhow. In fact there is
quite a raft of changes likely to happen in parallel.



> > 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.
>
> I basically get this sentiment.  But just so we can be clear: why do you
> want them bits?  Is it just an insatiable craving, or does a round 512
> sound better in product advertisements, or is there a foreseeable attack
> that the extra bits will protect you from?
>

If a competitor launches a 512 bit ECC cert then I will have to.


> If most CAs today are OK with security equivalent to 224-bit curves, but
> they're hedging to 384 bits, why are you convinced that 384 or 414 or 448
> or 480 bits would not be enough?  And if they aren’t enough, why not go to
> 607 or 640 or 1024 bits?


Same reason as 2048 and 1024 the next nearest power of 2 that gives close
to the desired work factor.

When we chose 1024 we were working with 2^80 as an acceptable work factor.
Now we are generally looking for 128 and 256. So RSA2048 is showing its age.

Making the choice for TLS is perhaps not ideal as TLS is a transport
protocol and so we are not that worried about long term security. For
S/MIME we really do want 30 year security.



>
> >>> 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.
>
> The only new bigger-than-256-bit curve which would ease legacy transition
> is E-521.


I think the legacy argument is a lot stronger for Curve 25519. Not in the
TLS space but he has got a lot of mindshare elsewhere.


>
> > 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.
>
>
> Platinum is heavy and very, very expensive.  It resists corrosion
> phenomenally well, but not cutting.  Quite the metaphor.
>

I rejected diamond because its brittle.