Discussion:
curve25519-dalek: a pure Rust ECC library
(too old to reply)
Henry de Valence
2016-12-10 06:33:41 UTC
Permalink
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
Dirkjan Ochtman
2016-12-11 19:14:44 UTC
Permalink
On Sat, Dec 10, 2016 at 7:33 AM, Henry de Valence
Post by Henry de Valence
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.
Did you look at Brian Smith's *ring*, and if so, why did you decide
not to go with it?

Cheers,

Dirkjan
Tony Arcieri
2016-12-11 20:23:27 UTC
Permalink
Post by Dirkjan Ochtman
Did you look at Brian Smith's *ring*, and if so, why did you decide
not to go with it?
As a Rust crypto consumer, I view these libraries differently.

*ring* is a fantastic library and one I've been using in my Rust crypto
projects for awhile. However, it's a "safe" library in the same sort of
lineage as NaCl and libsodium: it tries to expose a high-level,
minimalistic API. Types like curve points/group elements are not directly
exposed for safety reasons and remain part of the private API.

curve25519-dalek seems much better suited for people implementing more
exotic constructions using types *ring* does not (for good reasons) expose
as part of its public API. These would include things like SPAKE2,
hierarchical key derivation, semiprivate keys, blinded signatures, ring
signatures, threshold multisignatures.

Building any of the things I listed above above on top of *ring* would
require forking *ring* and building atop its private API. Maybe some of
those things should eventually wind up in *ring*, but I appreciate Brian
being conservative about what he includes.
--
Tony Arcieri
Michael Scott
2016-12-22 18:45:34 UTC
Permalink
There is an another pure Rust ECC (and Pairings) library available here

https://github.com/MIRACL/amcl

Not sure how the speed compares. But things will definitely improves when
the i128 type (128-bit integers) is supported in version 1.17 (due out in
March 2017 I believe)


Mike Scott
Post by Tony Arcieri
Post by Dirkjan Ochtman
Did you look at Brian Smith's *ring*, and if so, why did you decide
not to go with it?
As a Rust crypto consumer, I view these libraries differently.
*ring* is a fantastic library and one I've been using in my Rust crypto
projects for awhile. However, it's a "safe" library in the same sort of
lineage as NaCl and libsodium: it tries to expose a high-level,
minimalistic API. Types like curve points/group elements are not directly
exposed for safety reasons and remain part of the private API.
curve25519-dalek seems much better suited for people implementing more
exotic constructions using types *ring* does not (for good reasons) expose
as part of its public API. These would include things like SPAKE2,
hierarchical key derivation, semiprivate keys, blinded signatures, ring
signatures, threshold multisignatures.
Building any of the things I listed above above on top of *ring* would
require forking *ring* and building atop its private API. Maybe some of
those things should eventually wind up in *ring*, but I appreciate Brian
being conservative about what he includes.
--
Tony Arcieri
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Loading...