Re: [Cfrg] Side Channel Attacks Against Curve25519

[Ilari Liusvaara <[e-mail]>]

On Sun, Sep 10, 2017 at 08:12:28AM +0100, Thomas Garcia wrote:

> something similar be done to encourage correct bignum arithmetic? Is it
> possible to choose the parameters, such as the prime, such that the
> simplest implementation will be less susceptible to side channel attacks?
> What I imagine is a prime which would normally have long computation times,
> but has a trick that enables simpler addition which is coincidentally
> constant time.

I do not know how much modern bigint libraries optimize based on the
prime. However, the very idea of fast primes for ECC is that those
primes have various tricks to perform fast modular multiplication
(since multiplication is the dominant cost). And those kinds of primes
are pretty rare, especially the more efficient (relative to size) ones.


Both X25519 and X448 have useful reductions in base field
((2^51)^5 -> 19 and ((2^56)^4)^2 -> ((2^56)^4)^1 + ((2^56)^4)^0,
respectively).


Of course, one could use reductions like that to optimize the modulo
operation with bigint library, but dedicated constant-time routine
would still likely be faster with little optimization. Especially as
one can partially fold those reductions into multiplication itself.


Then there are other forms of side-channel leakage beside base field
arithmetic. E.g. the conditional swaps in Montgomery ladder. However,
most other forms of elliptic curves have actual conditional adds or
even worse, edge cases in addition.


-Ilari