Henry de Valence

2016-12-10 06:33:41 UTC

Hi all,

Isis Lovecruft and I have published curve25519-dalek, a (draft of an)

ECC library for Rust, written entirely in Rust. The documentation can

be found at https://docs.rs/crate/curve25519-dalek, and we have imported

our code to a public repository on GitHub [1].

The code is originally based on Adam Langley's Go implementation of

Ed25519, which is in turn based on the reference `ref10` implementation.

It is still in fairly rough shape, there are features still missing, and

we have not yet thoroughly checked that we didn't introduce any errors.

However, it seems to work and have reasonable performance: unscientific

testing of `cargo bench` versus `go test -bench .` suggests that it is

on par with the original Golang implementation, or slightly better [2].

In terms of the levels in Trevor's previous post [3] to the list, we're

aiming this library at the "groups" / "elliptic curves" level --

hopefully, it will be a useful building block for ECC-based protocols.

In fact, that was the original motivation: we wanted to build a protocol

using ECC, and it seemed like the only real option below the protocol

level was OpenSSL, which is unappealing for obvious reasons.

So far, our Rust code has implementations of:

- Arithmetic mod p = 2^255 -19 (for the field);

- Arithmetic mod l = basepoint order (for scalar multiplication);

- Curve addition, subtraction, doubling;

- Point compression and decompression;

- Scalar multiplication of the basepoint (x,4/5);

- Scalar multiplication of arbitrary points;

- Double scalar multiplication in variable time.

In the coming weeks, we plan to implement:

- hashing to the curve (Elligator2);

- other serialization formats (incl. Montgomery form, as in X25519);

- careful code review of point addition formulae;

- careful code review of finite field arithmetic;

- possibly Decaf (with the goal of letting users use a prime-order

subgroup without worrying about cofactors)?

In the future, we would like to work in the following directions:

- Enforcement of constant-time guarantees: our code is already written

to be constant-time, except where otherwise noted (e.g., variable time

scalar multiplication). However, our code is subject to optimization

at the rustc and LLVM levels, and we do not enforce constant-time

guarantees using the type system, so non-ct code could still compile.

We would like to work from both ends: on the one hand, attempt to

enforce constant-time guarantees pre-optimization using Rust's type

system, as well as experiment with applying Adam Langley's ctgrind [4]

to Rust to check the compiled binary.

- There is an open RFC [5] to implement dependent types for Rust. If

and when this RFC is merged, we would like to experiment with using

dependent types for the finite field arithmetic, so that rustc's

compile-time type checking corresponds to, e.g., producing a proof

that there are no integer overflows. This would allow us to have some

formal verification fully integrated into the actual implementation,

rather than bolted on via an external tool.

Many thanks to all of the people on this list contributing helpful and

clear explanations of ECC-related topics, and to the Rust community, who

have worked hard to create a positive environment where people can

experiment with new ideas without being shot down. Both of these

communities are a welcome breath of fresh air.

Cheers,

Henry de Valence

[1]: https://github.com/isislovecruft/curve25519-dalek

[2]: Of course, if we wished to be totally precise, we could rewrite all

of our code and all of Adam's code to target a benchmarking API in

another language, and carefully compute exact cycle counts on many

machines. But we won't, because cycle counts are not the sole metric of

sound software engineering practices (such as version control, API

usability, memory safety, code readability, &c).

[3]: https://moderncrypto.org/mail-archive/curves/2016/000803.html

[4]: https://github.com/agl/ctgrind

[5]: https://github.com/rust-lang/rfcs/pull/1657

Isis Lovecruft and I have published curve25519-dalek, a (draft of an)

ECC library for Rust, written entirely in Rust. The documentation can

be found at https://docs.rs/crate/curve25519-dalek, and we have imported

our code to a public repository on GitHub [1].

The code is originally based on Adam Langley's Go implementation of

Ed25519, which is in turn based on the reference `ref10` implementation.

It is still in fairly rough shape, there are features still missing, and

we have not yet thoroughly checked that we didn't introduce any errors.

However, it seems to work and have reasonable performance: unscientific

testing of `cargo bench` versus `go test -bench .` suggests that it is

on par with the original Golang implementation, or slightly better [2].

In terms of the levels in Trevor's previous post [3] to the list, we're

aiming this library at the "groups" / "elliptic curves" level --

hopefully, it will be a useful building block for ECC-based protocols.

In fact, that was the original motivation: we wanted to build a protocol

using ECC, and it seemed like the only real option below the protocol

level was OpenSSL, which is unappealing for obvious reasons.

So far, our Rust code has implementations of:

- Arithmetic mod p = 2^255 -19 (for the field);

- Arithmetic mod l = basepoint order (for scalar multiplication);

- Curve addition, subtraction, doubling;

- Point compression and decompression;

- Scalar multiplication of the basepoint (x,4/5);

- Scalar multiplication of arbitrary points;

- Double scalar multiplication in variable time.

In the coming weeks, we plan to implement:

- hashing to the curve (Elligator2);

- other serialization formats (incl. Montgomery form, as in X25519);

- careful code review of point addition formulae;

- careful code review of finite field arithmetic;

- possibly Decaf (with the goal of letting users use a prime-order

subgroup without worrying about cofactors)?

In the future, we would like to work in the following directions:

- Enforcement of constant-time guarantees: our code is already written

to be constant-time, except where otherwise noted (e.g., variable time

scalar multiplication). However, our code is subject to optimization

at the rustc and LLVM levels, and we do not enforce constant-time

guarantees using the type system, so non-ct code could still compile.

We would like to work from both ends: on the one hand, attempt to

enforce constant-time guarantees pre-optimization using Rust's type

system, as well as experiment with applying Adam Langley's ctgrind [4]

to Rust to check the compiled binary.

- There is an open RFC [5] to implement dependent types for Rust. If

and when this RFC is merged, we would like to experiment with using

dependent types for the finite field arithmetic, so that rustc's

compile-time type checking corresponds to, e.g., producing a proof

that there are no integer overflows. This would allow us to have some

formal verification fully integrated into the actual implementation,

rather than bolted on via an external tool.

Many thanks to all of the people on this list contributing helpful and

clear explanations of ECC-related topics, and to the Rust community, who

have worked hard to create a positive environment where people can

experiment with new ideas without being shot down. Both of these

communities are a welcome breath of fresh air.

Cheers,

Henry de Valence

[1]: https://github.com/isislovecruft/curve25519-dalek

[2]: Of course, if we wished to be totally precise, we could rewrite all

of our code and all of Adam's code to target a benchmarking API in

another language, and carefully compute exact cycle counts on many

machines. But we won't, because cycle counts are not the sole metric of

sound software engineering practices (such as version control, API

usability, memory safety, code readability, &c).

[3]: https://moderncrypto.org/mail-archive/curves/2016/000803.html

[4]: https://github.com/agl/ctgrind

[5]: https://github.com/rust-lang/rfcs/pull/1657