This claims to have constant time operations, but the addition law is very clearly not constant time: https://github.com/Bren2010/ecc/blob/master/src/curves.rs#L9... Likewise, the field operations are not constant time. Simply doing both the 1 and 0 path and throwing the other side out is not generally adequate to achieve constant time behaviour when the underlying operations are variable time (and also see, for example, the flush/reload attacks in the literature).
Also the field operations appear to be variable time. (So, it looks like the inversions to convert back to affine would leak shared secret data for ECDH, or information about the nonce in ECDSA.) It looks like the reduction in kinv alone would likely leak log2(k^-1) pretty directly in timing, so if you could capture some large number of signatures with a single key you could probably recover it, potentially even remotely. (Not trying to be harsh here, OpenSSL is just as bad for their generic code... but if someone is advertised as constant time, it ought to meet the strongest definition of it since the caller is not going to be a cryptographer and he's going to treat it as a black box and inevitably use it in the most exploitable way possible. :) )
General question about rust: Is there any way to reliably write constant time code in it? Or are you always at the mercy of the compiler undermining you? E.g. happily unrolling loops, optimizing out dummy operations, and turning branchless comparisons into branchy ones. (I wouldn't have expected that would be, since there isn't really in C; unless you're able to audit the compiler output ... and rust is even higher level).
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.
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.
Rust generates LLVM code, which means that the optimizer is going to do pretty much the same stuff you'd expect from clang (except that with Rust, LLVM doesn't need to worry as much about aliasing, so it can be more aggressive). For inline assembly, see:
http://doc.rust-lang.org/guide-unsafe.html#inline-assembly
Rust also has a very convenient FFI, so if you have a chunk of assembly which uses the platform ABI, you can wrap it and call it easily.
Here's a syntax extension that tries to use black magic to turn a subset of Rust code into corresponding asm! macros:
https://github.com/klutzy/nadeko/blob/tmp/tests/rot13.rs
Note it presently has no support for loops whatsoever.
Could you comment on why? Is it perhaps necessary to save/restore ECX [edit: I meant RCX for 64bit] between procedure/function calls/rets?
http://www.meetup.com/Rust-Bay-Area/events/210632582/
We are currently full, but we are live streaming it on:
https://air.mozilla.org/bay-area-rust-meetup-december-2014/
We also have about 10-15 people unrsvp the day-of, so there is a chance spots for free up between now and then.
I don't even like having to implement NIST's speedup for A = -3, and it's fairly trivial.
- 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.