[curves] Twist security for elliptic curves

[Michael Hamburg]

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


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

— Mike