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

Brian LaMacchia <bal@microsoft.com> Tue, 02 September 2014 00:46 UTC

Return-Path: <bal@microsoft.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 B7D8B1A6F25 for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 17:46:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
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 HDZq5_Joej_d for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 17:46:14 -0700 (PDT)
Received: from na01-bn1-obe.outbound.protection.outlook.com (mail-bn1lp0139.outbound.protection.outlook.com [207.46.163.139]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 27F6F1A6F21 for <cfrg@ietf.org>; Mon, 1 Sep 2014 17:46:13 -0700 (PDT)
Received: from BL2PR03MB242.namprd03.prod.outlook.com (10.255.231.18) by BL2PR03MB244.namprd03.prod.outlook.com (10.255.231.26) with Microsoft SMTP Server (TLS) id 15.0.1015.19; Tue, 2 Sep 2014 00:46:05 +0000
Received: from BL2PR03MB242.namprd03.prod.outlook.com ([169.254.8.218]) by BL2PR03MB242.namprd03.prod.outlook.com ([169.254.8.218]) with mapi id 15.00.1015.018; Tue, 2 Sep 2014 00:46:04 +0000
From: Brian LaMacchia <bal@microsoft.com>
To: Andy Lutomirski <luto@amacapital.net>
Thread-Topic: [Cfrg] On the use of Montgomery form curves for key agreement
Thread-Index: Ac/GFKdVASv0pPTeROyHvj6EvV57FQAAYtoAAAwdIdA=
Date: Tue, 2 Sep 2014 00:46:04 +0000
Message-ID: <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com>
In-Reply-To: <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [63.229.25.58]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 0322B4EDE1
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(13464003)(189002)(199003)(377454003)(99286002)(107046002)(105586002)(21056001)(77982001)(106356001)(83322001)(74316001)(54356999)(76482001)(46102001)(95666004)(79102001)(33646002)(110136001)(77096002)(74502001)(4396001)(74662001)(86612001)(64706001)(92566001)(80022001)(66066001)(76576001)(20776003)(15975445006)(15202345003)(83072002)(19580405001)(19580395003)(31966008)(81342001)(76176999)(85306004)(90102001)(99396002)(86362001)(50986999)(2656002)(85852003)(81542001)(108616004)(101416001)(87936001)(24736002)(42262002); DIR:OUT; SFP:; SCL:1; SRVR:BL2PR03MB244; H:BL2PR03MB242.namprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: microsoft.onmicrosoft.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/bFid0S2jzyEf9bOe8Z9qQsl_a0M
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 00:46:23 -0000

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.  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. 

>Also, can we please stop claiming that things are "clear" problems?
>This isn't clearly a problem.  As has been noted as nauseum on this list, most of the work is in the field >arithmetic, and a Montgomery ladder and, say, Edwards EC arithmetic can share that.

I respectfully disagree; yes the field arithmetic is common, but the curve arithmetic is not and I really don’t think the complexity of the curve arithmetic can just be swept under the rug.  Writing and maintaining two sets of curve arithmetic – both of which need to be side-channel resistant – has cost, and why maintain two when only one is needed? 

>> 2.       Assuming that implementations will implement more than one security
>> level, choosing X25519 for ECDHE at the 128 bit security level will 
>> require implementations to use different curve arithmetic for the 128 
>> bit security level than other security levels.  Again from an 
>> engineering standpoint this is a negative.

>You're pre-supposing that other security levels wouldn't use Montgomery coordinates.

That’s correct, and I based that statement on what’s been submitted to CFRG and the conversation to date.  Do you disagree?  Except for X25519 no other curves mandating use of Montgomery form are currently on the table (e.g. Bernstein et al use the Edwards form over 2^414-17).  Yes, some Edwards curve implementations might choose to move back-and-forth between the two forms if they think that helps them, but (a) that should be an option left up to implementers if CFRG chooses an Edwards curve, not a requirement, and (b) as our recent research shows such manipulations are unlikely to be helpful anyway.

>> Those arguing for adoption of X25519 are requesting that CFRG (a) treat the
>> 128 bit security level different from other security levels,

>This is the first time that I've seen this request on this list.

See previous reply.  No one is arguing for mandatory use of Montgomery form at any other security level.  

>> (b) force
>> implementations of multiple security levels of key agreement to 
>> implement different curve arithmetic for different security levels,

>I really don't see any justification for this claim.

See previous reply; there are no Montgomery form curves on the table for the 192- and 256-bit security levels.  

>> (c) force
>> implementations of protocols with both key agreement and digital 
>> signatures to implement different curve arithmetic for those two 
>> operations, even at the same security level,

>This would be an option available to implementers, not a requirement.

You’ve just made my point for me: if using the Montgomery form was just an option for implementers that they could consider using if they saw a benefit, that would be perfectly fine and well in line with the IETF tradition of standardizing protocols and letting implementations compete.  But that’s not the way X25519 is defined.  (OK, I guess one could do everything in Edwards and then at the very end convert to Montgomery coordinates in order to just send the X coordinate, but why do all that work and why do it only at that security level, for little to no performance gains?)

Alternatively and for the record, it seems to me that it would be perfectly reasonable for CFRG to decide to specify only Edwards curves (*not* twisted, just plain Edwards curves) as Mike Hamburg and others have suggested, and leave *all* of the optimizations as implementation choices.  So whether someone wants to use twisted Edwards curves, the Montgomery ladder, some other improvement, etc., would be completely up to them.  

>> (d) force point conversions between curve forms to avoid efficiency 
>> loss in ECDHE, and

>Now I'm completely lost.  I honestly have no idea what you mean by this.

OK, please go take a look at Section 6 of the NUMS paper (http://eprint.iacr.org/2014/130, starting on page 20), which describes the situation in detail.  Here’s the short version: for ECDHE you need one fixed-base and one variable-base computation, but you can’t take advantage of the Montgomery ladder for fixed-based computations so if you want an efficient implementation you do the fixed-base computation in (twisted) Edwards and the variable-base computation using the Montgomery ladder.  This is what’s called the “hybrid” solution in the paper.  Doing that, and the necessary coordinate conversion in between, turns out to be slightly slower than simply doing both computations in twisted Edwards in the first place.  

--bal