New releases of elliptic curve crates

[tarcieri]

I'd like to cut releases of the following crates relatively soon (next few days / week):

• elliptic-curve v0.5.0
• ecdsa v0.7.0
• k256 v0.4.0
• p256 v0.4.0
• p384 v0.3.0

These will be the first releases supporting an integrated ECDSA implementation as well as initial (and rather rudimentary) support for implementing algorithms generically over elliptic curve groups.

If there's anything else you'd like to get into these releases, let me know, otherwise I plan on doing it soon.

When I say that, I'm also looking for small items rather than more significant changes. There's plenty of bigger issues to address (e.g. eliminating fallible APIs via eliminating the invalid representations that cause them in PublicKey/SecretKey) but I'd rather not make any bigger items release blockers at this point and we can continue making large and breaking changes in the next release.

cc @str4d @tuxxy @fjarri @nickray

[fjarri]

I've got some problems in my library that uses ecdsa and k256 - when I updated to the current state of elliptic-curves, traits and signatures from ~week old commits, I started getting incorrect results (some internal verification fails). Currently investigating the reason.

Also, there is a bug in k256/ecdsa/signer.rs: in try_sign_recoverable_prehashed(), let r_is_odd = R.y.is_odd(); should read let r_is_odd = R.y.normalize().is_odd();. There is an assertion that checks that you don't call is_odd() for non-normalized FieldElement, so it was supposed to be caught in testing. But, I guess, we only run tests for two feature sets:

