[curves] Same Value Analysis on Edwards Curves

[Michael Hamburg]

Wait, did I miss something?  Have Edwards curves been broken?

The linked paper did not break Edwards curves, and didn’t use any sort of “shift properties” as far as I know.  (What does that even mean?)  It’s not specific to Edwards either: it’s a port of a certain side-channel attack which was already known for other curve shapes.

It’s also not clear whether Edwards curves are more or less dangerous with respect to this particular attack.  The fastest formulas for Edwards happen to use fewer powers of Z than a typical Jacobian implementation, which might give more attack opportunities for SVA.  But they are also shorter, which makes them intrinsically more resistant to SVA and ZVP.  Also, confining points to subgroups might mitigate the attacks and this isn’t possible in a prime-order curve.  Finally, RPA/ZVP probably reduces Edwards’ curves’ advantage from unified formulas, but they can’t possibly be worse than Weierstrass in this regard.


As for special properties, this is conceivable.  But as far as I’m aware, nobody has published any reason to believe that such an attack exists.  Also, some special properties ought not to help too much.  For example, every curve is an Edwards curve over some extension field, so just being an Edwards curve ought not to lead to a subexponential attack.  I’ve heard speculation that Solinas primes might be somehow weak, but I’ve never seen an outline of how an attack on them might work.

The Brainpool curves are relatively unoptimized, particularly in their original form without the isogeny to a=-3.  Of course, you could always add more random coefficients to make everything even less optimized.

Cheers,
— Mike

> On Jul 27, 2015, at 10:19 AM, Ray Dillinger <bear at sonic.net> wrote:
> 
> 
> I have no strong mathematical reason to believe this, but I have
> a nasty suspicion that the same properties that make ECC curves
> fast to compute are likely to be the properties that enable future
> attacks that no one has thought of yet.  The recent break on
> Edwards Curves seems tied to their shift properties.
> 
> Are there any canonical examples of completely un-optimized curves
> that mean you have to use actual bignumber math to do every step of?
> 
> 				Bear
> 
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves