[curves] Same Value Analysis on Edwards Curves

[Michael Hamburg]

> On Jul 26, 2015, at 7:06 PM, Samuel Neves <sneves at dei.uc.pt> wrote:
> 
> On 27-07-2015 01:48, Tony Arcieri wrote:
>> Seems targeted at sidechannels against the embedded / IoT scenario:
>> 
>> https://eprint.iacr.org/2015/731.pdf
>> 
>> Bold claim: "Our results indicate that no Edwards curve is safe from such
>> an attacks."
> 
> This is a direct application of the COSADE 2012 SVA attack to Edwards curves. This kind of attack is defeated with most
> standard countermeasures, such as scalar randomization.
> 
> The authors demonstrate that all _currently proposed_ curves have points conducive to mounting SVA attacks; as far as I
> can tell no argument was made that _all_ Edwards curves have them. Even if this is the case, it would not be a big deal.

I wonder which SVA attacks apply on the q-order or 2q-order subgroups of these curves, so that if you multiply by 4 or even by 2 first you might be safe.  For example, if I’m calculating correctly, the SVA attack on Ed448Goldilocks that they reported (y=2x in the doubling formula) applies only on an input of order 4q.  So if you double first or use an isogeny it might avoid at least this list of attacks.

I also checked if these attacks applied to the isogenous twisted curve to Ed448-Goldilocks, and it seems that they do.  But I didn’t check the q-order subgroup, only the 2q-order subgroup, because it’s a Sunday night and I’m lazy.

You might also be able to find a doubling formula for a given curve which isn’t much slower, and avoids the SVA.

— Mike