Re: [Cfrg] Not the same thread -> was Re: Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)

Watson Ladd <watsonbladd@gmail.com> Fri, 27 February 2015 02:22 UTC

Return-Path: <watsonbladd@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 9761D1A6FF6 for <cfrg@ietfa.amsl.com>; Thu, 26 Feb 2015 18:22:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
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 kx5gF4_8nJBw for <cfrg@ietfa.amsl.com>; Thu, 26 Feb 2015 18:22:32 -0800 (PST)
Received: from mail-yh0-x22a.google.com (mail-yh0-x22a.google.com [IPv6:2607:f8b0:4002:c01::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CD7921A6F87 for <cfrg@irtf.org>; Thu, 26 Feb 2015 18:22:31 -0800 (PST)
Received: by yhaf73 with SMTP id f73so6660830yha.3 for <cfrg@irtf.org>; Thu, 26 Feb 2015 18:22:31 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=n5mGjwTvZU5TO3xIkTLCnUPGmzWbYgHlK6JLxD0wVSw=; b=TyucD6xwP8j/frMIpU4QZsbghHYYjuOiXICo2JsAIg5htJgUCtfYAuCfVq0qkqZWdj EN1SVSUbRDNXAbjHIEwmhpVnojpO1cVp8j0e2CVZdMG5PZHmjWa41dYaaAapbnGTQwb3 uZ4bzqWXSo6nJduzHLztAa+D4dfGyKcbwEs5irYpIyb9vVm0OfUF8ioFGEpe46CN314d DSfgMRXXK1xOs2xo+GeqUt3FNHApZuv4OO3pi7U7SX6/DDe9gNqTfgKL0bja1hpPcbu/ w0qZMWT9GD+K+De1/XaC7x0wAWI+WsYw3hadaokGG1XhAkkDgW0HIQ8rpHK+SfNsjIfv MHeA==
MIME-Version: 1.0
X-Received: by 10.236.209.129 with SMTP id s1mr11016002yho.49.1425003750949; Thu, 26 Feb 2015 18:22:30 -0800 (PST)
Received: by 10.170.126.10 with HTTP; Thu, 26 Feb 2015 18:22:30 -0800 (PST)
In-Reply-To: <CAMm+Lwgw9BP2HsMFx5SZ6oF-X0kteiKzwX2oQLknkb9DAwhmrQ@mail.gmail.com>
References: <D1133BAF.5C3D2%paul@marvell.com> <54EE0D4D.2080009@shiftleft.org> <sjm7fv4wtt4.fsf@securerf.ihtfp.org> <CAMm+Lwgw9BP2HsMFx5SZ6oF-X0kteiKzwX2oQLknkb9DAwhmrQ@mail.gmail.com>
Date: Thu, 26 Feb 2015 18:22:30 -0800
Message-ID: <CACsn0c=wuN+D20oCAXFs6vTBYs-o62Bhc0cdA3kT2kD=QC7bHA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/3QMv-midVGoJUSPOrq7iYkt4Z2Y>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Not the same thread -> was Re: Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)
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, 27 Feb 2015 02:22:34 -0000

On Thu, Feb 26, 2015 at 9:38 AM, Phillip Hallam-Baker
<phill@hallambaker.com> wrote:
>
>
> On Thu, Feb 26, 2015 at 10:56 AM, Derek Atkins <derek@ihtfp.com> wrote:
>>
>> Mike Hamburg <mike@shiftleft.org> writes:
>>
>> > Thanks, Paul.
>> >
>> > On 3.6GHz Haswell with OpenSSL 1.0.1f:
>> > RSA-2048: sign 1028us, verify 31us
>> > Ed448: sign 51us, verify 163us, dh 148us
>> > Ed480: sign 55us, verify 183us, dh 170us
>> > E-521: sign 79us, verify 256us, dh 241us
>>
>> I asked this in the previous thread but it was lost, so I'll ask this
>> again in this thread: Why are you looking at RSA 2048 for this
>> comparison?  That's only a 2^112 work factor (C.f. Section 1 of
>> RFC4492).
>>
>> If you want a 2^256 work factor you need to go up to RSA 15360.  If you
>> only want to get to 2^128 then you need to look at RSA 3072.
>>
>> Let's at least compare apples to apples.
>
>
> The reason is that as far as customers are concerned, they are switching
> from RSA2048 to something else. We have already established that the CPU
> demands of RSA2048 are not prohibitive for any class of device currently
> using TLS.

What about devices and services that don't use TLS because of the CPU
demands? Or is encrypting everything no longer on the agenda? Is
Cloudflare conducting a RSA2048 private key operation every time I
connect? Is Google?

