Re: [Cfrg] Fwd: Re: Safecurves draft

Robert Ransom <rransom.8774@gmail.com> Thu, 09 January 2014 16:38 UTC

Return-Path: <rransom.8774@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 506F71AE17F for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 08:38:12 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.45
X-Spam-Level:
X-Spam-Status: No, score=-1.45 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, MIME_8BIT_HEADER=0.3, 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 VSBYFqh4vPwi for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 08:38:10 -0800 (PST)
Received: from mail-qa0-x229.google.com (mail-qa0-x229.google.com [IPv6:2607:f8b0:400d:c00::229]) by ietfa.amsl.com (Postfix) with ESMTP id A114C1ACC81 for <cfrg@irtf.org>; Thu, 9 Jan 2014 08:38:10 -0800 (PST)
Received: by mail-qa0-f41.google.com with SMTP id w5so3142215qac.14 for <cfrg@irtf.org>; Thu, 09 Jan 2014 08:38:01 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=bh+A5xMsPRZP8/zwOJDCOXd2YrbhxiKGwwVMyd3tsTw=; b=Gyh7ZJ1Yh+SGS+6H+JUECAtPYQBvcFwBkcLuo8/RlYhY9goqQKjstOD3e2S+jkQf9h LmiOjiAyx4jvYSsNZ7OpmMD8wy5giras6/4Y+dFpy9Gt/tyFHKiB2/q0w4sZRnSouIdQ mhevr3yrECpRWo6n/KLERHRdvi7lEEepY1vHBxZzQiAr0XXgfRhYY8cJSBS8/7Gg+Ih+ bvGe4aHZWHYY/dvmtwpW9pkra4ikXX1drsEWCMB+ciLlcu9r9XCyCFZtsDb3yQ0tKhF1 5MndgaRGcUsKqqw2vA/4yhyAkutfV5GcF5OVmslx7/7vR1beWhYZ+ThcT3qVTUIZ9hC6 C9cw==
MIME-Version: 1.0
X-Received: by 10.49.53.66 with SMTP id z2mr9126734qeo.45.1389285480902; Thu, 09 Jan 2014 08:38:00 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Thu, 9 Jan 2014 08:38:00 -0800 (PST)
In-Reply-To: <52CE783C.40504@elzevir.fr>
References: <52CE59C1.6020500@akr.io> <52CE59F4.8050205@akr.io> <52CE6B92.4030504@elzevir.fr> <CABqy+srwc1xTkYfLB+DYPkNDNQdDHLdYdw+BWBxuV4ECY-zs=Q@mail.gmail.com> <52CE783C.40504@elzevir.fr>
Date: Thu, 9 Jan 2014 08:38:00 -0800
Message-ID: <CABqy+sr6FBz16Le8aRb5gDv5MgW67zJdb-MJrqEjW57t0O390w@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: =?UTF-8?Q?Manuel_P=C3=A9gouri=C3=A9=2DGonnard?= <mpg@elzevir.fr>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Fwd: Re: Safecurves draft
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: Thu, 09 Jan 2014 16:38:12 -0000

On 1/9/14, Manuel Pégourié-Gonnard <mpg@elzevir.fr> wrote:
> On 09/01/2014 10:50, Robert Ransom wrote:
>>> About names, I'd really like the names to reflect the type of the curve
>>> (Montgomery or Edwards). This is already the case for other curve
>>> families,
>>> by
>>> the way. So, Mxxx and Exxx seem great to me. I'd even go so far as to
>>> rename
>>> Curve25519 as M255, but I'm sure there are good reasons to disagree on
>>> this
>>> point.
>>
>> Remember that Curve25519's parameter is *not* minimal subject to the
>> constraint of twist security with minimal cofactors -- Dr. Bernstein
>> considered a slightly more subtle criterion regarding the group orders
>> too.  Keep that in mind if you try to establish a systematic name for
>> Curve25519.
>>
> I'm not sure it goes against my argument that the name should reflect the
> type
> of the curve. Or did I miss something?

That's an argument against making curve names appear systematic (e.g.
“M255”) when they may not be.  (I particularly dislike the naming
schemes used in the various versions of 2013/647.)

I guess I have more of a problem with the idea that Montgomery and
Edwards are two different types of curves at all.  The important fact
to convey for a SafeCurve is which *part* of the curve one is talking
about:

* the Montgomery line (i.e. the subset of a curve over the quadratic
extension field whose Montgomery-form x coordinates are ‘rational’);
* the Edwards curve (i.e. the subgroup of a curve whose coordinates
are both ‘rational’); or
* the non-trivial quadratic twist of the Edwards curve (which I'm
pretty sure no one uses).

Curve25519 is a Montgomery line; Ed25519 is an Edwards curve which is
part of Curve25519.  Curve1174 and Curve3617 are Edwards curves.  (I
implemented Curve1174 for 64-bit processors, and called my
Montgomery-form routines “mont1174”, but don't treat that as
normative.)

All of this makes good nomenclature for the various curves and
subcurves and subgroups and subsets both more difficult and more
important to define properly.


>>> and to be fair point 4 is a bit easier to
>>> address
>>> with these curves too.
>>
>> Why 4?  The benefit of complete addition formulas is that
>> implementations don't need to switch to a doubling routine when two
>> points are equal.  Nothing about SafeCurves makes constant-time table
>> lookups any easier.
>>
> Right, I was making an unstated assumption again, sorry for that. The
> assumption
> was that other curves are more likely to use a larger table for performance,
> while a Curve25519 implementation will generally use a ladder with no
> precomputed table, so it will only have to safely swap two points, which is
> less
> expensive than doing a constant-time lookup in a larger (say 16 or 32
> points)
> table. So it lessens the performance vs security conflict.

A Curve25519 (Montgomery-line ECDH) implementation will generally use
a ladder with no precomputed table because Montgomery's formulas are
so much faster that way.

An Ed25519 (Edwards curve, typically signature-related) implementation
will generally use either (a) the variable-time Bos-Coster algorithm
(for batch verification of signatures), (b) the potentially
constant-time Brauer and/or Straus algorithm (for constant-time
signature verification or weird protocols like Ace), or (c) fixed-base
single-scalar multiplication using a huge precomputed table (for key
generation, which had better be done in constant time).


Robert Ransom