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> Fri, 27 February 2015 18:00 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 4F3501AD05B for <cfrg@ietfa.amsl.com>; Fri, 27 Feb 2015 10:00:09 -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 n9_QXuPdRhID for <cfrg@ietfa.amsl.com>; Fri, 27 Feb 2015 10:00:07 -0800 (PST)
Received: from mail-la0-x234.google.com (mail-la0-x234.google.com [IPv6:2a00:1450:4010:c03::234]) (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 45E881ACF5D for <cfrg@irtf.org>; Fri, 27 Feb 2015 10:00:05 -0800 (PST)
Received: by labgf13 with SMTP id gf13so19141835lab.9 for <cfrg@irtf.org>; Fri, 27 Feb 2015 10:00:03 -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=BS40b8QwZRPA3FlMMvJathB065Vtxeekw2ikTpQBI3k=; b=bgTuS1gaNj5u0l43IUD9+I1W37+Iw21/2jH42tHoE06X/kB28yJf/KuE//ZMxu0PaY LpBgO+mf6enxfqvkJPCdq0dxyaBUZIN1XS9mpybSPGvsb6S1ZfbPzRXLEIOOvRvjy1iS pTOxdb41mkAaRObdFaL1PWITUevrWbNxmgzcAgxI3/kjfNnYqrfctLyGMRjfb9Oba0tS /tZ0hBryygVOaLuj6JZhlUfdNThI1vKr4Xu5jiwGqFZx3cbtCj0VEfdh6IJsStW0XQMx R3UMPjD5TGmAoDbf9Z8HQOkoSJvi1m1yB5u49GeEigf0oNhJQ4vbVuD227sO0JS8wnzh pppA==
MIME-Version: 1.0
X-Received: by 10.152.191.135 with SMTP id gy7mr13555027lac.91.1425060003567; Fri, 27 Feb 2015 10:00:03 -0800 (PST)
Sender: hallam@gmail.com
Received: by 10.113.3.165 with HTTP; Fri, 27 Feb 2015 10:00:03 -0800 (PST)
In-Reply-To: <sjmsidruvhp.fsf@securerf.ihtfp.org>
References: <D1133BAF.5C3D2%paul@marvell.com> <54EE0D4D.2080009@shiftleft.org> <sjm7fv4wtt4.fsf@securerf.ihtfp.org> <CAMm+Lwgw9BP2HsMFx5SZ6oF-X0kteiKzwX2oQLknkb9DAwhmrQ@mail.gmail.com> <sjmsidruvhp.fsf@securerf.ihtfp.org>
Date: Fri, 27 Feb 2015 13:00:03 -0500
X-Google-Sender-Auth: gZy_zM5L9N7SJ0RZp3t1Zd5ANu0
Message-ID: <CAMm+LwhoNY9cc4tP6ig-OvnJUVyKQSZW+MVf-wpmnye=-MAp2w@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Derek Atkins <derek@ihtfp.com>
Content-Type: multipart/alternative; boundary=001a1134303a4bdf38051015a3d0
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/kECnmARULjxUTdwAFPcxjp-tITI>
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 18:00:09 -0000

On Fri, Feb 27, 2015 at 12:14 PM, Derek Atkins <derek@ihtfp.com> wrote:

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

No, I am suggesting that the class of device that require more security
than Curve25519 and find P448 performance acceptable that will not find the
additional 60% extra time to do P521 is either the null set or not worth
bothering with.

The choice between P448 and P521 is not going to be a make or break issue
for whether your lightbulb is going to be viable. It isn't even going to
force a choice of chip.



> 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??  ;)


Yes, because the reason we are going to ECC in the first place is they
don't work.

RSA2048 has a WF of approx 112 bits. RSA4096 is only a WF of 128 bits. To
get to 256 bit security you need those 15360 bits.

If RSA15360 performance was acceptable then P521 would definitely be
acceptable.


Remember the days of the BBN Safekeeper which took 9 hours to generate
RSA4096 keypairs? THAT is quite definitely a make/break issue. If an
operation is taking hours or even minutes then 60% is arguably significant.
But I just don't think you are going to be doing P448 or P521 all that many
times.


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


That *IS* your constrained curve, sorry.

If you are more constrained than that and can't live with Curve25519 then
Goldilocks isn't going to be relevant to you anyway.