Compatibility with RustCypto/traits/elliptic-curve trait Curve on API side.

[SergeStrashko]

like it was done for P-521 ?

[tarcieri]

What do you want this for specifically? Are you looking for compatibility with e.g. hash2curve?

Note that #473 adds trait impls that elliptic-curve re-exports from the ff and group crates.

[SergeStrashko]

ecdh

[tarcieri]

The Mul trait (in combination with the Group trait) should work fine for that purpose, once #473 lands

[ycscaly]

I also would vouch for this feature. I believe a standard trait that multiple elliptic curves implement is needed. ECDH is one usecase, implementing a geneeic ECIES is another, but I'm thinking more broadly -- for generic signature code, and even more specifically TSS (MPC) code running on generic curves.

ZenGo's curv is an alternative for that, however there are no compatibility between curv's Curve and Rust Crypto's Curve.

[tarcieri]

I believe a standard trait that multiple elliptic curves implement is needed.

The difficult part is different use cases require different traits.

implementing a geneeic ECIES is another

We have the kem crate for that, which is not specific to elliptic curves:

https://github.com/RustCrypto/traits/tree/master/kem

for generic signature code

We have the signature crate for that:

https://github.com/RustCrypto/traits/tree/master/signature

[ycscaly]

Thanks for the reply.

1. I know of KEM but a) I saw you mentioned that ECDH is not implemented for it and that's needed for ECIES and b) there are no traits for asymmetric encryption, and no generic implementation of ECIES (and although ECIES pretty much reduced to ECDH->KDF->AES we still would rather have it exported as a single functionality both for readability and because users can still mess this up. Cryptography is hard not to mess up, even the easy parts.)
2. Although Signature is generic for signature types it is less trivial than one would expect for EC: e.g. a PK setting where you have a public key which is a point on the curve and the secret key is a scalar. I understand the reasoning but it does not take away from use-cases that wish to keep it all in software but still be generic over different groups. And that's the least of my pains when viewed distinctly but when you think about it in the perspective of KEM/ECDH this starts to lose it sense: you have created the Verifier/Signer traits so that software amd hardware signers can be used interchangeably (which makes a lot of sense) but in order to do ECDH and therefore ECIES you need to multiply by the secret scalar - and there is no interface (afaik) that allows that in a similar fashion, forcing hardware signers to use software asymmetric decryption PKIs which in some settings completely negate the original point of having the signing key kept in hardware anyways.
3. I would love to discuss the reasoning behind the 'different use-cases require different traits'. Foe what I have in my mind, curve arithmetics enable it all. In any case, even if we could agree on points 1 and 2, as someone who's going to write a lot of multi party computation code in the near future, I would be stuck with two incompatibles stacks of elliptic curves (curv and elliptic-curves) which each have different things the other doesn't and I need both. And I think this doesn't make sense. A dalek-elliptic-curves-curv interchangeablity would solve a lot of issues for me, and we can discuss contributing for it.

[tarcieri]

ECDH is not implemented
in order to do ECDH and therefore ECIES you need to multiply by the secret scalar - and there is no interface (afaik) that allows that in a similar fashion,

ECDH is just scalar multiplication, and as I mentioned earlier that's covered by combining the Group trait with Mul.

That's all the elliptic-curve crate is doing under the hood.

there are no traits for asymmetric encryption

The traits are for KEMs which can be used for hybrid encryption. If you don't consider hybrid encryption under the purview of asymmetric encryption, aside from El Gamal (which is rarely used), there aren't really asymmetric cryptosystems which work across algorithms. That's why the NIST PQcrypto competition focused on KEMs.

no generic implementation of ECIES

ECIES is just one example of hybrid encryption. HPKE is an effort to standardize hybrid encryption, and the Rust HPKE implementation is built on the kem crate

Although Signature is generic for signature types it is less trivial than one would expect for EC: e.g. a PK setting where you have a public key which is a point on the curve and the secret key is a scalar. I understand the reasoning but it does not take away from use-cases that wish to keep it all in software but still be generic over different groups.

Different elliptic curves have wildly different properties and not all signature systems work for all elliptic curves.

ECDSA requires prime order elliptic curves.

EdDSA requires Edwards curves.

The ecdsa crate provides a generic implementation of ECDSA, but you can't just plug curve25519::{Scalar, EdwardsPoint} into that even if they did impl the ff/group traits, because there's a PrimeCurve bound.

Getting things to work in a generic manner at all requires extremely careful design to prevent incompatibilities between the underlying elliptic curve type and the signature algorithm.

there is no interface (afaik) that allows that in a similar fashion, forcing hardware signers to use software asymmetric decryption PKIs

RSA-KEM and (EC)DH-based KEMs can both be used with the kem API, even when backed with hardware.

KEMs are the modern API for asymmetric encryption.

