crypto/ecdh: new package

FiloSottile commented 2 years ago

According to the Debian and the Google internal code search, crypto/elliptic is used almost exclusively as part of ECDSA (via crypto/ecdsa) and ECDH. It is however a very low-level and unsafe API for ECDH.

As part of an effort to move math/big outside the security perimeter, I have been moving the NIST curve implementations to a safe API in the nistec package (#52182). The nistec API is safe but still lower-level than necessary.

ECDH is used in TLS, SSH, JOSE, OpenPGP, PIV, and HPKE, as well as a component of other various ECIES schemes. There are a myriad of standards (ISO, NIST, ANSI, SECG, IETF) but thankfully they all work the same for NIST P curves at the ECDH level.

I'm proposing adding a new crypto/ecdh package that exposes a safe, []byte-based API for ECDH.

Between this package and crypto/ecdsa, there should be no need for direct uses of crypto/elliptic, and the big.Int-based methods of elliptic.Curve (ScalarMult, ScalarBaseMult, Add, Double, IsOnCurve) can be deprecated.

Below is the proposed API. Here are the motivating design goals of the API:

Most direct uses of crypto/elliptic can be replaced with it.
No support for custom curves.
- Ideally, X25519 can be supported alongside NIST curves.
It can be implemented entirely in constant time.
Invalid states can't be represented.
- For example, it's not possible to provide an invalid point to the scalar multiplication.
Errors are returned for every invalid input.
Using one curve does not make the other curve implementations reachable.
- This helps both with binary size and with govulncheck accuracy.
PublicKey and PrivateKey are compatible with analogous types in other packages.
- This is why PrivateKey has a Public() crypto.PublicKey method.
It's possible to add any additional methods we realized might be necessary later.
- This is why the main interface has a private method, so it can't be implemented by external types and can be extended while retaining backwards compatibility.
In addition to the standard ECDH flow, it's possible to validate a public key, and to convert a private key to a public key.
With collaboration from the compiler it's possible to use the API with zero allocations.
- For the proposed API, this requires devirtualization, then inlining, then escape analysis.
- See #52193

/cc @golang/security @golang/proposal-review

package ecdh

type Curve interface {
    // ECDH performs a ECDH exchange and returns the shared secret.
    //
    // For NIST curves, this performs ECDH as specified in SEC 1, Version 2.0,
    // Section 3.3.1, and returns the x-coordinate encoded according to SEC 1,
    // Version 2.0, Section 2.3.5. In particular, if the result is the point at
    // infinity, ECDH returns an error. (Note that for NIST curves, that's only
    // possible if the private key is the all-zero value.)
    //
    // For X25519, this performs ECDH as specified in RFC 7748, Section 6.1. If
    // the result is the all-zero value, ECDH returns an error.
    ECDH(local *PrivateKey, remote *PublicKey) ([]byte, error)

    // GenerateKey generates a new PrivateKey from rand.
    GenerateKey(rand io.Reader) (*PrivateKey, error)

    // NewPrivateKey checks that key is valid and returns a PrivateKey.
    //
    // For NIST curves, this follows SEC 1, Version 2.0, Section 2.3.6, which
    // amounts to decoding the bytes as a fixed length big endian integer and
    // checking that the result is lower than the order of the curve. The zero
    // private key is also rejected, as the encoding of the corresponding public
    // key would be irregular.
    //
    // For X25519, this only checks the scalar length. Adversarially selected
    // private keys can cause ECDH to return an error.
    NewPrivateKey(key []byte) (*PrivateKey, error)

    // NewPublicKey checks that key is valid and returns a PublicKey.
    //
    // For NIST curves, this decodes an uncompressed point according to SEC 1,
    // Version 2.0, Section 2.3.4. Compressed encodings and the point at
    // infinity are rejected.
    //
    // For X25519, this only checks the u-coordinate length. Adversarially
    // selected public keys can cause ECDH to return an error.
    NewPublicKey(key []byte) (*PublicKey, error)

    // Has unexported methods.
}

func P256() Curve
func P384() Curve
func P521() Curve
func X25519() Curve

type PrivateKey struct {
    // Has unexported fields.
}

func (k *PrivateKey) Bytes() []byte
func (k *PrivateKey) Curve() Curve
func (k *PrivateKey) Equal(x crypto.PrivateKey) bool
func (k *PrivateKey) Public() crypto.PublicKey
func (k *PrivateKey) PublicKey() *PublicKey

type PublicKey struct {
    // Has unexported fields.
}

func (k *PublicKey) Bytes() []byte
func (k *PublicKey) Curve() Curve
func (k *PublicKey) Equal(x crypto.PublicKey) bool

gopherbot commented 2 years ago

Change https://go.dev/cl/398914 mentions this issue: crypto/ecdh: new package

rsc commented 2 years ago

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group

FiloSottile commented 2 years ago

Spec compliance summary

There are broadly three publishers of relevant specifications that matter to us: NIST, ANSI, and SECG. NIST makes open standards for the US government, ANSI makes paywalled standards for the banking industry, and SECG made a couple open standards. NIST standards cited ANSI standards until recently, while SECG effectively made open versions of them.

NIST Draft FIPS 186-5 specifies ECDSA. FIPS 186-4 (2013) used to reference ANSI X9.62 (2005). NIST SP 800-56A Rev. 3 (2018) specifies ECDH. Rev. 2 (2013) used to reference ANSI X9.63 (2011). SEC 1, Version 2.0 (2009) profiles all of the above. See Appendix B.6 of SEC 1 for an extensive discussion of its interoperability.

NIST P curves are defined in Appendix D of FIPS 186-4, in Draft NIST SP 800-186, and in SEC 2, Version 2.0 (2010).

We reference SEC 1, Version 2.0 and FIPS 186-4, but we target a subset that is compatible with all of them 🎉

FiloSottile commented 2 years ago

Compressed points

In #34105, we added support for MarshalCompressed and UnmarshalCompressed to crypto/elliptic. It would seem logical to support compressed points in crypto/ecdh, too.

If we want to support them, I would propose adding

func (k *PublicKey) BytesCompressed() []byte
type Curve interface {
    NewPublicKeyFromCompressed(key []byte) (*PublicKey, error)
}

Technically, we could just make Curve.NewPublicKey support both compressed and uncompressed encodings, as they have different type prefixes. However, it’s unlikely that any application wishes to support both at the same time, and this would force every user (including our own crypto/tls) to check the prefix before calling NewPublicKey.

A wrinkle is that technically speaking all X25519 public keys are compressed. So, Bytes/BytesCompressed and NewPublicKey/NewPublicKeyFromCompressed would do the same thing for X25519.

An option I like is to not add these methods now, and wait some time to see if the requirement materializes, and in what shape.

FiloSottile commented 2 years ago

CryptoKit compatibility

A few people mentioned needing interoperability with Apple’s CryptoKit.

I played with it in the Swift Playground to figure out what its encodings are, because the docs are very intent on being vague about it.

The summary is that for public keys, their x963Representation is what our Bytes() method generates, their rawRepresentation is just x963Representation without the 0x04 prefix, and their compactRepresentation is what our BytesCompressed() would return without the 0x02/0x03 prefix.

“But wait”, you’ll say, “that prefix conveys an important bit of information!” Uh, I agree? Looking at the implementation reveals that this follows an expired 2014 IETF draft, draft-jivsov-ecc-compact-05, which basically says… to make sure the key always has a lexicographically lower Y coordinate. Indeed, CryptoKit will loop until it finds such a key, unless compactRepresentable: false is used in init, in which case publicKey.compactRepresentation might fail. Now, that makes me sad because it doesn’t match the disambiguation that all other specs use (which switch on the least significant bit, not on lexicographical order that corresponds to the most significant bit instead), so you can’t just say “always add or remove a 0x20 prefix”. However, since the ECDH operation only returns the x coordinate, the y coordinate doesn’t really matter: if you always use a 0x20 prefix you have a 50% chance of being wrong, but the ECDH output will be correct either way.

For private keys, their rawRepresentation is what our Bytes() method generates, and their x963Representation is the concatenation of PublicKey.Bytes() and Bytes(). The shared secret is what our ECDH() method returns. The PEM/DER encodings are the PKCS#8 and PKIX formats we support in crypto/x509.

In summary, it takes some tweaking but the proposed APIs are compatible with CryptoKit. If we implement the compressed encoding, it will be possible to support the Apple compactRepresentation with some tweaking and approximation. Otherwise, we’ll support only the x963Representation and rawRepresentation.

``` import CryptoKit import Foundation let key = P256.KeyAgreement.PrivateKey() print(key.pemRepresentation) print(key.publicKey.pemRepresentation) print("// Raw private key,", key.rawRepresentation) print(key.rawRepresentation.base64EncodedString()) print("// X9.63 private key,", key.x963Representation) print(key.x963Representation.base64EncodedString()) print("// Raw public key,", key.publicKey.rawRepresentation) print(key.publicKey.rawRepresentation.base64EncodedString()) print("// Compact public key,", key.publicKey.compactRepresentation) print(key.publicKey.compactRepresentation!.base64EncodedString()) print("// X9.63 public key,", key.publicKey.x963Representation) print(key.publicKey.x963Representation.base64EncodedString()) try key.sharedSecretFromKeyAgreement(with: key.publicKey).withUnsafeBytes{ print("// Raw shared secret,", Data(Array($0))) print(Data(Array($0)).base64EncodedString()) } ``` ``` -----BEGIN PRIVATE KEY----- MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQgDmJcofW/gvmaAind jjIEAWGyZ24MKbb5VDvjHzZL60mhRANCAATFC9iQkp8dYI5EiWXi2APCusnMtNEr c00/Frv3gbfSzTE6SX8NKEjM6JaO7c1w2rO5MRzgn+iJA8KFijctsPi/ -----END PRIVATE KEY----- -----BEGIN PUBLIC KEY----- MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAExQvYkJKfHWCORIll4tgDwrrJzLTR K3NNPxa794G30s0xOkl/DShIzOiWju3NcNqzuTEc4J/oiQPChYo3LbD4vw== -----END PUBLIC KEY----- // Raw private key, 32 bytes DmJcofW/gvmaAindjjIEAWGyZ24MKbb5VDvjHzZL60k= // X9.63 private key, 97 bytes BMUL2JCSnx1gjkSJZeLYA8K6ycy00StzTT8Wu/eBt9LNMTpJfw0oSMzolo7tzXDas7kxHOCf6IkDwoWKNy2w+L8OYlyh9b+C+ZoCKd2OMgQBYbJnbgwptvlUO+MfNkvrSQ== // Raw public key, 64 bytes xQvYkJKfHWCORIll4tgDwrrJzLTRK3NNPxa794G30s0xOkl/DShIzOiWju3NcNqzuTEc4J/oiQPChYo3LbD4vw== // Compact public key, Optional(32 bytes) xQvYkJKfHWCORIll4tgDwrrJzLTRK3NNPxa794G30s0= // X9.63 public key, 65 bytes BMUL2JCSnx1gjkSJZeLYA8K6ycy00StzTT8Wu/eBt9LNMTpJfw0oSMzolo7tzXDas7kxHOCf6IkDwoWKNy2w+L8= // Raw shared secret, 32 bytes Jeh6s9Kz5HWtCik8jzfPL1qbmg53PyEtt2fS8LEEtjY= ```

FiloSottile commented 2 years ago

I made a small change to the proposed API: the PublicKey embedded in PrivateKey is gone, so now NewPrivateKey doesn't have to generate the public key every time, which is an expensive operation. This doesn't matter in ephemeral ECDH, because the public key needs to be generated and set to the peer, but for static ECDH it would have been unnecessary overhead.

Instead, we now have these two methods on PrivateKey, where the PublicKey will compute the public key with a sync.Once. The Curve method is just because it's not visible through the embedding anymore.

func (k *PrivateKey) Curve() Curve
func (k *PrivateKey) PublicKey() *PublicKey

PublicKey() gets away with not returning an error because in X25519 the operation can always succeed, and with NIST curves it only fails (well, return an irregular encoding) for the identity element, which can only happen for the zero key, which we reject in NewPrivateKey.

Why both Public() and PublicKey()? The latter returns a *PublicKey, while the former returns a crypto.PublicKey to implement the informal crypto.PrivateKey interface.

interface{
    Public() crypto.PublicKey
    Equal(x crypto.PrivateKey) bool
}

elagergren-spideroak commented 2 years ago

PublicKey() gets away with not returning an error because in X25519 the operation can always succeed, and with NIST curves it only fails (well, return an irregular encoding) for the identity element, which can only happen for the zero key, which we reject in NewPrivateKey.

In other words PublicKey can panic? (Thinking about BoringCrypto and other similar implementations.)

FiloSottile commented 2 years ago

PublicKey() gets away with not returning an error because in X25519 the operation can always succeed, and with NIST curves it only fails (well, return an irregular encoding) for the identity element, which can only happen for the zero key, which we reject in NewPrivateKey.

In other words PublicKey can panic? (Thinking about BoringCrypto and other similar implementations.)

No, as long as the semantics of NewPrivateKey are correctly implemented (that is, the zero scalar is rejected, as it's documented to do), PublicKey() can't hit the panic conditions. BoringCrypto is expected to follow those semantics.

elagergren-spideroak commented 2 years ago

@FiloSottile I don't know what Go's BoringCrypto ECDH will look like since it doesn't exist yet, but I'm looking at mine right now and there are 5 spots where it can "fail":

EC_POINT_new returns NULL
EC_POINT_set_affine_coordinates_GFp returns false (zero)
EC_KEY_new_by_curve_name returns NULL
EC_KEY_set_private_key returns false (zero)
ECDH_compute_key returns an invalid length

Maybe I'm missing something or being too pessimistic, but those cases seem unavoidable.

gopherbot commented 2 years ago

Change https://go.dev/cl/404276 mentions this issue: crypto/ecdh: implement compressed points

FiloSottile commented 2 years ago

@elagergren-spideroak hmm, EC_POINT_new should only fail on a malloc failure, EC_POINT_set_affine_coordinates_GFp should not fail for a point that is known to be valid, EC_KEY_new_by_curve_name should not fail for a curve that is known to be supported, EC_KEY_set_private_key should not fail for a private key that is known to be good, and ECDH_compute_key should not return an invalid length unless the private key is zero which must be rejected by NewPrivateKey.

In general, I don't think we should make the Go API significantly harder to use to accommodate cgo reimplementations, but in this specific case I think panic'ing would be fine because those cases would be unreachable.

Otherwise, cgo reimplementations are free to do all the work in NewPrivateKey (which returns an error) and just take the performance hit.

elagergren-spideroak commented 2 years ago

@FiloSottile yeah, so I also agree that PublicKey shouldn't return an error. But it does mean that PublicKey isn't exactly panic free (in the way that the Go implementations are panic free).

Like I mentioned, it's possible I'm being overly pessimistic here. BoringSSL is great, but I've also seen too many "that can't happen" failures from other C cryptography libraries I've written cgo for. 🤷‍♀️

FiloSottile commented 2 years ago

At the end of the day, cgo backends are a tradeoff in simplicity, performance, and reliability against compliance, so yeah :)

FiloSottile commented 2 years ago

The CLs for crypto/ecdh are ready and reviewed: https://go.dev/cl/398914 and https://go.dev/cl/402555.

https://go.dev/cl/404276 implements compressed points per https://github.com/golang/go/issues/52221#issuecomment-1111153164, but I've decided to wait to land it. They add complexity and we can always add them in Go 1.20.

gopherbot commented 2 years ago

Change https://go.dev/cl/402555 mentions this issue: crypto/ecdh,crypto/internal/nistec: enable pruning of unused curves

FiloSottile commented 2 years ago

Encoding and decoding keys

ECDH public and private keys are encoded exactly like ECDSA keys (as PKIX and PKCS#8, respectively), so we already have parsers and encoders for them in crypto/x509, but they return *ecdsa.PublicKey and *ecdsa.PrivateKey. There are two options: add methods to the ECDSA key types to convert them to the ECDH key types, or duplicate the parsers and encoders in crypto/ecdh.

It will be hard to preserve the property that "if you only use curve X, the implementation of curve Y is not reachable" property when using generic encoders/decoders, because they are expected to be capable of returning any curve based on the OID in the encoding. Unless we make them methods on Curve and make them support only one curve at a time, which would be a nice nudge towards avoiding needless agility.

We could also do both. Like compressed points, I'm suggesting leaving it for Go 1.20, as we can always add more things, and so we have time to collect feedback and look at early adopters, too.

awnumar commented 2 years ago

@FiloSottile

Why both Public() and PublicKey()? The latter returns a *PrivateKey, while the former returns a crypto.PublicKey to implement the informal crypto.PrivateKey interface.

Do you mean PublicKey() returns a *PublicKey?

This part of the proposed API seems confusing to me. It's not clear when to use which of the two methods, or why there are PrivateKeys returned in the PublicKey methods. Could the method names be made more clear?

ECDH public and private keys are encoded exactly like ECDSA keys (as PKIX and PKCS#8, respectively), so we already have parsers and encoders for them in crypto/x509, but they return ecdsa.PublicKey and ecdsa.PrivateKey.

When using crypto/elliptic to implement ECDH, it's currently necessary to import the *ecdsa.{PublicKey, PrivateKey} types which is already a little strange. Ideally there'd be a generic *ec.{PublicKey, PrivateKey} type shared by the ecdh, ecdsa, and x509 packages (but this is obviously not possible now due to breaking changes).

There are two options: add methods to the ECDSA key types to convert them to the ECDH key types, or duplicate the parsers and encoders in crypto/ecdh.

If we go with option A it'd be useful to be able to convert in either direction. With option B it's somewhat strange to have different ways of encoding/decoding ecdh and ecdsa keys (through methods vs. calling crypto/x509)

FiloSottile commented 2 years ago

Why both Public() and PublicKey()? The latter returns a *PrivateKey, while the former returns a crypto.PublicKey to implement the informal crypto.PrivateKey interface.

Do you mean PublicKey() returns a *PublicKey?

This part of the proposed API seems confusing to me. It's not clear when to use which of the two methods, or why there are PrivateKeys returned in the PublicKey methods. Could the method names be made more clear?

Typo! Yeah I meant it returns a *PublicKey like in the API listing in the top comment.

func (k *PrivateKey) PublicKey() *PublicKey

ECDH public and private keys are encoded exactly like ECDSA keys (as PKIX and PKCS#8, respectively), so we already have parsers and encoders for them in crypto/x509, but they return ecdsa.PublicKey and ecdsa.PrivateKey.

When using crypto/elliptic to implement ECDH, it's currently necessary to import the *ecdsa.{PublicKey, PrivateKey} types which is already a little strange. Ideally there'd be a generic *ec.{PublicKey, PrivateKey} type shared by the ecdh, ecdsa, and x509 packages (but this is obviously not possible now due to breaking changes).

There are two options: add methods to the ECDSA key types to convert them to the ECDH key types, or duplicate the parsers and encoders in crypto/ecdh.

If we go with option A it'd be useful to be able to convert in either direction. With option B it's somewhat strange to have different ways of encoding/decoding ecdh and ecdsa keys (through methods vs. calling crypto/x509)

I agree it would be a bit weird, but the crypto/ecdsa types force a round-trip through big.Int which is unfortunate, and it would be nice to have a way to avoid it. We also want to avoid making crypto/ecdh depend on math/big at all.

rsc commented 2 years ago

Does anyone object to the API as proposed?

rsc commented 2 years ago

Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group

rsc commented 2 years ago

No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — rsc for the proposal review group

elagergren-spideroak commented 2 years ago

@FiloSottile is Curve safe for comparison?

FiloSottile commented 2 years ago

Yeah, they are comparable singletons like elliptic.Curve values. We should document that.

ericlagergren commented 2 years ago

@FiloSottile thanks. Another thing that could be useful is some sort of String method to print out the name of the curve. I've been playing with the API and found myself wanting to include it in logs, etc.

FiloSottile commented 2 years ago

Yeah, they are comparable singletons like elliptic.Curve values. We should document that.

From the docs of the P256(), P384(), and P521() functions:

Multiple invocations of this function will return the same value, so it can be used for equality checks and switch statements.

Added String functions to the Curve implementations (but not to the interface). Not an exposed API change, so I guess we don't need to go through the proposal process again.

ericlagergren commented 2 years ago

@FiloSottile thanks!

gopherbot commented 1 year ago

Change https://go.dev/cl/450816 mentions this issue: crypto/ecdsa,crypto/x509: add encoding paths for NIST crypto/ecdh keys

gopherbot commented 1 year ago

Change https://go.dev/cl/451115 mentions this issue: curve25519: use crypto/ecdh on Go 1.20

gopherbot commented 1 year ago

Change https://go.dev/cl/453256 mentions this issue: crypto/elliptic: remove deprecation markers

gopherbot commented 1 year ago

Change https://go.dev/cl/459977 mentions this issue: crypto/elliptic: re-apply some deprecation markers

ProtoGhost commented 1 year ago

cannot find package "crypto/ecdh" in any of:

ProtoGhost commented 1 year ago

how to fix it

markuspeloquin commented 8 months ago

Change https://go.dev/cl/404276 mentions this issue: crypto/ecdh: implement compressed points

@FiloSottile What ever happened to this? Currently we have to pass compressed bytes through elliptic.UnmarshalCompressed and the deprecated elliptic.Marshal just to use crypto/ecdh.

golang / go