[Cfrg] Fwd: Complexity of the Microsoft curve proposal

[Watson Ladd <[e-mail]>]

On Tue, Oct 14, 2014 at 6:03 PM, Michael Hamburg <[e-mail]> wrote:
>
> On Oct 14, 2014, at 4:54 PM, Craig Costello <[e-mail]> wrote:
>
> Hi Watson,
>
> To elaborate a little on what Mike said, when p == 3 mod 4, defining
> searches for twist-secure curves that minimize the absolute value of the
> Montgomery constant automatically minimize the absolute value of the
> constant on the isogenous (complete) Edwards curve and the absolute value of
> the constant on the isogenous twisted Edwards curve. So regardless of
> whether our curves are implemented using Edwards coordinates, twisted
> Edwards coordinates, or Montgomery coordinates, the corresponding curve
> constant will be small (see Section 2 of http://eprint.iacr.org/2014/027.pdf
> or Section 3.3 of http://eprint.iacr.org/2014/130.pdf to see that there is
> no problem here).
>
> On the other hand, I’m not sure if this happens when p == 1 mod 4: for
> example, the Edwards version of Curve25519 has a curve constant that’s a
> fraction of small numbers, which the implementation documented in
> http://eprint.iacr.org/2011/368.pdf ends up treating as a generic (large)
> field element.
>
>
> This is because Bernstein et al specified an isomorphic curve and not an
> isogenous one.  They could have specified the 4-isogenous curve
>
> x^2 + y^2 = 1 + d x^2 y ^2 where d = (2-A)/4 = -121665.
>
> [
> At least if I haven’t made a mistake:
>   x = 4v(u^2-1) / ((u^2-1)^2+4v^2)
>   y = u (4v^2 - (u^2-1)^2) / (2v^2(u^2+1) - u(u^2-1)^2)
>
> dual:
>   u = y^2/x^2
>   v = y(x^2+y^2-2)/x^3
> ]
>
> or the curve
>
> -x^2 + y^2 = 1 - d x^2 y^2
>
> which is isomorphic to that one under the map x -> ix.  Both of these curves
> are complete, because GF(2^255-16)(+-121665) is nonsquare.
>
> All other things being equal, I therefore think that switching between
> coordinates (if desired) slightly favors p == 3 mod 4.
>
>
> There are advantages to p == 3 mod 4, but I don’t think this is one of them.
> Note that p == 1 mod 4 supports curves which are both twisted [a=-1] and
> complete, but 3 mod 4 does not.  So in terms of coordinate systems, that’s
> the simplest, fastest option.  You can recover most of that with the isogeny
> trick, but not all of it.
>
> Furthermore, in this case, if the curve is defined as an a=1 (complete)
> Edwards curve, implementers then have the option of staying in Edwards form
> at the expense of 1 field multiplication per addition operation (like the
> implementation of Curve41417 inhttp://eprint.iacr.org/2014/526.pdf does) or
> of using Mike’s isogeny trick for enhanced
> performance:http://eprint.iacr.org/2014/027.pdf).
>
>
> I think Watson’s points were:
> 1) If the NUMS curves are chosen, they should be changed to the isogenous
> untwisted ones.
> 2) Whatever curves are chosen, they should compress points.

That's exactly right. I want the simplest, fastest, possible solution.
Simplicity matters more because most implementations need to favor
correctness over speed. But speed also matters, to avoid temptation.
So if twisted coordinates are complete, that works great. If not, we
should use untwisted coordinates, so that simple implementations are
secure implementations.

Sadly 2^521-1 is likely to be the prime we need to use for the big
workfactor because of performance/lack of nice primes in that range,
and is 3 (mod 4), so likely untwisted Edwards coordinates will have to
be used for signatures if we want to minimize the number of coordinate
systems used. (The penalty for a performant multiplication with
Edwards coordinates of either twistedness in code size is fairly
large, and the isogeny trick requires implementing arithmetic in the
group order. On the other hand, for signatures this is likely already
needed. In comparison, Montgomery form is very compact in code, even
when performant)

Point compression incurs a slight penalty. However, it entirely
eliminates a class of attacks caused by not checking the order,
provided the square root routine properly checks that the square root
exists. (What happens when a non-quadratic residue is square rooted by
exponentiation or the p=5 (mod 8) method may be exploitable. Yes,
after dividing by i it's a point on the twist, but I don't think
that's what comes out of the formula. And then the addition formulas
aren't right for the twist, so I don't know how to exploit the result
or show it isn't exploitable. However, it's a barrier to exploitation
in any case)

The big advantage of Montgomery coordinates is that they eliminate
entirely validation, so this is a non-issue for ECDH. Sadly, we can't
do signatures with them in a reasonable way, so we're stuck with a
step that might get skipped and cause vulnerabilities when skipped.

>
> In any case, this is (as you say) about the coordinates, not the curve.
> However, changing coordinates can change the corresponding curve constant,
> but when p == 3 mod 4 small constants will remain small irrespective of the
> coordinate system.
>
>
> An isogeny is a bit more than just a change in coordinates, but I agree that
> it’s reasonable to pick a curve structure, and later discuss which isogenous
> or isomorphic curves and which coordinates should be used for which
> protocols.
>
> I don’t think everyone on this list would agree with the above statement,
> though.  A pretty big part of Benjamin Black’s argument against \w+25519 is
> the idea that they are different curves, not just different coordinates for
> the same curve, even though the curves are isomorphic and not just
> isogenous.dd
>
> This is also why I listed “Curves isogenous to NUMS” as a separate candidate
> from NUMS in the “current candidates” email.

This email, along with the "Curve, Coordinates and Computations" email
is required reading for anyone who wants to understand the issues.
Sadly, I can't find it in my inbox.

Sincerely,
Watson Ladd

>
> Cheers,
> Craig
>
>
> Peace,
> — Mike
>
>
>



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


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