crypto/tls: use pool building for certificate checking

Previously we checked the certificate chain from the leaf
upwards and expected to jump from the last cert in the chain to
a root certificate.

Although technically correct, there are a number of sites with
problems including out-of-order certs, superfluous certs and
missing certs.

The last of these requires AIA chasing, which is a lot of
complexity. However, we can address the more common cases by
using a pool building algorithm, as browsers do.

We build a pool of root certificates and a pool from the
server's chain. We then try to build a path to a root
certificate, using either of these pools.

This differs from the behaviour of, say, Firefox in that Firefox
will accumulate intermedite certificate in a persistent pool in
the hope that it can use them to fill in gaps in future chains.

We don't do that because it leads to confusing errors which only
occur based on the order to sites visited.

This change also enabled SNI for tls.Dial so that sites will return
the correct certificate chain.

R=rsc
CC=golang-dev
https://golang.org/cl/2916041

3 files changed, 80 insertions, 52 deletions

diff --git a/src/pkg/crypto/tls/ca_set.go b/src/pkg/crypto/tls/ca_set.go
index d2fb69ced8..fe2a540f4d 100644
--- a/src/pkg/crypto/tls/ca_set.go
+++ b/src/pkg/crypto/tls/ca_set.go
@@ -12,14 +12,14 @@ import (
 
 // A CASet is a set of certificates.
 type CASet struct {
-	bySubjectKeyId map[string]*x509.Certificate
-	byName         map[string]*x509.Certificate
+	bySubjectKeyId map[string][]*x509.Certificate
+	byName         map[string][]*x509.Certificate
 }
 
 func NewCASet() *CASet {
 	return &CASet{
-		make(map[string]*x509.Certificate),
-		make(map[string]*x509.Certificate),
+		make(map[string][]*x509.Certificate),
+		make(map[string][]*x509.Certificate),
 	}
 }
 
@@ -27,13 +27,36 @@ func nameToKey(name *x509.Name) string {
 	return strings.Join(name.Country, ",") + "/" + strings.Join(name.Organization, ",") + "/" + strings.Join(name.OrganizationalUnit, ",") + "/" + name.CommonName
 }
 
-// FindParent attempts to find the certificate in s which signs the given
-// certificate. If no such certificate can be found, it returns nil.
-func (s *CASet) FindParent(cert *x509.Certificate) (parent *x509.Certificate) {
+// FindVerifiedParent attempts to find the certificate in s which has signed
+// the given certificate. If no such certificate can be found or the signature
+// doesn't match, it returns nil.
+func (s *CASet) FindVerifiedParent(cert *x509.Certificate) (parent *x509.Certificate) {
+	var candidates []*x509.Certificate
+
 	if len(cert.AuthorityKeyId) > 0 {
-		return s.bySubjectKeyId[string(cert.AuthorityKeyId)]
+		candidates = s.bySubjectKeyId[string(cert.AuthorityKeyId)]
+	}
+	if len(candidates) == 0 {
+		candidates = s.byName[nameToKey(&cert.Issuer)]
+	}
+
+	for _, c := range candidates {
+		if cert.CheckSignatureFrom(c) == nil {
+			return c
+		}
 	}
-	return s.byName[nameToKey(&cert.Issuer)]
+
+	return nil
+}
+
+// AddCert adds a certificate to the set
+func (s *CASet) AddCert(cert *x509.Certificate) {
+	if len(cert.SubjectKeyId) > 0 {
+		keyId := string(cert.SubjectKeyId)
+		s.bySubjectKeyId[keyId] = append(s.bySubjectKeyId[keyId], cert)
+	}
+	name := nameToKey(&cert.Subject)
+	s.byName[name] = append(s.byName[name], cert)
 }
 
 // SetFromPEM attempts to parse a series of PEM encoded root certificates. It
@@ -57,10 +80,7 @@ func (s *CASet) SetFromPEM(pemCerts []byte) (ok bool) {
 			continue
 		}
 
-		if len(cert.SubjectKeyId) > 0 {
-			s.bySubjectKeyId[string(cert.SubjectKeyId)] = cert
-		}
-		s.byName[nameToKey(&cert.Subject)] = cert
+		s.AddCert(cert)
 		ok = true
 	}
 
diff --git a/src/pkg/crypto/tls/handshake_client.go b/src/pkg/crypto/tls/handshake_client.go
index bef6d20de8..b6b0e0fad3 100644
--- a/src/pkg/crypto/tls/handshake_client.go
+++ b/src/pkg/crypto/tls/handshake_client.go
@@ -77,6 +77,7 @@ func (c *Conn) clientHandshake() os.Error {
 	finishedHash.Write(certMsg.marshal())
 
 	certs := make([]*x509.Certificate, len(certMsg.certificates))
+	chain := NewCASet()
 	for i, asn1Data := range certMsg.certificates {
 		cert, err := x509.ParseCertificate(asn1Data)
 		if err != nil {
@@ -84,50 +85,47 @@ func (c *Conn) clientHandshake() os.Error {
 			return os.ErrorString("failed to parse certificate from server: " + err.String())
 		}
 		certs[i] = cert
+		chain.AddCert(cert)
 	}
 
-	for i := 1; i < len(certs); i++ {
-		if !certs[i].BasicConstraintsValid || !certs[i].IsCA {
-			c.sendAlert(alertBadCertificate)
-			return os.ErrorString("intermediate certificate does not have CA bit set")
+	// If we don't have a root CA set configured then anything is accepted.
+	// TODO(rsc): Find certificates for OS X 10.6.
+	for cur := certs[0]; c.config.RootCAs != nil; {
+		parent := c.config.RootCAs.FindVerifiedParent(cur)
+		if parent != nil {
+			break
 		}
-		// KeyUsage status flags are ignored. From Engineering
-		// Security, Peter Gutmann:
-		// A European government CA marked its signing certificates as
-		// being valid for encryption only, but no-one noticed. Another
-		// European CA marked its signature keys as not being valid for
-		// signatures. A different CA marked its own trusted root
-		// certificate as being invalid for certificate signing.
-		// Another national CA distributed a certificate to be used to
-		// encrypt data for the country’s tax authority that was marked
-		// as only being usable for digital signatures but not for
-		// encryption. Yet another CA reversed the order of the bit
-		// flags in the keyUsage due to confusion over encoding
-		// endianness, essentially setting a random keyUsage in
-		// certificates that it issued. Another CA created a
-		// self-invalidating certificate by adding a certificate policy
-		// statement stipulating that the certificate had to be used
-		// strictly as specified in the keyUsage, and a keyUsage
-		// containing a flag indicating that the RSA encryption key
-		// could only be used for Diffie-Hellman key agreement.
 
-		if err := certs[i-1].CheckSignatureFrom(certs[i]); err != nil {
-			c.sendAlert(alertBadCertificate)
-			return os.ErrorString("could not validate certificate signature: " + err.String())
-		}
-	}
-
-	// TODO(rsc): Find certificates for OS X 10.6.
-	if c.config.RootCAs != nil {
-		root := c.config.RootCAs.FindParent(certs[len(certs)-1])
-		if root == nil {
+		parent = chain.FindVerifiedParent(cur)
+		if parent == nil {
 			c.sendAlert(alertBadCertificate)
 			return os.ErrorString("could not find root certificate for chain")
 		}
-		if err := certs[len(certs)-1].CheckSignatureFrom(root); err != nil {
+
+		if !parent.BasicConstraintsValid || !parent.IsCA {
 			c.sendAlert(alertBadCertificate)
-			return os.ErrorString("could not validate signature from expected root: " + err.String())
+			return os.ErrorString("intermediate certificate does not have CA bit set")
 		}
+		// KeyUsage status flags are ignored. From Engineering
+		// Security, Peter Gutmann: A European government CA marked its
+		// signing certificates as being valid for encryption only, but
+		// no-one noticed. Another European CA marked its signature
+		// keys as not being valid for signatures. A different CA
+		// marked its own trusted root certificate as being invalid for
+		// certificate signing.  Another national CA distributed a
+		// certificate to be used to encrypt data for the country’s tax
+		// authority that was marked as only being usable for digital
+		// signatures but not for encryption. Yet another CA reversed
+		// the order of the bit flags in the keyUsage due to confusion
+		// over encoding endianness, essentially setting a random
+		// keyUsage in certificates that it issued. Another CA created
+		// a self-invalidating certificate by adding a certificate
+		// policy statement stipulating that the certificate had to be
+		// used strictly as specified in the keyUsage, and a keyUsage
+		// containing a flag indicating that the RSA encryption key
+		// could only be used for Diffie-Hellman key agreement.
+
+		cur = parent
 	}
 
 	pub, ok := certs[0].PublicKey.(*rsa.PublicKey)
diff --git a/src/pkg/crypto/tls/tls.go b/src/pkg/crypto/tls/tls.go
index 052212f0bb..61f0a9702d 100644
--- a/src/pkg/crypto/tls/tls.go
+++ b/src/pkg/crypto/tls/tls.go
@@ -6,12 +6,13 @@
 package tls
 
 import (
+	"crypto/rsa"
+	"crypto/x509"
+	"encoding/pem"
 	"io/ioutil"
 	"net"
 	"os"
-	"encoding/pem"
-	"crypto/rsa"
-	"crypto/x509"
+	"strings"
 )
 
 func Server(conn net.Conn, config *Config) *Conn {
@@ -67,7 +68,16 @@ func Dial(network, laddr, raddr string) (net.Conn, os.Error) {
 	if err != nil {
 		return nil, err
 	}
-	conn := Client(c, nil)
+
+	colonPos := strings.LastIndex(raddr, ":")
+	if colonPos == -1 {
+		colonPos = len(raddr)
+	}
+	hostname := raddr[:colonPos]
+
+	config := defaultConfig()
+	config.ServerName = hostname
+	conn := Client(c, config)
 	err = conn.Handshake()
 	if err == nil {
 		return conn, nil