Re: [Cfrg] revised requirements for new curves

Michael Hamburg <> Mon, 15 September 2014 00:46 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 6E0071A0424 for <>; Sun, 14 Sep 2014 17:46:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 3.454
X-Spam-Level: ***
X-Spam-Status: No, score=3.454 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id xzato05_fdRr for <>; Sun, 14 Sep 2014 17:46:07 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 155C61A0415 for <>; Sun, 14 Sep 2014 17:46:06 -0700 (PDT)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id DE9E83AA12; Sun, 14 Sep 2014 17:42:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1410741765; bh=58MwwvzEE5Yp6/YyIprQ6aDZ9QTNfhGEVRiJvleUV4U=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=f1/zK6M5EpzbCE0PCLDKYEDU9n61MTtgyvIfmkrvuiOBAb72/3VnWZS0dslSSSft4 YgDBD4ZPvakzpIE0rmTNEzmeOX1SzM7hMbriAI7FVs0nm830nKMoAxWgoTkAFlr8EL qWo6ZBH9ZUwRs0KGy2hAqjnVbsjYPjIGpvnWxx0A=
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1973.6\))
From: Michael Hamburg <>
In-Reply-To: <>
Date: Sun, 14 Sep 2014 17:46:04 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <> <> <>
To: Phillip Hallam-Baker <>
X-Mailer: Apple Mail (2.1973.6)
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:46:08 -0000

While this is partly true, it’s also an example of the NIST curves not getting an entirely fair shake because I just ran `openssl speed` with whatever was on my Mac, whereas most of the other curves are optimized.

I’ve added teal dots from the Gueron-Krasnov NIST-P256 paper (citing also the Käsper-Langley paper) to show this effect: at least for NIST-P256, the Mavericks OpenSSL release is about 3.4x worse than the state of the art.

— Mike

> On Sep 14, 2014, at 5:22 PM, Phillip Hallam-Baker <> wrote:
> 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