crypto/x509: Verify fails to find valid path when some paths have EKU constraint violations

[JackOfMostTrades]

What version of Go are you using (go version)?

1.17.2

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/ihaken/.cache/go-build"
GOENV="/home/ihaken/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/ihaken/go/pkg/mod"
GONOPROXY="stash.corp.netflix.com"
GONOSUMDB="stash.corp.netflix.com"
GOOS="linux"
GOPATH="/home/ihaken/go"
GOPRIVATE="stash.corp.netflix.com"
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/ihaken/bin/go1.17.2-linux-amd64"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/ihaken/bin/go1.17.2-linux-amd64/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.17.2"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3893857195=/tmp/go-build -gno-record-gcc-switches"

What did you do?

The path building in x509/verify.go appears to fail to find a valid path when some paths are invalid due to EKU constraints on intermediate CAs.

The certificates in this test case form the following graph (lifted from RFC 4158, figure 7):

     +---------+
     |  Trust  |
     | Anchor  |
     +---------+
      |       |
      v       v
   +---+    +---+
   | A |<-->| C |
   +---+    +---+
    |         |
    |  +---+  |
    +->| B |<-+
       +---+
         |
         v
       +----+
       | EE |
       +----+

There are seven certificates (besides the self-signed certificate for the trust anchor), but the certificate "C => B" has an "Email Protection" EKU which causes it to be considered invalid for this x509.Verify call (which requires CAs to allow for Server Authentication EKU). Despite this certificate being invalid, x509.Verify should be able to find a path such as "Trust Anchor => C => A => B => EE".

A test case reproducing this is below. Note that simply excluding the first intermediate cert below allows x509.Verify to find the expected path.

package foo

import (
	"crypto/x509"
	"encoding/base64"
	"testing"
	"time"
)

func mustParse(s string) *x509.Certificate {
	certBytes, err := base64.StdEncoding.DecodeString(s)
	if err != nil {
		panic(err)
	}
	cert, err := x509.ParseCertificate(certBytes)
	if err != nil {
		panic(err)
	}
	return cert
}

func TestEkuPathBuilding(t *testing.T) {
	truststore := x509.NewCertPool()
	truststore.AddCert(mustParse("MIICDTCCAbSgAwIBAgISAYNv3E86soSvTqnYh7AQuZp1MAoGCCqGSM49BAMCMGYxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xHTAbBgNVBAMMFGJldHRlcnRsc190cnVzdF9yb290MS0wKwYDVQQFEyQ3ZTUwODA0ZC03YTg0LTRiMmUtYTkyOC03MDI3MjFjYzU0MDMwHhcNMjExMDA3MTcyMjM0WhcNMjIxMDA5MTcyMjM0WjBmMRYwFAYDVQQKEw1iZXR0ZXJ0bHMuY29tMR0wGwYDVQQDDBRiZXR0ZXJ0bHNfdHJ1c3Rfcm9vdDEtMCsGA1UEBRMkN2U1MDgwNGQtN2E4NC00YjJlLWE5MjgtNzAyNzIxY2M1NDAzMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAENGXYZwSkdK6+vAvj7/il3Ny7TKLlEVoyMfy9OeJkxzWEwDT1yziP/qLrq9lyczJTSkf89boGIfYWtkulJhGufqNCMEAwDgYDVR0PAQH/BAQDAgIEMA8GA1UdEwEB/wQFMAMBAf8wHQYDVR0OBBYEFKLkJSmoYL7BBE+YTsJrYerI6BpkMAoGCCqGSM49BAMCA0cAMEQCICfcFvAkR8A6a7kSercJ0097QhufwlLOulxDurchFRzjAiBqImnlB5ba5ZoosJMGb9tdOQpyB3P35L8DxBOwBtvdJA=="))
	
	leafCert := mustParse("MIIB/jCCAaSgAwIBAgISAY7+auYZRhGK+2ljtZkwdohXMAoGCCqGSM49BAMCMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUIxLTArBgNVBAUTJGVkNmNkMWNiLTFiOWEtNGMyZC04Zjk3LWVjMjYyY2VjNWNmMzAeFw0yMTEwMDcxNzIyMzRaFw0yMjEwMDkxNzIyMzRaMFQxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCzAJBgNVBAMTAkVFMS0wKwYDVQQFEyQxOTY2NDc4Yi01YWQ4LTRmZDAtODFhYy03YmJlODczYmNiZjAwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAAQFChvHbqUXsBfGrWEojOk0csKDBOs5Ad8v/QnXuq+a8GYlamS+zy9XvCNC13nGgPX4isJLzTXw5ptYf333Ex+lo1cwVTAOBgNVHQ8BAf8EBAMCB4AwDAYDVR0TAQH/BAIwADAfBgNVHSMEGDAWgBTtMMD8JlKX+vA33cElQe2GOlECgTAUBgNVHREEDTALgglsb2NhbGhvc3QwCgYIKoZIzj0EAwIDSAAwRQIgJPo8+u371jzPFkG5YQkOhCCE8B8TS7oHlXiaKCxc7wgCIQDJoXSBzvm5f/OUojj/PdxnZtY1Vznf0oDP9hI8LvSFpA==")
		
	intermediates := x509.NewCertPool()
	for _, cert := range []string{
		"MIICHzCCAcSgAwIBAgISAZ/vGwdCCamGv0KKXppr4dc1MAoGCCqGSM49BAMCMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUMxLTArBgNVBAUTJDBjMWZiZDZkLWRmYTktNDA0Zi1iNGE4LTg4MTlhYjIxNTkyNTAeFw0yMTEwMDcxNzIyMzRaFw0yMjEwMDkxNzIyMzRaMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUIxLTArBgNVBAUTJGVkNmNkMWNiLTFiOWEtNGMyZC04Zjk3LWVjMjYyY2VjNWNmMzBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABOYibTGILHFXfbH3DOKJjodZ3v6UuPu3F8rT9m37Xa1O3tCvIecBE8VZ1+migbzeRxUV3LUGPxXed9bE60ENvO2jeDB2MA4GA1UdDwEB/wQEAwICBDATBgNVHSUEDDAKBggrBgEFBQcDBDAPBgNVHRMBAf8EBTADAQH/MB0GA1UdDgQWBBTtMMD8JlKX+vA33cElQe2GOlECgTAfBgNVHSMEGDAWgBSzLYGv7LzSVT+vq38dh28P45qy9DAKBggqhkjOPQQDAgNJADBGAiEApfI8g4xzvRThwztZYEdVV+bLZw4dk7lV2/pVI0S3HVgCIQCxpPenGZY9myDBAC4B9bYfhxGo6ZxVmYFQLuFuJOoEcQ==",
		"MIICCTCCAa+gAwIBAgISAby+6XTq4ojH1RUoePd9hHlJMAoGCCqGSM49BAMCMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUExLTArBgNVBAUTJGI5YzRlMWFlLTgyNTEtNDgzZC04OWMzLTQ1YTc1MjUwNzc5ZDAeFw0yMTEwMDcxNzIyMzRaFw0yMjEwMDkxNzIyMzRaMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUIxLTArBgNVBAUTJGVkNmNkMWNiLTFiOWEtNGMyZC04Zjk3LWVjMjYyY2VjNWNmMzBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABOYibTGILHFXfbH3DOKJjodZ3v6UuPu3F8rT9m37Xa1O3tCvIecBE8VZ1+migbzeRxUV3LUGPxXed9bE60ENvO2jYzBhMA4GA1UdDwEB/wQEAwICBDAPBgNVHRMBAf8EBTADAQH/MB0GA1UdDgQWBBTtMMD8JlKX+vA33cElQe2GOlECgTAfBgNVHSMEGDAWgBSTUb2mpweQtatmY5bbxTHqUJfwrDAKBggqhkjOPQQDAgNIADBFAiAYmqcbTJPPE2aJhTjTSr49yKQSHEFKffCi2wTIr15MxgIhAKT1XlaFHrX3zlyzaE3Bq9KTT89hdYyYXpRyucK+eG3F",
		"MIICCDCCAa+gAwIBAgISAWiJ6wlu8cnqlmE8mo/NwxErMAoGCCqGSM49BAMCMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUMxLTArBgNVBAUTJDBjMWZiZDZkLWRmYTktNDA0Zi1iNGE4LTg4MTlhYjIxNTkyNTAeFw0yMTEwMDcxNzIyMzRaFw0yMjEwMDkxNzIyMzRaMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUExLTArBgNVBAUTJGI5YzRlMWFlLTgyNTEtNDgzZC04OWMzLTQ1YTc1MjUwNzc5ZDBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABFyCj4kv2+ksqHeAH1Oc9vkaWfNFvlgdnjw2k3Sgdyld+7wnxYmqtIA8KqVUMR7Xk3TcKpP3Wq62yMvZ/KmoE1SjYzBhMA4GA1UdDwEB/wQEAwICBDAPBgNVHRMBAf8EBTADAQH/MB0GA1UdDgQWBBSTUb2mpweQtatmY5bbxTHqUJfwrDAfBgNVHSMEGDAWgBSzLYGv7LzSVT+vq38dh28P45qy9DAKBggqhkjOPQQDAgNHADBEAiBxTzv5TZYlSzUZDI1TxCMMIExd0t80Cf43MaP1p+31mgIgJ/MOjtCSconc2IJE66fUwg3UpttPZIKkfrQgVsc4u2I=",
		"MIICCDCCAa+gAwIBAgISATAvFW8FOPawt5+dEiyysohYMAoGCCqGSM49BAMCMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUExLTArBgNVBAUTJGI5YzRlMWFlLTgyNTEtNDgzZC04OWMzLTQ1YTc1MjUwNzc5ZDAeFw0yMTEwMDcxNzIyMzRaFw0yMjEwMDkxNzIyMzRaMFMxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xCjAIBgNVBAMTAUMxLTArBgNVBAUTJDBjMWZiZDZkLWRmYTktNDA0Zi1iNGE4LTg4MTlhYjIxNTkyNTBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABOtbqq4w2iVAgrzIB1cOYZcJ+3l3IhHNAaHUaStOaic5cKhJZngYW/etsKsBTEeGf85QZZkK9GTnGgz0Jy3fygujYzBhMA4GA1UdDwEB/wQEAwICBDAPBgNVHRMBAf8EBTADAQH/MB0GA1UdDgQWBBSzLYGv7LzSVT+vq38dh28P45qy9DAfBgNVHSMEGDAWgBSTUb2mpweQtatmY5bbxTHqUJfwrDAKBggqhkjOPQQDAgNHADBEAiBL5hGkVTDYq/MfGICTeJUveAAznZUSZuTObCPYFbE04gIgA50pAT434f/DkQYtzTR5cuEn5evJlmAr354Kepcg5VU=",
		"MIICGzCCAcKgAwIBAgISAcZvyHEGNKO8tB6ha1i4TmvgMAoGCCqGSM49BAMCMGYxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xHTAbBgNVBAMMFGJldHRlcnRsc190cnVzdF9yb290MS0wKwYDVQQFEyQ3ZTUwODA0ZC03YTg0LTRiMmUtYTkyOC03MDI3MjFjYzU0MDMwHhcNMjExMDA3MTcyMjM0WhcNMjIxMDA5MTcyMjM0WjBTMRYwFAYDVQQKEw1iZXR0ZXJ0bHMuY29tMQowCAYDVQQDEwFDMS0wKwYDVQQFEyQwYzFmYmQ2ZC1kZmE5LTQwNGYtYjRhOC04ODE5YWIyMTU5MjUwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAATrW6quMNolQIK8yAdXDmGXCft5dyIRzQGh1GkrTmonOXCoSWZ4GFv3rbCrAUxHhn/OUGWZCvRk5xoM9Cct38oLo2MwYTAOBgNVHQ8BAf8EBAMCAgQwDwYDVR0TAQH/BAUwAwEB/zAdBgNVHQ4EFgQUsy2Br+y80lU/r6t/HYdvD+OasvQwHwYDVR0jBBgwFoAUouQlKahgvsEET5hOwmth6sjoGmQwCgYIKoZIzj0EAwIDRwAwRAIgDSQ75/Ak83lhe636BxoL0PHvn6k54rjSlx+VrrqZ03wCIBNeVrWX2yBvgDHVwS9q+CNfckH+yhZjEOSBTW3k0XxJ",
		"MIICHTCCAcKgAwIBAgISAX9H6Ko+SZUQe21jNfmjU/KjMAoGCCqGSM49BAMCMGYxFjAUBgNVBAoTDWJldHRlcnRscy5jb20xHTAbBgNVBAMMFGJldHRlcnRsc190cnVzdF9yb290MS0wKwYDVQQFEyQ3ZTUwODA0ZC03YTg0LTRiMmUtYTkyOC03MDI3MjFjYzU0MDMwHhcNMjExMDA3MTcyMjM0WhcNMjIxMDA5MTcyMjM0WjBTMRYwFAYDVQQKEw1iZXR0ZXJ0bHMuY29tMQowCAYDVQQDEwFBMS0wKwYDVQQFEyRiOWM0ZTFhZS04MjUxLTQ4M2QtODljMy00NWE3NTI1MDc3OWQwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAARcgo+JL9vpLKh3gB9TnPb5GlnzRb5YHZ48NpN0oHcpXfu8J8WJqrSAPCqlVDEe15N03CqT91qutsjL2fypqBNUo2MwYTAOBgNVHQ8BAf8EBAMCAgQwDwYDVR0TAQH/BAUwAwEB/zAdBgNVHQ4EFgQUk1G9pqcHkLWrZmOW28Ux6lCX8KwwHwYDVR0jBBgwFoAUouQlKahgvsEET5hOwmth6sjoGmQwCgYIKoZIzj0EAwIDSQAwRgIhALawfPf6YECsKcbKn46wFABqalUAF1TTQoYiuupSfs08AiEAuP9jGMiUzrMet9TJDpvS1daX8gfMGfQUrPM08SykJgY=",
	} {
		intermediates.AddCert(mustParse(cert))
	}
	
	chains, err := leafCert.Verify(x509.VerifyOptions{
		DNSName:                   "localhost",
		Intermediates:             intermediates,
		Roots:                     truststore,
		CurrentTime:               time.Unix(1633713295, 0),
		KeyUsages:                 []x509.ExtKeyUsage{x509.ExtKeyUsageServerAuth},
	})
	if err != nil {
		t.Error(err)
	} else {
		if len(chains) == 0 {
			t.Error("Unable to discover valid chain.")
		}
	}
}

