Re: [Cfrg] A draft merging rpgecc and thecurve25519function.

Tanja Lange <tanja@hyperelliptic.org> Fri, 02 January 2015 19:38 UTC

Return-Path: <tanja@hyperelliptic.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 19D571A0AF7 for <cfrg@ietfa.amsl.com>; Fri, 2 Jan 2015 11:38:42 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.094
X-Spam-Level: **
X-Spam-Status: No, score=2.094 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545] 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 ZcJQgasNXegP for <cfrg@ietfa.amsl.com>; Fri, 2 Jan 2015 11:38:40 -0800 (PST)
Received: from calvin.win.tue.nl (calvin.win.tue.nl [131.155.70.11]) by ietfa.amsl.com (Postfix) with SMTP id E407F1A19F7 for <cfrg@ietfa.amsl.com>; Fri, 2 Jan 2015 11:38:38 -0800 (PST)
Received: (qmail 26820 invoked from network); 2 Jan 2015 19:38:59 -0000
Received: from unknown (HELO hyperelliptic.org) (131.155.71.33) by calvin.win.tue.nl with SMTP; 2 Jan 2015 19:38:59 -0000
Received: (qmail 9301 invoked by uid 1000); 2 Jan 2015 19:38:19 -0000
Date: Fri, 2 Jan 2015 20:38:19 +0100
From: Tanja Lange <tanja@hyperelliptic.org>
To: cfrg@ietfa.amsl.com
Message-ID: <20150102193819.GB28778@cph.win.tue.nl>
References: <CAAwjuuy19Yg-TVWm5BAEkPnwRkfvC2M0T=Aeck5iG7Y9FM13cw@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAAwjuuy19Yg-TVWm5BAEkPnwRkfvC2M0T=Aeck5iG7Y9FM13cw@mail.gmail.com>
User-Agent: Mutt/1.5.11
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/lbu388DFq8Y4RcLI2nNhM3XSaCA
Cc: agl@imperialviolet.org
Subject: Re: [Cfrg] A draft merging rpgecc and thecurve25519function.
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, 02 Jan 2015 19:38:42 -0000

>    Perhaps it's worth making an explicit decision on whether or not
>    'rigidity' is actually a required feature. The very rough consensus
>    appears to be 'no', because it's regarded as improbable ('alien
>    technology') that anyone would be able to 'backdoor' the elliptic curve.
>    In either case it appears to me that deciding this question ought to fix
>    the curve on purely technical grounds (no -> curve25519, yes -> rpgecc)
>
This would be quite a mischaracterization of X25519. The 2006 paper
contains full justifications about every single choice made and
X25519 is historically the first fully rigid curve (unless one includes
Koblitz curves or other curves with very special properties which
coincidentally limit the choice down to just one curve). Its coefficient
A is the smallest one achieving all required properties. The reason
that this draft finds a different (isogenous) curve is that it searches
for the smallest coefficient d for a curve in _Edwards_ form rather 
than for the smallest coefficient A for a curve in _Montgomery_ form. 

This 'wiggle room' of choosing a curve shape cannot be eliminated
but it's quite small. (Note that the paper introducing the NUMS curves
had 26 curves spread over 3 levels of security, because of this and
a similar decision of how to optimize the prime choice.)

I don't understand why the procedure should be part of the draft 
anyways. A description of how to rigidly choose curves already
appears in ACM-CSS 2013 [1]. This could be cited along with the 
NUMS paper as informative references in the security considerations. 
The generation method does not matter for the implementor

Regards
	Tanja

[1] "Elligator: Elliptic-curve points indistinguishable from uniform 
random strings", Bernstein, Hamburg, Krasnova, Lange, ACM-CCS 2013,
http://dx.doi.org/10.1145/2508859.2516734 (Open Access)