Re: [Cfrg] On the use of Montgomery form curves for key agreement

Robert Ransom <rransom.8774@gmail.com> Tue, 02 September 2014 07:25 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 404111A00AA for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 00:25:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 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] 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 6roylkOwiluX for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 00:25:22 -0700 (PDT)
Received: from mail-qg0-x22d.google.com (mail-qg0-x22d.google.com [IPv6:2607:f8b0:400d:c04::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DC47A1A00AD for <cfrg@ietf.org>; Tue, 2 Sep 2014 00:25:20 -0700 (PDT)
Received: by mail-qg0-f45.google.com with SMTP id e89so6052068qgf.4 for <cfrg@ietf.org>; Tue, 02 Sep 2014 00:25:20 -0700 (PDT)
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=MqPYW4j2xVRSzuYXTjpSclTtgaOBlC732M+Jo0taSkk=; b=Oo23bv5wEM2JZrW5NxHrE2kaw5EJOcqpe8jADfCOvv2QKOOEscXkEs8Pc1utheYd+o wrBvZLLuyms0FD0m8e+ovMeV0hxAnW8DNWtKtukEFTZBxrqYVDbJDId5Hqm3VwycK8YU 2Cj7i+yHShSt3XJdhBVTqtNF7YiSGuEkb9uzz0j43Zb6yGooWAWkSSXP0h4TfhRpt+MW th5PfMcwnTjDACMymdaSicSUAPp+bXnM/7174OPo+0ymYu8Ik1CUbJlHW0tvvKQQEbxP gluannlmAHFUzNBPtu7qsr19xfb3Laudi5/diOlIpw4tgplKZx1jdHMjeZSpkoCDfg11 4EfQ==
MIME-Version: 1.0
X-Received: by 10.229.232.1 with SMTP id js1mr52392482qcb.20.1409642720174; Tue, 02 Sep 2014 00:25:20 -0700 (PDT)
Received: by 10.140.51.233 with HTTP; Tue, 2 Sep 2014 00:25:20 -0700 (PDT)
In-Reply-To: <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com>
Date: Tue, 2 Sep 2014 00:25:20 -0700
Message-ID: <CABqy+srA6KmTcKZ39jbWOibd0-5ZhvjCuRDiWh1qBTor2q=qoA@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Brian LaMacchia <bal@microsoft.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/CYRf9YkWG1f7OY3tLyRk9h2HBKs
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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: Tue, 02 Sep 2014 07:25:23 -0000

On 9/1/14, Brian LaMacchia <bal@microsoft.com>; wrote:
> See responses inlined below
>
> -----Original Message-----
> From: Andy Lutomirski [mailto:luto@amacapital.net]
> Sent: Monday, September 1, 2014 11:55 AM
> To: Brian LaMacchia
> Cc: cfrg@ietf.org
> Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
>
>>> 1.       Requiring a Montgomery form curve for key agreement and for a
>>> particular security level means that implementations of protocols with
>>> both key agreement and digital signatures must implement both
>>> Montgomery curve arithmetic and additionally curve arithmetic for
>>> another curve form.  From an engineering perspective there is thus a
>>> clear drawback to requiring different curve forms for key agreement
>>> and digital signature at the same security level.
>
>>You can do arithmetic on a curve points given in Montgomery form without a
>> Montgomery ladder >implementation by converting to a different coordinate
>> system.  I'm not sure why you'd want to in >anything other than the
>> tiniest embedded implementation, but you could.
>
> Yes, technically you could do that, but I haven’t seen anyone suggest that
> was in any way practical or interesting.

I've suggested that
(<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>).

To summarize:

* If the point format contains an Edwards-form y coordinate instead of
a Montgomery-form x coordinate, implementations which use the
Montgomery ladder, for whatever reason, must incur a significant extra
cost.  (The Montgomery ladder is far simpler than the algorithms you
recommend, and can be implemented with far less RAM than any tolerably
efficient scalar-multiplication routine based on Edwards form, so many
implementations will use the Montgomery ladder in practice, and some
implementations must use it.)

* If the point format consists of a Montgomery-form x coordinate
(possibly together with a sign bit for an Edwards-form x coordinate),
point decompression to projective Edwards (or twisted Edwards) form
costs only trivially more.  There is a small added cost over Dr.
Bernstein's ‘Curve41417’ ECDH implementation (but only because it is
sub-optimal), and essentially no added cost for your algorithms (which
must double their input before table construction).


(I do believe that using Edwards-form point formats in the Ed25519
signature system and the Curve41417 ECDH system was a bad decision --
in particular, if Ed25519 had used a Montgomery-form point format
instead, it would have been far more convenient for many applications
-- but I disagree strongly with your claim that using a different
point format for a signature system's nonces is inherently bad.  I'll
post more details about that at some point, hopefully soon.)


>  To be clear, the reason you would
> want to change to another form in ECDHE is for significant performance gains
> in the fixed-base key generation.

This is false, and you clearly know that: your own research group's
paper gives performance figures for a ‘hybrid’ ECDHE implementation
which uses Edwards form internally for key generation, and uses the
Montgomery ladder for the variable-base scalar multiplication.

(For everyone else, the added cost (during key generation) of encoding
a projective Edwards-form point to a Montgomery-form point format
rather than an Edwards-form point format is trivial: two additions.)


Robert Ransom