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

Derek Atkins <derek@ihtfp.com> Fri, 27 February 2015 17:15 UTC

Return-Path: <derek@ihtfp.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 8D5941ACE9B for <cfrg@ietfa.amsl.com>; Fri, 27 Feb 2015 09:15:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.289
X-Spam-Level:
X-Spam-Status: No, score=-1.289 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HELO_MISMATCH_ORG=0.611] 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 SyJZuNqP4Kzu for <cfrg@ietfa.amsl.com>; Fri, 27 Feb 2015 09:15:06 -0800 (PST)
Received: from mail2.ihtfp.org (MAIL2.IHTFP.ORG [204.107.200.7]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7AA651ACE61 for <cfrg@irtf.org>; Fri, 27 Feb 2015 09:15:05 -0800 (PST)
Received: from localhost (localhost [127.0.0.1]) by mail2.ihtfp.org (Postfix) with ESMTP id 38E63E2039; Fri, 27 Feb 2015 12:15:04 -0500 (EST)
Received: from mail2.ihtfp.org ([127.0.0.1]) by localhost (mail2.ihtfp.org [127.0.0.1]) (amavisd-maia, port 10024) with ESMTP id 14302-02; Fri, 27 Feb 2015 12:15:02 -0500 (EST)
Received: from securerf.ihtfp.org (unknown [IPv6:fe80::ea2a:eaff:fe7d:235]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mocana.ihtfp.org", Issuer "IHTFP Consulting Certification Authority" (verified OK)) by mail2.ihtfp.org (Postfix) with ESMTPS id E59CDE2036; Fri, 27 Feb 2015 12:15:01 -0500 (EST)
Received: (from warlord@localhost) by securerf.ihtfp.org (8.14.8/8.14.8/Submit) id t1RHEx6M017721; Fri, 27 Feb 2015 12:14:59 -0500
From: Derek Atkins <derek@ihtfp.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
References: <D1133BAF.5C3D2%paul@marvell.com> <54EE0D4D.2080009@shiftleft.org> <sjm7fv4wtt4.fsf@securerf.ihtfp.org> <CAMm+Lwgw9BP2HsMFx5SZ6oF-X0kteiKzwX2oQLknkb9DAwhmrQ@mail.gmail.com>
Date: Fri, 27 Feb 2015 12:14:58 -0500
In-Reply-To: <CAMm+Lwgw9BP2HsMFx5SZ6oF-X0kteiKzwX2oQLknkb9DAwhmrQ@mail.gmail.com> (Phillip Hallam-Baker's message of "Thu, 26 Feb 2015 12:38:04 -0500")
Message-ID: <sjmsidruvhp.fsf@securerf.ihtfp.org>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Virus-Scanned: Maia Mailguard 1.0.2a
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/jO7pdvhA6ne2tw4L4cflgv7S8Vw>
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 17:15:07 -0000

Phillip Hallam-Baker <phill@hallambaker.com> writes:

> 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. 

Maybe that's the case for your customers, but certainly not mine.

You're ignoring the classes of devices not using TLS because the CPU
demands of RSA2048 *ARE* prohibitive.  That's where I live these days.
(Honestly, even the cost of ECC is sometimes prohibitive in the space I
live these days).

You're welcome to compare apples to kumquats if you desire, but my
customers need an apples-to-apples comparison.  Is it really too much to
ask for timings of RSA 3072, 4096, 7680, 8192, and 15360??  ;)

> 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.

Or your current car just up and died and you get to buy a car from
scratch, which means you don't have to compare your old to your new, but
you're comparing new#1 to new#2 to new#3.  In which case knowing that
your old van used to get 15MPG is completely irrelevant, because all the
new ones you get to choose from are above 20.

> 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.

Really?  And which one would that be?  We seem to have only shown
consensus for 25519 so far.

> 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.

That may be YOUR objective, but I don't know that we have consensus on
that being the ONLY objective.  From where I sit I'd like to see it in
the reverse: if I have a particular constraint (space,time,cpu,etc)
what's the best security I can get within that constraint?  Or
similarly, if I only need X-level security, how does it affect my
performance if I switch from AlgA to AlgB?

> 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.

True, a 33% reduction in execution time might not be very interesting to
some.  But asking for more data shouldn't ever be a bad thing.

> 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.

I cannot give you the same guarantee in my world.

-derek

-- 
       Derek Atkins                 617-623-3745
       derek@ihtfp.com             www.ihtfp.com
       Computer and Internet Security Consultant