I would love to discuss the reasoning behind the 'different use-cases require different traits'

Cryptography has a litany of ways in which it can be generically composed, but that all depends on the specific properties of algorithms.

As you can see at https://github.com/rustcrypto/traits we have a large number of traits for the different subcomponents of cryptosystems, and they're designed to cover much more than just elliptic curves.

I would be stuck with two incompatibles stacks of elliptic curves (curv and elliptic-curves) which each have different things the other doesn't and I need both.

If #473 were to land, what are you missing?

[ycscaly]

ECDH is not implemented
in order to do ECDH and therefore ECIES you need to multiply by the secret scalar - and there is no interface (afaik) that allows that in a similar fashion,

ECDH is just scalar multiplication, and as I mentioned earlier that's covered by combining the Group trait with Mul.

That's all the elliptic-curve crate is doing under the hood.

there are no traits for asymmetric encryption

The traits are for KEMs which can be used for hybrid encryption. If you don't consider hybrid encryption under the purview of asymmetric encryption, aside from El Gamal (which is rarely used), there aren't really asymmetric cryptosystems which work across algorithms. That's why the NIST PQcrypto competition focused on KEMs.

no generic implementation of ECIES

ECIES is just one example of hybrid encryption. HPKE is an effort to standardize hybrid encryption, and the Rust HPKE implementation is built on the kem crate

Although Signature is generic for signature types it is less trivial than one would expect for EC: e.g. a PK setting where you have a public key which is a point on the curve and the secret key is a scalar. I understand the reasoning but it does not take away from use-cases that wish to keep it all in software but still be generic over different groups.

Different elliptic curves have wildly different properties and not all signature systems work for all elliptic curves.

ECDSA requires prime order elliptic curves.

EdDSA requires Edwards curves.

The ecdsa crate provides a generic implementation of ECDSA, but you can't just plug curve25519::{Scalar, EdwardsPoint} into that even if they did impl the ff/group traits, because there's a PrimeCurve bound.

Getting things to work in a generic manner at all requires extremely careful design to prevent incompatibilities between the underlying elliptic curve type and the signature algorithm.

there is no interface (afaik) that allows that in a similar fashion, forcing hardware signers to use software asymmetric decryption PKIs

RSA-KEM and (EC)DH-based KEMs can both be used with the kem API, even when backed with hardware.

KEMs are the modern API for asymmetric encryption.

I would love to discuss the reasoning behind the 'different use-cases require different traits'

Cryptography has a litany of ways in which it can be generically composed, but that all depends on the specific properties of algorithms.

As you can see at https://github.com/rustcrypto/traits we have a large number of traits for the different subcomponents of cryptosystems, and they're designed to cover much more than just elliptic curves.

I would be stuck with two incompatibles stacks of elliptic curves (curv and elliptic-curves) which each have different things the other doesn't and I need both.

If #473 were to land, what are you missing?

Thanks for the detailed response, it was very helpful and got my along pretty far, but I'm stuck again now.

Here are my thoughts;