>
> If I am looking at buying a new van, the question I am going to ask is not
> which one has most capacity, fuel economy, etc. but whether it is the same,
> better or worse than what I already have and whether the current situation
> is acceptable or not. If I am moving from a van to a truck I am going to ask
> what the impact on fuel consumption is even though I know the truck holds
> more because I know if my current fuel costs are acceptable or not.

>
>
> We already have an EC curve that is optimized for new applications in
> constrained devices etc. So knowing how we are doing relative to the
> baseline of RSA2048 is informative.

Down at the bottom this email you explain that public CAs won't be
using Curve25519. Never mind that encrypted data, not past
authentication, needs to survive into the future. Never mind that CAs
didn't rush out and compete to make RSA3072 keys, or even depreciate
RSA1024 with anything close to a reasonable timescale. But if what you
say is in fact true, then devices don't have a choice: they need to
carry out a verification with superfluous strength unless they aren't
going to use TLS.

Brian Smith and Tony Aceri have lengthy emails explaining the problem,
which you've entirely ignored. I've explained why it makes sense for
authentication to be weaker than encryption: again, email entirely
ignored. Are you going to explain what we're missing?

>
> If we were looking at additional load on the server then we would have to be
> very concerned because that is a bottleneck.
>
>
>> > On 1GHz Cortex A8 with OpenSSL 1.0.1f:
>> > RSA-2048: sign 39.8ms, verify 1.2ms
>> > Ed448: sign 0.7ms, verify 1.9ms, dh 1.9ms
>> >
>> > On both CPUs, the elliptic curves are slower than RSA for verification,
>> > but
>> > much faster for signing.  The Haswell core is about 5-8x faster for RSA
>> > verify,
>> > and 20x slower for signing.
>>
>> But at quite different security levels, so it's not telling us anything
>> useful.  I think Ed448 is more like an RSA-4096 level (or possibly even
>> larger than that).
>
>
> The reason we are moving away from RSA is that 1) Index calculus continues
> to improve and 2) RSA hits steeply diminishing returns, its more like 16Kbit
> keys to get an interesting improvement in performance.
>
> RSA2048 is the baseline for performance. It is not the baseline for
> security. The objective here is to improve security without adverse impact
> on performance.

Objective for who? Of course, there already is an adverse impact on
performance: none of the options had faster verification.

>
> The reason I was asking the question is that if we can do P521 at lower cost
> than RSA2048 then the fact that P448 takes only 62% of the time that P521
> does isn't very interesting. If P521 was going to be a lot slower on the
> server then my customers would be really concerned about performance and
> demand P448 and we would have an objective criteria on which we can justify
> an answer.

By "your clients" you mean the people whose CSRs you sign to make
certificates, right?

They get to pick which algorithm to use on the server to sign the key
exchange. Which algorithm the root certificate uses to sign the
intermediate and the intermediate the entity cert are entirely
irrelevant to this process. Of course, it's not irrelevant to the
client, which has to conduct a large number of verifications, and
where additional time is a real PITA.

>
> As it is, I don't see performance as being an objective discriminator
> because there is only a negative impact on clients and the CPU overhead on
> the client side is a negligible fraction of the PKI overhead. I would bet
> that we improve performance client side for TLS on a Raspberry Pi 2 under
> real world test conditions using P521 over RSA2048 simply because all the
> cert chains etc are much smaller. Yes verifying signatures takes 8 times as
> long. But we are talking about an operation that takes a 1.2 ms on an iPhone
> CPU today.

What PKI overhead is there aside from the CPU cycles to verify
signatures? But let's actually do the calculation. 10^8 bits per
second, and we've replaced 2048 bits with 521*2=1042 bits, so saving
1006 bits per signature. That means we've saved 10 microseconds per
signature. The minimal cert chain is three certs, so we saved 30
microseconds. And then we throw it all away doing three verifications.
Even if we save .1 milliseconds per signature, it all vanishes with
the extra time for verification, even on fast CPUs. You'll need
batching to even get close.

>
>
> If we go for P521 then nobody can possible criticize us for having chosen
> something less secure than we did.

No, they still can: after all, there are an infinite number of primes,
and any bigger prime would increase security. But why aren't you
turning this around and saying that if we pick P448 no one can
criticize us for not increasing performance?

> If went for P521 and P448 I guarantee that my world will only use P521 and
> P255.

Why didn't this happen for the NIST curves? Why hasn't it happened for
RSA? And why require clients to do more work when P448 offers far more
than adequate security?

Sincerely,
Watson Ladd

>
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin