[prev in list] [next in list] [prev in thread] [next in thread] 

List:       moderncrypto-curves
Subject:    [curves] Same Value Analysis on Edwards Curves
From:       mike () shiftleft ! org (Michael Hamburg)
Date:       2015-07-27 19:29:17
Message-ID: 6CE042E9-2358-4339-8BEC-6281EEF09DD1 () shiftleft ! org
[Download RAW message or body]

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


[prev in list] [next in list] [prev in thread] [next in thread]