[curves] curve25519-dalek: a pure Rust ECC library

[Henry de Valence]

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