Re: [Cfrg] revised requirements for new curves

Phillip Hallam-Baker <phill@hallambaker.com> Mon, 15 September 2014 00: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 [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7FF561A0426 for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 17:22:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id DfkSn_MYqHEH for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 17:22:32 -0700 (PDT)
Received: from mail-la0-x22a.google.com (mail-la0-x22a.google.com [IPv6:2a00:1450:4010:c03::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CE0471A0104 for <cfrg@irtf.org>; Sun, 14 Sep 2014 17:22:31 -0700 (PDT)
Received: by mail-la0-f42.google.com with SMTP id hz20so3777665lab.29 for <cfrg@irtf.org>; Sun, 14 Sep 2014 17:22:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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 10.152.4.9 with SMTP id g9mr24972154lag.14.1410740550001; Sun, 14 Sep 2014 17:22:30 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.112.122.51 with HTTP; Sun, 14 Sep 2014 17:22:29 -0700 (PDT)
In-Reply-To: <C6D1200E-0CD5-4716-9948-D0CF039F7F3A@shiftleft.org>
References: <CAMfhd9UaJtcaRurEOtN289ribT7ZH6OUB55or+T1NN6U8jv9Rw@mail.gmail.com> <CAMm+LwhATMG9Pco-Bt1n-rgr3vEmgFKbpbvA0f9V9fW9t36UVw@mail.gmail.com> <C6D1200E-0CD5-4716-9948-D0CF039F7F3A@shiftleft.org>
Date: Sun, 14 Sep 2014 20:22:29 -0400
X-Google-Sender-Auth: tfRM863TqIjjCYY47rl6bErSGZs
Message-ID: <CAMm+LwipUBToG2b1A3z7NTDEzMC6og0zwjyQ=eGsdrCZGfwoQQ@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/z3hwCzqoEJk1Jvz7tOhlpXu_Lak
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: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 <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