Add ECDSA P-256 signing support

[briansmith]

This is harder than EdDSA because there's no code to do the actual ECDSA signing anymore; the ECDSA_sign function in crypto/ecdsa/ecdsa.c was removed to help with the migration to the new Rust ECC code. So, a new implementation of ECDSA signing in Rust is necessary.

For all platforms it is OK (preferable, even) to use crypto::ec::PrivateKey::generate for the key generation (i.e. base point multiplication). So, that part is already done.

I have some code sitting around to do the constant-time modular inversions (mod q) and (mod n). I will try to integrate it...soonish.

For 64-bit platforms, we can use crypto/ec/p256-64.c and crypto/ec/p256-x86_64.c for the variable point multiplication (the multiplication done during the signing operation). However, we don't have any usable code for 32-bit platforms yet (at least, not checked in).

For 32-bit ARM, x86, and AAarch64, I will eventually import in the ecp_nistz256 field operations from OpenSSL. Actually, I'm planning to do this real soon. However, I don't think the ecp_nistz256 group operations are good to use for any platform except x86-64 (even then...). We might try, instead, adapting the p256-64.c variable point multiplication to work using the ecp_nistz256 field operations (which would require adapting it to work on Montgomery-encoded field elements).

Similarly, we need to do make new nonce generation, as the old C code that Adam Langley wrote was removed. It may be worth copying how golang is doing it. Regardless, it would be nice to do as much of this as possible in Rust.

NIST has some test vectors for ECDSA signing, which are the absolute minimum level of testing necessary before the API can be exposed.

There is also no code for serializing private keys or deserializing them, which is pretty essential to most users of ECDSA signing. This should probably be split off into its own task as it is a fair amount of work on its own.

See also any general notes about signing APIs in #205.

[briansmith]

• [x] digest -> scalar conversion
• [x] dedicated, optimized, constant-time P-256 field operations.
• [x] constant-time inversion mod n (assuming scalar multiplication and squaring are constant-time)
• [x] constant-time Jacobian -> affine conversion (including constant-time inversion mod q)
• [x] constant-time point doubling and point addition*
• [x] constant-time base point multiplication for x86-64.
• [x] constant-time base point multiplication.for other platforms.
• [x] Serialization of signatures (ASN.1 DER)
• [x] Serialization of signatures (Fixed-length PKCS311 style)
• [x] The actual ECDSA signing function that combines all the above steps.
• [x] Tests
• [ ] Benchmarks in crypto-bench
• [x] key generation (partially done in ring::ec::PrivateKey)
• [x] Serialization of private keys
• [x] Deserialization of private keys
• [ ] Audit and document side channel resistance, including base assumptions.
• [ ] The point addition is constant-time assuming the exceptional cases aren't hit during ECDH and ECDSA signing, which is the same assumption that OpenSSL makes. We should verify that that is the case.
• [ ] Accidental nonce reuse/poor-PRNG hardening.

[briansmith]

See https://go-review.googlesource.com/#/c/3340/ and the papers it cites. See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.1538.

[briansmith]

Status update: All the checked-off stuff above is now in the main ring repo.

[briansmith]

Status update: More checked-off stuff is now in the ring repo. Unassigning myself in case somebody else wants to take this on before I get to it.

[Keats]

Is it still planned? It was asked for jsonwebtoken

I'm entirely unqualified to pick this up though :(

[briansmith]

I'm entirely unqualified to pick this up though :(

I doubt that is true!

Is it still planned?

Yes, I plan to do land it shortly, after I take care of the PR backlog.

[danstiner]

I've started to take a look at this and have some skeleton code (caveat, it gives incorrect results and is not cleaned up, but it does compile and is laid out following the NSA Suite B Implementer's Guide to ECDSA Section 3.4.1). However, before I dig too much deeper I'd like to ask a couple of questions and maybe get some feedback:

1. You checked off "The actual ECDSA signing function" above, but I do not see it anywhere. I assume it would have a signature similar to sign(msg: untrusted::Input, rng: &rand::SecureRandom) -> Result<signature::Signature, error::Unspecified>
2. Is there documentation on your big number implementation? Specifically there are few operations that seem to be still missing that I am not confident about implementing myself.
   1. In steps 2 and 3: Extracting a scalar from the x coordinate of the computed elliptic curve point. (r = xR mod n, where (xR,yR) = kG. private_key_ops.common.point_x() will give a Elem<R>, but then I don't see a way to do the mod n conversion into a Scalar. Ideally unencoded, as r needs to be output as part of the signature.
   2. In step 6: How to use the unencoded scalar r as part of a product with unencoded scalar d? I am not familiar with Montgomery modular multiplication, but from what I gather it may be more efficient to have a product function that works on unencoded scalars instead of first encoding one of d or r before multiplying. Comparing with BoringSSL, they seem to work on unencoded numbers but I haven't dug in to how BN_mod_mul actually works.
   3. In step 6: Summing two scalars: I couldn't find an implementation of this already done. I added one using common.elem_add_impl, but I suspect it may be using the wrong modulus as I didn't see how the modulus is determined in that impl and stopped digging once I saw assembly, figuring it was faster to ask than dig deeper.
3. How to best debug correctness. I see an example signature in the NSA implementer's guide complete with expected state at each step, is that a good place to start? If so, is there an existing function comparing hex to a Elem/Scalar? Otherwise It should be easy enough to write something.
4. I've ignored considerations of being constant time and side-channels for now, but that will likely be something I need help looking over before merging anything in.

Overall caveat: I have never worked on crypto before and Rust is still fairly new to me, but it has been enjoyable to work in this codebase, it is nicely organized!

[briansmith]

As far as your specific questions go, basically the answer is "I've written the code for it, but it isn't public yet."

That is, I have written all this code, but the implementation isn't in a PR yet. The problem is that it is using a 100% random nonce, and I want to change it to use a construction like https://blogs.cisco.com/security/fips-and-deterministic-ecdsa-achieving-robust-security-and-conformance, which is what BoringSSL also now does. However, I haven't had time to write the DRBG implementation yet, and that's what this is blocked on.

[danstiner]

That's great to hear! I can see the benefit of being deterministic and keeping to what BoringSSL does. I'd be happy to help as time allows, but again crypto code is beyond my current expertise.

[briansmith]

I've added the initial implementation of P-256 ECDSA signing in https://github.com/briansmith/ring/commit/e5a4fe96f77e6eda71b901f5bf790d5db49670d9 and I updated the checklist above to indicate what work is needed to call this "complete." The nonce reuse hardening will be added soon.

[briansmith]

Use ring::signature::key_pair_from_pkcs8() to parse the PKCS#8 private key. Use ring::signature::sign() to do the signing. The SigningAlgorithms for ECDSA are ring::signature::{ ECDSA_P256_SHA256_ASN1_SIGNING, ECDSA_P256_SHA256_FIXED_SIGNING, ECDSA_P384_SHA384_ASN1_SIGNING, ECDSA_P384_SHA384_FIXED_SIGNING}.

[eoger]

Apologies for the dumb question, is signature::ECDSAKeyPair::generate_pkcs8 followed by signature::ECDSAKeyPair::from_pkcs8 the correct way to generate a random ECDSAKeyPair? I couldn't find a convenience constructor.

[briansmith]

Apologies for the dumb question, is signature::ECDSAKeyPair::generate_pkcs8 followed by signature::ECDSAKeyPair::from_pkcs8 the correct way to generate a random ECDSAKeyPair? I couldn't find a convenience constructor.

Yes, currently. However, I would accept a PR that adds the ability to generate a key pair object directly, without going through PKCS#8.

[briansmith]

PR #662 implements a hardening countermeasure against bad PRNGs. Please take a look and provide feedback.

[manifest]

@briansmith I'm trying to figure it out how to generate key pair, sign and verify P-256 ECDSA signature in order to implement ES256 for jsonwebtoken. How can I get a public_key from P-256 ECDSA key_pair to use it with signature::verify function? It looks like there is no key_pair.public_key_bytes() or something similar.

    let rng = rand::SystemRandom::new();
    let alg = &signature::ECDSA_P256_SHA256_ASN1_SIGNING;
    let pkcs8 = signature::ECDSAKeyPair::generate_pkcs8(alg, &rng).unwrap();
    let key_pair = signature::key_pair_from_pkcs8(alg, untrusted::Input::from(pkcs8.as_ref())).unwrap();

    const MESSAGE: &'static [u8] = b"hello, world";
    let sig = signature::sign(&key_pair, &rng, untrusted::Input::from(MESSAGE)).unwrap();

//    signature::verify(
//        alg, 
//        untrusted::Input::from(keys.public_key_bytes()),
//        untrusted::Input::from(MESSAGE),
//        untrusted::Input::from(sig.as_ref())
//    ).unwrap();

[manifest]

To implement ES256 for jsonwebtoken we need an API that is dealing with keys in form of &[u8]. There is no way we could use KeyPair or any other structs.

fn sign(signing_input: &str, key: &[u8], algorithm: Algorithm) -> Result<String> { ... }
fn verify(signature: &str, signing_input: &str, key: &[u8], algorithm: Algorithm) -> Result<bool> { ... }

In ring we already have signature::verify function that accept public_key as &[u8]. May we also have signature::sign that will accept private_key as &[u8]?

pub fn verify(alg: &VerificationAlgorithm, public_key: untrusted::Input, msg: untrusted::Input, signature: untrusted::Input) -> Result<(), error::Unspecified> { ... }
pub fn sign(alg: &SigningAlgorithm, private_key: untrusted::Input, rng: &rand::SecureRandom, msg: untrusted::Input) -> Result<Signature, error::Unspecified> { ... }
// pub fn sign(key_pair: &KeyPair, rng: &rand::SecureRandom, msg: untrusted::Input) -> Result<Signature, error::Unspecified> { ... }

I'm willing to work on that issue, just need some guidance and help in understanding the ring API design. @briansmith what do you think?

[briansmith]

To implement ES256 for jsonwebtoken we need an API that is dealing with keys in form of &[u8]

I might be wrong, but I don't think that is true. My understanding is that you can implement all parts of ES256 with opaque keys. The only thing you can't do is import/export keys in the JWT format.

if you need key import/export for non-PKCS#8 keys, I am open to exposing such an API. Rather than adding a new variant of sign() that takes &[u8] private key, we should expose a function from ring::signature that constructs a private key pair from a bare non-PKCS#8 &[u8], so that the existing sign() function can be used.

[briansmith]

FWIW, the fact that the verify function takes the inputs as &[u8] instead of as more strongly-typed inputs is a deficiency that we should correct. It made sense in the beginning of ring when the goal was to just be a better alternative to using the OpenSSL API, but it isn't a good practice, and we can do better.

[manifest]

I might be wrong, but I don't think that is true. My understanding is that you can implement all parts of ES256 with opaque keys.

jsonwebtoken takes &[u8] as a private key, so it's currently impossible to use ring's KeyPair

fn sign(signing_input: &str, key: &[u8], algorithm: Algorithm) -> Result<String>

https://github.com/Keats/jsonwebtoken/blob/master/src/crypto.rs#L91

The only thing you can't do is import/export keys in the JWT format.

If you meant JWK, jsonwebtoken don't use them and that is a good thing. JWS specification doesn't require using JWK. It is just one format of many and definitely not an efficient one.

if you need key import/export for non-PKCS#8 keys, I am open to exposing such an API.

It would be great. It solves one part of the problem. I believe, it also will be useful in general.

Brian:

Rather than adding a new variant of sign() that takes &[u8] private key, we should expose a function from ring::signature that constructs a private key pair from a bare non-PKCS#8 &[u8], so that the existing sign() function can be used. https://github.com/briansmith/ring/issues/207#issuecomment-427996389

Vincent:

That would expose ring to end users which isn't really nice. I would rather wait for supports for signing from bytes to be implemented in ring https://github.com/Keats/jsonwebtoken/issues/21#issuecomment-418415882

@briansmith @Keats Would be great if you both agreed on some solution. At the moment, it looks as a deadlock. JWT is how everybody does authorization in the Web today. It is kind of shame there is no proper solution in Rust. The impact is huge, and we all may only benefit from a solution. Thanks guys. Looking forward for your decision. I'm ready to spend my time on the issue if needed.

[briansmith]

jsonwebtoken takes &[u8] as a private key, so it's currently impossible to use ring's KeyPair

That's not a good API. Even if the authors want to limit the use of ring types in that crate's API, they could do so like this:

use ring::signature;

struct KeyPair {
   inner: signature::KeyPair,
}

fn sign(signing_input: &str, key: &KeyPair) -> Result<String>

(FWIW, I generally don't spend a lot of time helping people build abstractions over different crypto libraries because I think such abstractions do more harm than good. IMO it would be better to just use ring::signature::KeyPair directly. I understand some crate authors disagree so I don't harp on that. But also, I don't make changes to ring just for the purpose of supporting such abstractions. Regardless, no matter what is decided, no change to ring is useful to improve jsonwebtoken's API.)

[manifest]

@briansmith Thanks for your quick response. I understand your position. In our case, we can't use even ring itself because of KeyPair.

We have one web application issuing access tokens (IAM) and many web applications that verifying a signature of these access tokens. Thus, the first one needs to know only about the private key. As for others, they only need a public key, and we can't trust them the private key. It makes no sense using an asymmetric algorithm otherwise.

Is it possible to split KeyPair into PrivateKey and PublicKey?

Personally, I would love to see something similar to Erlang's crypto library that allow you to generate both keys in just one function call:

{Pub, Priv} = crypto:generate_key(ecdh, secp256r1)

[Keats]

That's not a good API. Even if the authors want to limit the use of ring types in that crate's API, they could do so like this:

But then you have to have several functions depending on which algorithm to use, as HMAC won't have a key pair for example. Very often in the case of asymmetric signing, you only have the public key so you wouldn't be able to build a KeyPair as @manifest mentioned.

[briansmith]

But then you have to have several functions depending on which algorithm to use, as HMAC won't have a key pair for example.

HMAC and digital signatures shouldn't have the same API anyway. The fact that the syntax is the same for both in JOSE is widely seen as one of its biggest design flaws.

[manifest]

I still don't understand how the problem that I described might be solved. @briansmith could you please elaborate on how you see using ring to verify a signature in the untrusted environment?

[manifest]

@briansmith Sorry to bother you, I'm just trying to find a solution for our problem.

• Can we have Private Key and Public Key structs for ECDSA that we can use with sign / verify functions?
• Can we expose API for importing / exporting these keys?

It's what we need to solve the problem described above and start using ring library, or maybe you could suggest a different approach.

[briansmith]

I'm getting the impression we might be talking past each other since we seem to have some misunderstandings.

Very often in the case of asymmetric signing, you only have the public key so you wouldn't be able to build a KeyPair as @manifest mentioned.

The ECDSA verification API already takes &[u8] for the public key. (If you only have the public key then you can only verify signatures, not generate signatures.)

Only the ECDSA signing API requires a KeyPair object as input.

So my suggestion is to change the JWT crate to require a KeyPair object for signing (only). That would be a great improvement to the JWT crate. (Taking the private key as a &[u8] means that the user of the crate would have to keep the private key bytes easily-accessible which is bad.)

In the future we'll have a type signature::PublicKey(&[u8]) which will make this a little more symmetric. However, no changes are needed to ring to provide the functionality you need today.

[manifest]

How can KeyPair and &[u8] (that will be replaced by PublicKey in the future) be generated, in order to be used in signing and verification APIs? It's impossible without external tools at the moment, am I right?

[briansmith]

ring::signature;;ECDSAKeyPair::generate_pkcs8 will generate a new ECDSA private key as a serialized PKCS#8 document. ring::signature::key_pair_from_pkcs8 will create a KeyPair from the serialized document. (I understand that these APIs should be more symmetric; it's on the TODO ist

Incidentally, it turns out I already implemented the thing that was originally being asked for: ring::signature::ECDSAKeyPair::from_private_key_and_public_key will construct a ECDSAKeyPair from the public key bytes and the private key bytes directly. IIRC, I actually added that API to support deserialization of JWKs.

[manifest]

@briansmith I'm following the steps you described above. I've generated KeyPair, then I used it to sign a message. How can I generate a public key from KeyPair in order to pass it to another application that will use it to verify the signed message?

There is public_key_bytes() for Ed25519KeyPair but nothing for ECDSAKeyPair.

Example

    let rng = rand::SystemRandom::new();
    let alg = &signature::ECDSA_P256_SHA256_ASN1_SIGNING;
    let pkcs8 = signature::ECDSAKeyPair::generate_pkcs8(alg, &rng).unwrap();
    let key_pair = signature::key_pair_from_pkcs8(alg, untrusted::Input::from(pkcs8.as_ref())).unwrap();

    const MESSAGE: &'static [u8] = b"hello, world";
    let sig = signature::sign(&key_pair, &rng, untrusted::Input::from(MESSAGE)).unwrap();

//    signature::verify(
//        alg, 
//        untrusted::Input::from(keys.public_key_bytes()),
//        untrusted::Input::from(MESSAGE),
//        untrusted::Input::from(sig.as_ref())
//    ).unwrap();

[briansmith]

@keats @manifest Please try ring 0.14.0-alpha2. In particular, look at ring::signature::KeyPair::public_key(). I've temporarily removed the "generic" API that was was working on and I've renamed some types (RSA* -> Rsa*, ECDSA* -> Ecdsa*) and made some other minor changes which will (I hope) eventually make everything easier to use.

[briansmith]

I'm closing this because for the most part it was done. There are some details that need to be taken care of but it doesn't make sense to leave this issue open any more. If you run into troubles, please file a new issue.

[manifest]

Thanks. Everything looks good. The only problem that it's still impossible to retrieve a public key because public_key function is private. I've opened an issue.

[briansmith]

Thanks. Everything looks good. The only problem that it's still impossible to retrieve a public key because public_key function is private.

Thanks for the feedback. I replied in the issue you filed. Let's continue the discussion there.

[moeziniaf]

@briansmith I'm trying to figure it out how to generate key pair, sign and verify P-256 ECDSA signature in order to implement ES256 for jsonwebtoken. How can I get a public_key from P-256 ECDSA key_pair to use it with signature::verify function? It looks like there is no key_pair.public_key_bytes() or something similar.

    let rng = rand::SystemRandom::new();
    let alg = &signature::ECDSA_P256_SHA256_ASN1_SIGNING;
    let pkcs8 = signature::ECDSAKeyPair::generate_pkcs8(alg, &rng).unwrap();
    let key_pair = signature::key_pair_from_pkcs8(alg, untrusted::Input::from(pkcs8.as_ref())).unwrap();

    const MESSAGE: &'static [u8] = b"hello, world";
    let sig = signature::sign(&key_pair, &rng, untrusted::Input::from(MESSAGE)).unwrap();

//    signature::verify(
//        alg, 
//        untrusted::Input::from(keys.public_key_bytes()),
//        untrusted::Input::from(MESSAGE),
//        untrusted::Input::from(sig.as_ref())
//    ).unwrap();

How do you use verify? I can't figure out how to in version 0.16.14? I tried rust::signature::verify and rust::signature::EcdsaKeyPair::verify..

[briansmith]

@moeziniaf Doesn't the example for Ed25519 work for P-256 too?: https://docs.rs/ring/0.16.14/ring/signature/index.html#signing-and-verifying-with-ed25519

[thomaseizinger]

As far as your specific questions go, basically the answer is "I've written the code for it, but it isn't public yet."

That is, I have written all this code, but the implementation isn't in a PR yet. The problem is that it is using a 100% random nonce, and I want to change it to use a construction like blogs.cisco.com/security/fips-and-deterministic-ecdsa-achieving-robust-security-and-conformance, which is what BoringSSL also now does. However, I haven't had time to write the DRBG implementation yet, and that's what this is blocked on.

Is implementation of RFC6979 still something that is planned for ring? I might have a go at implementing it then.