From 582a6c2db4dfb617e709b7c8d859ff548aee1b1a Mon Sep 17 00:00:00 2001 From: Filippo Valsorda Date: Thu, 25 Aug 2022 12:19:06 +0200 Subject: [PATCH] crypto/ecdh: update ECDH docs and add tests for edge cases Two edge cases that were mentioned in the docs are actually impossible: * For NIST curves, ECDH can't fail, since the zero scalar is rejected by NewPrivateKey, the identity point is rejected by NewPublicKey, and NIST curves are a prime-order group. Let's call the inputs to scalar multiplication k and P, and the order of the group q. If k[P] is the identity, and also q[P] is the identity by definition, then P's order is a divisor of q-k, because k[P] + [q-k]P = q[P] = I P's order is either 1 or q, and can only be a divisor of q-k if it's 1 (so P is the identity), or if k is zero. * For X25519, PrivateKey.PublicKey can't return the all-zero value, since no value is equivalent to zero after clamping. Clamping unsets the lowest three bit, sets the second-to-highest bit, and unsets the top bit; this means that a scalar equivalent to zero needs to be a multiple of 8*q, and needs to be between 2**254 and 2**255-1, but 8*p > 2**255-1. Tests for other exotic edge cases such as non-canonical point encodings, clamping, points on the twist, and low-order components are covered by x/crypto/wycheproof. Change-Id: I731a878c58bd59aee5636211dc0f19ad8cfae9db Reviewed-on: https://go-review.googlesource.com/c/go/+/425463 TryBot-Result: Gopher Robot Reviewed-by: Bryan Mills Run-TryBot: Filippo Valsorda Auto-Submit: Filippo Valsorda Reviewed-by: Russ Cox --- src/crypto/ecdh/ecdh.go | 13 ++- src/crypto/ecdh/ecdh_test.go | 154 +++++++++++++++++++++++++++++++++++ src/crypto/ecdh/nist.go | 37 +++++++-- 3 files changed, 189 insertions(+), 15 deletions(-) diff --git a/src/crypto/ecdh/ecdh.go b/src/crypto/ecdh/ecdh.go index d835b04573..74e198222c 100644 --- a/src/crypto/ecdh/ecdh.go +++ b/src/crypto/ecdh/ecdh.go @@ -18,9 +18,7 @@ type Curve interface { // // 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.) + // Version 2.0, Section 2.3.5. The result is never the point at infinity. // // 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. @@ -37,8 +35,7 @@ type Curve interface { // 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. + // For X25519, this only checks the scalar length. NewPrivateKey(key []byte) (*PrivateKey, error) // NewPublicKey checks that key is valid and returns a PublicKey. @@ -54,9 +51,9 @@ type Curve interface { // privateKeyToPublicKey converts a PrivateKey to a PublicKey. It's exposed // as the PrivateKey.PublicKey method. // - // This method always succeeds: for X25519, it might output the all-zeroes - // value (unlike the ECDH method); for NIST curves, it would only fail for - // the zero private key, which is rejected by NewPrivateKey. + // This method always succeeds: for X25519, the zero key can't be + // constructed due to clamping; for NIST curves, it is rejected by + // NewPrivateKey. // // The private method also allow us to expand the ECDH interface with more // methods in the future without breaking backwards compatibility. diff --git a/src/crypto/ecdh/ecdh_test.go b/src/crypto/ecdh/ecdh_test.go index 5fd690b129..947eef1ef1 100644 --- a/src/crypto/ecdh/ecdh_test.go +++ b/src/crypto/ecdh/ecdh_test.go @@ -195,6 +195,160 @@ func TestString(t *testing.T) { }) } +func TestX25519Failure(t *testing.T) { + identity := hexDecode(t, "0000000000000000000000000000000000000000000000000000000000000000") + lowOrderPoint := hexDecode(t, "e0eb7a7c3b41b8ae1656e3faf19fc46ada098deb9c32b1fd866205165f49b800") + randomScalar := make([]byte, 32) + rand.Read(randomScalar) + + t.Run("identity point", func(t *testing.T) { testX25519Failure(t, randomScalar, identity) }) + t.Run("low order point", func(t *testing.T) { testX25519Failure(t, randomScalar, lowOrderPoint) }) +} + +func testX25519Failure(t *testing.T, private, public []byte) { + priv, err := ecdh.X25519().NewPrivateKey(private) + if err != nil { + t.Fatal(err) + } + pub, err := ecdh.X25519().NewPublicKey(public) + if err != nil { + t.Fatal(err) + } + secret, err := ecdh.X25519().ECDH(priv, pub) + if err == nil { + t.Error("expected ECDH error") + } + if secret != nil { + t.Errorf("unexpected ECDH output: %x", secret) + } +} + +var invalidPrivateKeys = map[ecdh.Curve][]string{ + ecdh.P256(): { + // Bad lengths. + "", + "01", + "01010101010101010101010101010101010101010101010101010101010101", + "000101010101010101010101010101010101010101010101010101010101010101", + strings.Repeat("01", 200), + // Zero. + "0000000000000000000000000000000000000000000000000000000000000000", + // Order of the curve and above. + "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", + "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + }, + ecdh.P384(): { + // Bad lengths. + "", + "01", + "0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101", + "00010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101", + strings.Repeat("01", 200), + // Zero. + "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", + // Order of the curve and above. + "ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973", + "ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52974", + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + }, + ecdh.P521(): { + // Bad lengths. + "", + "01", + "0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101", + "00010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101", + strings.Repeat("01", 200), + // Zero. + "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", + // Order of the curve and above. + "01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409", + "01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e9138640a", + "11fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409", + "03fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff4a30d0f077e5f2cd6ff980291ee134ba0776b937113388f5d76df6e3d2270c812", + }, + ecdh.X25519(): { + // X25519 only rejects bad lengths. + "", + "01", + "01010101010101010101010101010101010101010101010101010101010101", + "000101010101010101010101010101010101010101010101010101010101010101", + strings.Repeat("01", 200), + }, +} + +func TestNewPrivateKey(t *testing.T) { + testAllCurves(t, func(t *testing.T, curve ecdh.Curve) { + for _, input := range invalidPrivateKeys[curve] { + k, err := curve.NewPrivateKey(hexDecode(t, input)) + if err == nil { + t.Errorf("unexpectedly accepted %q", input) + } else if k != nil { + t.Error("PrivateKey was not nil on error") + } + } + }) +} + +var invalidPublicKeys = map[ecdh.Curve][]string{ + ecdh.P256(): { + // Bad lengths. + "", + "04", + strings.Repeat("04", 200), + // Infinity. + "00", + // Compressed encodings. + "036b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", + "02e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852", + // Points not on the curve. + "046b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f6", + "0400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", + }, + ecdh.P384(): { + // Bad lengths. + "", + "04", + strings.Repeat("04", 200), + // Infinity. + "00", + // Compressed encodings. + "03aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", + "0208d999057ba3d2d969260045c55b97f089025959a6f434d651d207d19fb96e9e4fe0e86ebe0e64f85b96a9c75295df61", + // Points not on the curve. + "04aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab73617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e60", + "04000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", + }, + ecdh.P521(): { + // Bad lengths. + "", + "04", + strings.Repeat("04", 200), + // Infinity. + "00", + // Compressed encodings. + "030035b5df64ae2ac204c354b483487c9070cdc61c891c5ff39afc06c5d55541d3ceac8659e24afe3d0750e8b88e9f078af066a1d5025b08e5a5e2fbc87412871902f3", + "0200c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", + // Points not on the curve. + "0400c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16651", + "04000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", + }, + ecdh.X25519(): {}, +} + +func TestNewPublicKey(t *testing.T) { + testAllCurves(t, func(t *testing.T, curve ecdh.Curve) { + for _, input := range invalidPublicKeys[curve] { + k, err := curve.NewPublicKey(hexDecode(t, input)) + if err == nil { + t.Errorf("unexpectedly accepted %q", input) + } else if k != nil { + t.Error("PublicKey was not nil on error") + } + } + }) +} + func testAllCurves(t *testing.T, f func(t *testing.T, curve ecdh.Curve)) { t.Run("P256", func(t *testing.T) { f(t, ecdh.P256()) }) t.Run("P384", func(t *testing.T) { f(t, ecdh.P384()) }) diff --git a/src/crypto/ecdh/nist.go b/src/crypto/ecdh/nist.go index 091d6aec9f..c5d37b5fb2 100644 --- a/src/crypto/ecdh/nist.go +++ b/src/crypto/ecdh/nist.go @@ -154,6 +154,12 @@ func (c *nistCurve[Point]) NewPublicKey(key []byte) (*PublicKey, error) { } func (c *nistCurve[Point]) ECDH(local *PrivateKey, remote *PublicKey) ([]byte, error) { + // Note that this function can't return an error, as NewPublicKey rejects + // invalid points and the point at infinity, and NewPrivateKey rejects + // invalid scalars and the zero value. BytesX returns an error for the point + // at infinity, but in a prime order group such as the NIST curves that can + // only be the result of a scalar multiplication if one of the inputs is the + // zero scalar or the point at infinity. p, err := c.newPoint().SetBytes(remote.publicKey) if err != nil { return nil, err @@ -161,14 +167,13 @@ func (c *nistCurve[Point]) ECDH(local *PrivateKey, remote *PublicKey) ([]byte, e if _, err := p.ScalarMult(p, local.privateKey); err != nil { return nil, err } - // BytesX will return an error if p is the point at infinity. return p.BytesX() } // P256 returns a Curve which implements NIST P-256 (FIPS 186-3, section D.2.3), // also known as secp256r1 or prime256v1. // -// Multiple invocations of this function will return the same value, so it can +// Multiple invocations of this function will return the same value, which can // be used for equality checks and switch statements. func P256() Curve { return p256 } @@ -178,12 +183,16 @@ var p256 = &nistCurve[*nistec.P256Point]{ scalarOrder: p256Order, } -var p256Order = []byte{0xff, 0xff, 0xff, 0xff, 0x0, 0x0, 0x0, 0x0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84, 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51} +var p256Order = []byte{ + 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84, + 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51} // P384 returns a Curve which implements NIST P-384 (FIPS 186-3, section D.2.4), // also known as secp384r1. // -// Multiple invocations of this function will return the same value, so it can +// Multiple invocations of this function will return the same value, which can // be used for equality checks and switch statements. func P384() Curve { return p384 } @@ -193,12 +202,18 @@ var p384 = &nistCurve[*nistec.P384Point]{ scalarOrder: p384Order, } -var p384Order = []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf, 0x58, 0x1a, 0xd, 0xb2, 0x48, 0xb0, 0xa7, 0x7a, 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73} +var p384Order = []byte{ + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf, + 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a, + 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73} // P521 returns a Curve which implements NIST P-521 (FIPS 186-3, section D.2.5), // also known as secp521r1. // -// Multiple invocations of this function will return the same value, so it can +// Multiple invocations of this function will return the same value, which can // be used for equality checks and switch statements. func P521() Curve { return p521 } @@ -208,4 +223,12 @@ var p521 = &nistCurve[*nistec.P521Point]{ scalarOrder: p521Order, } -var p521Order = []byte{0x1, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa, 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b, 0x7f, 0xcc, 0x1, 0x48, 0xf7, 0x9, 0xa5, 0xd0, 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x9} +var p521Order = []byte{0x01, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa, + 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b, + 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0, + 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae, + 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09} -- 2.50.0