|
Uh, users almost never want ElGamal encryption. It has a few interesting applications, but its very easy to make insecure systems using it. Where it's used it should be packaged up into a complete protocol that handles the footgunnery. 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.