crypto/ecdh: new package

[FiloSottile]

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 cmd/compile: inlining after devirtualization #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]

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

[rsc]

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]

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]

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]

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]

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]

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]

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]

@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":

1. EC_POINT_new returns NULL
2. EC_POINT_set_affine_coordinates_GFp returns false (zero)
3. EC_KEY_new_by_curve_name returns NULL
4. EC_KEY_set_private_key returns false (zero)
5. ECDH_compute_key returns an invalid length

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

[gopherbot]

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

[FiloSottile]

@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.