• default features (which doesn't include ecdsa and therefore does not cover signer.rs), and
• all features (which includes field-montgomery and therefore does not check for normalization)

I can make a separate PR for this, but I wanted to figure out the remaining problems first.

[tarcieri]

Okay, sounds good. I'll try to wrap up what I'm working on and let you have at it.

If there's no pressing reason not to, I might cut releases of the elliptic-curve and ecdsa crates in the meantime.

[fjarri]

Another way to fix that bug would be to force normalization in is_odd(), the same way to_bytes() does. Makes it easier to test, but does hide some performance loss (after all, people don't expect is_odd() to be very complicated).

I'll try to have something more definite today - I guess I'll just start advancing commits from the working versions and see when my code starts failing. Can't eyeball anything suspicious at the moment.

[tarcieri]

I guess I'll just start advancing commits from the working versions and see when my code starts failing

Perhaps use git bisect?

[fjarri]

That's what I did, the difficulty was that I had to bisect elliptic-curves, traits and signatures simultaneously :)

Anyway, the issue is in commit 29e98d6 . When you moved impl SignPrimitive<Secp256k1> from ecdsa.rs to signer.rs, you removed normalize_s() on return. Since my code currently uses try_sign_prehashed(), it started to fail; adding normalize_s() back fixes it.

Is it supposed to work this way? I'll probably use the high-level Signer/Verifier anyway, since they're available now. I just want to make sure it was an intentional change.

An unrelated question about the API: why is NormalizeLow::normalize_low() in ecdsa mutating? All the other scalar functions are pure, so one would expect this one to be pure as well.

[tarcieri]

When you moved impl SignPrimitive from ecdsa.rs to signer.rs, you removed normalize_s() on return. Since my code currently uses try_sign_prehashed(), it started to fail; adding normalize_s() back fixes it.

Is it supposed to work this way?

@fjarri There's a few complications here.

The first is to efficiently compute the "recovery ID" for public key recovery (i.e. without doing a brute force search), the signer implementation needs to know if S was "high" prior to normalization:

https://github.com/RustCrypto/elliptic-curves/blob/93f7ff9/k256/src/ecdsa/signer.rs#L76

Another option to solve this particular problem would be to pass through something closer to a full "recovery ID" as part of the 2-tuple return value from RecoverableSignPrimitive, rather than what it's doing currently (passing through whether or not the y-coordinate of k*G=R was odd).

The second complication is hardware ECDSA accelerators and using SignPrimitive as a "crypto HAL" for them. I think it'd be nice to ensure when used via the high-level ecdsa::*Signer interface(s) they always produce low-S normalized signatures, but for any multi-curve accelerators that support secp256k1, I think it's generally not safe to assume they do that by default (every one I've used does not). So I ended up doing the normalization in the high-level interface rather than the low-level one.

An unrelated question about the API: why is NormalizeLow::normalize_low() in ecdsa mutating? All the other scalar functions are pure, so one would expect this one to be pure as well.

I could have it return a new value, sure. Everything was previously non-mutating when I had a module-level k256::ecdsa::normalize_s free function. There wasn't a specific reason I used a mutating one, other than I switched to a mutating normalize_s ala how it was done in rust-secp256k1. I could go either way on that.

[fjarri]

Thanks, I see. I'm not too familiar with the specifics of ECDSA, so if that's the expected behavior, it's fine by me. After all, it is in hazmat for a reason.

There wasn't a specific reason I used a mutating one, other than I switched to a mutating normalize_s ala how it was done in rust-secp256k1. I could go either way on that.

My vote would be for a pure function (for the scalar; I guess, mutating normalize_s() for a signature makes sense since, as you're saying, they can get large). I can try and make a PR.

[tarcieri]

@fjarri sure, that's fine. Perhaps we should consider putting it in elliptic_curve::ops, although I'm not sure where else it would be useful besides ECDSA.

[fjarri]

Created RustCrypto/signatures#119 and #122

[fjarri]

Hm, @tarcieri , could you explain briefly how to use the new high-level ECSDA API in a generic way? Namely, if I have a SecretKey<C>, is it possible to derive a Signer of some form for it? Currently there's a Signer<C> trait in ecdsa (with low-level API) and a Signer object in k256, which doesn't implement Signer<C>, which is a bit confusing.

[tarcieri]

@fjarri I originally instantiated k256::ecdsa::Signer as a concrete (ecdsa::Signer<Secp256k1>) type alias of ecdsa::signer::Signer. That was changed from a type alias to a newtype in #108, which added native support for k256::ecdsa::recoverable::Signature.

The implementation in #108 is a newtype around the original generic type though, with added functionality (namely support for Ethereum-style recoverable signatures). You can still use it generically as ecdsa::signer::Signer<k256::Secp256k1> though if you don't desire that functionality.

(Also a type alias vs newtype seems somewhat irrelevant to generic usage, so I'm not sure what concrete problem you're having. ecdsa::Signer<C> usage didn't change with #108)

[fjarri]

I must have misunderstood the intention for ecdsa::Signer<C> then. Now it is basically a wrapper on top of SignPrimitive, which I was using before — I will still have to call normalize_s() on the result, for example. It would be nice to have a high-level generic interface encapsulating ephemeral scalar creation, normalization, zeroization, and whatever else is needed.

[tarcieri]

I will still have to call normalize_s() on the result, for example. I

This is really the only thing that changed...

It would be nice to have a high-level generic interface encapsulating ephemeral scalar creation, normalization, zeroization, and whatever else is needed.

It does all of this and none of that changed in #108.

The changes in #108 added a newtype which added support for recoverable signatures. To do this, as I outlined above in this comment, I had to remove "pre-normalization" of signatures within SignPrimitive:

#119 (comment)

Also as I described above, I think this is good for reasons beyond supporting recoverable signatures, namely SignPrimitive is a nice API for supporting things like hardware accelerators, but also things like assembly implementations, without the implicit assumption that they also normalize the signatures.

RustCrypto/signatures#115 made it possible to generically support low-S normalization, and I think that'd be great for signers. We could move low-S normalization into the ecdsa::signer::Signer implementation if we made it a requirement for all curves. I think that'd be okay, but potentially a bit onerous.

All that said, aside from moving k256 low-S normalization out of its specific implementation of SignPrimitive, the other changes in #108 e.g. introducing a newtype shouldn't have had any other effects on your generic-over-curves implementation, AFAICT?

[fjarri]

It does all of this and none of that changed in #108.

That's true. What I was hoping for is to ditch my whole implementation based on low-level traits from hazmat and just have something along the lines of

let s = SecretKey::<C>::generate();
let signer = Signer::<C>::from(&s);
let signature = signer.sign(&message);
# or even
let signature = s.sign(&message);

Now I'm looking at signatures/ecdsa::signer (which has a generic Signer struct), traits/signature::signer (which has a generic Signer trait), and k256::ecsda::signer (which has a concrete Signer struct), and I'm honestly at a loss. Is that kind of high-level API impossible to make generic? Am I thinking about it wrong?

[tarcieri]

The main reason the k256::ecdsa::Signer newtype exists is as an extension to support k256::ecdsa::recoverable::Signature (i.e. Ethereum-style signatures) in addition to ecdsa::Signature<k256::Secp256k1>.

But that extension is just a newtype wrapper for ecdsa::signer::Signer<Secp256k1>. If you don't care about recoverable signatures, you can still use ecdsa::signer::Signer<Secp256k1>.

...but also, k256::ecdsa::Signer isn't generic, so if you're writing generic code, ecdsa::signer::Signer<C> is the only option.

The alternative to a newtype would be making a special k256::ecdsa::recoverable::Signer type which only produces k256::ecdsa::recoverable::Signatures. But I'm not sure that makes sense as opposed to having one newtype that can do it all (and also, handle low-S normalization, which in practice is a special-case secp256k1 thing).

tl;dr:

• ecdsa::signer::Signer<C> implements the parts of ECDSA that are truly generic over elliptic curves.
• k256::ecdsa::Signer is a ecdsa::signer::Signer<Secp256k1> newtype wrapper which implements things which are specific/unique to secp256k1.