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

[Watson Ladd <[e-mail]>]

On Mon, Sep 1, 2014 at 5:46 PM, Brian LaMacchia <[e-mail]> wrote:
> 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?

Have you read DJB's email in which the entire code implementing the
montgomery ladder in tweetnacl is presented? Every argument that
Curve25519 is inferior has to deal with the applications that are
adopting it, today. And so far the Microsoft group has been unable to
deal with this.

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

One could trivially send Curve241417 points in Montgomery form.
Furthermore the curve doesn't mandate a particular set of coordinates.
This has been stated several times on this list.

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

I don't see how this arguments work. Whatever advantages Montgomery
form has (independent of the adoption of Curve25519)  are independent
of security level. Now, if in 2006 Edwards form had been known,
Curve25519 would likely not have been presented in the way it was. The
fact that it is in Montgomery form is a historical accident.

But guess what: the rail gage in England is the size of two horses.
Refer is misspelled in HTTP. A 3/4 inch copper pipe doesn't have a
single dimension 3/4 of an inch big. Wet and dry cups are different (a
fact that made my mother incapable of following US baking recipes
without a scale). The question should be "is there any reason not to
adopt X25519 given the widespread adoption, lack of security
weaknesses, and strong desire for faster ECDH performance?".

>
>>> (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?)

Did you read the "Curve25519: New Speed Records" paper? The X25519
function is the x coordinate of a curve y^2=x^3+486662x^2+x over
E(F_p^2), with x restricted to lie in F_p.  How is this different from
the definition of P256 in terms of leaving things open to
implementors?

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

Which is the case anyway: your code could implement Weierstrass
coordinates and interop with X25519. But leaving the choice of
coordinates open isn't a possibility.

The question we need to answer is what goes on the wire? That needs to
have an answer. And how the computations take place is largely
irrelevant, although we do need to address security considerations,
some of which our choice of coordinates and curve influence. What's
the difference between specifying twisted Edwards and Edwards from
this perspective?

>
>>> (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
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin