Re: [Cfrg] Safecurves draft

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Thu, 09 January 2014 08:08 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 3E4571ADFD0 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 00:08:39 -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 a4IulyDPcQtm for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 00:08:37 -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 575361ACC89 for <cfrg@irtf.org>; Thu, 9 Jan 2014 00:08:37 -0800 (PST)
Received: from thue.elzevir.fr (thue.elzevir.fr [88.165.216.11]) by mordell.elzevir.fr (Postfix) with ESMTPS id 4AC47161DF for <cfrg@irtf.org>; Thu, 9 Jan 2014 09:08:27 +0100 (CET)
Received: from [192.168.0.124] (unknown [192.168.0.254]) by thue.elzevir.fr (Postfix) with ESMTPSA id 45FB02988A for <cfrg@irtf.org>; Thu, 9 Jan 2014 09:08:26 +0100 (CET)
Message-ID: <52CE58F9.7020606@elzevir.fr>
Date: Thu, 09 Jan 2014 09:08:25 +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: <CACsn0cmPj-=bfwCLJXvHSbOS_U5AfZH2vTWfrVsXwOXF4Y9hcg@mail.gmail.com> <52CD9B98.2010208@elzevir.fr> <CACsn0c=OqqF4QhW8RH-BD_wtFoBtQKfYWqsGQ0mYDxohk=VbXQ@mail.gmail.com> <52CDDAE2.50708@akr.io> <CACsn0ckRQiAQEy-9TZt18EmkePicm8kvr6tkjMEa2+=MAbkWuQ@mail.gmail.com>
In-Reply-To: <CACsn0ckRQiAQEy-9TZt18EmkePicm8kvr6tkjMEa2+=MAbkWuQ@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: 7bit
Subject: Re: [Cfrg] 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 08:08:39 -0000

On 09/01/2014 00:50, Watson Ladd wrote:
> The EFD formulas will go in appendix to address the URL problem, and
> to address some people's desire for explicit formulas.

When copying the EFD formulas in the appendix, please don't forget to define the
meaning of the variables. For example, for Montgomery curves [1] use X1, X2, ...
X5 without mentioning explicitly (unless I missed something) that the formulas give

	(X4, Z4) = 2 (X2, Z2)
	(X5, Z5) = (X2, Z2) + (X3, Z3)

for inputs such that (X1, 1) = (X2, Z2) - (X3, Z3). Reminding readers about
Montgomery ladders (so that this last condition makes sense) cannot hurt. By the
way, it might be worth pointing out that the formulas in the EFD use (A+2)/4, as
opposed to the formulas in the Curve25519 paper, that use (A-2)/4. (I may be
dense, but I got bitten by this.)

[1]: http://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#ladder-mladd-1987-m

This was for Montgomery curves since that's the kind I'm the most familiar with
right now, but similar remarks probably apply for twisted Edwards curves.

By the way, it might be good to insert a word of warning about the fact that the
design of the curves themselves doesn't automatically protect from all
side-channels, and some points are still the responsibility of implementers:
avoid branches and data-dependant memory accesses in the ladder, and either use
constant-time field arithmetic or randomize projective coordinates.

Manuel.