Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Elliptic curve arithmetic and cryptography library in Rust

github.com

Post reply on HN
Print view View original

11–15 of 15 posts

Re: Elliptic curve arithmetic and cryptography library in Rust

#11

Post by bren2013 »

pbsd wrote: post #10
bren2013 wrote: post #7

Earlier quoted context omitted.

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…

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.

Re: Elliptic curve arithmetic and cryptography library in Rust

#12

Post by bren2013 »

comex wrote: post #8
bren2013 wrote: post #7

Earlier quoted context omitted.

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.

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.

Re: Elliptic curve arithmetic and cryptography library in Rust

#13

Post by bren2013 »

indeyets wrote: post #9

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.

Re: Elliptic curve arithmetic and cryptography library in Rust

#14

Post by e12e »

bascule wrote: post #3
nullc wrote: post #2

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 fiel…

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?

Re: Elliptic curve arithmetic and cryptography library in Rust

#15

Post by bascule »

e12e wrote: post #14
bascule wrote: post #3

Earlier quoted context omitted.

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 call s/ ret s?

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