search

RustCrypto / elliptic-curves

Collection of pure Rust elliptic curve implementations: NIST P-224, P-256, P-384, P-521, secp256k1, SM2
661 stars 182 forks source link

Missing elliptic curves #114

Open tarcieri opened 4 years ago

tarcieri commented 4 years ago

This is a tracking issue for additional elliptic curves we could potentially implement.

Note that we are presently focusing on short Weierstrass curves which can be implemented using the primeorder crate. There are many other Rust projects implementing newer curve forms, such as bls12_381, curve25519-dalek and ed448-goldilocks.

tarcieri commented 3 years ago

I added an initial set of Brainpool curves (bp256 and bp384) in #281 and #280 respectively.

Unfortunately I'm not a Brainpool user, so I was unclear around usage of brainpoolP256r1/brainpoolP384r1 vs brainpoolP256t1/brainpoolP384t1. The crates I added assume the former.

Happy to hear from Brainpool users about how the curves are used in practice. If it turns out *r1 is a mistake we can potentially transition over to *t1 or support both *r1 and *t1.

tarcieri commented 3 years ago

Circling back on Brainpool, I see a couple ways forward. We should decide which one makes sense.

First, for background:

So, it seems like we should probably support both r1 and t1, for both the 256-bit and 384-bit modulus sizes. Here are a couple of ways that could be done:

Include both r1 and t1 curves in the same crate

This would result in the following crates:

Separate crates for r1 and t1 curves

This would look like:

My vote would be for bp256 and bp384 crates for now, each containing both the r1 and t1 variants respectively.

They could be placed under r1 and t1 modules, e.g. bp256::r1 and bp256::t1

As it were, I went ahead and registered bp256r1, bp256t1, bp384r1, and bp384t1 just in case.

Edit: split r1 and t1 variants of bp256 and bp384 in #286

kamulos commented 3 years ago

I know it is not one of the most widespread curves, but is there any chance, that secp224r1 is supported at some point?

tarcieri commented 3 years ago

@kamulos it might be possible to support sometime after #218 lands

pdeligia commented 3 years ago

@tarcieri, I know that you mentioned in your original post that:

Note that we are presently focusing on "legacy" short Weierstrass curves. There are many other Rust projects implementing newer curve forms, such as curve25519-dalek and bls12_381.

But is there any chance (or are planning already) to implement the curve25519 natively in RustCrypto's elliptic-curves crate?

I know that someone can use curve25519-dalek, but I am mainly looking for a solution that plays along well with the RustCrypto elliptic_curve::PublicKey (and other related) APIs and especially the "parsing SPKI" feature. This would be super awesome, as I don't think with curve25519-dalek you can do something similar (i.e. parse from PEM/DER), nor that it interops with the elliptic-curves crate, unless I am missing something?

tarcieri commented 3 years ago

I assume you're specifically interested in Ed25519 and RFC 8410 support?

There's an open PR to add PKCS#8 and SPKI support to ed25519-zebra:

https://github.com/ZcashFoundation/ed25519-zebra/pulls

I'll also note that similar functionality is available through the signatory crate:

https://docs.rs/signatory/0.23.2/signatory/ed25519/struct.SigningKey.html#method.from_pkcs8_der

We do also maintain the ed25519 crate which is used by ed25519-dalek. I could potentially add support for decoding/encoding PKCS#8 and SPKI public keys and private keys to bytes:

https://github.com/RustCrypto/signatures/tree/master/ed25519

tarcieri commented 2 years ago

I added PKCS#8 support to the ed25519 crate in https://github.com/RustCrypto/signatures/pull/381

It now provides a KeypairBytes type which can be decoded from/encoded into PKCS#8.

Note it's still unreleased though

diachedelic commented 2 years ago

Deno, a popular JavaScript runtime, uses RustCrypto's implementation of the P-256 and P-384 curves. A lack of support for the P-521 curve is the only thing holding it back from full compliance the WebCrypto standard, implemented by all major browsers. I humbly request the P-521 curve. Thank you very much!

tarcieri commented 2 years ago

