[release-branch.go1.11] all: merge release-branch.go1.11-security into release-branch.go1.11

Change-Id: I2aa2c7056a719f911f68a1710b3c0578a7f595b6

12 files changed, 562 insertions, 60 deletions

diff --git a/VERSION b/VERSION
index ae7717dfe4..aa1dbdc189 100644
--- a/VERSION
+++ b/VERSION
@@ -1 +1 @@
-go1.11.2
\ No newline at end of file
+go1.11.3
\ No newline at end of file
diff --git a/doc/devel/release.html b/doc/devel/release.html
index b02efed501..4e1f7cbc50 100644
--- a/doc/devel/release.html
+++ b/doc/devel/release.html
@@ -49,6 +49,13 @@ See the <a href="https://github.com/golang/go/issues?q=milestone%3AGo1.11.2">Go
 1.11.2 milestone</a> on our issue tracker for details.
 </p>
 
+<p>
+go1.11.3 (released 2018/12/12) includes three security fixes to "go get" and
+the <code>crypto/x509</code> package.
+See the <a href="https://github.com/golang/go/issues?q=milestone%3AGo1.11.3">Go
+1.11.3 milestone</a> on our issue tracker for details.
+</p>
+
 <h2 id="go1.10">go1.10 (released 2018/02/16)</h2>
 
 <p>
@@ -98,6 +105,14 @@ See the <a href="https://github.com/golang/go/issues?q=milestone%3AGo1.10.5">Go
 1.10.5 milestone</a> on our issue tracker for details.
 </p>
 
+<p>
+go1.10.6 (released 2018/12/12) includes three security fixes to "go get" and
+the <code>crypto/x509</code> package.
+It contains the same fixes as Go 1.11.3 and was released at the same time.
+See the <a href="https://github.com/golang/go/issues?q=milestone%3AGo1.10.6">Go
+1.10.6 milestone</a> on our issue tracker for details.
+</p>
+
 <h2 id="go1.9">go1.9 (released 2017/08/24)</h2>
 
 <p>
diff --git a/src/cmd/go/internal/get/get.go b/src/cmd/go/internal/get/get.go
index e4148bceb0..f4b969fcb2 100644
--- a/src/cmd/go/internal/get/get.go
+++ b/src/cmd/go/internal/get/get.go
@@ -402,6 +402,10 @@ func downloadPackage(p *load.Package) error {
 		security = web.Insecure
 	}
 
