curve25519: ed25519, x25519 and ristretto255

[daxpedda]

While working on voprf and opaque-ke I noticed that a lot of implementations and traits could be removed if curve25519-dalek would support necessary traits from elliptic-curves, like Curve and ProjectiveArithmetic. Using some of these already uncovered serious bugs and other issues.

It might be possible to implement some of it through PR's or wrappers for ed25519 and x25519, but it will be much harder for ristretto255. Among other problems in the library, the dependency maintenance story isn't ideal, as seen by the many PR's to update rand.

Specifically, voprf is interested in support for ristretto255 arithmetic, including hash2curve. For opaque-ke x25519 and ristretto255 support for DH is a requirement.

I am myself no cryptographer and sadly can only contribute, but not actually implement something like it.

[tarcieri]

It's something we can potentially discuss with the upstream dalek maintainers. This hasn't been the first request for this sort of thing.

[isislovecruft]

Hi @tarcieri and @daxpedda! Switching to implementing the the elliptic curves traits is not something I've yet had time to look into, so I can't speak to the feasibility of it at the moment, but in principle is something we would be happy to support.

[daxpedda]

This is amazing to hear!

I've already done some preliminary work here dalek-cryptography/curve25519-dalek#375 and am willing to go all the way, as much as I'm capable of at least.

Another issue that has to be discussed, for this to work long-term, is that if these traits are to be implemented in curve25519-dalek, and not in a wrapper crate like ed25519, we need a good dependency update policy. This issue has come up with rand for example, currently all downstream users have to pull in two different versions. In the case of implementing traits, it will simply be impossible to be useful unless the dependencies are up-to-date.

I am willing to help in any way @isislovecruft, sadly IANA cryptographer, so my capabilities are limited, but if there is anything I can do to minimize your maintenance burden, please feel free to hit me up :).

[kayabaNerve]

I recently published dalek-ff-group, wrapping the Ed25519 prime subgroup and Ristretto into the ff/group APIs. While a few functions remain unimplemented, blocking dalek's PR yet not a new crate, it's usable now and will do its best to maintain parity with modern dependency versions.

I'm currently working on the PrimeFieldBits API, and also have an eye on CofactorCurve.

[daxpedda]

Wow! Amazing stuff!

In the meantime I have just stopped using curve25519-dalek completely 😆. Especially with the recent introduction of P-384 arithmetic.

So the next step is to either close my PR or update it. Updating it at least is realistic now as I can learn from the work you have done @kayabaNerve! In any case I'm glad to have the work split up like this, as it decreases the maintenance burden on isislovecruft.

Last problem that would have to be addressed is to actually update dependencies of curve25519-dalek.

[kayabaNerve]

It's not a new crate, just a wrapper around dalek, and I think we have about the same amount of unimplemented code :p Though we may have differences in what is unimplemented. I will note I have yet to bother with sqrt, so that would be mutual.

I also took the easy route for some of it, which may make it technically improper according to expectations, and don't mean to disparage or end the work that was happening with curve25519-dalek. Solely to allow people to use dalek without further abstractions in modular code today, as I myself frequently need.

In the past, I wrote a CryptEngine type, with a FfGroupEngine, Ed25519Engine, and RistrettoEngine behind it (as dalek doesn't even offer a DalekPoint trait enabling DalekEngine<P>, unfortunately). I've seen other parties not use ff/group, yet manually redefine all the arithmetic relationships needed, and then manually fill out the rest per-curve. Now, I'm just trying to use ff/group as intended, and I didn't feel like waiting through the dalek bureaucracy, even if I respect it and hope I can eventually deprecate my work.

EDIT: I'd also like to clarify this does use modern dependencies, and I'll continue to update them as feasible (ff/group and this repo updating). I'd also like to clarify the "easy route" was over some CtOption and similar handling. I don't believe anything breaks specs, and will take any PRs increasing correctness.

[jplatte]

Being able to use actively maintained, trusted forks of {curve,ed,x}25519-dalek would be a big quality-of-life improvement for vodozemac, used primarily for end-to-end encryption in the matrix-rust-sdk.

I think the Signal folk would also be happy about this, they seem to be using at least one of these crates: https://github.com/signalapp/libsignal/blob/2c32fb802d1f8d6739ade32901a3f5d84e7ec19b/rust/attest/Cargo.toml#L26.

[decathorpe]

Speaking as the primary maintainer of Rust crates on Fedora Linux, I would be interested in actually maintained RustCrypto-backed forks of these crates, as well.

We are trying to package some of the *-dalek crates, but doing that currently forces us to make old versions of some crates available (or keep them available even though they're outdated and not used by other crates any longer), and this blowing up of the dependency tree results in a lot of unnecessary work and resource use on Fedora server infrastructure.

[kayabaNerve]

As a slight update, dalek-ff-group, while not containing any optimizations, no longer has unimplemented code and is fully correct under the ff/group API. While I personally advocate for RustCrypto taking over dalek, and natively offering the ff/group API, a modern dependency view (with a standardized API) can be offered by it. Not that it helps too much with the dependency tree :/

Also happy to transfer dalek-ff-group/its API bindings to RustCrypto, though I'd see that as pointless compared to forking dalek and...

EDIT: I see this has effectively happened, just still under the dalek-cryptography org.

[tarcieri]

Yeah, there's a PR to add it here: dalek-cryptography/curve25519-dalek#473

[ycscaly]

Yeah, there's a PR to add it here: dalek-cryptography/curve25519-dalek#473

Can we count on it being merged in the future?
And if it will, can we count on either an actively-maintained forks here or the original crates supporting the elliptic-curve traits?

I am writing code that needs to generically work over group-arithemetics for both secp256k1 and curve25519, and want to know whether to use ff and group as my underlying traits, or the elliptic-curve ones (which I prefer)

[daxpedda]

Now that dalek-cryptography/curve25519-dalek#562 was merged, I believe this can be closed. I think any further compatibility with the RustCrypto ecosystem is covered by RustCrypto/traits#1177.

[tarcieri]

Closing this