Now that p384 is mostly good to go and based on what are hopefully reusable wrappers around fiat-crypto (#586), it might be possible to wrap their implementation of P-521's fields, although first I'll probably take a look at migrating the field implementations in p256 to also use fiat-crypto.

kamulos commented 2 years ago

Has the secp224r1 come any closer with the work? The #218 you mentioned last time seems to be abandoned.

tarcieri commented 2 years ago

Do you have a real use case for it?

Note that there's quite a bit of duplication between p256 and p384, and more work is needed to extract things like the addition formulas and make them generic around the underlying field elements, so we're still not in great shape to start supporting more P-curves.

If it's just p256, p384, and p521, things are a bit more manageable until more of the implementation can be provided generically.

kamulos commented 2 years ago

Sounds reasonable :+1:

I need the curve for my company's product. Having this without importing one of the few C crypto libraries supporting it would be nice to have, but obviously I am aware that this is a quite exotic curve.

tarcieri commented 2 years ago

607 added the initial boilerplate for a p521 crate.

However, implementing it properly will require some breaking changes to the elliptic-curve crate as various properties which can presently be computed/inferred, such as the size of a serialized field element, will require explicit configuration with p521.

tarcieri commented 2 years ago

631 extracts a proper generic implementation of AffinePoint and ProjectivePoint, which eliminates a lot of code duplication and will make it much easier to implement p521 as well as adding arithmetic backends to bp256 and bp384.

tarcieri commented 1 year ago

@newpavlov we got a request on Zulip for a p224 crate. Can you grant ownership to the elliptic-curves team?

newpavlov commented 1 year ago

@tarcieri Done.

tarcieri commented 1 year ago

@newpavlov thank you!

tarcieri commented 1 year ago

p224 and p521 now have base and scalar field implementations, as well as curve parameter definitions, although none of it is properly tested and all gated under the wip-arithmetic-do-not-use crate feature.

halvors commented 1 year ago

Could you please add secp192r1 to this list?

tarcieri commented 1 year ago

@halvors added, although given its small modulus size it will probably be a fairly low priority (i.e. we should finish up P-224, P-521, and the Brainpool curves first, at least)

tarcieri commented 1 year ago

@newpavlov it looks like you're an owner of the sm2 crate. Do you know its status?

newpavlov commented 1 year ago

@tarcieri I have added @RustCrypto/elliptic-curves to owners of sm2 (though I don't remember exactly how I got it).

P.S.: I think it would be better to use the Zulip private chat for such questions, since I doubt other users are interested in these matters.

halvors commented 1 year ago

I see that secp256k1 is supported, and seems to be the most complete so far, is this generalized? Would it be easy to support other k1 curves, for example secp224k1 ?

tarcieri commented 1 year ago

@halvors supporting any given curve is a lot of work, as we need to synthesize field implementations (both base and scalar) for each curve, and plug in formulas for the parts of the field implementation which can't be synthesized.

The curve arithmetic implementation is generic; the field arithmetic implementations are not.

tarcieri commented 1 year ago

As of v0.13.1 (#820), p224 has an arithmetic feature as well as support for ECDH and ECDSA

halvors commented 1 year ago

@halvors supporting any given curve is a lot of work, as we need to synthesize field implementations (both base and scalar) for each curve, and plug in formulas for the parts of the field implementation which can't be synthesized.

The curve arithmetic implementation is generic; the field arithmetic implementations are not.

I fully understand that it is a lot of work, but would it still be possible to add it to the list to eventually be added in the future when the other curves are finished?

Also I can to the best of my ability help out, I don't think I am skilled enough to write the field arithmetic implementation myself, but still I can help out with other tedious work like adding test vectors etc that maybe isn't a lot of help but hopefully still can reduce the amount of work that has to be done.

tarcieri commented 1 year ago

Okay, I can add it, although I'd prefer to implement curves people are actually using

halvors commented 1 year ago

Okay, I can add it, although I'd prefer to implement curves people are actually using

Very understandable, in my use case i have to verify signature using P-192, P-224, and k224 (but not signing) this is due to the fact that i am verifying authentication tokens issued by an external provider (somewhat dated one of that). So me personally have a use case for it, but i understand that the curve is rather exotic and not much used in general.

Has there been any progress on generalizing k256? If so could generic implementations be reused for k224? Or is something that is yet to be done?

fjarri commented 1 year ago

Has there been any progress on generalizing k256? If so could generic implementations be reused for k224? Or is something that is yet to be done?

@halvors https://github.com/RustCrypto/elliptic-curves/tree/master/primeorder seems to be it? Have you tried applying it to your curves?

tarcieri commented 1 year ago

Yeah, primeorder should work fine for it, but there are other curves I'd like to work on first which are niche but more commonly used, like the Brainpool curves

halvors commented 1 year ago

Yeah, primeorder should work fine for it, but there are other curves I'd like to work on first which are niche but more commonly used, like the Brainpool curves

For future reference the problem with primeorder is that it doesn't support n bigger than it's size. For secp224k1 this is 29 bytes long not 28 bytes as other 224 sized curves. AFAIK this requires a breaking change in the primeorder crate.

halvors commented 1 year ago

@tarcieri I think secp192r1 can be marked as done in this issue, you agree?

tarcieri commented 1 year ago

Yes, secp192r1 is "complete" in that high-level private key operations are deliberately not implemented due to the small modulus size, following NIST recommendations. Public-key operations are still available.

AFAIK this requires a breaking change in the primeorder crate.

It's deeper than that, it would be a change to the elliptic-curve crate: https://github.com/RustCrypto/traits/issues/1304

Unactived commented 1 year ago

p224 and p521 now have base and scalar field implementations, as well as curve parameter definitions, although none of it is properly tested and all gated under the wip-arithmetic-do-not-use crate feature. https://github.com/RustCrypto/elliptic-curves/issues/114#issuecomment-1427237213

Hello, does this mean basic field arithmetic is currently expected to "work" with these curves (but untested and potentially having bugs and security flaws)?

Is it expected that this snippet features unmarked multiplication overflows (which panics in debug)?

use elliptic_curve::SecretKey;
use p521::NistP521; // with feature wip-arithmetic-do-not-use

fn main() {
    let mut rng = rand::thread_rng();

    let secret_key : SecretKey<NistP521> = SecretKey::random(&mut rng);
    let public_key = secret_key.public_key();

    println!("{:?}", public_key);
}

Which apparently occurs in fiat generated code, at https://github.com/RustCrypto/elliptic-curves/blob/master/p521/src/arithmetic/field/p521_64.rs#L324

Moreover if one forgets overflows (e.g. compiles in release), the snippet still does not work as multiplication here relies on inversion, which is unimplemented at the moment. So it appears a scalar multiplication cannot be performed.

I am not too familiar with the structure of the repository and its implementation ; what is the current state of the implementation of these curves, besides the lack of tests and security confidence?

Sorry if this should be in another issue, I don't know as I don't know how much this is expected.

tarcieri commented 1 year ago

p521 is not expected to work, no. I'm not sure why you expected that from a feature called wip-arithmetic-do-not-use to indicate it's expected to work.

p224 has since been promoted to a proper arithmetic feature after tests were added, but p521 has not and has known issues.

It uses a different fiat-crypto code generator specific to Solinas primes, which is a unique property of the prime modulus of the P-521 base field. However, something is wrong with the implementation and I haven't figured out what.

I've been hoping the new codegen in fiat-crypto which uses newtypes in place of type aliases might help track down the issue, but haven't had time to try to update the generated code (and note in general that's a relatively difficult thing to do).

MasterAwesome commented 11 months ago

I've been hoping the new codegen in fiat-crypto which uses newtypes in place of type aliases might help track down the issue, but haven't had time to try to update the generated code (and note in general that's a relatively difficult thing to do).

I can help in creating a PR to update the existing code into the new type codegen by fiat-crypto. Would that be helpful?

MasterAwesome commented 11 months ago 

use elliptic_curve::SecretKey;
use p521::NistP521; // with feature wip-arithmetic-do-not-use

fn main() {
    let mut rng = rand::thread_rng();

    let secret_key : SecretKey<NistP521> = SecretKey::random(&mut rng);
    let public_key = secret_key.public_key();

    println!("{:?}", public_key);
}
```.

This note returns a valid public key :)

Required changes:

tarcieri commented 11 months ago

Yep, p521 looks close now. I'm filling in some additional tests.

Dustin-Ray commented 10 months ago

Any strong feelings on Curve448-Goldilocks?

Seeing it standardized and favored for inclusion in TLS might be worth the effort to investigate on our end. (I see an emphasis on legacy curves, so maybe not this one for now)

tarcieri commented 10 months ago

@drcapybara there's already a few implementations of it out there, e.g. https://crates.io/crates/ed448-goldilocks

We could potentially ask about upstreaming them

Dustin-Ray commented 10 months ago

@drcapybara there's already a few implementations of it out there, e.g. https://crates.io/crates/ed448-goldilocks

We could potentially ask about upstreaming them

This is a solid example. It appears there may be some good opportunity to upgrade some of the scalar arithmetic with functionality offered by crypto-bigint here.

samlaf commented 10 months ago

Any plans to support bn254?

tarcieri commented 10 months ago

Arkworks already has an implementation of BN254: https://github.com/arkworks-rs/curves/tree/master/bn254

halvors commented 9 months ago

Is the required refactoring done in primeorder in order to support secp224k1 with N being 1 bit larger than the curve? If not what is blocking this and when can it be done?

tarcieri commented 9 months ago

The breaking change needs to happen in the elliptic-curve crate, not just primeorder, and it probably needs some design work, i.e. new type names, which is something that's really needed revisiting for awhile. Regardless, the relevant issue and place for discussion is here: https://github.com/RustCrypto/traits/issues/1304

AbeerHaroon commented 7 months ago

Thank you for all of your work, it's a great endeavor. Did you get to spend any time on the Brainpool curves down the road?

tarcieri commented 7 months ago

Yeah, still haven't gotten to the bottom of what the issue is with them, but they should be close to having arithmetic backends

theaddonn commented 6 months ago

Has the secp384r1 been done?

tarcieri commented 6 months ago

Yes, along with all of the other NIST P-curves: https://github.com/RustCrypto/elliptic-curves/tree/master/p384

Dustin-Ray commented 5 months ago

@drcapybara there's already a few implementations of it out there, e.g. https://crates.io/crates/ed448-goldilocks

We could potentially ask about upstreaming them

where does this stand currently? The last published version of this crate came in about a year ago it looks like