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

[Trevor Perrin]

On Sat, Jun 20, 2015 at 4:17 PM, Mike Hamburg <mike at shiftleft.org> wrote:
>
> 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.


I think Lochter et al would argue for point validation at the *start*
of the computation, since they're thinking about fault and sidechannel
attacks.

If they'd be happy just rejecting small-order points that's cheap and
fairly easy [1].  But if they want point-in-main-subgroup validation,
then for cofactor>1 curves typically a scalar-multiply by the main
subgroup's order would be needed.  Perhaps that's why they continue to
argue for Weierstrass (cofactor=1)?


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

Interesting...


Trevor

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