From 7f9494c277a471f6f47f4af3036285c0b1419816 Mon Sep 17 00:00:00 2001 From: Filippo Valsorda Date: Wed, 2 Feb 2022 09:13:17 -0800 Subject: [PATCH] crypto/elliptic: make IsOnCurve return false for invalid field elements Thanks to Guido Vranken for reporting this issue. Fixes #50974 Fixes CVE-2022-23806 Change-Id: I0201c2c88f13dd82910985a495973f1683af9259 Reviewed-on: https://go-review.googlesource.com/c/go/+/382455 Run-TryBot: Filippo Valsorda TryBot-Result: Gopher Robot Trust: Filippo Valsorda Reviewed-by: Roland Shoemaker Reviewed-by: Katie Hockman Trust: Katie Hockman --- src/crypto/elliptic/elliptic.go | 5 +++ src/crypto/elliptic/elliptic_test.go | 55 ++++++++++++++++++++++++++++ src/crypto/elliptic/p224.go | 3 ++ src/crypto/elliptic/p384.go | 3 ++ src/crypto/elliptic/p521.go | 3 ++ 5 files changed, 69 insertions(+) diff --git a/src/crypto/elliptic/elliptic.go b/src/crypto/elliptic/elliptic.go index c5c5a906c4..7ead09f8d3 100644 --- a/src/crypto/elliptic/elliptic.go +++ b/src/crypto/elliptic/elliptic.go @@ -89,6 +89,11 @@ func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool { return specific.IsOnCurve(x, y) } + 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 f5b36f75ca..5481929db1 100644 --- a/src/crypto/elliptic/elliptic_test.go +++ b/src/crypto/elliptic/elliptic_test.go @@ -182,6 +182,61 @@ func testUnmarshalToLargeCoordinates(t *testing.T, curve 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) + } +} + func TestMarshalCompressed(t *testing.T) { t.Run("P-256/03", func(t *testing.T) { data, _ := hex.DecodeString("031e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79") diff --git a/src/crypto/elliptic/p224.go b/src/crypto/elliptic/p224.go index a8533b85ff..8a431c4769 100644 --- a/src/crypto/elliptic/p224.go +++ b/src/crypto/elliptic/p224.go @@ -61,6 +61,9 @@ func p224PointFromAffine(x, y *big.Int) (p *nistec.P224Point, ok bool) { if x.Sign() == 0 && y.Sign() == 0 { return nistec.NewP224Point(), true } + if x.Sign() < 0 || y.Sign() < 0 { + return nil, false + } if x.BitLen() > 224 || y.BitLen() > 224 { return nil, false } diff --git a/src/crypto/elliptic/p384.go b/src/crypto/elliptic/p384.go index 0fb7471850..33a441d090 100644 --- a/src/crypto/elliptic/p384.go +++ b/src/crypto/elliptic/p384.go @@ -66,6 +66,9 @@ func p384PointFromAffine(x, y *big.Int) (p *nistec.P384Point, ok bool) { if x.Sign() == 0 && y.Sign() == 0 { return nistec.NewP384Point(), true } + if x.Sign() < 0 || y.Sign() < 0 { + return nil, false + } if x.BitLen() > 384 || y.BitLen() > 384 { return nil, false } diff --git a/src/crypto/elliptic/p521.go b/src/crypto/elliptic/p521.go index 6c9eed30e5..6a3ade3c36 100644 --- a/src/crypto/elliptic/p521.go +++ b/src/crypto/elliptic/p521.go @@ -71,6 +71,9 @@ func p521PointFromAffine(x, y *big.Int) (p *nistec.P521Point, ok bool) { if x.Sign() == 0 && y.Sign() == 0 { return nistec.NewP521Point(), true } + if x.Sign() < 0 || y.Sign() < 0 { + return nil, false + } if x.BitLen() > 521 || y.BitLen() > 521 { return nil, false } -- 2.50.0