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

[Brian LaMacchia <[e-mail]>]

See responses inlined below

-----Original Message-----
From: Andy Lutomirski [mailto:[e-mail]] 
Sent: Monday, September 1, 2014 11:55 AM
To: Brian LaMacchia
Cc: [e-mail]
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