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

[Mike Hamburg]

Sent from my phone.  Please excuse brevity and typos.

> On Jun 20, 2015, at 15:42, Trevor Perrin <trevp at trevp.net> wrote:
> 
>> 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.

Yeah I usually code to reject those too. 

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

It's good enough for ecdh. For other protocols, you're probably using Edwards form anyway so you will at least need to reject twist elements. 

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

Actually, checking point on curve and point not in small subgroup is cheapish if the scalar is a multiple of the cofactor, as in x25519.  At the end you need to compute x/z. If you compute (x/sqrt (xz))^2 and bail if the invsqrt doesn't exist, it rejects small order and twist points. (The even points on the twist have xz zero or non square.). It still doesn't reject non-main-subgroup points but for simplicity it may be worth it. 

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

On a related note, I figured out a sane way to decaffeinate a cofactor-8 curve like curve25519. Working on implementing it. Of course, it's still a lot more complicated than not checking. 

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