1. whilst HPKE definitely seems like the correct choice for me, rust_hpke, which you mentioned, does not work with the RustCrypto Kem, Aead (there's no Kdf trait?) traits but its own traits. Ideally, RustCrypto would have its own HPKE implementation that works with its traits, to complete the crypto toolbox. I personally prefer working with a single ecosystem over a lot of different ones.

But besides not working with RustCrypto traits, it also lacks some features that currently make it impossible for me to implement my logic (e.g. the Kem::PublicKey type does implement PartialEq, which makes it impossible for me to find a public key in a list of public keys. This is one example but I've already opened three issues which haven't been tended to yet).
2. Verifier and Signer traits do not reflect public key (at least over elliptic curves) cryptography, or at least elliptic curve cryptography, the way I'd imagine them to. And it's very limiting.
2.1. I need to extract the public key from the verifier (I am writing an MPC protocol that needs to generate a party ID from the public key of the party -- but there's no public key), and that's impossible with the current design.
2.2. This also means we can't compare between verification keys (again the PartialEq problem)
2.3. I now need to generalize my code over Sig, Verifier and Signer in addition to the curve C. The way I would imagine implementing these traits is how RustCrypto's ecdsa crate works: to be generic over the curve C. But not limited to ECDSA, but a generic PublicKey and PrivateKey which can then later be used to either sign with Schnorr or ECDSA in a generic manner (again: this is where the fact curve25519-dalek does not implement the elliptic-curve trait is problematic) and also there's only a generic ECDSA implementation but not a generic Schnorr implementation for some reason?

(I understand that this implies software-only public, private keys but that's OK for some use-cases, as for mine.)
3. Assuming we do get to a PublicKey, PrivateKey types, I'd still be stuck with two incompatible elliptic curve traits: curv::elliptic::curves::Curve (which I need for their implementation of various building blocks for MPC protocols like zk-proofs and commitment schemes) and C: elliptic_curve:: CurveArithmetic + PrimeCurve (which I'd need for the PKI code). Not only that's two generic parameters that have the same meaning, and that taking two different parameters means the user would have the option to choose a different curve for MPC and a different one for signing, which is bad practice, but even worse it means different concrete implementations! That would mean that I'd write an MPC code that would, for example, if instantiated over the secp256k1 curve, use two different underlying implementations: curv uses bitcoin's secp256k1 crate, whereas RustCrypto has k256.
4. The same as in 3 applies to BigInt, where curv uses a trait for BigInt that doesn't support RustCrypto's BigInt implementation. That is really undesired, and would again expose me to two different implementations of the same thing, which means double the attack vector.

I understand this is a lot, but I really envision a unified ecosystem of Rust crypto's libraries and it is not the case right now. And I would love to help make it so.

[tarcieri]

Pinging @rozbb about HPKE questions

[ycscaly]

Oh, and I would have liked Kem to be derived from the same curve too and work with the same Public, PrivateKey structs.

[ycscaly]

Ideally, what is now:
`pub struct MPCParty<
E: Curve,
V: Verifier + Clone + Debug,
S: Signer + Clone,
Sig: Clone + Debug,
A: Ahead,
Kd: Kdf,
K: Kem,
H: Digest + Clone,

would be:pub struct MPCParty<
E: Curve,
A: Ahead,
H: Digest + Clone,
because I’ll be usingPublicKey, PrivateKey(actually theE::PointAndE::ScalarTypes) for V,S and aschnorr::Signaturefor Sig, and an implementationKemfor kem andKdffor kdf (actually, we can just haveHPKE<E, A, H>` directly as well)

I think that, given that the only three real building blocks are curve, ahead and digest, it would make sense everything else could be derived from it.

[ycscaly]

Opened an issue for rust-hpke working directly with RustCrypto traits rozbb/rust-hpke#37

In any case @tarcieri I think the main issue I described is not with rust-hpke but with curve25519-dalek which needs to support the PrimeCurve + CurveArithmetic traits. Following that, there's a lot of easy wins from my previously mentioned points. So I'd like to come back to this point please.

[tarcieri]

curve25519-dalek which needs to support the PrimeCurve

…but that’s a marker trait for prime order curves, which Curve25519 isn’t

[rozbb]

fwiw it's not a prime curve but we already wave this away in
#473
by restricting to the prime order subgroup.

@ycscaly thank you for the HPKE issues. I'm currently sprinting to a paper deadline but I will review them asap

[ycscaly]

curve25519-dalek which needs to support the PrimeCurve

…but that’s a marker trait for prime order curves, which Curve25519 isn’t

I checked before writing this-from Wikipedia;
"The curve used is y^{2}=x^{3}+486662x^{2}+x a Montgomery curve, over the prime field defined by the prime number 2^{255}-19 and it uses the base point x=9. This point generates a cyclic subgroup whose order is the prime ..."

What am I missing? and perhaps the fact it is not prime shouldn't effect our purpose and we can simply work with CurveArithmetic?

[ycscaly]

Thank you, that'll be appreciated. Happy to help & contribute if that's needed

[tarcieri]

This point generates a cyclic subgroup whose order is the prime...

What am I missing?

^^^ the subgroup. There are a total of 8 such subgroups, i.e. Curve25519 is cofactor-8

[tarcieri]

fwiw it's not a prime curve but we already wave this away in
#473
by restricting to the prime order subgroup.

@rozbb that's fine for making the implementation of the prime order subgroup work, however...

PrimeCurve is a marker which means it's safe to use a given curve implementation to implement protocols whose description explicitly requires a group of prime order.

When a curve has a cofactor, the security of such protocols can be broken in the presence of low order points. Making protocols secure in the presence of such points requires adding checks that e.g. a given point is a member of the prime order subgroup.

[ycscaly]

Thanks that's helpful. One of those things that are brushed over in papers and could lead to serious security issues in the implementation. What about implementing CurveArithmetic?

[tarcieri]

That's a possibility, although CurveArithmetic is really just a wrapper for the ff and group traits with a few extra bounds

[ycscaly]

I guess it is a possibility to work with ff and group instead of working with curve arithmetic in general. But it's probably better to have both options, so that users that need to assure the group is an elliptic curve, may.

[ycscaly]

Any updates here?

Still highly valuable for me

[tarcieri]

#473 needs to land first

[sushisilence]

@tarcieri Is there any plan for this currently?, I can help push this over the line. The consensus is to implement the CurveArithmetic trait?

[tarcieri]

Nobody is working on it to my knowledge. Feel free to open a PR.