[Cfrg] Good and bad curves

Phillip Hallam-Baker <phill@hallambaker.com> Wed, 13 August 2014 12: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 756C11A870B for <cfrg@ietfa.amsl.com>; Wed, 13 Aug 2014 05:22:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.422
X-Spam-Level: *
X-Spam-Status: No, score=1.422 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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 okrnM0aXGbQH for <cfrg@ietfa.amsl.com>; Wed, 13 Aug 2014 05:22:36 -0700 (PDT)
Received: from mail-lb0-x22f.google.com (mail-lb0-x22f.google.com [IPv6:2a00:1450:4010:c04::22f]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8E8101A8715 for <cfrg@irtf.org>; Wed, 13 Aug 2014 05:22:17 -0700 (PDT)
Received: by mail-lb0-f175.google.com with SMTP id 10so8064092lbg.20 for <cfrg@irtf.org>; Wed, 13 Aug 2014 05:22:15 -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=GmBJj7xrqyqLT8VEbySJeulYiVXXRwtLTGTbx/dQOO8=; b=lRazEp62C0CrZYUfHxSXtHDHXFdkbwxyuEz8s9WqKaH9Uz2g4dhEi33kwQEC4GqZ17 jAJHcz2MP2/9M8aPpPXtfyUKrbgtje9HJ9qc/bHSyxWv1hMNkwoInTBLhCfF49fGd/Y3 oWWxzeGbsW24D7vyCJJ2aVGF/pTkVyp7r2FeDaVrrYJHirLkIcpeSiUrW5IPKtwP7WZ8 RVVHjIcCbDHV7QKttYWifEGNdDQMf1RGr5HQvV75vUWn7xyMSoZjoBv3EH2KSh671SBt kNjkuc9LpkLEgODGZMs6WG8XWMYjLN+8a46P5urrWfeBeQrQuKZ3II1CSsA3KWQy5O0l MzNQ==
MIME-Version: 1.0
X-Received: by with SMTP id s6mr4214655laa.85.1407932535612; Wed, 13 Aug 2014 05:22:15 -0700 (PDT)
Sender: hallam@gmail.com
Received: by with HTTP; Wed, 13 Aug 2014 05:22:15 -0700 (PDT)
Date: Wed, 13 Aug 2014 08:22:15 -0400
X-Google-Sender-Auth: -TSLeQz408UhMTzDp4GJFzfiQ5M
Message-ID: <CAMm+Lwjg2d+qigTuitnCSAggSWf80B9dLu7NCH-1So9QyXoFrw@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/XPfH2jZRTgsSHLVXIfBRK0ctRWE
Subject: [Cfrg] Good and bad curves
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, 13 Aug 2014 12:22:38 -0000

Certain curves are known to be weaker than other due to attacks that
require the curve meet specific criteria. There are essentially three
ways to address this problem

1) Reject curve choices that are known to be 'weak', i.e. vulnerable
to known attacks.

2) Do 1 and increase the bit length by a safety factor in case the
attack can be extended.

3) Just increase the bit length and do not attempt to reject weak curves.

My preference is for (3) since any attempt to select curves creates an
opening for IPR claims and we are going to need the safety margin

The problem we face is not to find the best compromise or speed and
performance as some suggest. None of us know the set of unknown
attacks by definition. Even Fort Meade only knows a subset of unknown
attacks. So none of us is competent to decide on a compromise.

What the known attacks can tell us usefully is how big a safety margin
we need. So if there is an attack against curves formed from
co-factors of warped smooth numbers that reduces the work factor from
x bits to x/2 then we want a safety margin of 2 times the number of
bits regardless. So it would be interesting to see people raise those

What this is really about is coming to a defensible choice that can
become the industry consensus. And this gets us to Bruce's observation
that any security signal inevitably gets wound up to one step below
maximum and stays there. Because nobody wants to take responsibility
for lowering the security precautions. [We now have confirmation of
what was suspected at the time, that the DHS scheme only ever went to
yellow when there was a political need to raise it to orange in the
near future],

The industry can't manage a large number of curves. In fact we only
have a need for an orange curve and a red one. Curve 25519 is plenty
fast enough that we don't need to consider alternatives and it is
comfortably secure for use as the orange curve.

We really only need one red curve and the criteria that matters is
defensibility. The 56 bit DES key space was always suspect because it
was such an odd number. 64 bits would have been just as easy, So it
was pretty clear that there was a fix in somewhere. If we go for a 480
bit key we will get similar questions.

If CFRG proposes a 480 bit key and some other group proposes 512 then
the 512 is going to win. Because there is a cost to explaining the
reason 480 bits are 'enough' and there will also be lost sales. And
those matter far more to me than some explanation about a blend of
performance that requires a PhD to fully understand.

The Red curve is going to be 512 bit. I can defend that choice very
easily because it is the largest memory bus size in common use.

Now '512 bit' could mean a prime slightly smaller like 511 or 510
bits. But it can't be suspiciously lower.

There is also a personal career development issue here. I don't think
anyone wants to leave this discussion being known as the guy (or gal)
who persuaded the industry to use the lower security option.