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.

[fjarri]

and also, handle low-S normalization, which in practice is a special-case secp256k1 thing

That is exactly the problem. Using the generic ecdsa::signer::Signer<C> with C = Secp256k1 leads to verification errors because the low-S normalization is not handled. If Secp256k1 needs some specific handling of signing, shouldn't it be reflected in an implementation of some signing trait for Secp256k1 (say, SignPrimitive), and not in a newtype? Otherwise I don't see what the generic Signer<C> is even useful for.

To be more specific, the following compiles but fails the assertion:

use ecdsa::{SecretKey, Signer, Signature, PublicKey, Verifier};
use elliptic_curve::{Generate};
use rand_core::OsRng;
use signature::RandomizedSigner;
use signature::Verifier as _;
use k256::Secp256k1;

fn main() {

    let secret_key = SecretKey::<Secp256k1>::generate(&mut OsRng);
    let signer = Signer::new(&secret_key).expect("secret key invalid");
    let message = b"ECDSA proves knowledge of a secret number in the context of a single message";
    let signature: Signature<Secp256k1> = signer.sign_with_rng(&mut OsRng, message);

    let public_key = PublicKey::from_secret_key(&secret_key, true).expect("secret key invalid");
    let verifier = Verifier::new(&public_key).expect("public key invalid");

    assert!(verifier.verify(message, &signature).is_ok());
}

[tarcieri]

@fjarri as I explained in this post, it's possible to normalize in the RecoverableSignPrimitive impl, but it'd require some changes from the current implementation:

#119 (comment)

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

It's a tricky set of concerns to square... but also note that just doing that would break using a secp256k1 SignPrimitive implementation backed by a hardware accelerator.

So I guess we could normalize in both places? That would address your concerns for receiving low-S normalized signatures through the generic API, and my concerns about receiving them through a hardware accelerator which doesn't perform the normalization (which isn't just an academic concern: I'm targeting a device with an ECDSA accelerator which doesn't low-S normalize signatures, I'd like to use it, and such accelerators not low-S normalizing signatures is pretty much par for the course with all such devices).

I'm thinking it might make sense to just have RecoverableSignPrimitive take an associated recoverable signature type, always compute that, bound it on an Into conversion to the normal Signature<C>, and change the blanket impl for that to handle the Into conversion now. I think that'd work and avoids trying to specify the nature of the "recovery ID".

[fjarri]

The way I understand it is that there is an implied contract in the high-level API (what's signed by Signer<C> can be verified by Verifier<C>) whose correct operation should be the first priority. There's no point of having it if it can just randomly not work for some C without even any compilation errors. I feel like all the other design decisions should stem from there.

Now, I admit, I currently have a very vague idea of what hardware acceleration involves. Is there a function that gets called? At what level and how do you substitute it? Can it just be wrapped to perform the normalization in software? If it is just a Secp256k1 thing, would it make sense to have a RecoverableSignPrimitiveNotNormalized trait that would encompass hardware accelerators, and have a blanket impl of RecoverableSignPrimitive for the cases when it is present?

[tarcieri]

The way I understand it is that there is an implied contract in the high-level API (what's signed by Signer<C> can be verified by Verifier<C>) whose correct operation should be the first priority. There's no point of having it if it can just randomly not work for some C without even any compilation errors. I feel like all the other design decisions should stem from there.

The problem is low-S normalization is a secp256k1-specific concern, and beyond that, a cryptocurrency-specific concern. Low-S normalization is specifically a concern of ECDSA/secp256k1 when following BIP 0062 rules, which were introduced in 2014 and target a cryptocurrency vertical (they were originally Bitcoin-specific, but have gained more widespread adoption in other cryptocurrencies).

There are several implementations of ECDSA/secp256k1, including pretty much all of them in non-cryptowallet hardware, but also several in software, which will both produce and verify secp256k1 signatures without low-S normalization applied.
A ECDSA/secp256k1 signature is still valid without low-S normalization applied, just not under BIP62 rules.

I hope this makes it clear how this is a very specific complication which introduces rules beyond what the typical ECDSA standards require, which is difficult to work into a generic-across-curves ECDSA implementation.

I think it's good to make sure a secp256k1 library is cryptocurrency-friendly, but I am a bit wary to let these concerns leak out into cross-curve abstractions.

At what level and how do you substitute it? Can it just be wrapped to perform the normalization in software?

Until Rust lands specialization in the stable API, any cross-curve abstractions for solving this (i.e. in this case for a peripheral driver for an ECDSA accelerator) need to do the exact same thing for every curve. In this case, if we wanted the peripheral driver to apply low-S normalization, we'd have to apply it for every curve it supports. This would involve bounding <C as Arithmetic>::Scalar for SignPrimitive<C> on the NormalizeLow trait.

We can do this: I think it'd be nice that all signatures produced by the ecdsa crate are non-malleable. But no one using ECDSA with any curve besides secp256k1 actually cares about that, and it's an onerous requirement to impose on all ECDSA implementations just to satisfy the BIP62 rules for secp256k1. I'd be fine with it for now though, although I may not have time to impl this trait for p256 (which is the immediate concern).

Once specialization eventually lands, it will be possible to specialize the impl<C: ...> SignPrimitive<C> for T implementation for Secp256k1, and we could potentially apply low-S normalization specialized to the impl<C: ...> SignPrimitive<Secp256k1> for T impl. Unfortunately until specialization lands, Rust's type system is incapable of expressing that concern, aside from the newtype approach the k256 crate is presently using.

EDIT: I take this back, there's a gross hack that will probably work here, which would be introspecting whatever generic property of the curve used to select the curve to pass the peripheral (e.g. the OID) at runtime, getting a generic signature type out of the peripheral, and if the e.g. OID is for secp256k1, parsing it as a secp256k1 signature (i.e. k256::ecdsa::Signature), and then applying low-S normalization to the concrete type, then reserializing it, then re-parsing it again as the generic ecdsa::Signature<C> type. Pretty ugly, but it'd get the job done I guess. It'd also require every ECDSA peripheral driver that wants to support secp256k1 do this, as opposed to being able to handle it in a single place.

Another option would be adding some sort of curve-specific parsing logic for the signature type which would low-S normalize all secp256k1 signatures at the time they're parsed.

All that said, I think having the k256::ecdsa::Signer newtype apply low-S normalization is a reasonable stopgap for the case where SignPrimitive isn't applying it, e.g. in a hardware accelerator peripheral driver. We can still have the software implementation of SignPrimitive apply it as well so it works with ecdsa::signer::Signer<C>.

[tarcieri]

Another option is to introduce traits specifically for consensus-critical signing applications which have different rules from the "regular" rules (e.g. ConsensusSigner, ConsensusVerifier)

This has also been discussed in the context of ZIP-215 rules for Ed25519 verification.

[fjarri]

I feel like we're going in circles and not understanding one another. I realize that normalization is a specific Secp256k1 detail, so why not handle it in a specific Secp256k1 implementation? Why should it leak into the high-level API? impl RecoverableSignPrimitive<Secp256k1> seems like the perfect place for it. The performance hit of one negation is negligible compared to the rest of the signing, so I don't see a problem in always doing it for Secp256k1 (if we have to). If you want to take into account hardware accelerators or some third-party signers, you will have some kind of a conditional compilation anyway (if the support is built in k256), so it can be handled there.

There are several implementations of ECDSA/secp256k1, including pretty much all of them in non-cryptowallet hardware, but also several in software, which will both produce and verify secp256k1 signatures without low-S normalization applied.

Do you have some public code with an example of usage of such hardware accelerator? I honestly don't understand what problems might arise. We will have either a conditional compilation in k256, or a separate Secp256k1HardwareAccelerated type or whatever, and in both cases we can selectively apply the normalization.

---

In the end of the day, as a user, I expect the library to handle these issues internally. Today I find out that sign()/verify() contract is broken for some special curve, so what's next? Another curve not restoring a serialized key properly without some additional call? A specific scalar type isn't always equal to itself after a double inversion?

The high-level API should be hard, ideally impossible to misuse. If I absolutely can't use a Signature in a verify call with Secp256k1, I should have a compile-time error for that, or, at the very least, a certain Err result with contents explaining what I did wrong, not a 50% chance of a verification failure. I was lucky that this time I didn't change my code and was able to narrow down the possible failure reason to RustCrypto libraries. If I was using some other curve for tests, and then switched to secp256k1, it would be the last place I'd look, and I'd probably spend days sifting through my algorithm.

[tarcieri]

In the end of the day, as a user, I expect the library to handle these issues internally.

Let me put it this way. To my knowledge, there is no implementation of ECDSA/secp256k1, in hardware or software form, that presently does both of these things simultaneously:

1. Supports more than one elliptic curve besides secp256k1
2. Supports low-S normalization

Perhaps there's one I haven't encountered yet, but otherwise I feel like squaring these concerns simultaneously does not exist in other implementations, or is at best exceedingly rare. I agree we should try to find a solution that produces a low-S normalized signature from ecdsa::signature::Signature, but it's difficult and also not typically done.

We can add yet another trait specific to hardware accelerators, but these concerns also potentially apply to things like ASM implementations, so a "hardware accelerator trait" isn't necessarily the best solution to this particular problem (but that said, might be generally useful, particularly one which takes &mut self which would be nice for accessing hardware peripherals).

Another option is for RecoverableSignPrimitive to have an associated type for recoverable signatures, and change the blanket impl for SignPrimitive to be bounded on a From/Into conversion from the associated recoverable signature type to ecdsa::Signature<C>. Then RecoverableSignPrimitive can handle the full recoverable signature construction and "pre-normalize".

[tarcieri]

I think this change makes it possible to apply normalization generically, by moving the full recoverable signature construction into the RecoverableSignPrimitive trait, such that it has enough information to compute the recovery ID without a brute force search.

RustCrypto/signatures#120

What form generic normalization would take is still up for debate, though.

[fjarri]

To my knowledge, there is no implementation of ECDSA/secp256k1, in hardware or software form, that presently does both of these things simultaneously

Well, someone has to be the first, right?

I am not sure I understand at the moment how your solution will be reflected in specific implementations, but if it makes sign()/verify() work together, I'm all for it.

As an alternative solution, would it be such a big problem to simply always do the normalization in the Secp256k1 implementation, until we figure out the best way to handle malleable and non-malleable signatures separately? It will deteriorate the performance very slightly, but there are no other drawbacks, as far as I can see.

[tarcieri]

As an alternative solution, would it be such a big problem to simply always do the normalization in the Secp256k1 implementation, until we figure out the best way to handle malleable and non-malleable signatures separately? It will deteriorate the performance very slightly, but there are no other drawbacks, as far as I can see.

That's what I was proposing here with ConsensusSigner / ConsensusVerifier (which are also applicable to Ed25519 via ZIP-215)

#119 (comment)

The basic idea is consensus critical applications may want different rules from the typical rules: stricter signature construction rules, but also validation rules which are well-defined and universally agreed upon.

[tarcieri]

@fjarri any other showstopper issues you can think of that need to be addressed prior to a release?

[fjarri]

I would love to have some kind of a ProjectivePoint trait, but it is too big of an issue to handle now - I'll see if I can help with it after this release. Otherwise nothing I can think of.

[tarcieri]

Cool, yeah that sounds like something to work on next.

I'd also like to make it possible for SecretKey and PublicKey to wrap NonZeroScalar and AffinePoint (or potentially ProjectivePoint), or rather make them generic around some associated type defined by the curve, but those all sound like some "next steps" sort of things to work on after this release.

[tarcieri]

They're out:

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