[Cfrg] Complexity of the Microsoft curve proposal

[Watson Ladd <[e-mail]>]

Dear all,
Sadly DJBs linked slides aren't explicitly about the microsoft curves.
So I'd like to explain why the NUMS curves, with the prefered
coordinate system, are more complex than the curve and coordinate
choices DJB and Mike Hamburg have made in their prefered curves.

If we send twisted Edward points with a=-1, d nonsquare, and p
congruent to 3 mod 4, the addition law is incomplete as a is not a
square. This forces implementers to add checks required for security,
but not interoperability, which will be neglected. Sending points in
coordinates where a complete addition law exists, even if an
incomplete one is used internally, removes this temptation. I have
exploited this issue against Bouncycastle (now fixed) and several
other TLS implementations. Sending regular Edwards points solves this
issue: the addition law is complete so long as d is a nonsquare.

If we send twisted Edwards points, we also have to check that x and y
lie on the curve. Failure to make this check is exploitable as well.

By contrast, sending compressed points or Montgomery coordinates
removes this difficulty. The Montgomery ladder is also easy to make
timing-attack resistant with high performance, and is very simple to
implement.

So long as p is not congruent to plus or minus 1 mod 8, taking square
roots mod p is easy.

Again, this is an argument about coordinates, not the curve. The curve
is virtually irrelevant.

Sincerely,
Watson Ladd