Re: [Cfrg] revised requirements for new curves

Phillip Hallam-Baker <> Mon, 15 September 2014 00:22 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 7FF561A0426 for <>; Sun, 14 Sep 2014 17:22:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id DfkSn_MYqHEH for <>; Sun, 14 Sep 2014 17:22:32 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4010:c03::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CE0471A0104 for <>; Sun, 14 Sep 2014 17:22:31 -0700 (PDT)
Received: by with SMTP id hz20so3777665lab.29 for <>; Sun, 14 Sep 2014 17:22:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type:content-transfer-encoding; bh=fQCvxM3dzllq5Vdu3H+cB0AWi6n+2QWkFAzbrpvZIJY=; b=sS5408+NRQYp/UgmuQ1D53zJvtserfVTVfDt4SLPGNkFRIV4gFMJjV/1aiHSyzoVE3 VnOr/ELPTw1Ks+Gx54yfXW2EtT5NWF0Rb1mLNKT/fdUWUrJ77PWbkUJj/flQV8AGT+gd 5ZaVj6q1s4owxcQYkJ33VzqAtXDOpb4/HK2ECUozvbW2QIfSc+wkHrRs/Qc3TVgjd5PB 5IgrzS2iR9Nk42+peRuBKFl14Mvamo+qcqFK1NH1xYgPFglkLcbNT4sD/kMJuV7LSnJ3 nwtRKlcaY64yfVnnRlznkWFfpIEtFvhmANwMltOXoRxFqRUEFz4g/B3yeRW2UsTVN/5m y8sg==
MIME-Version: 1.0
X-Received: by with SMTP id g9mr24972154lag.14.1410740550001; Sun, 14 Sep 2014 17:22:30 -0700 (PDT)
Received: by with HTTP; Sun, 14 Sep 2014 17:22:29 -0700 (PDT)
In-Reply-To: <>
References: <> <> <>
Date: Sun, 14 Sep 2014 20:22:29 -0400
X-Google-Sender-Auth: tfRM863TqIjjCYY47rl6bErSGZs
Message-ID: <>
From: Phillip Hallam-Baker <>
To: Michael Hamburg <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: Adam Langley <>, "" <>
Subject: Re: [Cfrg] revised requirements for new curves
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 15 Sep 2014 00:22:34 -0000

Well one thing that leaps out is that I can get 512 bits of the NUMS
curves for the price of 256 bits of the NIST curves. And that is a BIG
difference as far as I am concerned.

The performance difference between the NUMS curves and the various
'cherry picked' primes is visible but much less significant.

On Sun, Sep 14, 2014 at 6:59 PM, Michael Hamburg <> wrote:
> On Sep 14, 2014, at 7:22 AM, Phillip Hallam-Baker <>
> wrote:
> But if we plot the points on graphs of defender effort vs attacker
> work factor and look at the curves we can probably see quite easily
> what we are buying with the different approaches.
> I hacked up some plots for ECDH (protected variable-base scalarmul) on Intel
> Sandy Bridge and Cortex A8, A9 platforms at
> Lots of caveats follow!
> It’s important to note that the curves aren’t all on equal footing here.
> The measurements are from the NUMS paper, the Curve41417 paper, `openssl
> speed`, the Goldilocks bench utility (on SBR and Tegra 2); curve25519-donna
> (Curve25519 on Tegra2), SUPERCOP (Curve25519 on other platforms, Goldilocks
> on A8+NEON).  Of these, SUPERCOP and `openssl speed` almost certainly give
> less favorable numbers.
> I haven’t fully implemented Ed480-Ridinghood.  The point in the graph is an
> estimate based on the field arithmetic being identical to Ed448-Goldilocks
> on 64-bit except for the shift amounts.  This is also why it doesn’t appear
> in the 32-bit numbers: it cannot use the same arithmetic on 32-bit
> platforms, but instead would take ~50% longer, which is why I didn’t propose
> it.
> Curve25519, Curve41417, Goldilocks, and the MS “mont” curves are performing
> point (de)compression, but OpenSSL and the NUMS “ed” curves are not.  Point
> decompression would be about a 10% performance hit, but this hit may be
> mitigated (for stronger curves) or negated (for weaker ones) by the use of
> the Montgomery ladder.  Some of the software is also hashing the results and
> some are not.  (Goldilocks hashes; NUMS do not; I don’t know about the
> others.)  Goldilocks tests whether points are on the curve or twist while
> Curve25519 does not, but this test is cheap and adds little security.
> The software benchmarked here has different amounts of optimization and is
> designed for different platforms.  Curve41417 has only been benchmarked on
> Cortex A8+NEON, and the NUMS curves have only been benchmarked on SBR.
> The OpenSSL curves don’t include the latest optimizations, since they’re
> from 1.0.1 or 1.0.1f, compiled however the OS maintainers decided.
> Curve25519-donna is not at all optimized for ARM, but I don’t have any other
> vectorless ARM numbers to go by, since I couldn’t get Curve25519 working in
> SUPERCOP on that platform.
> I expect that the NUMS curves would perform passably well in scalar code on
> the Cortex-A9, because UMAAL can help with the carry handling.  But they
> would be at a disadvantage in NEON, where carry handling is much more
> expensive.  So I would expect the situation on Tegra 2 (with its fast scalar
> core but no NEON) to be comparable to that on Sandy Bridge, but on A8+NEON I
> would expect it to be considerably worse for the NUMS curves.
> In the other direction, I expect that the numbers for Curve41417 would be
> similar on Sandy Bridge to how they are on NEON.  Field arithmetic is
> probably comparable to Ed448-Goldilocks, just as on NEON, so curve ops
> should be about 8% faster due to the 8% smaller curve.
> I know that variable-base scalar multiplication is not the only benchmark
> which matters, but it’s consistently available across many curves.
> I believe that all of the software contains comparable levels of
> side-channel protection.
> Cheers,
> — Mike