crypto/x509: quadratic work in policy validation with large PolicyMappings (CVE-2026-32281) #78281

Go version

go 1.26.1

Output of go env in your module/workspace:

GOARCH=arm64

What did you do?

Note: This was reported to security@golang.org and assigned a PUBLIC track.

Confirmed on Go 1.26.1 that x509.Certificate.Verify can become pathologically slow during certificate policy validation in the Go verifier.

The expensive path is reached after a candidate chain has already been built to a trusted root. If an intermediate contains a large PolicyMappings extension and policy mapping has already been inhibited by an earlier certificate (InhibitPolicyMapping=0), verification does much more work than expected.

Representative local measurement on Apple M2 with GOMAXPROCS=1: about 79 ms in a baseline case versus about 3715 ms with roughly 1 MB of certificate data.

What did you see happen?

In crypto/x509/verify.go, Verify builds candidate chains first and then calls policiesValid on them.

Inside policiesValid, when policyMapping > 0, mappings are collected and applied. But when policyMapping == 0, the current code deletes one mapped policy and then calls pg.prune() for each entry in cert.PolicyMappings.

Because pg.prune() rescans the policy graph that has already been built, doing that inside the loop repeats the same work many times. With large PolicyMappings inputs, verification time appears to grow roughly quadratically with the number of mappings.

This seems most relevant to applications that verify peer-supplied certificate chains against a configured root pool, such as mTLS/private PKI services or APIs that accept certificate chains as input.

What did you expect to see?

Once policy mapping has been inhibited, policy validation should not rescan the policy graph once per mapping entry. Verification time should remain reasonable for large PolicyMappings inputs.

Additional reproduction details were shared with the security team.