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 <dneil@google.com>
Trust: Cherry Mui <cherryyz@google.com>
Trust: Roland Shoemaker <roland@golang.org>
Run-TryBot: Roland Shoemaker <roland@golang.org>
Auto-Submit: Roland Shoemaker <roland@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>

2 files changed, 551 insertions, 96 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 (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, ""}
+			}
+		}
+	}
 
-				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
-				}
+	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)
+					}
 
-			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, "email address", name, mailbox,
+						func(parsedName, constraint any) (bool, error) {
+							return matchEmailConstraint(parsedName.(rfc2821Mailbox), constraint.(string))
+						}, c.PermittedEmailAddresses, c.ExcludedEmailAddresses); err != nil {
+						return err
+					}
 
-				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 nameTypeDNS:
+					name := string(data)
+					if _, ok := domainToReverseLabels(name); !ok {
+						return fmt.Errorf("x509: cannot parse dnsName %q", name)
+					}
 
-			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, "DNS name", name, name,
+						func(parsedName, constraint any) (bool, error) {
+							return matchDomainConstraint(parsedName.(string), constraint.(string))
+						}, c.PermittedDNSDomains, c.ExcludedDNSDomains); err != nil {
+						return err
+					}
 
-				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 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)
+					}
 
-			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, "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 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
-				}
+				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)
+					}
 
-			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
-		}
+		return [][]*Certificate{{c}}, nil
 	}
-
-	for _, candidate := range candidateChains {
-		if checkChainForKeyUsage(candidate, keyUsages) {
-			chains = append(chains, candidate)
-		}
-	}
-
-	if len(chains) == 0 {
-		return nil, CertificateInvalidError{c, IncompatibleUsage, ""}
-	}
-
-	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"))
+			}
+		})
+	}
+}