Missing elliptic curves

Question

Missing elliptic curves

tarcieri opened this issue 4 years ago · 52 comments

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.

Answer 1 · 2021-01-22T04:03:41.000Z

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.

Answer 2 · 2021-01-26T21:29:11.000Z

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

First, for background:

r1 curves are "verifiably pseudorandom" (or rather, were supposed to be but were erroneously generated)
t1 curves are the "twist" curves and provide the same effective security properties but permit a slightly more efficient implementation due to the use of smaller parameters

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:

bp256: brainpoolP256r1 and brainpoolP256t1
bp384: brainpoolP384r1 and brainpoolP384t1

Separate crates for `r1` and `t1` curves

This would look like:

bp256r1: brainpoolP256r1
bp256t1: brainpoolP256t1
bp384r1: brainpoolP384r1
bp384r1: brainpoolP384t1

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

Answer 3 · 2021-05-03T22:51:32.000Z

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

Answer 4 · 2021-05-03T22:52:33.000Z

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

Answer 5 · 2021-09-28T02:21:32.000Z

@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?

Answer 6 · 2021-09-28T17:45:43.000Z

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

Answer 7 · 2021-10-22T16:44:53.000Z

I added PKCS#8 support to the ed25519 crate in RustCrypto/signatures#381

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

Note it's still unreleased though

Answer 8 · 2022-06-01T07:14:08.000Z

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!

Answer 9 · 2022-06-01T13:13:22.000Z

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.

Answer 10 · 2022-06-01T16:51:21.000Z

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

Answer 11 · 2022-06-01T17:09:55.000Z

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.

Answer 12 · 2022-06-01T19:07:07.000Z

Sounds reasonable 👍

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.

Answer 13 · 2022-06-27T20:11:29.000Z

#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.

Answer 14 · 2022-08-03T00:21:06.000Z

#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.

Answer 15 · 2022-12-29T18:37:09.000Z

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

Answer 16 · 2022-12-29T20:18:59.000Z

@tarcieri Done.

Answer 17 · 2022-12-29T20:19:58.000Z

@newpavlov thank you!

Answer 18 · 2023-02-13T02:26:46.000Z

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.

Answer 19 · 2023-03-16T20:40:14.000Z

Could you please add secp192r1 to this list?

Answer 20 · 2023-03-16T20:50:52.000Z

@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)

Answer 21 · 2023-03-20T16:22:45.000Z

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

Answer 22 · 2023-03-21T05:33:49.000Z

@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.

Answer 23 · 2023-03-21T13:11:30.000Z

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 ?

Answer 24 · 2023-03-21T13:16:31.000Z

@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.

Answer 25 · 2023-04-10T03:07:53.000Z

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

Answer 26 · 2023-04-14T11:17:48.000Z

@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.

Answer 27 · 2023-04-14T13:57:35.000Z

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

Answer 28 · 2023-04-14T22:53:56.000Z

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?

Answer 29 · 2023-04-14T22:59:15.000Z

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?

Answer 30 · 2023-04-14T23:05:54.000Z

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

Answer 31 · 2023-06-03T16:18:31.000Z

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.

Answer 32 · 2023-06-03T16:24:49.000Z

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

Answer 33 · 2023-06-03T19:03:29.000Z

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: RustCrypto/traits#1304

Answer 34 · 2023-09-12T10:42:04.000Z

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.
#114 (comment)

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.

Answer 35 · 2023-09-12T13:06:57.000Z

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).

Answer 36 · 2023-10-28T19:37:27.000Z

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?

Looks like new types instead of type aliases was added in fiat-crypto v0.0.21. I can import v0.0.24's version. Added in #944
fiat-constify doesn't support new syntax. This seems straightforward to fix. Fixed in RustCrypto/utils#978

Answer 37 · 2023-11-02T20:25:27.000Z

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:

Answer 38 · 2023-11-02T20:48:47.000Z

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

Answer 39 · 2023-11-09T23:36:16.000Z

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)

Answer 40 · 2023-11-10T00:07:47.000Z

@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

Answer 41 · 2023-11-10T00:34:45.000Z

@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.

Answer 42 · 2023-11-22T04:59:25.000Z

Any plans to support bn254?

Answer 43 · 2023-11-22T13:31:24.000Z

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

Answer 44 · 2023-12-10T02:46:00.000Z

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?

Answer 45 · 2023-12-10T19:15:17.000Z

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: RustCrypto/traits#1304

Answer 46 · 2024-02-09T10:23:40.000Z

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?

Answer 47 · 2024-02-09T21:11:54.000Z

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

Answer 48 · 2024-03-20T10:04:29.000Z

Has the secp384r1 been done?

Answer 49 · 2024-03-20T10:30:44.000Z

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

Answer 50 · 2024-04-12T20:33:21.000Z

@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

Answer 51 · 2024-04-12T20:37:26.000Z

We could potentially inquire on the upstream repo: https://github.com/crate-crypto/Ed448-Goldilocks

Answer 52 · 2024-04-14T22:16:35.000Z

We could potentially inquire on the upstream repo: https://github.com/crate-crypto/Ed448-Goldilocks

sounds like the authors might be interested: crate-crypto/Ed448-Goldilocks#35

Include both r1 and t1 curves in the same crate

Separate crates for r1 and t1 curves

Include both `r1` and `t1` curves in the same crate

Separate crates for `r1` and `t1` curves