6 ms·

Elliptic curve arithmetic and cryptography library in Rust

65 points by bren2013 12y ago

nullc 12y ago
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#L93 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).
- bascule 12y ago
  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 https://github.com/klutzy/nadeko/blob/tmp/tests/rot13.rs Note it presently has no support for loops whatsoever.
  - e12e 12y ago
    > 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?
    - bascule 12y ago
      It's because nadeko is a young project and it hasn't been implemented yet. Coming soon!
- bren2013 12y ago
  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 12y ago
    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.
    - comex 12y ago
      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 12y ago
        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.
- ekidd 12y ago
  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 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.
erickt 12y ago
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/ 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/ 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.
indeyets 12y ago
Do you plan to have implementation of DJB's curves/primitives?
- bren2013 12y ago
  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.

65 points by bren2013 12y ago

nullc 12y ago

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

bascule 12y ago
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 https://github.com/klutzy/nadeko/blob/tmp/tests/rot13.rs Note it presently has no support for loops whatsoever.
- e12e 12y ago
  > 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?
  - bascule 12y ago
    It's because nadeko is a young project and it hasn't been implemented yet. Coming soon!
bren2013 12y ago
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 12y ago
  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.
  - comex 12y ago
    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 12y ago
      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.
ekidd 12y ago
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 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.

erickt 12y ago

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

indeyets 12y ago

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

bren2013 12y ago
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.