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
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves William Whyte
- Re: [Cfrg] revised requirements for new curves Manuel Pégourié-Gonnard
- Re: [Cfrg] revised requirements for new curves Phillip Hallam-Baker
- Re: [Cfrg] revised requirements for new curves Stephen Farrell
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Watson Ladd
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves David Jacobson
- Re: [Cfrg] revised requirements for new curves Manuel Pégourié-Gonnard
- Re: [Cfrg] revised requirements for new curves D. J. Bernstein
- Re: [Cfrg] revised requirements for new curves Michael Hamburg
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Adam Langley
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Adam Langley
- Re: [Cfrg] revised requirements for new curves Damien Miller
- Re: [Cfrg] revised requirements for new curves Damien Miller
- Re: [Cfrg] revised requirements for new curves Torsten Schuetze
- Re: [Cfrg] revised requirements for new curves Eric Rescorla
- Re: [Cfrg] revised requirements for new curves Markulf Kohlweiss
- Re: [Cfrg] revised requirements for new curves Phillip Hallam-Baker
- Re: [Cfrg] revised requirements for new curves Alyssa Rowan
- Re: [Cfrg] revised requirements for new curves Michael Hamburg
- Re: [Cfrg] revised requirements for new curves Phillip Hallam-Baker
- Re: [Cfrg] revised requirements for new curves Michael Hamburg
- Re: [Cfrg] revised requirements for new curves Andrey Jivsov
- Re: [Cfrg] revised requirements for new curves Andrey Jivsov