Elliptic curve arithmetic and cryptography library in Rust | Hacker News Reader

Elliptic curve arithmetic and cryptography library in Rust

github.com

65 pointsbren201314 comments

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).

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.

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.

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

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.

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.

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.

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?

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.

Rust has an asm! macro. You can implement the constant time operations in assembly.

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.

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

It's because nadeko is a young project and it hasn't been implemented yet. Coming soon!

If anyone is interested in rust and cryptography, we have a meetup this Thursday in San Francsico focused on it:

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.

Do you plan to have implementation of DJB's curves/primitives?

Not for a while. DJB's curves have entirely too much structure and I'd prefer to get something general purpose working first.

I don't even like having to implement NIST's speedup for A = -3, and it's fairly trivial.

Reply on news.ycombinator.com