crypto/x509: memorize chain building.

I ran the new verification code against a large number of certificates
with a huge (>1000) number of intermediates.

I had previously convinced myself that a cycle in the certificate
graph implied a cycle in the hash graph (and thus, a contradiction).
This is bogus because the signatures don't cover each other.

Secondly, I managed to drive the verification into a time explosion
with a fully connected graph of certificates. The code would try to
walk the factorial number of paths.

This change switches the CertPool to dealing with indexes of
certificates rather than pointers: this makes equality easy. (I didn't
want to compare pointers because a reasonable gc could move objects
around over time.)

Secondly, verification now memorizes the chains from a given
certificate. This is dynamic programming for the lazy, but there's a
solid reason behind it: dynamic programming would ignore the Issuer
hints that we can exploit by walking up the chain rather than down.

R=bradfitzgo
CC=golang-dev
https://golang.org/cl/4439070

3 files changed, 39 insertions, 17 deletions

diff --git a/src/pkg/crypto/x509/cert_pool.go b/src/pkg/crypto/x509/cert_pool.go
index 7de8dfa2ec..c295fd97e8 100644
--- a/src/pkg/crypto/x509/cert_pool.go
+++ b/src/pkg/crypto/x509/cert_pool.go
@@ -11,15 +11,17 @@ import (
 
 // Roots is a set of certificates.
 type CertPool struct {
-	bySubjectKeyId map[string][]*Certificate
-	byName         map[string][]*Certificate
+	bySubjectKeyId map[string][]int
+	byName         map[string][]int
+	certs          []*Certificate
 }
 
 // NewCertPool returns a new, empty CertPool.
 func NewCertPool() *CertPool {
 	return &CertPool{
-		make(map[string][]*Certificate),
-		make(map[string][]*Certificate),
+		make(map[string][]int),
+		make(map[string][]int),
+		nil,
 	}
 }
 
@@ -27,11 +29,11 @@ func nameToKey(name *Name) string {
 	return strings.Join(name.Country, ",") + "/" + strings.Join(name.Organization, ",") + "/" + strings.Join(name.OrganizationalUnit, ",") + "/" + name.CommonName
 }
 
-// FindVerifiedParents attempts to find certificates in s which have signed the
+// findVerifiedParents attempts to find certificates in s which have signed the
 // given certificate. If no such certificate can be found or the signature
 // doesn't match, it returns nil.
-func (s *CertPool) FindVerifiedParents(cert *Certificate) (parents []*Certificate) {
-	var candidates []*Certificate
+func (s *CertPool) findVerifiedParents(cert *Certificate) (parents []int) {
+	var candidates []int
 
 	if len(cert.AuthorityKeyId) > 0 {
 		candidates = s.bySubjectKeyId[string(cert.AuthorityKeyId)]
@@ -41,7 +43,7 @@ func (s *CertPool) FindVerifiedParents(cert *Certificate) (parents []*Certificat
 	}
 
 	for _, c := range candidates {
-		if cert.CheckSignatureFrom(c) == nil {
+		if cert.CheckSignatureFrom(s.certs[c]) == nil {
 			parents = append(parents, c)
 		}
 	}
@@ -51,12 +53,26 @@ func (s *CertPool) FindVerifiedParents(cert *Certificate) (parents []*Certificat
 
 // AddCert adds a certificate to a pool.
 func (s *CertPool) AddCert(cert *Certificate) {
+	if cert == nil {
+		panic("adding nil Certificate to CertPool")
+	}
+
+	// Check that the certificate isn't being added twice.
+	for _, c := range s.certs {
+		if c.Equal(cert) {
+			return
+		}
+	}
+
+	n := len(s.certs)
+	s.certs = append(s.certs, cert)
+
 	if len(cert.SubjectKeyId) > 0 {
 		keyId := string(cert.SubjectKeyId)
-		s.bySubjectKeyId[keyId] = append(s.bySubjectKeyId[keyId], cert)
+		s.bySubjectKeyId[keyId] = append(s.bySubjectKeyId[keyId], n)
 	}
 	name := nameToKey(&cert.Subject)
-	s.byName[name] = append(s.byName[name], cert)
+	s.byName[name] = append(s.byName[name], n)
 }
 
 // AppendCertsFromPEM attempts to parse a series of PEM encoded root
diff --git a/src/pkg/crypto/x509/verify.go b/src/pkg/crypto/x509/verify.go
index df3e2ec298..9145880a23 100644
--- a/src/pkg/crypto/x509/verify.go
+++ b/src/pkg/crypto/x509/verify.go
@@ -151,7 +151,7 @@ func (c *Certificate) Verify(opts VerifyOptions) (chains [][]*Certificate, err o
 			return
 		}
 	}
-	return c.buildChains([]*Certificate{c}, &opts)
+	return c.buildChains(make(map[int][][]*Certificate), []*Certificate{c}, &opts)
 }
 
 func appendToFreshChain(chain []*Certificate, cert *Certificate) []*Certificate {
@@ -161,8 +161,9 @@ func appendToFreshChain(chain []*Certificate, cert *Certificate) []*Certificate
 	return n
 }
 
-func (c *Certificate) buildChains(currentChain []*Certificate, opts *VerifyOptions) (chains [][]*Certificate, err os.Error) {
-	for _, root := range opts.Roots.FindVerifiedParents(c) {
+func (c *Certificate) buildChains(cache map[int][][]*Certificate, currentChain []*Certificate, opts *VerifyOptions) (chains [][]*Certificate, err os.Error) {
+	for _, rootNum := range opts.Roots.findVerifiedParents(c) {
+		root := opts.Roots.certs[rootNum]
 		err = root.isValid(rootCertificate, opts)
 		if err != nil {
 			continue
@@ -170,13 +171,18 @@ func (c *Certificate) buildChains(currentChain []*Certificate, opts *VerifyOptio
 		chains = append(chains, appendToFreshChain(currentChain, root))
 	}
 
-	for _, intermediate := range opts.Intermediates.FindVerifiedParents(c) {
+	for _, intermediateNum := range opts.Intermediates.findVerifiedParents(c) {
+		intermediate := opts.Intermediates.certs[intermediateNum]
 		err = intermediate.isValid(intermediateCertificate, opts)
 		if err != nil {
 			continue
 		}
 		var childChains [][]*Certificate
-		childChains, err = intermediate.buildChains(appendToFreshChain(currentChain, intermediate), opts)
+		childChains, ok := cache[intermediateNum]
+		if !ok {
+			childChains, err = intermediate.buildChains(cache, appendToFreshChain(currentChain, intermediate), opts)
+			cache[intermediateNum] = childChains
+		}
 		chains = append(chains, childChains...)
 	}
 
diff --git a/src/pkg/crypto/x509/verify_test.go b/src/pkg/crypto/x509/verify_test.go
index ca9f91381a..6a103dcfba 100644
--- a/src/pkg/crypto/x509/verify_test.go
+++ b/src/pkg/crypto/x509/verify_test.go
@@ -137,7 +137,7 @@ func TestVerify(t *testing.T) {
 		for j, root := range test.roots {
 			ok := opts.Roots.AppendCertsFromPEM([]byte(root))
 			if !ok {
-				t.Error("#%d: failed to parse root #%d", i, j)
+				t.Errorf("#%d: failed to parse root #%d", i, j)
 				return
 			}
 		}
@@ -145,7 +145,7 @@ func TestVerify(t *testing.T) {
 		for j, intermediate := range test.intermediates {
 			ok := opts.Intermediates.AppendCertsFromPEM([]byte(intermediate))
 			if !ok {
-				t.Error("#%d: failed to parse intermediate #%d", i, j)
+				t.Errorf("#%d: failed to parse intermediate #%d", i, j)
 				return
 			}
 		}