Re: [Cfrg] Chopping out curves

Robert Ransom <rransom.8774@gmail.com> Fri, 17 January 2014 14:33 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 ABB751AE0F3 for <cfrg@ietfa.amsl.com>; Fri, 17 Jan 2014 06:33:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.628
X-Spam-Level:
X-Spam-Status: No, score=-0.628 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, SPF_PASS=-0.001, URI_HEX=1.122] 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 xkvJ2NipFpcr for <cfrg@ietfa.amsl.com>; Fri, 17 Jan 2014 06:33:37 -0800 (PST)
Received: from mail-qe0-x233.google.com (mail-qe0-x233.google.com [IPv6:2607:f8b0:400d:c02::233]) by ietfa.amsl.com (Postfix) with ESMTP id 22E591AE0D1 for <cfrg@irtf.org>; Fri, 17 Jan 2014 06:33:37 -0800 (PST)
Received: by mail-qe0-f51.google.com with SMTP id d4so3202362qej.24 for <cfrg@irtf.org>; Fri, 17 Jan 2014 06:33:24 -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=4mxBJVZHF10bfxWB/BeLGKOzvjSUceo6P3zL/BfCZvE=; b=lQgrtNRUwPLzWrJhansCpgyHAc5pHvLKEv+9X9eAoXLQFLMh2tHO5ImRW2Ew7MpuVE WnaHa9JmYTfzuB1MniwUp/aIOoA9Uu8h1awHmPGhtyzJ1kozXcnkuTfaYJQSYXSNM4gY qSK0JqFIu1NX3HDvcAwEhnkiyY6VHKGyznVer1g9ITrL+aw/HzbJd8HMB9N8LA4TvcF1 i6vt8zCUffuw8Z8LuUQ7hZFxKHTO85YgT4y9zHpj3qBz4ypbInZs0t3xGIldGoi3156T hjmHMnxUthYs7TZs0HRiGelOd3FMBtkfp0Af7+cnO0w03f/9ID9xuu4EyvbdfHFyYZej wCpQ==
MIME-Version: 1.0
X-Received: by 10.140.91.12 with SMTP id y12mr3486511qgd.26.1389969204506; Fri, 17 Jan 2014 06:33:24 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Fri, 17 Jan 2014 06:33:24 -0800 (PST)
In-Reply-To: <3374f0a3-9998-44e9-a052-61a4a94fe00c@email.android.com>
References: <CACsn0cmJX2begH0q8vOUZhP2t3CFo_2Ad71Neke4EKejoYCPRg@mail.gmail.com> <CAGZ8ZG1qF4ba3ogjHQnMwgXV+0Fj7eR44QdvuSw3GYBvNVFZBA@mail.gmail.com> <c406386b6fc67d11332141423f2f0f40.squirrel@www.trepanning.net> <CACsn0c=Eh1J81JHq=u8WsTtVK4HAJDghyisTZnM6U61jdr2KUQ@mail.gmail.com> <20140117011414.GA3413@netbook.cypherspace.org> <20140117023629.GA4435@netbook.cypherspace.org> <52D8DEC1.9060805@akr.io> <20140117124159.GA9258@netbook.cypherspace.org> <3374f0a3-9998-44e9-a052-61a4a94fe00c@email.android.com>
Date: Fri, 17 Jan 2014 06:33:24 -0800
Message-ID: <CABqy+soq1uvuiMRyF2FVXZoQ1gpdiO92Gj9A+Ri5FQa=5yp3-w@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Alyssa Rowan <akr@akr.io>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Chopping out 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: Fri, 17 Jan 2014 14:33:38 -0000

On 1/17/14, Alyssa Rowan <akr@akr.io> wrote:

> There are arguments in favour of both the existing or a new basepoint for
> t25519 (which is what I'll call the twisted Edwards representation of
> Curve25519 used in Ed25519, as I'm not sure it actually has a name of its
> own?).

The curve specified as ‘T25519’ (a=121666, d=121665) in
draft-ladd-safecurves-03 is something that Watson Ladd made up.  The
Ed25519 signature scheme paper
(<http://ed25519.cr.yp.to/ed25519-20110926.pdf>) specifies the a=-1
form (a=-1, d=-121665/121666).

> Generating a new basepoint for t25519:
> • Elegant; we can select minimum y that satisfies SafeCurves criteria
>   - What advantage, really, would that give in implementation?
>   - Is it worth any perceived benefit?
>   - Absolute rigidity would be critical to avoid potential manipulation
> concerns

Watson Ladd actually chose a point with small Edwards-form x, not
small Edwards-form y.

There is no benefit to choosing a new basepoint, but there's also no
benefit to using ‘T25519’ instead of the (more efficient) form
specified for Ed25519.

As you point out, using a different basepoint does prevent use of keys
in different protocols, even when the protocols are designed to be
safe to use with the same key material, so that's a real (and
unnecessary) cost.

> • Reverification necessary, I think.
>   - New basepoint → new prime order → new primality tests for SafeCurve
> script? (Damn. They're the expensive part.)

‘T25519’ is isomorphic to Curve25519, so any non-identity group
element of odd order on T25519 generates the same group as the
standard basepoint of Curve25519 (and has the same order).

> On balance I have to say, I think I prefer keeping the basepoint Ed25519
> already uses for t25519, but it's not a strong preference. If we do change
> it, we do need to dot the i's and cross the t's, so to speak.

I have a strong preference for throwing out T25519 and using Ed25519
with its standard basepoint.


Robert Ransom