[curves] Twist security for elliptic curves

[Johannes Merkle]

Trevor Perrin schrieb am 19.06.2015 um 23:15:
> 
> 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

Well, that depends on what you call "inadequate". If points are validated, a blinding factor of n/2 bit is sufficient
even for Pseudo-Mersenne primes, but this twist attack requires n bit blinding. So, the attack indeed requires longer
blindings that necessary otherwise.

>  (4) attacker can observe the input and output points
> 
> That's a rare set of conditions (particularly last 2).
> 

(2) and (4) might not be satisfied in many important applications, but we should select curves that provide security
independent of specific properties of the application.

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

I am not sure what you are comparing here. Your statement "128 bit blinding factors for a special-prime curve like
Curve25519, vs 64 bits for a "random-prime" holds only in the absence of the twist attack under discussion. If an
implementation satisfies conditions (1),(2) and (4) above and does not validate points, it needs to use 252 bit blinding
factors, resulting in a slowdown of 59% for random primes (504 vs 316 bit scalars) and a slowdown of approx. 20% for
special primes (379 vs 316 bit scalars). For higher security levels (e.g. for Ed448-Goldilocks) the impact is larger.

My conclusion of that paper (and I have not contributed to it) would be that twist security does not provide any
performance benefit for implementations that need to thwart this attack by longer blinding factors. Thus, if someone
wants to select curves specifically for hostile environment scenarios (smart cards etc), it is questionable if twist
security should be a requirement, as it might be misleading to implementors.

-- 
Johannes