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.
- 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].
Issue #2: Rust has explicitly taken all memory management away from me. There's nothing I can do about that.
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.
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.