Re: [Cfrg] revised requirements for new curves

Michael Hamburg <mike@shiftleft.org> Mon, 15 September 2014 00:46 UTC

Return-Path: <mike@shiftleft.org>
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 6E0071A0424 for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 17:46:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xzato05_fdRr for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 17:46:07 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 155C61A0415 for <cfrg@irtf.org>; Sun, 14 Sep 2014 17:46:06 -0700 (PDT)
Received: from [192.168.1.113] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id DE9E83AA12; Sun, 14 Sep 2014 17:42:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; 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 <mike@shiftleft.org>
In-Reply-To: <CAMm+LwipUBToG2b1A3z7NTDEzMC6og0zwjyQ=eGsdrCZGfwoQQ@mail.gmail.com>
Date: Sun, 14 Sep 2014 17:46:04 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <9B3EDBDA-F4F4-441C-9F21-14DEC8BB530E@shiftleft.org>
References: <CAMfhd9UaJtcaRurEOtN289ribT7ZH6OUB55or+T1NN6U8jv9Rw@mail.gmail.com> <CAMm+LwhATMG9Pco-Bt1n-rgr3vEmgFKbpbvA0f9V9fW9t36UVw@mail.gmail.com> <C6D1200E-0CD5-4716-9948-D0CF039F7F3A@shiftleft.org> <CAMm+LwipUBToG2b1A3z7NTDEzMC6og0zwjyQ=eGsdrCZGfwoQQ@mail.gmail.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
X-Mailer: Apple Mail (2.1973.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/bf-1PwQwfjaG0OBSB00kM3w2KGI
Cc: Adam Langley <agl@imperialviolet.org>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] revised requirements for new 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: 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 <phill@hallambaker.com> 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 <mike@shiftleft.org> wrote:
>> 
>> On Sep 14, 2014, at 7:22 AM, Phillip Hallam-Baker <phill@hallambaker.com>
>> 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
>> 
>> http://ed448goldilocks.sourceforge.net/comparison/
>> 
>> 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