Scalar arithmetic about elliptic-curves HOT 9 CLOSED

I was planning to implement scalar arithmetic myself for p256 later this week 😝 so yes, it would be good to have. It will be required in any case for implementing the ff and group crate traits.

from elliptic-curves.

I'm happy to PR my scalar arithmetic if so desired. In any case, there are decisions to make:

• I implement scalars via Barrett reduction on pub struct Scalar([u64; 4]), is this what is desired?
• Scalar field inversion via Euler's theorem is unbearably slow on microcontrollers. My current implementation (not published) uses Stein's theorem instead, which is highly not-constant time and would necessitate a masking scalar in signature generation (calculate r*(1/(k*r)) for random r).
• Would we want both implementations, and if so, configure via feature flag, or separate methods, or...?

My current signature implementation ("hazmat", entropy to be generated and hashes to be calculated externally, e.g. with hardware acceleration) looks like

impl Scalar {
    pub fn try_sign_prehashed(&self,    
        ephemeral_scalar: Scalar,    
        // for side channel protection
        masking_scalar: Option<Scalar>,    
        hashed_msg: &[u8; 32],        
    ) -> Result<[u8; 64], Error> { (...) }
}

It's not clear to me what the intended implementation approach for DH and signatures is in p256, but that would be a next step anyway.

from elliptic-curves.

My current signature implementation ("hazmat", entropy to be generated and hashes to be calculated externally, e.g. with hardware acceleration) looks like...

Neat! How did you implement masking_scalar: Option<Scalar>?

I'm thinking it probably makes the most sense to implement RFC 6979, but also providing that sort of masking_scalar, using techniques like the ones described in draft-mattsson-cfrg-det-sigs-with-noise Section 3.

I think this combination gives you the best of both worlds: avoiding the catastrophic pitfalls of biased ECDSA nonces while also (optionally) hardening it against fault attacks using added entropy.

It's not clear to me what the intended implementation approach for DH and signatures is in p256, but that would be a next step anyway.

I've been talking with @str4d a lot about the next steps towards ECDSA.

Ideally we'd like to have a set of traits that would allow us to implement ECDSA generically over any weierstrass::Curve, but we'd like to do it in a way that doesn't leak the FieldElements that comprise the coordinates of an AffinePoint for applications other than ECDSA (which only needs the x-coordinate, but even then we'd only want to expose it for ECDSA).

All that said, if you'd like to prototype adding an ECDSA implementation directly to the p256 crate, while we wouldn't merge that PR directly I think it'd be a great starting point for discussion about what features/traits we need to add to both the elliptic-curve crate and p256 crate to support a generic ECDSA implementation.

from elliptic-curves.

You already leak the affine coordinates, e.g. via to_uncompressed_pubkey, which people do use to get things done (e.g. https://github.com/jonas-schievink/rubble/blob/508f93bc6c8ba5f267c3ceeb53d19b8ac65c1faa/rubble/src/ecdh/p256.rs#L80).

To me as a mathematician, it's honestly quite weird to suppress the coordinates of an object that is by definition a pair of coordinates. I understand the concern, but maybe this is better handled by offering access but with a long, detailed, illuminating doc comment of when not to use the coordinates and why not? Alternatively/additionally (although I'm usually not a fan of this abuse of "unsafe"), you could offer unsafe accessors? Perhaps I'm tainted by Python's "we're all consenting adults here" philosophy, I think the way to prevent abuse of coordinates is by offering safe implementations of the things library users need, which are easier to use than unsafe implementations they might come up with themselves.

from elliptic-curves.

I understand the concern, but maybe this is better handled by offering access but with a long, detailed, illuminating doc comment of when not to use the coordinates and why not?

I think this approach might work well enough in tandem with an AffineCoordinates trait (like the one I tried to introduce in #50)

from elliptic-curves.

You already leak the affine coordinates, e.g. via to_uncompressed_pubkey, which people do use to get things done (e.g. https://github.com/jonas-schievink/rubble/blob/508f93bc6c8ba5f267c3ceeb53d19b8ac65c1faa/rubble/src/ecdh/p256.rs#L80).

What we are exposing is an opaque uncompressed encoding that is type-bound to the curve in question (up until as_bytes() is used). We obviously can't prevent someone from dropping the type safety and then manually parsing the byte encoding.

To me as a mathematician, it's honestly quite weird to suppress the coordinates of an object that is by definition a pair of coordinates.

It is a pair of coordinates that lie on a specific elliptic curve. The core problem with exposing the underlying affine coordinates is that you lose this context: you now have a pair of field elements, and are no longer bound by the curve equations for the specific curve the coordinates are for. Encapsulating the coordinates with the curve equation context, and ensuring that the operations performed upon them make sense, is exactly what AffinePoint does.

I think the way to prevent abuse of coordinates is by offering safe implementations of the things library users need, which are easier to use than unsafe implementations they might come up with themselves.

I agree, which is why I think we should be providing traits for ECDSA and ECDH, that supported curves (which have the necessary context) can implement. In the example you linked, they would be using an ECDH trait, and the p256 crate would implement the trait and return something like a SharedSecret<NistP256> wire type.

I understand the concern, but maybe this is better handled by offering access but with a long, detailed, illuminating doc comment of when not to use the coordinates and why not?

I think this approach might work well enough in tandem with an AffineCoordinates trait (like the one I tried to introduce in #50)

I am still currently against this, but if we did also have an AffineCoordinates trait, making it very clear that this is only for backwards-compatibility with existing protocols and should be discouraged for new protocols would be a base-line requirement for me. Making it a separate contained trait, and naming it clearly as not part of the main public API, would also help to stop people reaching directly for it (as we did with DecryptionPrimitive in the rsa crate, which exists to support other decryption backends like YubiKeys, but the main user API is the PrivateKey trait).

from elliptic-curves.

To me as a mathematician, it's honestly quite weird to suppress the coordinates of an object that is by definition a pair of coordinates.

It is a pair of coordinates that lie on a specific elliptic curve. The core problem with exposing the underlying affine coordinates is that you lose this context: you now have a pair of field elements, and are no longer bound by the curve equations for the specific curve the coordinates are for. Encapsulating the coordinates with the curve equation context, and ensuring that the operations performed upon them make sense, is exactly what AffinePoint does.

I understand this, which is why Affine{Curve,}Point's constructor(s) must enforce that coordinate pairs lie on the curve. But we're talking about the other direction points -> coordinates, in other words a specific embedding of the curve in the plane. So I still don't understand this. Not trying to be obstinate - I just don't understand how exposing this embedding differs from exposing "uncompressed encoding as bytes"? What can people do with a field element that's not bound to a curve (but that they happend to have gotten from a curve point), which they can't do with any other field element they came up with? Is this a purity concern or a security concern?

from elliptic-curves.

@str4d some thoughts on my #65 PR (which exposes the affine coordinates).

Instead of exposing the affine coordinates, I think we could add some traits for the specific functionality needed for ECDSA, since it seems pretty concrete.

I think we really need two things:

• Conversions from AffinePoint x-coordinate to Scalar type for a particular curve. Perhaps something like a legacy::ReduceAffineX trait with an associated Scalar type specific to a curve? I think that would address your previous concerns about type safety.
• Trait for determining if the y-coordinate is odd

EDIT: opened #67 with a WIP implementation of the above as an alternative to #65

from elliptic-curves.

We have enough scalar arithmetic now to implement at least ECDSA signing/verification.

If there's anything else you have in mind, please feel free to reopen, but I'd say at least k256 and p256 (the only crates with arithmetic implementations) support the basics now.

from elliptic-curves.