+	if err := CheckImportPath(p.ImportPath); err != nil {
+		return fmt.Errorf("%s: invalid import path: %v", p.ImportPath, err)
+	}
+
 	if p.Internal.Build.SrcRoot != "" {
 		// Directory exists. Look for checkout along path to src.
 		vcs, rootPath, err = vcsFromDir(p.Dir, p.Internal.Build.SrcRoot)
diff --git a/src/cmd/go/internal/get/path.go b/src/cmd/go/internal/get/path.go
new file mode 100644
index 0000000000..d443bd28a9
--- /dev/null
+++ b/src/cmd/go/internal/get/path.go
@@ -0,0 +1,192 @@
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package get
+
+import (
+	"fmt"
+	"strings"
+	"unicode"
+	"unicode/utf8"
+)
+
+// The following functions are copied verbatim from cmd/go/internal/module/module.go,
+// with a change to additionally reject Windows short-names,
+// and one to accept arbitrary letters (golang.org/issue/29101).
+//
+// TODO(bcmills): After the call site for this function is backported,
+// consolidate this back down to a single copy.
+//
+// NOTE: DO NOT MERGE THESE UNTIL WE DECIDE ABOUT ARBITRARY LETTERS IN MODULE MODE.
+
+// CheckImportPath checks that an import path is valid.
+func CheckImportPath(path string) error {
+	if err := checkPath(path, false); err != nil {
+		return fmt.Errorf("malformed import path %q: %v", path, err)
+	}
+	return nil
+}
+
+// checkPath checks that a general path is valid.
+// It returns an error describing why but not mentioning path.
+// Because these checks apply to both module paths and import paths,
+// the caller is expected to add the "malformed ___ path %q: " prefix.
+// fileName indicates whether the final element of the path is a file name
+// (as opposed to a directory name).
+func checkPath(path string, fileName bool) error {
+	if !utf8.ValidString(path) {
+		return fmt.Errorf("invalid UTF-8")
+	}
+	if path == "" {
+		return fmt.Errorf("empty string")
+	}
+	if strings.Contains(path, "..") {
+		return fmt.Errorf("double dot")
+	}
+	if strings.Contains(path, "//") {
+		return fmt.Errorf("double slash")
+	}
+	if path[len(path)-1] == '/' {
+		return fmt.Errorf("trailing slash")
+	}
+	elemStart := 0
+	for i, r := range path {
+		if r == '/' {
+			if err := checkElem(path[elemStart:i], fileName); err != nil {
+				return err
+			}
+			elemStart = i + 1
+		}
+	}
+	if err := checkElem(path[elemStart:], fileName); err != nil {
+		return err
+	}
+	return nil
+}
+
+// checkElem checks whether an individual path element is valid.
+// fileName indicates whether the element is a file name (not a directory name).
+func checkElem(elem string, fileName bool) error {
+	if elem == "" {
+		return fmt.Errorf("empty path element")
+	}
+	if strings.Count(elem, ".") == len(elem) {
+		return fmt.Errorf("invalid path element %q", elem)
+	}
+	if elem[0] == '.' && !fileName {
+		return fmt.Errorf("leading dot in path element")
+	}
+	if elem[len(elem)-1] == '.' {
+		return fmt.Errorf("trailing dot in path element")
+	}
+
+	charOK := pathOK
+	if fileName {
+		charOK = fileNameOK
+	}
+	for _, r := range elem {
+		if !charOK(r) {
+			return fmt.Errorf("invalid char %q", r)
+		}
+	}
+
+	// Windows disallows a bunch of path elements, sadly.
+	// See https://docs.microsoft.com/en-us/windows/desktop/fileio/naming-a-file
+	short := elem
+	if i := strings.Index(short, "."); i >= 0 {
+		short = short[:i]
+	}
+	for _, bad := range badWindowsNames {
+		if strings.EqualFold(bad, short) {
+			return fmt.Errorf("disallowed path element %q", elem)
+		}
+	}
+
+	// Reject path components that look like Windows short-names.
+	// Those usually end in a tilde followed by one or more ASCII digits.
+	if tilde := strings.LastIndexByte(short, '~'); tilde >= 0 && tilde < len(short)-1 {
+		suffix := short[tilde+1:]
+		suffixIsDigits := true
+		for _, r := range suffix {
+			if r < '0' || r > '9' {
+				suffixIsDigits = false
+				break
+			}
+		}
+		if suffixIsDigits {
+			return fmt.Errorf("trailing tilde and digits in path element")
+		}
+	}
+
+	return nil
+}
+
+// pathOK reports whether r can appear in an import path element.
+//
+// NOTE: This function DIVERGES from module mode pathOK by accepting Unicode letters.
+func pathOK(r rune) bool {
+	if r < utf8.RuneSelf {
+		return r == '+' || r == '-' || r == '.' || r == '_' || r == '~' ||
+			'0' <= r && r <= '9' ||
+			'A' <= r && r <= 'Z' ||
+			'a' <= r && r <= 'z'
+	}
+	return unicode.IsLetter(r)
+}
+
+// fileNameOK reports whether r can appear in a file name.
+// For now we allow all Unicode letters but otherwise limit to pathOK plus a few more punctuation characters.
+// If we expand the set of allowed characters here, we have to
+// work harder at detecting potential case-folding and normalization collisions.
+// See note about "safe encoding" below.
+func fileNameOK(r rune) bool {
+	if r < utf8.RuneSelf {
+		// Entire set of ASCII punctuation, from which we remove characters:
+		//     ! " # $ % & ' ( ) * + , - . / : ; < = > ? @ [ \ ] ^ _ ` { | } ~
+		// We disallow some shell special characters: " ' * < > ? ` |
+		// (Note that some of those are disallowed by the Windows file system as well.)
+		// We also disallow path separators / : and \ (fileNameOK is only called on path element characters).
+		// We allow spaces (U+0020) in file names.
+		const allowed = "!#$%&()+,-.=@[]^_{}~ "
+		if '0' <= r && r <= '9' || 'A' <= r && r <= 'Z' || 'a' <= r && r <= 'z' {
+			return true
+		}
+		for i := 0; i < len(allowed); i++ {
+			if rune(allowed[i]) == r {
+				return true
+			}
+		}
+		return false
+	}
+	// It may be OK to add more ASCII punctuation here, but only carefully.
+	// For example Windows disallows < > \, and macOS disallows :, so we must not allow those.
+	return unicode.IsLetter(r)
+}
+
+// badWindowsNames are the reserved file path elements on Windows.
+// See https://docs.microsoft.com/en-us/windows/desktop/fileio/naming-a-file
+var badWindowsNames = []string{
+	"CON",
+	"PRN",
+	"AUX",
+	"NUL",
+	"COM1",
+	"COM2",
+	"COM3",
+	"COM4",
+	"COM5",
+	"COM6",
+	"COM7",
+	"COM8",
+	"COM9",
+	"LPT1",
+	"LPT2",
+	"LPT3",
+	"LPT4",
+	"LPT5",
+	"LPT6",
+	"LPT7",
+	"LPT8",
+	"LPT9",
+}
diff --git a/src/cmd/go/internal/get/vcs.go b/src/cmd/go/internal/get/vcs.go
index 5cd164f2ff..ff4f9d12ef 100644
--- a/src/cmd/go/internal/get/vcs.go
+++ b/src/cmd/go/internal/get/vcs.go
@@ -966,10 +966,14 @@ func matchGoImport(imports []metaImport, importPath string) (metaImport, error)
 
 // expand rewrites s to replace {k} with match[k] for each key k in match.
 func expand(match map[string]string, s string) string {
+	// We want to replace each match exactly once, and the result of expansion
+	// must not depend on the iteration order through the map.
+	// A strings.Replacer has exactly the properties we're looking for.
+	oldNew := make([]string, 0, 2*len(match))
 	for k, v := range match {
-		s = strings.Replace(s, "{"+k+"}", v, -1)
+		oldNew = append(oldNew, "{"+k+"}", v)
 	}
-	return s
+	return strings.NewReplacer(oldNew...).Replace(s)
 }
 
 // vcsPaths defines the meaning of import paths referring to
diff --git a/src/cmd/go/testdata/script/get_brace.txt b/src/cmd/go/testdata/script/get_brace.txt
new file mode 100644
index 0000000000..be81d8f487
--- /dev/null
+++ b/src/cmd/go/testdata/script/get_brace.txt
@@ -0,0 +1,49 @@
+[!exec:git] skip
+
+# Set up some empty repositories.
+cd $WORK/_origin/foo
+exec git init
+exec git config user.name 'Nameless Gopher'
+exec git config user.email 'nobody@golang.org'
+exec git commit --allow-empty -m 'create master branch'
+
+cd $WORK
+cd '_origin/{confusing}'
+exec git init
+exec git config user.name 'Nameless Gopher'
+exec git config user.email 'nobody@golang.org'
+exec git commit --allow-empty -m 'create master branch'
+
+# Clone the empty repositories into GOPATH.
+# This tells the Go command where to find them: it takes the place of a user's meta-tag redirector.
+mkdir $GOPATH/src/example.com
+cd $GOPATH/src/example.com
+exec git clone $WORK/_origin/foo
+exec git clone $WORK/_origin/{confusing}
+
+# Commit contents to the repositories.
+cd $WORK/_origin/foo
+exec git add main.go
+exec git commit -m 'add main'
+
+cd $WORK
+cd '_origin/{confusing}'
+exec git add confusing.go
+exec git commit -m 'just try to delete this!'
+
+# 'go get' should refuse to download or update the confusingly-named repo.
+cd $GOPATH/src/example.com/foo
+! go get -u 'example.com/{confusing}'
+stderr 'invalid char'
+! go get -u example.com/foo
+stderr 'invalid import path'
+! exists example.com/{confusing}
+
+-- $WORK/_origin/foo/main.go --
+package main
+import _ "example.com/{confusing}"
+
+func main() {}
+
+-- $WORK/_origin/{confusing}/confusing.go --
+package confusing
diff --git a/src/cmd/go/testdata/script/get_dotfiles.txt b/src/cmd/go/testdata/script/get_dotfiles.txt
new file mode 100644
index 0000000000..1876114362
--- /dev/null
+++ b/src/cmd/go/testdata/script/get_dotfiles.txt
@@ -0,0 +1,61 @@
+[!exec:git] skip
+
+# Set up a benign repository and a repository with a dotfile name.
+cd $WORK/_origin/foo
+exec git init
+exec git config user.name 'Nameless Gopher'
+exec git config user.email 'nobody@golang.org'
+exec git commit --allow-empty -m 'create master branch'
+
+cd $WORK/_origin/.hidden
+exec git init
+exec git config user.name 'Nameless Gopher'
+exec git config user.email 'nobody@golang.org'
+exec git commit --allow-empty -m 'create master branch'
+
+# Clone the empty repositories into GOPATH.
+# This tells the Go command where to find them: it takes the place of a user's meta-tag redirector.
+mkdir $GOPATH/src/example.com
+cd $GOPATH/src/example.com
+exec git clone $WORK/_origin/foo
+exec git clone $WORK/_origin/.hidden
+
+# Add a benign commit.
+cd $WORK/_origin/foo
+cp _ok/main.go main.go
+exec git add main.go
+exec git commit -m 'add ok'
+
+# 'go get' should install the benign commit.
+cd $GOPATH
+go get -u example.com/foo
+
+# Now sneak in an import of a dotfile path.
+cd $WORK/_origin/.hidden
+exec git add hidden.go
+exec git commit -m 'nothing to see here, move along'
+
+cd $WORK/_origin/foo
+cp _sneaky/main.go main.go
+exec git add main.go
+exec git commit -m 'fix typo (heh heh heh)'
+
+# 'go get -u' should refuse to download or update the dotfile-named repo.
+cd $GOPATH/src/example.com/foo
+! go get -u example.com/foo
+stderr 'leading dot'
+! exists example.com/.hidden/hidden.go
+
+-- $WORK/_origin/foo/_ok/main.go --
+package main
+
+func main() {}
+
+-- $WORK/_origin/foo/_sneaky/main.go --
+package main
+import _ "example.com/.hidden"
+
+func main() {}
+
+-- $WORK/_origin/.hidden/hidden.go --
+package hidden
diff --git a/src/cmd/go/testdata/script/get_tilde.txt b/src/cmd/go/testdata/script/get_tilde.txt
new file mode 100644
index 0000000000..08289ca405
--- /dev/null
+++ b/src/cmd/go/testdata/script/get_tilde.txt
@@ -0,0 +1,21 @@
+# Paths containing windows short names should be rejected before attempting to fetch.
+! go get example.com/longna~1.dir/thing
+stderr 'trailing tilde and digits'
+! go get example.com/longna~1/thing
+stderr 'trailing tilde and digits'
+! go get example.com/~9999999/thing
+stderr 'trailing tilde and digits'
+
+# A path containing an element that is just a tilde, or a tilde followed by non-digits,
+# should attempt to resolve.
+! go get example.com/~glenda/notfound
+! stderr 'trailing tilde and digits'
+stderr 'unrecognized import path'
+
+! go get example.com/~glenda2/notfound
+! stderr 'trailing tilde and digits'
+stderr 'unrecognized import path'
+
+! go get example.com/~/notfound
+! stderr 'trailing tilde and digits'
+stderr 'unrecognized import path'
diff --git a/src/cmd/go/testdata/script/get_unicode.txt b/src/cmd/go/testdata/script/get_unicode.txt
new file mode 100644
index 0000000000..31edcdb9f6
--- /dev/null
+++ b/src/cmd/go/testdata/script/get_unicode.txt
@@ -0,0 +1,37 @@
+[!exec:git] skip
+
+# Construct a repository that imports a non-ASCII path.
+cd $WORK/_origin/example.com/unicode
+exec git init
+exec git config user.name 'Nameless Gopher'
+exec git config user.email 'nobody@golang.org'
+exec git add unicode.go
+exec git commit -m 'add unicode.go'
+
+# Clone the repo into GOPATH so that 'go get -u' can find it.
+mkdir $GOPATH/src/example.com/unicode
+cd $GOPATH/src/example.com/unicode
+exec git clone $WORK/_origin/example.com/unicode .
+
+# Construct the imported repository.
+cd $WORK/_origin/example.com/испытание
+exec git init
+exec git config user.name 'Nameless Gopher'
+exec git config user.email 'nobody@golang.org'
+exec git add испытание.go
+exec git commit -m 'add испытание.go'
+
+# Clone that repo into GOPATH too.
+mkdir $GOPATH/src/example.com/испытание
+cd $GOPATH/src/example.com/испытание
+exec git clone $WORK/_origin/example.com/испытание .
+
+# Upgrading the importer should pull from the non-ASCII repo.
+cd $GOPATH
+go get -u example.com/unicode
+
+-- $WORK/_origin/example.com/unicode/unicode.go --
+package unicode
+import _ "example.com/испытание"
+-- $WORK/_origin/example.com/испытание/испытание.go --
+package испытание
diff --git a/src/crypto/x509/cert_pool.go b/src/crypto/x509/cert_pool.go
index a1646b9826..61107f86b8 100644
--- a/src/crypto/x509/cert_pool.go
+++ b/src/crypto/x509/cert_pool.go
@@ -65,32 +65,16 @@ func SystemCertPool() (*CertPool, error) {
 	return loadSystemRoots()
 }
 
-// findVerifiedParents attempts to find certificates in s which have signed the
-// given certificate. If any candidates were rejected then errCert will be set
-// to one of them, arbitrarily, and err will contain the reason that it was
-// rejected.
-func (s *CertPool) findVerifiedParents(cert *Certificate) (parents []int, errCert *Certificate, err error) {
+// findPotentialParents returns the indexes of certificates in s which might
+// have signed cert. The caller must not modify the returned slice.
+func (s *CertPool) findPotentialParents(cert *Certificate) []int {
 	if s == nil {
-		return
+		return nil
 	}
-	var candidates []int
-
 	if len(cert.AuthorityKeyId) > 0 {
-		candidates = s.bySubjectKeyId[string(cert.AuthorityKeyId)]
-	}
-	if len(candidates) == 0 {
-		candidates = s.byName[string(cert.RawIssuer)]
+		return s.bySubjectKeyId[string(cert.AuthorityKeyId)]
 	}
-
-	for _, c := range candidates {
-		if err = cert.CheckSignatureFrom(s.certs[c]); err == nil {
-			parents = append(parents, c)
-		} else {
-			errCert = s.certs[c]
-		}
-	}
-
-	return
+	return s.byName[string(cert.RawIssuer)]
 }
 
 func (s *CertPool) contains(cert *Certificate) bool {
diff --git a/src/crypto/x509/verify.go b/src/crypto/x509/verify.go
index 0b75778a03..d84272ecb4 100644
--- a/src/crypto/x509/verify.go
+++ b/src/crypto/x509/verify.go
@@ -765,7 +765,7 @@ func (c *Certificate) Verify(opts VerifyOptions) (chains [][]*Certificate, err e
 	if opts.Roots.contains(c) {
 		candidateChains = append(candidateChains, []*Certificate{c})
 	} else {
-		if candidateChains, err = c.buildChains(make(map[int][][]*Certificate), []*Certificate{c}, &opts); err != nil {
+		if candidateChains, err = c.buildChains(nil, []*Certificate{c}, nil, &opts); err != nil {
 			return nil, err
 		}
 	}
@@ -802,58 +802,74 @@ func appendToFreshChain(chain []*Certificate, cert *Certificate) []*Certificate
 	return n
 }
 
-func (c *Certificate) buildChains(cache map[int][][]*Certificate, currentChain []*Certificate, opts *VerifyOptions) (chains [][]*Certificate, err error) {
-	possibleRoots, failedRoot, rootErr := opts.Roots.findVerifiedParents(c)
-nextRoot:
-	for _, rootNum := range possibleRoots {
-		root := opts.Roots.certs[rootNum]
+// maxChainSignatureChecks is the maximum number of CheckSignatureFrom calls
+// that an invocation of buildChains will (tranistively) make. Most chains are
+// less than 15 certificates long, so this leaves space for multiple chains and
+// 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) {
+	var (
+		hintErr  error
+		hintCert *Certificate
+	)
+
+	considerCandidate := func(certType int, candidate *Certificate) {
 		for _, cert := range currentChain {
-			if cert.Equal(root) {
-				continue nextRoot
+			if cert.Equal(candidate) {
+				return
 			}
 		}
 
-		err = root.isValid(rootCertificate, currentChain, opts)
-		if err != nil {
-			continue
+		if sigChecks == nil {
+			sigChecks = new(int)
+		}
+		*sigChecks++
+		if *sigChecks > maxChainSignatureChecks {
+			err = errors.New("x509: signature check attempts limit reached while verifying certificate chain")
+			return
 		}
-		chains = append(chains, appendToFreshChain(currentChain, root))
-	}
 
-	possibleIntermediates, failedIntermediate, intermediateErr := opts.Intermediates.findVerifiedParents(c)
-nextIntermediate:
-	for _, intermediateNum := range possibleIntermediates {
-		intermediate := opts.Intermediates.certs[intermediateNum]
-		for _, cert := range currentChain {
-			if cert.Equal(intermediate) {
-				continue nextIntermediate
+		if err := c.CheckSignatureFrom(candidate); err != nil {
+			if hintErr == nil {
+				hintErr = err
+				hintCert = candidate
 			}
+			return
 		}
-		err = intermediate.isValid(intermediateCertificate, currentChain, opts)
+
+		err = candidate.isValid(certType, currentChain, opts)
 		if err != nil {
-			continue
+			return
 		}
-		var childChains [][]*Certificate
-		childChains, ok := cache[intermediateNum]
-		if !ok {
-			childChains, err = intermediate.buildChains(cache, appendToFreshChain(currentChain, intermediate), opts)
-			cache[intermediateNum] = childChains
+
+		switch certType {
+		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
+			}
+			chains = append(chains, childChains...)
 		}
-		chains = append(chains, childChains...)
+	}
+
+	for _, rootNum := range opts.Roots.findPotentialParents(c) {
+		considerCandidate(rootCertificate, opts.Roots.certs[rootNum])
+	}
+	for _, intermediateNum := range opts.Intermediates.findPotentialParents(c) {
+		considerCandidate(intermediateCertificate, opts.Intermediates.certs[intermediateNum])
 	}
 
 	if len(chains) > 0 {
 		err = nil
 	}
-
 	if len(chains) == 0 && err == nil {
-		hintErr := rootErr
-		hintCert := failedRoot
-		if hintErr == nil {
-			hintErr = intermediateErr
-			hintCert = failedIntermediate
-		}
 		err = UnknownAuthorityError{c, hintErr, hintCert}
 	}
 
diff --git a/src/crypto/x509/verify_test.go b/src/crypto/x509/verify_test.go
index 0e24d3b5da..85f4703d4c 100644
--- a/src/crypto/x509/verify_test.go
+++ b/src/crypto/x509/verify_test.go
@@ -5,10 +5,15 @@
 package x509
 
 import (
+	"crypto"
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/rand"
 	"crypto/x509/pkix"
 	"encoding/pem"
 	"errors"
 	"fmt"
+	"math/big"
 	"runtime"
 	"strings"
 	"testing"
@@ -1889,3 +1894,117 @@ 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
+	}
+
+	serialNumberLimit := new(big.Int).Lsh(big.NewInt(1), 128)
+	serialNumber, _ := rand.Int(rand.Reader, serialNumberLimit)
+
+	template := &Certificate{
+		SerialNumber: serialNumber,
+		Subject:      pkix.Name{CommonName: cn},
+		NotBefore:    time.Now().Add(-1 * time.Hour),
+		NotAfter:     time.Now().Add(24 * time.Hour),
+
+		KeyUsage:              KeyUsageKeyEncipherment | KeyUsageDigitalSignature | KeyUsageCertSign,
+		ExtKeyUsage:           []ExtKeyUsage{ExtKeyUsageServerAuth},
+		BasicConstraintsValid: true,
+		IsCA:                  isCA,
+	}
+	if issuer == nil {
+		issuer = template
+		issuerKey = priv
+	}
+
+	derBytes, err := CreateCertificate(rand.Reader, template, issuer, priv.Public(), issuerKey)
+	if err != nil {
+		return nil, nil, err
+	}
+	cert, err := ParseCertificate(derBytes)
+	if err != nil {
+		return nil, nil, err
+	}
+
+	return cert, priv, nil
+}
+
+func TestPathologicalChain(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)
+	}
+
+	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")
+	}
+
+	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 < 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)
+	}
+
+	leaf, _, err := generateCert("Leaf", false, parent, parentKey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	start := time.Now()
+	if _, err := leaf.Verify(VerifyOptions{
+		Roots:         roots,
+		Intermediates: intermediates,
+	}); err != nil {
+		t.Error(err)
+	}
+	t.Logf("verification took %v", time.Since(start))
+}