crypto/x509: quadratic complexity when checking name constraints (CVE-2025-58187)

[neild]

Due to the design of the name constraint checking algorithm, the processing time
of some inputs scales non-linearly with respect to the size of the certificate.

This affects programs which validate arbitrary certificate chains.

Thanks to Jakub Ciolek for reporting this issue.

This is CVE-2025-58187 and Go issue https://go.dev/issue/75681.

---

This is a PRIVATE issue for CVE-2025-58187, tracked in http://b/443719585 and fixed by https://go-internal-review.git.corp.google.com/c/go/+/2820.

/cc @golang/security and @golang/release

[neild]

@gopherbot please open backport issues for this security fix

[gopherbot]

Backport issue(s) opened: #75714 (for 1.24), #75715 (for 1.25).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

[gopherbot]

Change https://go.dev/cl/709839 mentions this issue: [release-branch.go1.24] crypto/x509: improve domain name verification

[gopherbot]

Change https://go.dev/cl/709848 mentions this issue: [release-branch.go1.25] crypto/x509: improve domain name verification

[gopherbot]

Change https://go.dev/cl/709854 mentions this issue: crypto/x509: improve domain name verification