Re: [Cfrg] Fwd: Re: Safecurves draft

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Thu, 09 January 2014 10:22 UTC

Return-Path: <mpg@elzevir.fr>
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 5FA731AE236 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 02:22:01 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.994
X-Spam-Level:
X-Spam-Status: No, score=0.994 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FH_RELAY_NODNS=1.451, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3, RDNS_NONE=0.793] 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 jKyTVlNtRb9F for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 02:22:00 -0800 (PST)
Received: from mordell.elzevir.fr (unknown [IPv6:2001:4b98:dc0:41:216:3eff:feeb:c406]) by ietfa.amsl.com (Postfix) with ESMTP id 5DF251AE234 for <cfrg@irtf.org>; Thu, 9 Jan 2014 02:22:00 -0800 (PST)
Received: from thue.elzevir.fr (thue.elzevir.fr [88.165.216.11]) by mordell.elzevir.fr (Postfix) with ESMTPS id 97604161DF for <cfrg@irtf.org>; Thu, 9 Jan 2014 11:21:49 +0100 (CET)
Received: from [192.168.0.124] (unknown [192.168.0.254]) by thue.elzevir.fr (Postfix) with ESMTPSA id AFB0E2988A for <cfrg@irtf.org>; Thu, 9 Jan 2014 11:21:48 +0100 (CET)
Message-ID: <52CE783C.40504@elzevir.fr>
Date: Thu, 09 Jan 2014 11:21:48 +0100
From: =?UTF-8?B?TWFudWVsIFDDqWdvdXJpw6ktR29ubmFyZA==?= <mpg@elzevir.fr>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.1.1
MIME-Version: 1.0
To: cfrg@irtf.org
References: <52CE59C1.6020500@akr.io> <52CE59F4.8050205@akr.io> <52CE6B92.4030504@elzevir.fr> <CABqy+srwc1xTkYfLB+DYPkNDNQdDHLdYdw+BWBxuV4ECY-zs=Q@mail.gmail.com>
In-Reply-To: <CABqy+srwc1xTkYfLB+DYPkNDNQdDHLdYdw+BWBxuV4ECY-zs=Q@mail.gmail.com>
X-Enigmail-Version: 1.6
OpenPGP: id=98EED379; url=https://elzevir.fr/gpg/mpg.asc
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
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 10:22:01 -0000

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?

> I don't see the benefit of defining both a ‘safe’ Montgomery curve
> (for the present definition of “safe”) and a ‘safe’ Edwards curve over
> the same coordinate field -- every Edwards curve with minimal
> parameter can be used efficiently with Montgomery's formulas.  (The
> Montgomery-form parameter becomes the reciprocal of a small integer,
> which can be handled as efficiently as a small integer itself.)
> 
> (For that matter, I would suggest replacing Curve25519 with the
> twisted Edwards curve a=-1, d=121665 over the same field in any new
> application or standard.)
> 
An interesting point.

> Issue 2 is obviated by twist security for single-scalar multiplication
> of a Montgomery-form x coordinate.  It remains relevant for any
> application which operates on full points (whether transmitted
> uncompressed or compressed).
> 
Absolutely. There was a hidden assumption that only the x coordinate be used in
my statement. Actually, I think it reinforces my point that the curves aren't
"magically" safe regardless of the how they are implemented or used in a
protocol: indeed, the fact that no public key validation is needed depends not
only on the curve (twist security), but also on the protocol (x coordinate only).

>> 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.

Manuel.