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, 2 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