[curves] Twist security for elliptic curves

[Trevor Perrin]

On Thu, Jun 18, 2015 at 2:55 PM, Alexandre Anzala-Yamajako
<anzalaya at gmail.com> wrote:
> Has anobody had time to read this paper already :
> http://eprint.iacr.org/2015/577


Mostly agree with Watson, but I think there's an interesting question here.

The paper argues "even for twist secure curves a point validation has
to be performed".  They give a case where point validation adds
security, even for twist-secure curves:
 (1) power or EM sidechannel can observe bits of the scalar during
scalar multiplication
 (2) implementation performs scalar multiplication (aka DH) with fixed
private key
 (3) implementation uses a scalar blinding countermeasure with
inadequate blinding factor
 (4) attacker can observe the input and output points

That's a rare set of conditions (particularly last 2).

This doesn't strongly support the claim "point validation has to be
performed".  A better conclusion might be "use adequate blinding
factors".

(I think they're suggesting 128 bit blinding factors for a
special-prime curve like Curve25519, vs 64 bits for a "random-prime"
curve like Brainpool-256.  So that's a 1.2x slowdown (~384 vs ~320
bits scalar) due to scalar-blinding, though the special-prime curve
will also have a 2x speedup in optimized implementations.)


Still, is there an argument that point-validation is a good
"robustness principle", even with twist-secure curves?

And if so - if implementations should perform point validation
regardless of twist-security - does that have any effect on curve
selection?  I think the answer is no - twist-secure curves are more
robust and should be preferred.  But I'd be curious if anyone thinks
otherwise.


Trevor