[bren2013]

About ElGamal: Agreed. I only planned to implement it for my own satisfaction, more than for anything else.

The addition law only leaks general cases--doubling, negatives, one argument is zero. Is that not generally considered okay? Intuitively, it doesn't seem like terribly valuable information--in the case of the Montgomery ladder, the attacker already knows we do one doubling and one addition per bit.

Earlier, I was using Euler's theorem for inversions, which should have been more constant-time than Euclid's algorithm. The only problem is, it took slightly over a minute to do one scalar multiplication. Could you describe an attack that would come from knowing information about the z-coordinate? Is there a good way to do constant-time inversion?

Edit: I just added a second benchmark testing scalar multiplication for a random value vs one with lots of zeros, and they produce different distributions with or without the #[const_time] (assuming I'm using it right). Thank you for bringing this up! I'll look into what needs tweaking.

[bren2013]

I missed my edit window...

I actually take the above back. Scalar multiplication on a point IS constant-time (the two distributions are indistinguishable).

Field exponentiation isn't constant-time and I will work on that.

[pbsd]

The way your scalar multiplication is performed leaves you open to two attacks:

- Scalar multiplication is variable-time, with the variation being correlated with the position of the most significant bit of the exponent (see https://github.com/Bren2010/ecc/blob/bd75261b6fe7839ddc751d6...). An attack like [1] on ECDSA seems plausible.

- The Montgomery ladder uses different code paths depending on whether the exponent bit is 0 or 1; this makes FLUSH+RELOAD attacks possible, as in [2].

[1] https://eprint.iacr.org/2011/232

[2] https://eprint.iacr.org/2014/140

[bren2013]

Issue #1: Yes, it's supposed to be like that. The point is that any n-bit scalar takes the same amount of time as any other n-bit scalar.

Issue #2: Rust has explicitly taken all memory management away from me. There's nothing I can do about that.

[comex]

Regardless of what seems to happen in practice, none of the BigUint operations (including comparison) are guaranteed to work in constant time. Since the implementation uses a Vec whose size depends on the size of the integer, this could easily have significant timing differences in other situations.

[bren2013]

I've tested a scalar of about 50% 1s against a scalar with almost no 1s, measuring at the nanosecond resolution, with 100 samples each.

The p-value of the 2-sample T-test was greater than 1%--there's no evidence that one takes less time than the other. That can be replicated by playing with the benchmarks yourself. If you have any evidence to the contrary, I'd be happy to look at it.