diff options
author | Filippo Valsorda <filippo@golang.org> | 2022-02-02 09:15:44 -0800 |
---|---|---|
committer | Cherry Mui <cherryyz@google.com> | 2022-02-07 19:24:54 +0000 |
commit | 6b3e741a834c34b8a844a33b3aa060dd4ed37231 (patch) | |
tree | 7babd8fe4425b5e609765d1fe41dc57856625d2e | |
parent | de76489a1b1cfce6b1258040c15b18ed97847758 (diff) | |
download | go-6b3e741a834c34b8a844a33b3aa060dd4ed37231.tar.gz go-6b3e741a834c34b8a844a33b3aa060dd4ed37231.zip |
[release-branch.go1.16] crypto/elliptic: make IsOnCurve return false for invalid field elements
Updates #50974
Fixes #50977
Fixes CVE-2022-23806
Change-Id: I0201c2c88f13dd82910985a495973f1683af9259
Reviewed-on: https://go-review.googlesource.com/c/go/+/382855
Trust: Filippo Valsorda <filippo@golang.org>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Katie Hockman <katie@golang.org>
Trust: Katie Hockman <katie@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
-rw-r--r-- | src/crypto/elliptic/elliptic.go | 5 | ||||
-rw-r--r-- | src/crypto/elliptic/elliptic_test.go | 81 | ||||
-rw-r--r-- | src/crypto/elliptic/p224.go | 5 |
3 files changed, 91 insertions, 0 deletions
diff --git a/src/crypto/elliptic/elliptic.go b/src/crypto/elliptic/elliptic.go index f93dc16419..afedf18df1 100644 --- a/src/crypto/elliptic/elliptic.go +++ b/src/crypto/elliptic/elliptic.go @@ -71,6 +71,11 @@ func (curve *CurveParams) polynomial(x *big.Int) *big.Int { } func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool { + if x.Sign() < 0 || x.Cmp(curve.P) >= 0 || + y.Sign() < 0 || y.Cmp(curve.P) >= 0 { + return false + } + // y² = x³ - 3x + b y2 := new(big.Int).Mul(y, y) y2.Mod(y2, curve.P) diff --git a/src/crypto/elliptic/elliptic_test.go b/src/crypto/elliptic/elliptic_test.go index e80e7731aa..bb16b0d163 100644 --- a/src/crypto/elliptic/elliptic_test.go +++ b/src/crypto/elliptic/elliptic_test.go @@ -721,3 +721,84 @@ func testMarshalCompressed(t *testing.T, curve Curve, x, y *big.Int, want []byte t.Errorf("point did not round-trip correctly: got (%v, %v), want (%v, %v)", X, Y, x, y) } } + +func testAllCurves(t *testing.T, f func(*testing.T, Curve)) { + tests := []struct { + name string + curve Curve + }{ + {"P256", P256()}, + {"P256/Params", P256().Params()}, + {"P224", P224()}, + {"P224/Params", P224().Params()}, + {"P384", P384()}, + {"P384/Params", P384().Params()}, + {"P521", P521()}, + {"P521/Params", P521().Params()}, + } + if testing.Short() { + tests = tests[:1] + } + for _, test := range tests { + curve := test.curve + t.Run(test.name, func(t *testing.T) { + t.Parallel() + f(t, curve) + }) + } +} + +// TestInvalidCoordinates tests big.Int values that are not valid field elements +// (negative or bigger than P). They are expected to return false from +// IsOnCurve, all other behavior is undefined. +func TestInvalidCoordinates(t *testing.T) { + testAllCurves(t, testInvalidCoordinates) +} + +func testInvalidCoordinates(t *testing.T, curve Curve) { + checkIsOnCurveFalse := func(name string, x, y *big.Int) { + if curve.IsOnCurve(x, y) { + t.Errorf("IsOnCurve(%s) unexpectedly returned true", name) + } + } + + p := curve.Params().P + _, x, y, _ := GenerateKey(curve, rand.Reader) + xx, yy := new(big.Int), new(big.Int) + + // Check if the sign is getting dropped. + xx.Neg(x) + checkIsOnCurveFalse("-x, y", xx, y) + yy.Neg(y) + checkIsOnCurveFalse("x, -y", x, yy) + + // Check if negative values are reduced modulo P. + xx.Sub(x, p) + checkIsOnCurveFalse("x-P, y", xx, y) + yy.Sub(y, p) + checkIsOnCurveFalse("x, y-P", x, yy) + + // Check if positive values are reduced modulo P. + xx.Add(x, p) + checkIsOnCurveFalse("x+P, y", xx, y) + yy.Add(y, p) + checkIsOnCurveFalse("x, y+P", x, yy) + + // Check if the overflow is dropped. + xx.Add(x, new(big.Int).Lsh(big.NewInt(1), 535)) + checkIsOnCurveFalse("x+2⁵³⁵, y", xx, y) + yy.Add(y, new(big.Int).Lsh(big.NewInt(1), 535)) + checkIsOnCurveFalse("x, y+2⁵³⁵", x, yy) + + // Check if P is treated like zero (if possible). + // y^2 = x^3 - 3x + B + // y = mod_sqrt(x^3 - 3x + B) + // y = mod_sqrt(B) if x = 0 + // If there is no modsqrt, there is no point with x = 0, can't test x = P. + if yy := new(big.Int).ModSqrt(curve.Params().B, p); yy != nil { + if !curve.IsOnCurve(big.NewInt(0), yy) { + t.Fatal("(0, mod_sqrt(B)) is not on the curve?") + } + checkIsOnCurveFalse("P, y", p, yy) + } +} diff --git a/src/crypto/elliptic/p224.go b/src/crypto/elliptic/p224.go index 8c76021464..ff5c834452 100644 --- a/src/crypto/elliptic/p224.go +++ b/src/crypto/elliptic/p224.go @@ -48,6 +48,11 @@ func (curve p224Curve) Params() *CurveParams { } func (curve p224Curve) IsOnCurve(bigX, bigY *big.Int) bool { + if bigX.Sign() < 0 || bigX.Cmp(curve.P) >= 0 || + bigY.Sign() < 0 || bigY.Cmp(curve.P) >= 0 { + return false + } + var x, y p224FieldElement p224FromBig(&x, bigX) p224FromBig(&y, bigY) |