[curves] Point validation (was: Twist security for elliptic curves)

[Trevor Perrin]

On Fri, Jun 19, 2015 at 2:20 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>
>> On Jun 19, 2015, at 2:15 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> Still, is there an argument that point-validation is a good
>> "robustness principle", even with twist-secure curves?
>>
[...]
>
>
> I prefer to validate all points if there isn’t a big perf/complexity hit, because that way the protocol designer doesn’t have to take twist points into account.

Or small-order points.


>  But I still think curves should be selected as twist-secure if there isn’t a good reason to do otherwise.  Some people will prefer the 20-line Curve25519-style Montgomery ladder, and there’s very little cost to giving those folks security against non-DPA-equipped adversaries.

I'm not convinced point-validation is that useful with "SafeCurves" [1].

But as a thought experiment, suppose most implementations will do it
(i.e. check both point-on-curve and point-in-main-subgroup).  Would
that affect which curves people prefer?

I think it would reduce the efficiency and simplicity win for
single-coordinate ladders, since checking point-on-curve has similar
costs to decompression?  Also checking small-order points for
cofactor>1 is not that time-consuming but is annoying [2].  So the
efficiency and simplicity advantage of newer curve forms vs
Weierstrass would be reduced, but I think would still be there?

I also wonder how much this would argue for 3 mod 4 primes (easier
square roots?  "Decaf"?) but I'm not sure.


Trevor


[1] http://safecurves.cr.yp.to/twist.html
[2] http://cr.yp.to/ecdh.html#validate