[Cfrg] Another perspective on the Curve256/255 problem

Phillip Hallam-Baker <phill@hallambaker.com> Thu, 31 July 2014 17:22 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 []) by ietfa.amsl.com (Postfix) with ESMTP id D43231B293C for <cfrg@ietfa.amsl.com>; Thu, 31 Jul 2014 10:22:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Status: No, score=-1.278 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, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id j3k5Q9G403-T for <cfrg@ietfa.amsl.com>; Thu, 31 Jul 2014 10:22:55 -0700 (PDT)
Received: from mail-la0-x22a.google.com (mail-la0-x22a.google.com [IPv6:2a00:1450:4010:c03::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DA9E51A0310 for <cfrg@irtf.org>; Thu, 31 Jul 2014 10:22:54 -0700 (PDT)
Received: by mail-la0-f42.google.com with SMTP id pv20so2315963lab.1 for <cfrg@irtf.org>; Thu, 31 Jul 2014 10:22:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:date:message-id:subject:from:to:content-type; bh=0ghl1eQ8i2RH+QlMd7W7yVSnEY9bMlDE44ptI57ZO8c=; b=Qn/aqdWNiE/bQsqGf+nngoW/oAQVjSLhc30YIHqM7TC5QruVUWE79hzRftkdStFrye YHb8C9nQ6tM9g+e3g72X7u9JMF5csnmHkIrGz4V6KchkuxALhup8RSrMuaLHcawSfGCh wEUdkSY5FsrhoSf/6FtHCj16XsC1iEVGJcobwWnNDX0JHY9gQHsKpVsBs3CFPLYq4xw5 ss1KE80isPliU6pNErEsvbT07QiQpXQUSmwPydQjRL/4upWh/OA1E976Q4Gkyu6rOcNR ZgrJz/qj9mpw7qJlfPVWlLfDAXVbN6AiIjKvXGHMm8zmHflGZra3xfDiLKWL5K2lNHe0 2AnQ==
MIME-Version: 1.0
X-Received: by with SMTP id v5mr13726750lag.84.1406827373061; Thu, 31 Jul 2014 10:22:53 -0700 (PDT)
Sender: hallam@gmail.com
Received: by with HTTP; Thu, 31 Jul 2014 10:22:53 -0700 (PDT)
Date: Thu, 31 Jul 2014 13:22:53 -0400
X-Google-Sender-Auth: tX0VDM65d69OLz_yAHo_rq6aSCw
Message-ID: <CAMm+LwgZp4sgLaFZeWV05UDvN=x7FUNbM5Gi32fJRRrKmais+A@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ibacgC74DfzpkMAESeRqsKxcSe0
Subject: [Cfrg] Another perspective on the Curve256/255 problem
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, 31 Jul 2014 17:22:57 -0000

Lets recap what we need for Internet protocols, as far as I am
concerned there are only two buckets that matter:

WF128 - High performance / small public key size. 2^128 work factor
WF256 - High security delivering a confidence factor of 50+ years.
2^256 work factor

[I am using WF128 to remind ourselves that this is a 2^128 Work Factor
which is what really matters here.]

Given that any ECC scheme is a LOT faster than RSA2048 and much more
secure than RSA4048, it is actually quite easy to fit most
applications into one bucket or the other. Without really good reasons
to the contrary:

* Any key that is relied on for encryption of stored data should be WF256
* Any key that is embedded as a long term Key Signing Key must be WF256

So PKIX, S/MIME and OpenPGP should just use WF256. Which means that a
TLS stack is going to need the ability to do WF256.

PFS is a different case since in a well designed protocol, PFS is an
additional confidentiality control rather than a single point of
failure. Breaking the PFS key should only affect the forward secrecy
of a communication and then only if the master key exchange has been

Since PFS is an additional control, there is a good argument that
performance is critical. The parties might just turn PFS off if it is
too slow. So there is quite an argument to be made to keep an WF128
bucket in that case.

At the meeting we saw the NUMS curves compared to the FastPrimes
curves and we saw two different arguments

DJB: Speed! Speed! Speed!

BAL: The most important thing is to assure people there is no special
reason for the choice of curve and so we must eliminate subjective
choices completely.

Now these are both important considerations of course. But DJB's
argument is only a good one for WF128 and BAL's is only really valid
for WF256.

Lets consider BAL's argument first.

For WF256, I think it is a really good one because the only way that
the 2^512-569 or E-521 curves is going to be breakable is if there is
either a flaw in the whole ECC approach or something really special
about a particular chosen curve. We can't know which curve might have
an issue but we can know the reason one curve is being chosen. 2^512
is a round number in crypto, 2^521 is a very odd one.

For WF128, BAL's argument is nonsense. Anyone who cares about the
possibility that the NSA might be manipulating the choice of prime
should be using WF256 crypto. There is a chance that there is
something odd about Curve25519 that makes it easier top break. But the
chance that there is a flaw in ECC that makes Curve25519 highly
vulnerable but leaves 2^256-x unscathed is much smaller.

Equally, DJB's arguments for speed don't really apply at the WF256
level. There isn't a conveniently close curve for a start. So there is
a 'gut check' call and we go looking for Goldilocks curves.

All of the curve choices on offer are significantly faster than
RSA2048 which is what every major application doing public key is
using today. All other things being equal, performance is significant.
But there are many things that have a higher priority:

* Explaining the choice.
* Compatibility with legacy crypto HSMs
* Compatibility with standard data paths

All these arguments favor the 2^512-569 curve. It is really easy to
explain that this is the natural compliment to AES256. E21 is not
going to be offering any more security and might well offer less.

Having sold crypto for 20 years I know that what people care about
most is strength even if they have no clue what it means. It is not
unusual for someone to argue that its too much CPU to turn on TLS
everywhere. Then after they finally decide to bit the bullet they turn
on AES256 because they can. This despite the fact that RSA2048 is the
weakest link.

My people can sell ECC certs pretty easily as being the essential
compliment to AES256. And that is probably the fastest route to
getting ubiquitous deployment of PFS. That speaks for a WF256 solution
that has as little to cloud the argument as possible.

So in my view, the split decision is actually a lot more principled
than splitting the baby. The two camps are focused on different
security needs at different poles and are making the arguments suited
to their chosen poles. Further, we are seeing deployment of Curve25519
which might well be making the issue of choosing a different curve

So in summary, these are the suite choices I think would be relevant to TLS:

Key Signing Certs:  RSA4096 or RSA2048 or NUMS-512 ECDSA
End-Entity Certs: RSA2048 or NUMS-512 ECDSA

WF128 security:
    AES-128-GCM + Curve25519 ECDHE PFS

WF256 security:
    AES-256-GCM + NUMS-512 ECDHE PFS

    AES-256-GCM + Curve25519 ECDHE PFS
    CHA-CHA-POLY + Curve25519 ECDHE PFS

That would make for a total of 10 new suite IDs assuming we go for the
CHA-CHA-POLY options as well.

This time I would want to restrict RSA to a specific key size. There
is no point in using a RSA4096 EE cert with ECC crypto (!) and nothing
less is permitted. So lets nix that degree of freedom.