Re: [Cfrg] Safecurves draft

Bodo Moeller <bmoeller@acm.org> Thu, 09 January 2014 14:25 UTC

Return-Path: <SRS0=d0zJ=WP=acm.org=bmoeller@srs.kundenserver.de>
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 B13591AE339 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 06:25:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.467
X-Spam-Level:
X-Spam-Status: No, score=-1.467 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HELO_EQ_DE=0.35, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.538, SPF_HELO_PASS=-0.001, 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 0ZUfi7I3sycK for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 06:25:33 -0800 (PST)
Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.171]) by ietfa.amsl.com (Postfix) with ESMTP id 2690B1AE325 for <cfrg@irtf.org>; Thu, 9 Jan 2014 06:25:33 -0800 (PST)
Received: from mail-ob0-f173.google.com (mail-ob0-f173.google.com [209.85.214.173]) by mrelayeu.kundenserver.de (node=mrbap4) with ESMTP (Nemesis) id 0MY6Rk-1Vwsok0oNM-00UuhQ; Thu, 09 Jan 2014 15:25:22 +0100
Received: by mail-ob0-f173.google.com with SMTP id gq1so3296856obb.4 for <cfrg@irtf.org>; Thu, 09 Jan 2014 06:25:19 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=R11fZ8AD5uvaJXcKrsBRfLE5RsaSZK+QDdPovNVjePQ=; b=CTbolz93VUVhBMHDDlNYPx+4zWafqB7Eh+ScU1NRI8VUtwpxjKPGg+XDe/EbikE44f LrIMvEBhsZVKp2UyMRpDkZyGGtpChQ0/Actv0YNOOupcQRAgPdMeXOLlExiuyMBBldG9 CbKDlLSdTY3WuFHqEs8DWi7npcaMtTm/9w2YLhrs3F4XHfVedqpcN5BRtXFS85+R+gST z+eSpgx9K+G64ajOOimCikFNX7Rlv5AjGBFHWkiZWKtNEySsvXOhtBFL2Unr4GwdYq0g 48o0u1tdIg/AmeWYo6DCLHOLuKxOOf3/qzKOwZHQuKP/g4nocXotX49gPgqs6OAkKk2A 5kmA==
MIME-Version: 1.0
X-Received: by 10.182.66.164 with SMTP id g4mr2401138obt.47.1389277519740; Thu, 09 Jan 2014 06:25:19 -0800 (PST)
Received: by 10.60.142.129 with HTTP; Thu, 9 Jan 2014 06:25:19 -0800 (PST)
In-Reply-To: <CABqy+soXxjY+fEzpHP+_yn9Y1Xtapm_9OWbgDcA_J_Lukz_YLw@mail.gmail.com>
References: <20140109031144.6111382.52184.8264@certicom.com> <20140109094731.GA12327@netbook.cypherspace.org> <CADMpkc+giuSZgrYmusRJmj5SyN9Dcu_Mdaqx5KQPyXGMmosFUw@mail.gmail.com> <CABqy+soXxjY+fEzpHP+_yn9Y1Xtapm_9OWbgDcA_J_Lukz_YLw@mail.gmail.com>
Date: Thu, 9 Jan 2014 15:25:19 +0100
Message-ID: <CADMpkcJFk2C5DPQX9RVWphUH25atsUX2vPA7RwNf8zbmR6dXJQ@mail.gmail.com>
From: Bodo Moeller <bmoeller@acm.org>
To: Robert Ransom <rransom.8774@gmail.com>
Content-Type: multipart/alternative; boundary=089e0160c35e0f0a9204ef8a6109
X-Provags-ID: V02:K0:2eZXn3Nu9vSIpxYlPMJux3D+iril94ufzmHLBnPby94 vwKHToh2JJM8dUK+S5KRKmjkce9Maxx0fNLvXlBExIbjYO4sAF VRoc0ZQQeRoEk29o7RbuM3Z6Vqw2g7pS+BJWsz2hzHBPHVwet9 0TlXfDnPl4vrfDAHcmsJaFceDxsRBpNRYXq7JZ8Al9W9meBtTI Ali2N1TjHEYi1koJ0iCQ4J9Uo39u5KrICBw7NTNeRcYTCR8iNx owz5JjC60iuLB0XIkcjdctk8JEh2ZyWC6TYLMoTuYLo8HkGBqH lSu2Y94H7JO63Dg2LPDjV0I846pLQDpHOBtpAuf2Tae4EuRSO4 7eR1fhky1KcctN0naQ2AVOzxWS+VIZFr6bGG8QfQcTNOUE7a0Z 6Z8N5oqx9Q73YbczLO2offhZzoS12zROHrDPZygEFVubtE25go xDIUc
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
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 14:25:34 -0000

Robert Ransom <rransom.8774@gmail.com>om>:

> On 1/9/14, Bodo Moeller <bmoeller@acm.org> wrote:
> > In that context, given that the name
> > "Curve25519" is already overloaded, and that we probably should make the
> > Edwards representation available for DH too (in addition to EdDSA),
>
> No.  Montgomery-form variable-base single-scalar multiplication takes
> 5M+4S per scalar bit; Edwards-form doublings alone (in ‘extended
> coordinates with a=-1’) are 4M+4S (or 3M+4S if the output will only be
> used as input to another doubling).


As pointed out by Section 6 in http://eprint.iacr.org/2007/286.pdf,
sliding-window multiplication using the Edwards form can be faster than
5M+4S per scalar bit for this curve (although that's probably no longer
true if you want a constant-time implementation -- while the non-sliding
window approach in Section 8 doesn't seem optimal because it's not making
use of signed windows, I don't think the extra savings are sufficient to
beat the Montgomery ladder).  More importantly, if you have a *fixed* base
(which is very relevant for ephemeral ECDH), with appropriate fixed
precomputation you won't need any double operations at all: so the total
time for one fixed-base single-scalar multiplication and one variable-base
signal-scalar multiplication as used in ECDH can be less than with the
Montgomery ladder, even if you want constant time with no secret-dependent
branches.  If you have severe space constraints, then an approach that
involves a few hundred precomputed points is not for you, but in many
typical scenarios this is not an issue at all.

So while the Montgomery-form Curve25519 certainly has its use, allowing
applications to negotiate a different form for ECDH would be beneficial.

Bodo