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

Phillip Hallam-Baker <phill@hallambaker.com> Thu, 26 February 2015 17:38 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 252BF1A92EA for <cfrg@ietfa.amsl.com>; Thu, 26 Feb 2015 09:38:08 -0800 (PST)
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 msGh4OhRY8UH for <cfrg@ietfa.amsl.com>; Thu, 26 Feb 2015 09:38:06 -0800 (PST)
Received: from mail-lb0-x22b.google.com (mail-lb0-x22b.google.com [IPv6:2a00:1450:4010:c04::22b]) (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 C76BF1AC398 for <cfrg@irtf.org>; Thu, 26 Feb 2015 09:38:05 -0800 (PST)
Received: by lbdu14 with SMTP id u14so12293597lbd.1 for <cfrg@irtf.org>; Thu, 26 Feb 2015 09:38:04 -0800 (PST)
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=uIL1PKjXNw191/YG11Ms/QepVpYOgAgV6fdvHn6xzh0=; b=IAYFHJm/0cOnDMEhYaqrj/jci82U+AFeJiCgpJ0YwqCA8snzyt0stuKtsBYZVuyE2s IacP1LZf4V//dWSmOnnnQlbuChr+kDav7q8fAaKru9nu4X2vCAnc0KhKFAkEh0TNNqFk A3mrEe6f+ptclfzcMVcGpkZGLBIFUGK/nP4qQesALSBf25qYnh0Z3+Izh9x4TDW+jARM L2cGJV+Pv9Zt+tcjBJc7ydiMsbXq3G/cLSW7OTFr/WnimwoYb796eggQ+olFJEiYiurN 5b1QnEqUZZ1PAn7SvdzHd2IqoJ1ktrBBTuiH65qRYRDwueTFWd6vIpry9m1Qyn7pFube Q9ww==
MIME-Version: 1.0
X-Received: by 10.152.18.225 with SMTP id z1mr8901148lad.124.1424972284320; Thu, 26 Feb 2015 09:38:04 -0800 (PST)
Sender: hallam@gmail.com
Received: by 10.113.3.165 with HTTP; Thu, 26 Feb 2015 09:38:04 -0800 (PST)
In-Reply-To: <sjm7fv4wtt4.fsf@securerf.ihtfp.org>
References: <D1133BAF.5C3D2%paul@marvell.com> <54EE0D4D.2080009@shiftleft.org> <sjm7fv4wtt4.fsf@securerf.ihtfp.org>
Date: Thu, 26 Feb 2015 12:38:04 -0500
X-Google-Sender-Auth: LfHTPjdkv8FaWpfbSJZL928vwcc
Message-ID: <CAMm+Lwgw9BP2HsMFx5SZ6oF-X0kteiKzwX2oQLknkb9DAwhmrQ@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Derek Atkins <derek@ihtfp.com>
Content-Type: multipart/alternative; boundary=089e014940aed2619905100136bc
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/4S8k--RtIsQ15blp7FEeQV67dWI>
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: Thu, 26 Feb 2015 17:38:08 -0000

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.

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.

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.

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.

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.


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

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