Re: [Cfrg] On the use of Montgomery form curves for key agreement
Robert Ransom <rransom.8774@gmail.com> Tue, 02 September 2014 08:50 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 765D31A01E7 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 01:50:16 -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 J-9mV_tsHnmc for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 01:50:14 -0700 (PDT)
Received: from mail-qg0-x22e.google.com (mail-qg0-x22e.google.com [IPv6:2607:f8b0:400d:c04::22e]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C3BA71A0184 for <cfrg@ietf.org>; Tue, 2 Sep 2014 01:50:13 -0700 (PDT)
Received: by mail-qg0-f46.google.com with SMTP id q107so6106765qgd.5 for <cfrg@ietf.org>; Tue, 02 Sep 2014 01:50:13 -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=PiBXCSpUQ726mkKsH0bjvfkmgqXgcXhX6fEOGiWmvEI=; b=CZ6P9PChtPxdbDaUZdp1c+cnKBmSk344SIkKYllpwxjo4bYrjTXzRLAbWfheb9MjLg XrwdODFEnaEH/WMw2IbVzhQWPzhzg3/6jJLdSZt+SofRWzx/p9+XQ3vhQOEwL3QbIFUK +32aFxPlbz1YuGDGg8SImsCeEgux83jWmZVQSU9UpZJl1ECSZeHKGOJAqa/TxYgqAGr1 XU3v8AP3rAQBpaWTY0LXTQIf1Gh7qA+gAdSbNVMQS/7y4kmhK/QKlRBCEuZoYTDpqWdm 4YFvLL8epsN8P8jwugnuZo88tA741yrmUrR0Z16YYLLJWxwLfXlnDkMcmU5CrmY4AQMW BAaw==
MIME-Version: 1.0
X-Received: by 10.229.53.133 with SMTP id m5mr52874076qcg.19.1409647812974; Tue, 02 Sep 2014 01:50:12 -0700 (PDT)
Received: by 10.140.51.233 with HTTP; Tue, 2 Sep 2014 01:50:12 -0700 (PDT)
In-Reply-To: <b7f734820451474085f91f7118d4ffad@BL2PR03MB242.namprd03.prod.outlook.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com> <CABqy+srA6KmTcKZ39jbWOibd0-5ZhvjCuRDiWh1qBTor2q=qoA@mail.gmail.com> <b7f734820451474085f91f7118d4ffad@BL2PR03MB242.namprd03.prod.outlook.com>
Date: Tue, 02 Sep 2014 01:50:12 -0700
Message-ID: <CABqy+soe=iYRsyeq6Dv-aoh9aRmkQtdv1uH7F3atYjrOb0MhTw@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/Y-dh-o7OgpCvrugpv8oQvsxa-Ac
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 08:50:16 -0000
On 9/2/14, Brian LaMacchia <bal@microsoft.com> wrote: > -----Original Message----- > From: Robert Ransom [mailto:rransom.8774@gmail.com] > Sent: Tuesday, September 2, 2014 12:25 AM > To: Brian LaMacchia > Cc: Andy Lutomirski; cfrg@ietf.org > Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement > >>On 9/1/14, Brian LaMacchia <bal@microsoft.com> wrote: >>> 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.) > > Hi Robert, > > I think you misread that portion of my email as being about the cost of > conversion between coordinate formats, when I was in fact referring to the > overall “hybrid” implementation. I'll quote that portion again, with all possible context: >>> 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. 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. I interpret “change to another form in ECDHE” to mean “change the ECDHE protocol to use another form” (in context, a form other than Montgomery form). I still consider that to be the most reasonable interpretation of that phrase, given the full context. If you meant “convert a point used in ECDHE to another form” (other than Montgomery form), then your statement is poorly worded and still clearly false: the performance improvement that you are referring to for fixed-base scalar multiplication relies on the base point being provided in the form of a precomputed table. The cost of converting a base point into that ‘format’ is greater than the benefit can possibly be for a single operation, so you cannot possibly be referring to the table precomputation as ‘chang[ing] to another form *in ECDHE*’ (emphasis added). > If you go back and reread the entire > message, you’ll see a more detailed comment on exactly this point at the > bottom of my reply to Andy. I did see that. However: * Your research group only considered one type of processor in its benchmarks, and made all design decisions based on the performance of its implementations on that processor. The results do not show which point format (or coordinate-field shape) will provide the best performance in a small processor (or other device) with limited memory, or in a processor with no (or small) cache RAM. (I expect that some implementations will be forced to use the Montgomery ladder even for signature verification, due to extreme memory or cache limitations.) * Your research group didn't know that the Montgomery ladder can tolerate leading zero bits, so they implemented the Montgomery ladder with an unnecessarily long scalar. As a consequence, I don't trust your initial benchmarking results for the Montgomery ladder. Have you corrected that implementation issue and published new benchmark results? * Your research group's paper did not, as of the last time I read it, explicitly state whether the twisted-Edwards-form benchmark results used compressed or uncompressed points. As Dr. Bernstein has pointed out, specifying an uncompressed point format in a standard meant to have multiple independent implementations introduces the risk that someone will omit input validation, so I would oppose the use of an uncompressed point format in any IETF protocol. Do your benchmark results for twisted-Edwards ECDHE include the cost of point compression? (Disclaimer: I've implemented software which uses uncompressed Edwards-form points; I now believe that both “uncompressed” and “Edwards-form” were bad design decisions.) Robert Ransom
- [Cfrg] On the use of Montgomery form curves for k… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… D. J. Bernstein
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tony Arcieri
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Michael Hamburg
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Jim Schaad
- Re: [Cfrg] On the use of Montgomery form curves f… Markulf Kohlweiss
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Manuel Pégourié-Gonnard
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov