Subject: [Cfrg] Side Channel Attacks Against Curve25519

From: Thomas Garcia <[email-masked]>
Date: Sun, 10 Sep 2017 08:12:28 +0100

Hello,
According to [1], the libgcrypt implementation of curve25519 is based on
bignum arithmetic which is not constant-time. A similar issue was raised in
[2], regarding the Go implementation. [1] proposed solving this by
rejecting small order inputs. But this recommendation is problematic [3].
As this issue seems to come up once in a while, I think it should be
addressed. Good crypto should encourage proper implementation, in the sense
that the simplest way of implementing it is the correct way (which isn't
vulnerable to side channel attacks). Curve25519 was developed in accordance
with that philosophy and the addition formulas are well implemented. Can
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.

Thanks,
Thomas G.

[1] - https://eprint.iacr.org/2017/806
[2] - https://moderncrypto.org/mail-archive/curves/2017/000930.html
[3] - https://twitter.com/hashbreaker/status/902415565435830273

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 10 Sep 2017 15:40:40 +0300

> but has a trick that enables simpler addition which is coincidentally

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Sep 2017 02:01:17 -0000

Thomas Garcia writes:
> According to [1], the libgcrypt implementation of curve25519 is based
> on bignum arithmetic which is not constant-time.

This isn't specific to Curve25519: libgcrypt has a huge amount of
non-constant-time code that needs to be fixed or replaced.

> Can 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?

Here's some discussion of prime choices from this perspective:

   https://cr.yp.to/talks.html#2015.06.11

Of course, bad choices at lower levels of the software stack can create
tensions between simplicity and security at higher levels. For example,
if your choice is between

   * simply calling a variable-time ECC library or
   * writing constant-time ECC software from scratch,

then the first option will be simpler for you, but will be insecure. As
a less extreme example, if your choice is between

   * simply calling a variable-time modular-arithmetic library or
   * writing constant-time modular-arithmetic software from scratch,

then the first option will again be simpler for you, but will be
insecure. The second option---done properly---produces a simpler,
smaller ECC software stack, but this is obscured by the existing
library for the first option.

---Dan