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> Wed, 25 February 2015 19:30 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 ED3211A870F for <cfrg@ietfa.amsl.com>; Wed, 25 Feb 2015 11:30:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.622
X-Spam-Level:
X-Spam-Status: No, score=0.622 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, 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 3ozpUGE6HIB7 for <cfrg@ietfa.amsl.com>; Wed, 25 Feb 2015 11:30:55 -0800 (PST)
Received: from mail-lb0-x22c.google.com (mail-lb0-x22c.google.com [IPv6:2a00:1450:4010:c04::22c]) (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 5725E1A1DE1 for <cfrg@irtf.org>; Wed, 25 Feb 2015 11:30:53 -0800 (PST)
Received: by lbiz11 with SMTP id z11so6150077lbi.5 for <cfrg@irtf.org>; Wed, 25 Feb 2015 11:30:51 -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=rLFnHPmzW88+WAIiRrizF4zrnCaY0wmlojrpF+3jsMM=; b=hyl4/w853E3lZFmhEGF6zoBeFbvRo2AREz7D3NirhwxFID3ha45fDv+gUUu0zIHxEK UC7RavK4KsdMx3D4NcUAgrCyi929hOSyzo7gQx7KD13mgaQh9N6kb3FFOSIFWYjZ1rGm 2CxbHv/asrs2eq9jDiQUubhkNCuEGrACC8/3l/s3IXYJvHMppxXzYRSh0FFgD1NeSs/8 8oBdoQKpaEHigxuWeWxIIMy4x4myk3GdkjN24q7Gsu4ev8d6NRJpJLqPj0qtuqFZL/S/ PxRY63nuvD9CvdCwokG3VEpGXQ56IfAeApViOL+Ctq85GIXT6mAiyIr3igxu73gdESff 9RIA==
MIME-Version: 1.0
X-Received: by 10.112.147.66 with SMTP id ti2mr4376675lbb.124.1424892651776; Wed, 25 Feb 2015 11:30:51 -0800 (PST)
Sender: hallam@gmail.com
Received: by 10.113.3.165 with HTTP; Wed, 25 Feb 2015 11:30:51 -0800 (PST)
In-Reply-To: <54EE0D4D.2080009@shiftleft.org>
References: <D1133BAF.5C3D2%paul@marvell.com> <54EE0D4D.2080009@shiftleft.org>
Date: Wed, 25 Feb 2015 14:30:51 -0500
X-Google-Sender-Auth: 33diHm8SB0CDTJtL4pMs8glEEic
Message-ID: <CAMm+LwhOaKJsB8vnm95NLDUpJWgLobPKqsgrY9DB9+vSzZDGpg@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Mike Hamburg <mike@shiftleft.org>
Content-Type: multipart/alternative; boundary=047d7b3a86905a329b050feeac4f
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/o1Sct38xV-pG-bZURG_UkpIEjr4>
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: Wed, 25 Feb 2015 19:30:57 -0000

On Wed, Feb 25, 2015 at 12:58 PM, Mike Hamburg <mike@shiftleft.org> wrote:

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

OK so ignoring the likelihood that we do an ephemeral in addition since
that is a good thing to do anyway and if the key agreement is designed
right, a WF-128 ephemeral only improves a WF-256 key.


For the server side

RSA2048: One decrypt, 1028 us
E-521: One DH agreement 241 us

So anything we do is a win on the server side. No need to consider the
other curves. EC is going to be faster. And that is before we consider
games like precalculation.


For the client side, if we have one intermediate and one EE cert:

RSA2040: One encrypt, two verifies, 93usec
EC 521: One DH, two verifies, 753 usec.

OK so performance is possibly an issue on the client. But only if we are on
a constrained device or the client is making a huge number of key
negotiations. And why would you want to do that on a constrained device.


Taking 448 as the baseline, 480 is 15% slower, 521 is 60% slower

Those figures might change a bit depending on optimization but I rather
doubt they will change greatly.


So on the one hand we have a measurable performance difference that makes
no real difference and on the other we have a measurable security
difference that makes no real difference.

Curve 521 does have the advantage of matching the work factor of AES 256.
It also has the advantage of squaring the work factor. The best
cryptanalytic technique we have to date is the meet in the middle attack
which reduces the work factor by the root, 2DES (112 bits) has the same
strength as DES (56 bits).


I don't care about the color of the bikeshed. What I care about is the
possibility that someone hates the color of ours so much that they insist
on building a new bike shed so that they can have their color. The Russian
requirement for P512 looked like it was an objection of that form till it
turned out that particular choice seems to have been made to exclude the US
proposal.

Tying back to the NIST discussion. If they really care about the color of
the bike shed, that is something I would personally consider very relevant.
Same for Microsoft or Google.


If P384 is the NIST baseline then I think it is easy to upsell them to 448.

If P521 is their established baseline then we could probably persuade them
to replace the P384 curve with ours but they are likely keeping their 521
curve.


>From time to time I attend meetings where it would be really easy to say to
someone with decision making ability that one of the best things that the
US Govt could do in the short term for cyber security would be to publish a
FIPS for the IETF curves. The problem being that the person who has
decision making authority has no idea what public key crypto is let alone
why they would want a particular curve.

If I push that button and the response that comes back up the chain is 'Our
521 curve is a billion billion times stronger', I doubt we get what we
want. If the response that comes back is 'we prefer Weinerschnitzel curves
with the double Irish option because they may have better security against
Schnorkelplage attack', it is rather more likely we get our way.