crypto/x509: fix signature checking limit

We added the "is this cert already in the chain" check (alreadyInChain)
to considerCandidates before the signature limit. considerCandidates
bails out when we exceed the signature check, but buildChains keeps
calling considerCandidates until it exhausts all potential parents. In
the case where a large number of certificates look to have signed each
other (e.g. all have subject==issuerSubject and the same key),
alreadyInChain is not particularly cheap, meaning even though we hit our
"this is too much work" limit, we still do a lot of work.

Move alreadyInChain after the signature limit, and also return a
sentinel error, and check it in buildChains so we can break out of the
loop early if we aren't actually going to do any more work.

Thanks to Jakub Ciolek for reporting this issue.

Fixes #78282
Fixes CVE-2026-32280

Change-Id: Ie6f05c6ba3b0a40c21f64f7c4f846e74fae3b10e
Reviewed-on: https://go-review.googlesource.com/c/go/+/758320
Reviewed-by: Damien Neil <dneil@google.com>
Reviewed-by: Neal Patel <nealpatel@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Jakub Ciolek <jakub@ciolek.dev>

2 files changed, 92 insertions, 81 deletions

diff --git a/src/crypto/x509/verify.go b/src/crypto/x509/verify.go
index 5f4fc0b6f3..8151a73125 100644
--- a/src/crypto/x509/verify.go
+++ b/src/crypto/x509/verify.go
@@ -720,6 +720,8 @@ func alreadyInChain(candidate *Certificate, chain []*Certificate) bool {
 // for failed checks due to different intermediates having the same Subject.
 const maxChainSignatureChecks = 100
 
+var errSignatureLimit = errors.New("x509: signature check attempts limit reached while verifying certificate chain")
+
 func (c *Certificate) buildChains(currentChain []*Certificate, sigChecks *int, opts *VerifyOptions) (chains [][]*Certificate, err error) {
 	var (
 		hintErr  error
@@ -727,16 +729,16 @@ func (c *Certificate) buildChains(currentChain []*Certificate, sigChecks *int, o
 	)
 
 	considerCandidate := func(certType int, candidate potentialParent) {
-		if candidate.cert.PublicKey == nil || alreadyInChain(candidate.cert, currentChain) {
-			return
-		}
-
 		if sigChecks == nil {
 			sigChecks = new(int)
 		}
 		*sigChecks++
 		if *sigChecks > maxChainSignatureChecks {
-			err = errors.New("x509: signature check attempts limit reached while verifying certificate chain")
+			err = errSignatureLimit
+			return
+		}
+
+		if candidate.cert.PublicKey == nil || alreadyInChain(candidate.cert, currentChain) {
 			return
 		}
 
@@ -777,11 +779,20 @@ func (c *Certificate) buildChains(currentChain []*Certificate, sigChecks *int, o
 		}
 	}
 
-	for _, root := range opts.Roots.findPotentialParents(c) {
-		considerCandidate(rootCertificate, root)
-	}
-	for _, intermediate := range opts.Intermediates.findPotentialParents(c) {
-		considerCandidate(intermediateCertificate, intermediate)
+candidateLoop:
+	for _, parents := range []struct {
+		certType   int
+		potentials []potentialParent
+	}{
+		{rootCertificate, opts.Roots.findPotentialParents(c)},
+		{intermediateCertificate, opts.Intermediates.findPotentialParents(c)},
+	} {
+		for _, parent := range parents.potentials {
+			considerCandidate(parents.certType, parent)
+			if err == errSignatureLimit {
+				break candidateLoop
+			}
+		}
 	}
 
 	if len(chains) > 0 {
diff --git a/src/crypto/x509/verify_test.go b/src/crypto/x509/verify_test.go
index f9bd313737..1d3e845d0f 100644
--- a/src/crypto/x509/verify_test.go
+++ b/src/crypto/x509/verify_test.go
@@ -1529,10 +1529,13 @@ func TestValidHostname(t *testing.T) {
 	}
 }
 
-func generateCert(cn string, isCA bool, issuer *Certificate, issuerKey crypto.PrivateKey) (*Certificate, crypto.PrivateKey, error) {
-	priv, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
-	if err != nil {
-		return nil, nil, err
+func generateCert(cn string, isCA bool, issuer *Certificate, issuerKey crypto.PrivateKey, priv crypto.PrivateKey) (*Certificate, crypto.PrivateKey, error) {
+	if priv == nil {
+		var err error
+		priv, err = ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
+		if err != nil {
+			return nil, nil, err
+		}
 	}
 
 	serialNumberLimit := new(big.Int).Lsh(big.NewInt(1), 128)
@@ -1543,6 +1546,7 @@ func generateCert(cn string, isCA bool, issuer *Certificate, issuerKey crypto.Pr
 		Subject:      pkix.Name{CommonName: cn},
 		NotBefore:    time.Now().Add(-1 * time.Hour),
 		NotAfter:     time.Now().Add(24 * time.Hour),
+		DNSNames:     []string{rand.Text()},
 
 		KeyUsage:              KeyUsageKeyEncipherment | KeyUsageDigitalSignature | KeyUsageCertSign,
 		ExtKeyUsage:           []ExtKeyUsage{ExtKeyUsageServerAuth},
@@ -1554,7 +1558,7 @@ func generateCert(cn string, isCA bool, issuer *Certificate, issuerKey crypto.Pr
 		issuerKey = priv
 	}
 
-	derBytes, err := CreateCertificate(rand.Reader, template, issuer, priv.Public(), issuerKey)
+	derBytes, err := CreateCertificate(rand.Reader, template, issuer, priv.(crypto.Signer).Public(), issuerKey)
 	if err != nil {
 		return nil, nil, err
 	}
@@ -1566,81 +1570,77 @@ func generateCert(cn string, isCA bool, issuer *Certificate, issuerKey crypto.Pr
 	return cert, priv, nil
 }
 
-func TestPathologicalChain(t *testing.T) {
+func TestPathologicalChains(t *testing.T) {
 	if testing.Short() {
-		t.Skip("skipping generation of a long chain of certificates in short mode")
-	}
-
-	// Build a chain where all intermediates share the same subject, to hit the
-	// path building worst behavior.
-	roots, intermediates := NewCertPool(), NewCertPool()
-
-	parent, parentKey, err := generateCert("Root CA", true, nil, nil)
-	if err != nil {
-		t.Fatal(err)
-	}
-	roots.AddCert(parent)
-
-	for i := 1; i < 100; i++ {
-		parent, parentKey, err = generateCert("Intermediate CA", true, parent, parentKey)
-		if err != nil {
-			t.Fatal(err)
-		}
-		intermediates.AddCert(parent)
+		t.Skip("skipping generation of a long chains of certificates in short mode")
 	}
 
-	leaf, _, err := generateCert("Leaf", false, parent, parentKey)
-	if err != nil {
-		t.Fatal(err)
-	}
-
-	start := time.Now()
-	_, err = leaf.Verify(VerifyOptions{
-		Roots:         roots,
-		Intermediates: intermediates,
-	})
-	t.Logf("verification took %v", time.Since(start))
-
-	if err == nil || !strings.Contains(err.Error(), "signature check attempts limit") {
-		t.Errorf("expected verification to fail with a signature checks limit error; got %v", err)
-	}
-}
-
-func TestLongChain(t *testing.T) {
-	if testing.Short() {
-		t.Skip("skipping generation of a long chain of certificates in short mode")
-	}
+	// Test four pathological cases, where the intermediates in the chain have
+	// the same/different subjects and the same/different keys. This covers a
+	// number of cases where the chain building algorithm might be inefficient,
+	// such as when there are many intermediates with the same subject but
+	// different keys, many intermediates with the same key but different
+	// subjects, many intermediates with the same subject and key, or many
+	// intermediates with different subjects and keys.
+	//
+	// The worst case for our algorithm is when all of the intermediates share
+	// both subject and key, in which case all of the intermediates appear to
+	// have signed each other, causing us to see a large number of potential
+	// parents for each intermediate.
+	//
+	// All of these cases, Certificate.Verify should return errSignatureLimit.
+	//
+	// In all cases, don't have a root in the pool, so a valid chain cannot actually be built.
 
-	roots, intermediates := NewCertPool(), NewCertPool()
+	for _, test := range []struct {
+		sameSubject bool
+		sameKey     bool
+	}{
+		{sameSubject: false, sameKey: false},
+		{sameSubject: true, sameKey: false},
+		{sameSubject: false, sameKey: true},
+		{sameSubject: true, sameKey: true},
+	} {
+		t.Run(fmt.Sprintf("sameSubject=%t,sameKey=%t", test.sameSubject, test.sameKey), func(t *testing.T) {
+			intermediates := NewCertPool()
 
-	parent, parentKey, err := generateCert("Root CA", true, nil, nil)
-	if err != nil {
-		t.Fatal(err)
-	}
-	roots.AddCert(parent)
+			var intermediateKey crypto.PrivateKey
+			if test.sameKey {
+				var err error
+				intermediateKey, err = ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
+				if err != nil {
+					t.Fatal(err)
+				}
+			}
 
-	for i := 1; i < 15; i++ {
-		name := fmt.Sprintf("Intermediate CA #%d", i)
-		parent, parentKey, err = generateCert(name, true, parent, parentKey)
-		if err != nil {
-			t.Fatal(err)
-		}
-		intermediates.AddCert(parent)
-	}
+			var leafSigner crypto.PrivateKey
+			var intermediate *Certificate
+			for i := range 100 {
+				cn := "Intermediate CA"
+				if !test.sameSubject {
+					cn += fmt.Sprintf(" #%d", i)
+				}
+				var err error
+				intermediate, leafSigner, err = generateCert(cn, true, intermediate, leafSigner, intermediateKey)
+				if err != nil {
+					t.Fatal(err)
+				}
+				intermediates.AddCert(intermediate)
+			}
 
-	leaf, _, err := generateCert("Leaf", false, parent, parentKey)
-	if err != nil {
-		t.Fatal(err)
-	}
+			leaf, _, err := generateCert("Leaf", false, intermediate, leafSigner, nil)
+			if err != nil {
+				t.Fatal(err)
+			}
 
-	start := time.Now()
-	if _, err := leaf.Verify(VerifyOptions{
-		Roots:         roots,
-		Intermediates: intermediates,
-	}); err != nil {
-		t.Error(err)
+			start := time.Now()
+			_, err = leaf.Verify(VerifyOptions{
+				Roots:         NewCertPool(),
+				Intermediates: intermediates,
+			})
+			t.Logf("verification took %v", time.Since(start))
+		})
 	}
-	t.Logf("verification took %v", time.Since(start))
 }
 
 func TestSystemRootsError(t *testing.T) {