From 65153e478e302eaf3556372ff257ebfc893943c1 Mon Sep 17 00:00:00 2001 From: Roland Shoemaker Date: Wed, 2 Mar 2022 13:20:02 -0800 Subject: [PATCH] crypto/x509: rework path building This change does four things: * removes the chain cache * during path building, equality is determined by checking if the subjects and public keys match, rather than checking if the entire certificates are equal * enforces EKU suitability during path building * enforces name constraints on intermediates and roots which have SANs during path building The chain cache is removed as it was causing duplicate chains to be returned, in some cases shadowing better, shorter chains if a longer chain was found first. Checking equality using the subjects and public keys, rather than the entire certificates, allows the path builder to ignore chains which contain cross-signature loops. EKU checking is done during path building, as the previous behavior of only checking EKUs once the path had been built caused the path builder to incorrectly ignore valid paths when it encountered a path which would later be ruled invalid because of unacceptable EKU usage. Name constraints are applied uniformly across all certificates, not just leaves, in order to be more consistent. Fixes #48869 Fixes #45856 Change-Id: I4ca1cd43510d061e148f953d6c1ed935100fdb10 Reviewed-on: https://go-review.googlesource.com/c/go/+/389555 Reviewed-by: Damien Neil Trust: Cherry Mui Trust: Roland Shoemaker Run-TryBot: Roland Shoemaker Auto-Submit: Roland Shoemaker TryBot-Result: Gopher Robot --- src/crypto/x509/verify.go | 208 +++++++-------- src/crypto/x509/verify_test.go | 449 +++++++++++++++++++++++++++++++++ 2 files changed, 556 insertions(+), 101 deletions(-) diff --git a/src/crypto/x509/verify.go b/src/crypto/x509/verify.go index 4be4eb6095..77ad6868fa 100644 --- a/src/crypto/x509/verify.go +++ b/src/crypto/x509/verify.go @@ -6,6 +6,7 @@ package x509 import ( "bytes" + "crypto" "errors" "fmt" "net" @@ -597,73 +598,101 @@ func (c *Certificate) isValid(certType int, currentChain []*Certificate, opts *V leaf = currentChain[0] } - if (certType == intermediateCertificate || certType == rootCertificate) && - c.hasNameConstraints() && leaf.hasSANExtension() { - err := forEachSAN(leaf.getSANExtension(), func(tag int, data []byte) error { - switch tag { - case nameTypeEmail: - name := string(data) - mailbox, ok := parseRFC2821Mailbox(name) - if !ok { - return fmt.Errorf("x509: cannot parse rfc822Name %q", mailbox) - } - - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "email address", name, mailbox, - func(parsedName, constraint any) (bool, error) { - return matchEmailConstraint(parsedName.(rfc2821Mailbox), constraint.(string)) - }, c.PermittedEmailAddresses, c.ExcludedEmailAddresses); err != nil { - return err - } - - case nameTypeDNS: - name := string(data) - if _, ok := domainToReverseLabels(name); !ok { - return fmt.Errorf("x509: cannot parse dnsName %q", name) - } - - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "DNS name", name, name, - func(parsedName, constraint any) (bool, error) { - return matchDomainConstraint(parsedName.(string), constraint.(string)) - }, c.PermittedDNSDomains, c.ExcludedDNSDomains); err != nil { - return err - } - - case nameTypeURI: - name := string(data) - uri, err := url.Parse(name) - if err != nil { - return fmt.Errorf("x509: internal error: URI SAN %q failed to parse", name) - } - - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "URI", name, uri, - func(parsedName, constraint any) (bool, error) { - return matchURIConstraint(parsedName.(*url.URL), constraint.(string)) - }, c.PermittedURIDomains, c.ExcludedURIDomains); err != nil { - return err + if (len(c.ExtKeyUsage) > 0 || len(c.UnknownExtKeyUsage) > 0) && len(opts.KeyUsages) > 0 { + acceptableUsage := false + um := make(map[ExtKeyUsage]bool, len(opts.KeyUsages)) + for _, u := range opts.KeyUsages { + um[u] = true + } + if !um[ExtKeyUsageAny] { + for _, u := range c.ExtKeyUsage { + if u == ExtKeyUsageAny || um[u] { + acceptableUsage = true + break } + } + if !acceptableUsage { + return CertificateInvalidError{c, IncompatibleUsage, ""} + } + } + } - case nameTypeIP: - ip := net.IP(data) - if l := len(ip); l != net.IPv4len && l != net.IPv6len { - return fmt.Errorf("x509: internal error: IP SAN %x failed to parse", data) + if (certType == intermediateCertificate || certType == rootCertificate) && + c.hasNameConstraints() { + toCheck := []*Certificate{} + if leaf.hasSANExtension() { + toCheck = append(toCheck, leaf) + } + if c.hasSANExtension() { + toCheck = append(toCheck, c) + } + for _, sanCert := range toCheck { + err := forEachSAN(sanCert.getSANExtension(), func(tag int, data []byte) error { + switch tag { + case nameTypeEmail: + name := string(data) + mailbox, ok := parseRFC2821Mailbox(name) + if !ok { + return fmt.Errorf("x509: cannot parse rfc822Name %q", mailbox) + } + + if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "email address", name, mailbox, + func(parsedName, constraint any) (bool, error) { + return matchEmailConstraint(parsedName.(rfc2821Mailbox), constraint.(string)) + }, c.PermittedEmailAddresses, c.ExcludedEmailAddresses); err != nil { + return err + } + + case nameTypeDNS: + name := string(data) + if _, ok := domainToReverseLabels(name); !ok { + return fmt.Errorf("x509: cannot parse dnsName %q", name) + } + + if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "DNS name", name, name, + func(parsedName, constraint any) (bool, error) { + return matchDomainConstraint(parsedName.(string), constraint.(string)) + }, c.PermittedDNSDomains, c.ExcludedDNSDomains); err != nil { + return err + } + + case nameTypeURI: + name := string(data) + uri, err := url.Parse(name) + if err != nil { + return fmt.Errorf("x509: internal error: URI SAN %q failed to parse", name) + } + + if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "URI", name, uri, + func(parsedName, constraint any) (bool, error) { + return matchURIConstraint(parsedName.(*url.URL), constraint.(string)) + }, c.PermittedURIDomains, c.ExcludedURIDomains); err != nil { + return err + } + + case nameTypeIP: + ip := net.IP(data) + if l := len(ip); l != net.IPv4len && l != net.IPv6len { + return fmt.Errorf("x509: internal error: IP SAN %x failed to parse", data) + } + + if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "IP address", ip.String(), ip, + func(parsedName, constraint any) (bool, error) { + return matchIPConstraint(parsedName.(net.IP), constraint.(*net.IPNet)) + }, c.PermittedIPRanges, c.ExcludedIPRanges); err != nil { + return err + } + + default: + // Unknown SAN types are ignored. } - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "IP address", ip.String(), ip, - func(parsedName, constraint any) (bool, error) { - return matchIPConstraint(parsedName.(net.IP), constraint.(*net.IPNet)) - }, c.PermittedIPRanges, c.ExcludedIPRanges); err != nil { - return err - } + return nil + }) - default: - // Unknown SAN types are ignored. + if err != nil { + return err } - - return nil - }) - - if err != nil { - return err } } @@ -767,6 +796,10 @@ func (c *Certificate) Verify(opts VerifyOptions) (chains [][]*Certificate, err e } } + if len(opts.KeyUsages) == 0 { + opts.KeyUsages = []ExtKeyUsage{ExtKeyUsageServerAuth} + } + err = c.isValid(leafCertificate, nil, &opts) if err != nil { return @@ -779,38 +812,10 @@ func (c *Certificate) Verify(opts VerifyOptions) (chains [][]*Certificate, err e } } - var candidateChains [][]*Certificate if opts.Roots.contains(c) { - candidateChains = append(candidateChains, []*Certificate{c}) - } else { - if candidateChains, err = c.buildChains(nil, []*Certificate{c}, nil, &opts); err != nil { - return nil, err - } - } - - keyUsages := opts.KeyUsages - if len(keyUsages) == 0 { - keyUsages = []ExtKeyUsage{ExtKeyUsageServerAuth} - } - - // If any key usage is acceptable then we're done. - for _, usage := range keyUsages { - if usage == ExtKeyUsageAny { - return candidateChains, nil - } - } - - for _, candidate := range candidateChains { - if checkChainForKeyUsage(candidate, keyUsages) { - chains = append(chains, candidate) - } - } - - if len(chains) == 0 { - return nil, CertificateInvalidError{c, IncompatibleUsage, ""} + return [][]*Certificate{{c}}, nil } - - return chains, nil + return c.buildChains([]*Certificate{c}, nil, &opts) } func appendToFreshChain(chain []*Certificate, cert *Certificate) []*Certificate { @@ -826,15 +831,22 @@ func appendToFreshChain(chain []*Certificate, cert *Certificate) []*Certificate // for failed checks due to different intermediates having the same Subject. const maxChainSignatureChecks = 100 -func (c *Certificate) buildChains(cache map[*Certificate][][]*Certificate, currentChain []*Certificate, sigChecks *int, opts *VerifyOptions) (chains [][]*Certificate, err error) { +func (c *Certificate) buildChains(currentChain []*Certificate, sigChecks *int, opts *VerifyOptions) (chains [][]*Certificate, err error) { var ( hintErr error hintCert *Certificate ) + type pubKeyEqual interface { + Equal(crypto.PublicKey) bool + } + considerCandidate := func(certType int, candidate *Certificate) { for _, cert := range currentChain { - if cert.Equal(candidate) { + // If a certificate already appeared in the chain we've built, don't + // reconsider it. This prevents loops, for isntance those created by + // mutual cross-signatures, or other cross-signature bridges oddities. + if bytes.Equal(cert.RawSubject, candidate.RawSubject) && cert.PublicKey.(pubKeyEqual).Equal(candidate.PublicKey) { return } } @@ -865,14 +877,8 @@ func (c *Certificate) buildChains(cache map[*Certificate][][]*Certificate, curre case rootCertificate: chains = append(chains, appendToFreshChain(currentChain, candidate)) case intermediateCertificate: - if cache == nil { - cache = make(map[*Certificate][][]*Certificate) - } - childChains, ok := cache[candidate] - if !ok { - childChains, err = candidate.buildChains(cache, appendToFreshChain(currentChain, candidate), sigChecks, opts) - cache[candidate] = childChains - } + var childChains [][]*Certificate + childChains, err = candidate.buildChains(appendToFreshChain(currentChain, candidate), sigChecks, opts) chains = append(chains, childChains...) } } diff --git a/src/crypto/x509/verify_test.go b/src/crypto/x509/verify_test.go index 100a8ff0f9..1b2cbe34dd 100644 --- a/src/crypto/x509/verify_test.go +++ b/src/crypto/x509/verify_test.go @@ -15,7 +15,9 @@ import ( "fmt" "internal/testenv" "math/big" + "reflect" "runtime" + "sort" "strings" "testing" "time" @@ -1910,3 +1912,450 @@ func TestIssue51759(t *testing.T) { } }) } + +type trustGraphEdge struct { + Issuer string + Subject string + Type int + MutateTemplate func(*Certificate) +} + +type trustGraphDescription struct { + Roots []string + Leaf string + Graph []trustGraphEdge +} + +func genCertEdge(t *testing.T, subject string, key crypto.Signer, mutateTmpl func(*Certificate), certType int, issuer *Certificate, signer crypto.Signer) *Certificate { + t.Helper() + + serial, err := rand.Int(rand.Reader, big.NewInt(100)) + if err != nil { + t.Fatalf("failed to generate test serial: %s", err) + } + tmpl := &Certificate{ + SerialNumber: serial, + Subject: pkix.Name{CommonName: subject}, + NotBefore: time.Now().Add(-time.Hour), + NotAfter: time.Now().Add(time.Hour), + } + if certType == rootCertificate || certType == intermediateCertificate { + tmpl.IsCA, tmpl.BasicConstraintsValid = true, true + tmpl.KeyUsage = KeyUsageCertSign + } else if certType == leafCertificate { + tmpl.DNSNames = []string{"localhost"} + } + if mutateTmpl != nil { + mutateTmpl(tmpl) + } + + if certType == rootCertificate { + issuer = tmpl + signer = key + } + + d, err := CreateCertificate(rand.Reader, tmpl, issuer, key.Public(), signer) + if err != nil { + t.Fatalf("failed to generate test cert: %s", err) + } + c, err := ParseCertificate(d) + if err != nil { + t.Fatalf("failed to parse test cert: %s", err) + } + return c +} + +func buildTrustGraph(t *testing.T, d trustGraphDescription) (*CertPool, *CertPool, *Certificate) { + t.Helper() + + certs := map[string]*Certificate{} + keys := map[string]crypto.Signer{} + roots := []*Certificate{} + for _, r := range d.Roots { + k, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader) + if err != nil { + t.Fatalf("failed to generate test key: %s", err) + } + root := genCertEdge(t, r, k, nil, rootCertificate, nil, nil) + roots = append(roots, root) + certs[r] = root + keys[r] = k + } + + intermediates := []*Certificate{} + var leaf *Certificate + for _, e := range d.Graph { + issuerCert, ok := certs[e.Issuer] + if !ok { + t.Fatalf("unknown issuer %s", e.Issuer) + } + issuerKey, ok := keys[e.Issuer] + if !ok { + t.Fatalf("unknown issuer %s", e.Issuer) + } + + k, ok := keys[e.Subject] + if !ok { + var err error + k, err = ecdsa.GenerateKey(elliptic.P256(), rand.Reader) + if err != nil { + t.Fatalf("failed to generate test key: %s", err) + } + keys[e.Subject] = k + } + cert := genCertEdge(t, e.Subject, k, e.MutateTemplate, e.Type, issuerCert, issuerKey) + certs[e.Subject] = cert + if e.Subject == d.Leaf { + leaf = cert + } else { + intermediates = append(intermediates, cert) + } + } + + rootPool, intermediatePool := NewCertPool(), NewCertPool() + for i := len(roots) - 1; i >= 0; i-- { + rootPool.AddCert(roots[i]) + } + for i := len(intermediates) - 1; i >= 0; i-- { + intermediatePool.AddCert(intermediates[i]) + } + + return rootPool, intermediatePool, leaf +} + +func chainsToStrings(chains [][]*Certificate) []string { + chainStrings := []string{} + for _, chain := range chains { + names := []string{} + for _, c := range chain { + names = append(names, c.Subject.String()) + } + chainStrings = append(chainStrings, strings.Join(names, " -> ")) + } + sort.Strings(chainStrings) + return chainStrings +} + +func TestPathBuilding(t *testing.T) { + tests := []struct { + name string + graph trustGraphDescription + expectedChains []string + expectedErr string + }{ + { + // Build the following graph from RFC 4158, figure 7 (note that in this graph edges represent + // certificates where the parent is the issuer and the child is the subject.) For the certificate + // C->B, use an unsupported ExtKeyUsage (in this case ExtKeyUsageCodeSigning) which invalidates + // the path Trust Anchor -> C -> B -> EE. The remaining valid paths should be: + // * Trust Anchor -> A -> B -> EE + // * Trust Anchor -> C -> A -> B -> EE + // + // +---------+ + // | Trust | + // | Anchor | + // +---------+ + // | | + // v v + // +---+ +---+ + // | A |<-->| C | + // +---+ +---+ + // | | + // | +---+ | + // +->| B |<-+ + // +---+ + // | + // v + // +----+ + // | EE | + // +----+ + name: "bad EKU", + graph: trustGraphDescription{ + Roots: []string{"root"}, + Leaf: "leaf", + Graph: []trustGraphEdge{ + { + Issuer: "root", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "root", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "inter a", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "inter b", + Type: intermediateCertificate, + MutateTemplate: func(t *Certificate) { + t.ExtKeyUsage = []ExtKeyUsage{ExtKeyUsageCodeSigning} + }, + }, + { + Issuer: "inter a", + Subject: "inter b", + Type: intermediateCertificate, + }, + { + Issuer: "inter b", + Subject: "leaf", + Type: leafCertificate, + }, + }, + }, + expectedChains: []string{ + "CN=leaf -> CN=inter b -> CN=inter a -> CN=inter c -> CN=root", + "CN=leaf -> CN=inter b -> CN=inter a -> CN=root", + }, + }, + { + // Build the following graph from RFC 4158, figure 7 (note that in this graph edges represent + // certificates where the parent is the issuer and the child is the subject.) For the certificate + // C->B, use a unconstrained SAN which invalidates the path Trust Anchor -> C -> B -> EE. The + // remaining valid paths should be: + // * Trust Anchor -> A -> B -> EE + // * Trust Anchor -> C -> A -> B -> EE + // + // +---------+ + // | Trust | + // | Anchor | + // +---------+ + // | | + // v v + // +---+ +---+ + // | A |<-->| C | + // +---+ +---+ + // | | + // | +---+ | + // +->| B |<-+ + // +---+ + // | + // v + // +----+ + // | EE | + // +----+ + name: "bad EKU", + graph: trustGraphDescription{ + Roots: []string{"root"}, + Leaf: "leaf", + Graph: []trustGraphEdge{ + { + Issuer: "root", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "root", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "inter a", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "inter b", + Type: intermediateCertificate, + MutateTemplate: func(t *Certificate) { + t.PermittedDNSDomains = []string{"good"} + t.DNSNames = []string{"bad"} + }, + }, + { + Issuer: "inter a", + Subject: "inter b", + Type: intermediateCertificate, + }, + { + Issuer: "inter b", + Subject: "leaf", + Type: leafCertificate, + }, + }, + }, + expectedChains: []string{ + "CN=leaf -> CN=inter b -> CN=inter a -> CN=inter c -> CN=root", + "CN=leaf -> CN=inter b -> CN=inter a -> CN=root", + }, + }, + { + // Build the following graph, we should find both paths: + // * Trust Anchor -> A -> C -> EE + // * Trust Anchor -> A -> B -> C -> EE + // + // +---------+ + // | Trust | + // | Anchor | + // +---------+ + // | + // v + // +---+ + // | A | + // +---+ + // | | + // | +----+ + // | v + // | +---+ + // | | B | + // | +---+ + // | | + // | +---v + // v v + // +---+ + // | C | + // +---+ + // | + // v + // +----+ + // | EE | + // +----+ + name: "all paths", + graph: trustGraphDescription{ + Roots: []string{"root"}, + Leaf: "leaf", + Graph: []trustGraphEdge{ + { + Issuer: "root", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "inter a", + Subject: "inter b", + Type: intermediateCertificate, + }, + { + Issuer: "inter a", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter b", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "leaf", + Type: leafCertificate, + }, + }, + }, + expectedChains: []string{ + "CN=leaf -> CN=inter c -> CN=inter a -> CN=root", + "CN=leaf -> CN=inter c -> CN=inter b -> CN=inter a -> CN=root", + }, + }, + { + // Build the following graph, which contains a cross-signature loop + // (A and C cross sign each other). Paths that include the A -> C -> A + // (and vice versa) loop should be ignored, resulting in the paths: + // * Trust Anchor -> A -> B -> EE + // * Trust Anchor -> C -> B -> EE + // * Trust Anchor -> A -> C -> B -> EE + // * Trust Anchor -> C -> A -> B -> EE + // + // +---------+ + // | Trust | + // | Anchor | + // +---------+ + // | | + // v v + // +---+ +---+ + // | A |<-->| C | + // +---+ +---+ + // | | + // | +---+ | + // +->| B |<-+ + // +---+ + // | + // v + // +----+ + // | EE | + // +----+ + name: "ignore cross-sig loops", + graph: trustGraphDescription{ + Roots: []string{"root"}, + Leaf: "leaf", + Graph: []trustGraphEdge{ + { + Issuer: "root", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "root", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "inter a", + Type: intermediateCertificate, + }, + { + Issuer: "inter a", + Subject: "inter c", + Type: intermediateCertificate, + }, + { + Issuer: "inter c", + Subject: "inter b", + Type: intermediateCertificate, + }, + { + Issuer: "inter a", + Subject: "inter b", + Type: intermediateCertificate, + }, + { + Issuer: "inter b", + Subject: "leaf", + Type: leafCertificate, + }, + }, + }, + expectedChains: []string{ + "CN=leaf -> CN=inter b -> CN=inter a -> CN=inter c -> CN=root", + "CN=leaf -> CN=inter b -> CN=inter a -> CN=root", + "CN=leaf -> CN=inter b -> CN=inter c -> CN=inter a -> CN=root", + "CN=leaf -> CN=inter b -> CN=inter c -> CN=root", + }, + }, + } + + for _, tc := range tests { + t.Run(tc.name, func(t *testing.T) { + roots, intermediates, leaf := buildTrustGraph(t, tc.graph) + chains, err := leaf.Verify(VerifyOptions{ + Roots: roots, + Intermediates: intermediates, + }) + if err != nil && err.Error() != tc.expectedErr { + t.Fatalf("unexpected error: got %q, want %q", err, tc.expectedErr) + } + gotChains := chainsToStrings(chains) + if !reflect.DeepEqual(gotChains, tc.expectedChains) { + t.Errorf("unexpected chains returned:\ngot:\n\t%s\nwant:\n\t%s", strings.Join(gotChains, "\n\t"), strings.Join(tc.expectedChains, "\n\t")) + } + }) + } +} -- 2.48.1