[seankhliao]

cc @FiloSottile

[FiloSottile]

Thank you for the report! This is indeed something we don't handle in the path building logic. We are thinking a lot about these "alternative path" situations right now because of #46287, and I am curious how you encountered this. Since we don't do AIA nor we extract system intermediates, for this to happen in TLS the peer would have to send both A and C, which feels unlikely, right? What other scenario leads to this?

(I am asking not because we wouldn't like to fix this instance, but because there are other similar cases that would be way more complex to fix, and we need to understand how likely they are.)

/cc @golang/security @rolandshoemaker

[JackOfMostTrades]

I am curious how you encountered this. ... for this to happen in TLS the peer would have to send both A and C, which feels unlikely, right?

Yea, this was part of a synthetic set of tests I've been putting together to evaluate path building in TLS clients. I've been building them through a few real-life examples of things like previous CA expiration but also some artificial examples from RFCs, etc. This was the only thing where the Go implementation did anything unexpected.

I would completely agree that anything like this seems unlikely to come up in a real-life use-case. If fixing it in general is complex, especially in the context of those other changes, I certainly wouldn't sweat this corner case. :)

[FiloSottile]

Excellent, thank you! We'll look at how complex it would be to handle this, and the adjacent case where there is a name constrained path and an unconstrained path, which would break in the same way. My guess is that we'll be able to make it work with the Go path builder, but might have to take the hit when using platform verifiers, because we can't easily dictate rules at path building time, and if the system verifier doesn't do EKUs (we do them nested) or NCs (we apply them to all leaf names) the same way we do, it will give us only the "wrong" path.

This sounds like an extremely useful testing effort, by the way. Thank you for doing it. If you'd like to upstream the test cases, we'd be more than glad to merge them!

[sfllaw]

For reference, it looks like this is the result of running the https://github.com/Netflix/bettertls scanner.

[gopherbot]

Change https://go.dev/cl/389555 mentions this issue: crypto/x509: rework path building