From 12d437c09a2ea871333547c8ac3ea536f433891b Mon Sep 17 00:00:00 2001 From: Roland Shoemaker Date: Thu, 25 Sep 2025 19:13:23 -0700 Subject: [PATCH] crypto/x509: sub-quadratic name constraint checking Previously, we implemented ~quadratic name constraint checking, wherein we would check every SAN against every respective constraint in the chain. This is the technique _basically everyone_ implements, because it's easy, but it requires also capping the total number of constraint checking operations to prevent denial of service. Instead, this change implements a log-linear checking technique, as originally described by davidben@google.com with some minor modifications. The comment at the top of crypto/x509/constraints.go describes this technique in detail. This technique is faster than the existing quadratic approach in all but one specific case, where there are a large number of constraints but only a single name, since our previous algorithm resolves to linear in that case. Change-Id: Icb761f5f9898c04e266c0d0c2b07ab2637f03418 Reviewed-on: https://go-review.googlesource.com/c/go/+/711421 Reviewed-by: Nicholas Husin Reviewed-by: Daniel McCarney LUCI-TryBot-Result: Go LUCI Auto-Submit: Roland Shoemaker Reviewed-by: Nicholas Husin --- src/crypto/x509/constraints.go | 624 +++++++++++++++++++++++++++++++++ src/crypto/x509/verify.go | 287 +-------------- src/crypto/x509/verify_test.go | 39 --- 3 files changed, 630 insertions(+), 320 deletions(-) create mode 100644 src/crypto/x509/constraints.go diff --git a/src/crypto/x509/constraints.go b/src/crypto/x509/constraints.go new file mode 100644 index 0000000000..5addedcf77 --- /dev/null +++ b/src/crypto/x509/constraints.go @@ -0,0 +1,624 @@ +// Copyright 2025 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 x509 + +import ( + "bytes" + "fmt" + "net" + "net/netip" + "net/url" + "slices" + "strings" +) + +// This file contains the data structures and functions necessary for +// efficiently checking X.509 name constraints. The method for constraint +// checking implemented in this file is based on a technique originally +// described by davidben@google.com. +// +// The basic concept is based on the fact that constraints describe possibly +// overlapping subtrees that we need to match against. If sorted in lexicographic +// order, and then pruned, removing any subtrees that overlap with preceding +// subtrees, a simple binary search can be used to find the nearest matching +// prefix. This reduces the complexity of name constraint checking from +// quadratic to log linear complexity. +// +// A close reading of RFC 5280 may suggest that constraints could also be +// implemented as a trie (or radix tree), which would present the possibility of +// doing construction and matching in linear time, but the memory cost of +// implementing them is actually quite high, and in the worst case (where each +// node has a high number of children) can be abused to require a program to use +// significant amounts of memory. The log linear approach taken here is +// extremely cheap in terms of memory because we directly alias the already +// parsed constraints, thus avoiding the need to do significant additional +// allocations. +// +// The basic data structure is nameConstraintsSet, which implements the sorting, +// pruning, and querying of the prefix sets. +// +// In order to check IP, DNS, URI, and email constraints, we need to use two +// different techniques, one for IP addresses, which is quite simple, and one +// for DNS names, which additionally compose the portions of URIs and emails we +// care about (technically we also need some special logic for email addresses +// as well for when constraints comprise of full email addresses) which is +// slightly more complex. +// +// IP addresses use two nameConstraintsSets, one for IPv4 addresses and one for +// IPv6 addresses, with no additional logic. +// +// DNS names require some extra logic in order to handle the distinctions +// between permitted and excluded subtrees, as well as for wildcards, and the +// semantics of leading period constraints (i.e. '.example.com'). This logic is +// implemented in the dnsConstraints type. +// +// Email addresses also require some additional logic, which does not make use +// of nameConstraintsSet, to handle constraints which define full email +// addresses (i.e. 'test@example.com'). For bare domain constraints, we use the +// dnsConstraints type described above, querying the domain portion of the email +// address. For full email addresses, we also hold a map of email addresses that +// map the local portion of the email to the domain. When querying full email +// addresses we then check if the local portion of the email is present in the +// map, and if so case insensitively compare the domain portion of the +// email. + +type nameConstraintsSet[T *net.IPNet | string, V net.IP | string] struct { + set []T +} + +// sortAndPrune sorts the constraints using the provided comparison function, and then +// prunes any constraints that are subsets of preceding constraints using the +// provided subset function. +func (nc *nameConstraintsSet[T, V]) sortAndPrune(cmp func(T, T) int, subset func(T, T) bool) { + if len(nc.set) < 2 { + return + } + + slices.SortFunc(nc.set, cmp) + + if len(nc.set) < 2 { + return + } + writeIndex := 1 + for readIndex := 1; readIndex < len(nc.set); readIndex++ { + if !subset(nc.set[writeIndex-1], nc.set[readIndex]) { + nc.set[writeIndex] = nc.set[readIndex] + writeIndex++ + } + } + nc.set = nc.set[:writeIndex] +} + +// search does a binary search over the constraints set for the provided value +// s, using the provided comparison function cmp to find the lower bound, and +// the match function to determine if the found constraint is a prefix of s. If +// a matching constraint is found, it is returned along with true. If no +// matching constraint is found, the zero value of T and false are returned. +func (nc *nameConstraintsSet[T, V]) search(s V, cmp func(T, V) int, match func(T, V) bool) (lowerBound T, exactMatch bool) { + if len(nc.set) == 0 { + return lowerBound, false + } + // Look for the lower bound of s in the set. + i, found := slices.BinarySearchFunc(nc.set, s, cmp) + // If we found an exact match, return it + if found { + return nc.set[i], true + } + + if i < 0 { + return lowerBound, false + } + + var constraint T + if i == 0 { + constraint = nc.set[0] + } else { + constraint = nc.set[i-1] + } + if match(constraint, s) { + return constraint, true + } + return lowerBound, false +} + +func ipNetworkSubset(a, b *net.IPNet) bool { + if !a.Contains(b.IP) { + return false + } + broadcast := make(net.IP, len(b.IP)) + for i := range b.IP { + broadcast[i] = b.IP[i] | (^b.Mask[i]) + } + return a.Contains(broadcast) +} + +func ipNetworkCompare(a, b *net.IPNet) int { + i := bytes.Compare(a.IP, b.IP) + if i != 0 { + return i + } + return bytes.Compare(a.Mask, b.Mask) +} + +func ipBinarySearch(constraint *net.IPNet, target net.IP) int { + return bytes.Compare(constraint.IP, target) +} + +func ipMatch(constraint *net.IPNet, target net.IP) bool { + return constraint.Contains(target) +} + +type ipConstraints struct { + // NOTE: we could store IP network prefixes as a pre-processed byte slice + // (i.e. by masking the IP) and doing the byte prefix checking using faster + // techniques, but this would require allocating new byte slices, which is + // likely significantly more expensive than just operating on the + // pre-allocated *net.IPNet and net.IP objects directly. + + ipv4 *nameConstraintsSet[*net.IPNet, net.IP] + ipv6 *nameConstraintsSet[*net.IPNet, net.IP] +} + +func newIPNetConstraints(l []*net.IPNet) interface { + query(net.IP) (*net.IPNet, bool) +} { + if len(l) == 0 { + return nil + } + var ipv4, ipv6 []*net.IPNet + for _, n := range l { + if len(n.IP) == net.IPv4len { + ipv4 = append(ipv4, n) + } else { + ipv6 = append(ipv6, n) + } + } + var v4c, v6c *nameConstraintsSet[*net.IPNet, net.IP] + if len(ipv4) > 0 { + v4c = &nameConstraintsSet[*net.IPNet, net.IP]{ + set: ipv4, + } + v4c.sortAndPrune(ipNetworkCompare, ipNetworkSubset) + } + if len(ipv6) > 0 { + v6c = &nameConstraintsSet[*net.IPNet, net.IP]{ + set: ipv6, + } + v6c.sortAndPrune(ipNetworkCompare, ipNetworkSubset) + } + return &ipConstraints{ipv4: v4c, ipv6: v6c} +} + +func (ipc *ipConstraints) query(ip net.IP) (*net.IPNet, bool) { + var c *nameConstraintsSet[*net.IPNet, net.IP] + if len(ip) == net.IPv4len { + c = ipc.ipv4 + } else { + c = ipc.ipv6 + } + if c == nil { + return nil, false + } + return c.search(ip, ipBinarySearch, ipMatch) +} + +// dnsHasSuffix case-insensitively checks if DNS name b is a label suffix of DNS +// name a, meaning that example.com is not considered a suffix of +// testexample.com, but is a suffix of test.example.com. +// +// dnsHasSuffix supports the URI "leading period" constraint semantics, which +// while not explicitly defined for dNSNames in RFC 5280, are widely supported +// (see errata 5997). In particular, a constraint of ".example.com" is +// considered to only match subdomains of example.com, but not example.com +// itself. +// +// a and b must both be non-empty strings representing (mostly) valid DNS names. +func dnsHasSuffix(a, b string) bool { + lenA := len(a) + lenB := len(b) + if lenA > lenB { + return false + } + i := lenA - 1 + offset := lenA - lenB + for ; i >= 0; i-- { + ar, br := a[i], b[i-(offset)] + if ar == br { + continue + } + if br < ar { + ar, br = br, ar + } + if 'A' <= ar && ar <= 'Z' && br == ar+'a'-'A' { + continue + } + return false + } + + if a[0] != '.' && lenB > lenA && b[lenB-lenA-1] != '.' { + return false + } + + return true +} + +// dnsCompareTable contains the ASCII alphabet mapped from a characters index in +// the table to its lowercased form. +var dnsCompareTable [256]byte + +func init() { + // NOTE: we don't actually need the + // full alphabet, but calculating offsets would be more expensive than just + // having redundant characters. + for i := 0; i < 256; i++ { + c := byte(i) + if 'A' <= c && c <= 'Z' { + // Lowercase uppercase characters A-Z. + c += 'a' - 'A' + } + dnsCompareTable[i] = c + } + // Set the period character to 0 so that we get the right sorting behavior. + // + // In particular, we need the period character to sort before the only + // other valid DNS name character which isn't a-z or 0-9, the hyphen, + // otherwise a name with a dash would be incorrectly sorted into the middle + // of another tree. + // + // For example, imagine a certificate with the constraints "a.com", "a.a.com", and + // "a-a.com". These would sort as "a.com", "a-a.com", "a.a.com", which would break + // the pruning step since we wouldn't see that "a.a.com" is a subset of "a.com". + // Sorting the period before the hyphen ensures that "a.a.com" sorts before "a-a.com". + dnsCompareTable['.'] = 0 +} + +// dnsCompare is a case-insensitive reversed implementation of strings.Compare +// that operates from the end to the start of the strings. This is more +// efficient that allocating reversed version of a and b and using +// strings.Compare directly (even though it is highly optimized). +// +// NOTE: this function treats the period character ('.') as sorting above every +// other character, which is necessary for us to properly sort names into their +// correct order. This is further discussed in the init function above. +func dnsCompare(a, b string) int { + idxA := len(a) - 1 + idxB := len(b) - 1 + + for idxA >= 0 && idxB >= 0 { + byteA := dnsCompareTable[a[idxA]] + byteB := dnsCompareTable[b[idxB]] + if byteA == byteB { + idxA-- + idxB-- + continue + } + ret := 1 + if byteA < byteB { + ret = -1 + } + return ret + } + + ret := 0 + if idxA < idxB { + ret = -1 + } else if idxB < idxA { + ret = 1 + } + return ret +} + +type dnsConstraints struct { + // all lets us short circuit the query logic if we see a zero length + // constraint which permits or excludes everything. + all bool + + // permitted indicates if these constraints are for permitted or excluded + // names. + permitted bool + + constraints *nameConstraintsSet[string, string] + + // parentConstraints contains a subset of constraints which are used for + // wildcard SAN queries, which are constructed by removing the first label + // from the constraints in constraints. parentConstraints is only populated + // if permitted is false. + parentConstraints map[string]string +} + +func newDNSConstraints(l []string, permitted bool) interface{ query(string) (string, bool) } { + if len(l) == 0 { + return nil + } + for _, n := range l { + if len(n) == 0 { + return &dnsConstraints{all: true} + } + } + constraints := slices.Clone(l) + + nc := &dnsConstraints{ + constraints: &nameConstraintsSet[string, string]{ + set: constraints, + }, + permitted: permitted, + } + + nc.constraints.sortAndPrune(dnsCompare, dnsHasSuffix) + + if !permitted { + parentConstraints := map[string]string{} + for _, name := range nc.constraints.set { + trimmedName := trimFirstLabel(name) + if trimmedName == "" { + continue + } + parentConstraints[trimmedName] = name + } + if len(parentConstraints) > 0 { + nc.parentConstraints = parentConstraints + } + } + + return nc +} + +func (dnc *dnsConstraints) query(s string) (string, bool) { + if dnc.all { + return "", true + } + + constraint, match := dnc.constraints.search(s, dnsCompare, dnsHasSuffix) + if match { + return constraint, true + } + + if !dnc.permitted && s[0] == '*' { + trimmed := trimFirstLabel(s) + if constraint, found := dnc.parentConstraints[trimmed]; found { + return constraint, true + } + } + return "", false +} + +type emailConstraints struct { + dnsConstraints interface{ query(string) (string, bool) } + + fullEmails map[string]string +} + +func newEmailConstraints(l []string, permitted bool) interface { + query(parsedEmail) (string, bool) +} { + if len(l) == 0 { + return nil + } + exactMap := map[string]string{} + var domains []string + for _, c := range l { + if !strings.ContainsRune(c, '@') { + domains = append(domains, c) + continue + } + parsed, ok := parseRFC2821Mailbox(c) + if !ok { + // We've already parsed these addresses in parseCertificate, and + // treat failures as a hard failure for parsing. The only way we can + // get a parse failure here is if the caller has mutated the + // certificate since parsing. + continue + } + exactMap[parsed.local] = parsed.domain + } + ec := &emailConstraints{ + fullEmails: exactMap, + } + if len(domains) > 0 { + ec.dnsConstraints = newDNSConstraints(domains, permitted) + } + return ec +} + +func (ec *emailConstraints) query(s parsedEmail) (string, bool) { + if len(ec.fullEmails) > 0 && strings.ContainsRune(s.email, '@') { + if domain, ok := ec.fullEmails[s.mailbox.local]; ok && strings.EqualFold(domain, s.mailbox.domain) { + return ec.fullEmails[s.email] + "@" + s.mailbox.domain, true + } + } + if ec.dnsConstraints == nil { + return "", false + } + constraint, found := ec.dnsConstraints.query(s.mailbox.domain) + return constraint, found +} + +type constraints[T any, V any] struct { + constraintType string + permitted interface{ query(V) (T, bool) } + excluded interface{ query(V) (T, bool) } +} + +func checkConstraints[T string | *net.IPNet, V any, P string | net.IP | parsedURI | parsedEmail](c constraints[T, V], s V, p P) error { + if c.permitted != nil { + if _, found := c.permitted.query(s); !found { + return fmt.Errorf("%s %q is not permitted by any constraint", c.constraintType, p) + } + } + if c.excluded != nil { + if constraint, found := c.excluded.query(s); found { + return fmt.Errorf("%s %q is excluded by constraint %q", c.constraintType, p, constraint) + } + } + return nil +} + +type chainConstraints struct { + ip constraints[*net.IPNet, net.IP] + dns constraints[string, string] + uri constraints[string, string] + email constraints[string, parsedEmail] + + index int + next *chainConstraints +} + +func (cc *chainConstraints) check(dns []string, uris []parsedURI, emails []parsedEmail, ips []net.IP) error { + for _, ip := range ips { + if err := checkConstraints(cc.ip, ip, ip); err != nil { + return err + } + } + for _, d := range dns { + if !domainNameValid(d, false) { + return fmt.Errorf("x509: cannot parse dnsName %q", d) + } + if err := checkConstraints(cc.dns, d, d); err != nil { + return err + } + } + for _, u := range uris { + if !domainNameValid(u.domain, false) { + return fmt.Errorf("x509: internal error: URI SAN %q failed to parse", u) + } + if err := checkConstraints(cc.uri, u.domain, u); err != nil { + return err + } + } + for _, e := range emails { + if !domainNameValid(e.mailbox.domain, false) { + return fmt.Errorf("x509: cannot parse rfc822Name %q", e.mailbox) + } + if err := checkConstraints(cc.email, e, e); err != nil { + return err + } + } + return nil +} + +func checkChainConstraints(chain []*Certificate) error { + var currentConstraints *chainConstraints + var last *chainConstraints + for i, c := range chain { + if !c.hasNameConstraints() { + continue + } + cc := &chainConstraints{ + ip: constraints[*net.IPNet, net.IP]{"IP address", newIPNetConstraints(c.PermittedIPRanges), newIPNetConstraints(c.ExcludedIPRanges)}, + dns: constraints[string, string]{"DNS name", newDNSConstraints(c.PermittedDNSDomains, true), newDNSConstraints(c.ExcludedDNSDomains, false)}, + uri: constraints[string, string]{"URI", newDNSConstraints(c.PermittedURIDomains, true), newDNSConstraints(c.ExcludedURIDomains, false)}, + email: constraints[string, parsedEmail]{"email address", newEmailConstraints(c.PermittedEmailAddresses, true), newEmailConstraints(c.ExcludedEmailAddresses, false)}, + index: i, + } + if currentConstraints == nil { + currentConstraints = cc + last = cc + } else if last != nil { + last.next = cc + last = cc + } + } + if currentConstraints == nil { + return nil + } + + for i, c := range chain { + if !c.hasSANExtension() { + continue + } + if i >= currentConstraints.index { + for currentConstraints.index <= i { + if currentConstraints.next == nil { + return nil + } + currentConstraints = currentConstraints.next + } + } + + uris, err := parseURIs(c.URIs) + if err != nil { + return err + } + emails, err := parseMailboxes(c.EmailAddresses) + if err != nil { + return err + } + + for n := currentConstraints; n != nil; n = n.next { + if err := n.check(c.DNSNames, uris, emails, c.IPAddresses); err != nil { + return err + } + } + } + + return nil +} + +type parsedURI struct { + uri *url.URL + domain string +} + +func (u parsedURI) String() string { + return u.uri.String() +} + +func parseURIs(uris []*url.URL) ([]parsedURI, error) { + parsed := make([]parsedURI, 0, len(uris)) + for _, uri := range uris { + host := strings.ToLower(uri.Host) + if len(host) == 0 { + return nil, fmt.Errorf("URI with empty host (%q) cannot be matched against constraints", uri.String()) + } + if strings.Contains(host, ":") && !strings.HasSuffix(host, "]") { + var err error + host, _, err = net.SplitHostPort(uri.Host) + if err != nil { + return nil, fmt.Errorf("cannot parse URI host %q: %v", uri.Host, err) + } + } + + // netip.ParseAddr will reject the URI IPv6 literal form "[...]", so we + // check if _either_ the string parses as an IP, or if it is enclosed in + // square brackets. + if _, err := netip.ParseAddr(host); err == nil || (strings.HasPrefix(host, "[") && strings.HasSuffix(host, "]")) { + return nil, fmt.Errorf("URI with IP (%q) cannot be matched against constraints", uri.String()) + } + + parsed = append(parsed, parsedURI{uri, host}) + } + return parsed, nil +} + +type parsedEmail struct { + email string + mailbox *rfc2821Mailbox +} + +func (e parsedEmail) String() string { + return e.mailbox.local + "@" + e.mailbox.domain +} + +func parseMailboxes(emails []string) ([]parsedEmail, error) { + parsed := make([]parsedEmail, 0, len(emails)) + for _, email := range emails { + mailbox, ok := parseRFC2821Mailbox(email) + if !ok { + return nil, fmt.Errorf("cannot parse rfc822Name %q", email) + } + mailbox.domain = strings.ToLower(mailbox.domain) + parsed = append(parsed, parsedEmail{strings.ToLower(email), &mailbox}) + } + return parsed, nil +} + +func trimFirstLabel(dnsName string) string { + firstDotInd := strings.IndexByte(dnsName, '.') + if firstDotInd < 0 { + // Constraint is a single label, we cannot trim it. + return "" + } + return dnsName[firstDotInd:] +} diff --git a/src/crypto/x509/verify.go b/src/crypto/x509/verify.go index b13e093345..fa46e226e3 100644 --- a/src/crypto/x509/verify.go +++ b/src/crypto/x509/verify.go @@ -13,9 +13,6 @@ import ( "iter" "maps" "net" - "net/netip" - "net/url" - "reflect" "runtime" "slices" "strings" @@ -430,180 +427,6 @@ func domainToReverseLabels(domain string) (reverseLabels []string, ok bool) { return reverseLabels, true } -func matchEmailConstraint(mailbox rfc2821Mailbox, constraint string, reversedDomainsCache map[string][]string, reversedConstraintsCache map[string][]string) (bool, error) { - // If the constraint contains an @, then it specifies an exact mailbox - // name. - if strings.Contains(constraint, "@") { - constraintMailbox, ok := parseRFC2821Mailbox(constraint) - if !ok { - return false, fmt.Errorf("x509: internal error: cannot parse constraint %q", constraint) - } - return mailbox.local == constraintMailbox.local && strings.EqualFold(mailbox.domain, constraintMailbox.domain), nil - } - - // Otherwise the constraint is like a DNS constraint of the domain part - // of the mailbox. - return matchDomainConstraint(mailbox.domain, constraint, reversedDomainsCache, reversedConstraintsCache) -} - -func matchURIConstraint(uri *url.URL, constraint string, reversedDomainsCache map[string][]string, reversedConstraintsCache map[string][]string) (bool, error) { - // From RFC 5280, Section 4.2.1.10: - // “a uniformResourceIdentifier that does not include an authority - // component with a host name specified as a fully qualified domain - // name (e.g., if the URI either does not include an authority - // component or includes an authority component in which the host name - // is specified as an IP address), then the application MUST reject the - // certificate.” - - host := uri.Host - if len(host) == 0 { - return false, fmt.Errorf("URI with empty host (%q) cannot be matched against constraints", uri.String()) - } - - if strings.Contains(host, ":") && !strings.HasSuffix(host, "]") { - var err error - host, _, err = net.SplitHostPort(uri.Host) - if err != nil { - return false, err - } - } - - // netip.ParseAddr will reject the URI IPv6 literal form "[...]", so we - // check if _either_ the string parses as an IP, or if it is enclosed in - // square brackets. - if _, err := netip.ParseAddr(host); err == nil || (strings.HasPrefix(host, "[") && strings.HasSuffix(host, "]")) { - return false, fmt.Errorf("URI with IP (%q) cannot be matched against constraints", uri.String()) - } - - return matchDomainConstraint(host, constraint, reversedDomainsCache, reversedConstraintsCache) -} - -func matchIPConstraint(ip net.IP, constraint *net.IPNet) (bool, error) { - if len(ip) != len(constraint.IP) { - return false, nil - } - - for i := range ip { - if mask := constraint.Mask[i]; ip[i]&mask != constraint.IP[i]&mask { - return false, nil - } - } - - return true, nil -} - -func matchDomainConstraint(domain, constraint string, reversedDomainsCache map[string][]string, reversedConstraintsCache map[string][]string) (bool, error) { - // The meaning of zero length constraints is not specified, but this - // code follows NSS and accepts them as matching everything. - if len(constraint) == 0 { - return true, nil - } - - domainLabels, found := reversedDomainsCache[domain] - if !found { - var ok bool - domainLabels, ok = domainToReverseLabels(domain) - if !ok { - return false, fmt.Errorf("x509: internal error: cannot parse domain %q", domain) - } - reversedDomainsCache[domain] = domainLabels - } - - // RFC 5280 says that a leading period in a domain name means that at - // least one label must be prepended, but only for URI and email - // constraints, not DNS constraints. The code also supports that - // behaviour for DNS constraints. - - mustHaveSubdomains := false - if constraint[0] == '.' { - mustHaveSubdomains = true - constraint = constraint[1:] - } - - constraintLabels, found := reversedConstraintsCache[constraint] - if !found { - var ok bool - constraintLabels, ok = domainToReverseLabels(constraint) - if !ok { - return false, fmt.Errorf("x509: internal error: cannot parse domain %q", constraint) - } - reversedConstraintsCache[constraint] = constraintLabels - } - - if len(domainLabels) < len(constraintLabels) || - (mustHaveSubdomains && len(domainLabels) == len(constraintLabels)) { - return false, nil - } - - for i, constraintLabel := range constraintLabels { - if !strings.EqualFold(constraintLabel, domainLabels[i]) { - return false, nil - } - } - - return true, nil -} - -// checkNameConstraints checks that c permits a child certificate to claim the -// given name, of type nameType. The argument parsedName contains the parsed -// form of name, suitable for passing to the match function. The total number -// of comparisons is tracked in the given count and should not exceed the given -// limit. -func (c *Certificate) checkNameConstraints(count *int, - maxConstraintComparisons int, - nameType string, - name string, - parsedName any, - match func(parsedName, constraint any) (match bool, err error), - permitted, excluded any) error { - - excludedValue := reflect.ValueOf(excluded) - - *count += excludedValue.Len() - if *count > maxConstraintComparisons { - return CertificateInvalidError{c, TooManyConstraints, ""} - } - - for i := 0; i < excludedValue.Len(); i++ { - constraint := excludedValue.Index(i).Interface() - match, err := match(parsedName, constraint) - if err != nil { - return CertificateInvalidError{c, CANotAuthorizedForThisName, err.Error()} - } - - if match { - return CertificateInvalidError{c, CANotAuthorizedForThisName, fmt.Sprintf("%s %q is excluded by constraint %q", nameType, name, constraint)} - } - } - - permittedValue := reflect.ValueOf(permitted) - - *count += permittedValue.Len() - if *count > maxConstraintComparisons { - return CertificateInvalidError{c, TooManyConstraints, ""} - } - - ok := true - for i := 0; i < permittedValue.Len(); i++ { - constraint := permittedValue.Index(i).Interface() - - var err error - if ok, err = match(parsedName, constraint); err != nil { - return CertificateInvalidError{c, CANotAuthorizedForThisName, err.Error()} - } - - if ok { - break - } - } - - if !ok { - return CertificateInvalidError{c, CANotAuthorizedForThisName, fmt.Sprintf("%s %q is not permitted by any constraint", nameType, name)} - } - - return nil -} - // isValid performs validity checks on c given that it is a candidate to append // to the chain in currentChain. func (c *Certificate) isValid(certType int, currentChain []*Certificate, opts *VerifyOptions) error { @@ -636,8 +459,10 @@ func (c *Certificate) isValid(certType int, currentChain []*Certificate, opts *V } } - if (certType == intermediateCertificate || certType == rootCertificate) && len(currentChain) == 0 { - return errors.New("x509: internal error: empty chain when appending CA cert") + if certType == intermediateCertificate || certType == rootCertificate { + if len(currentChain) == 0 { + return errors.New("x509: internal error: empty chain when appending CA cert") + } } // KeyUsage status flags are ignored. From Engineering Security, Peter @@ -794,9 +619,9 @@ func (c *Certificate) Verify(opts VerifyOptions) ([][]*Certificate, error) { incompatibleKeyUsageChains++ return true } - if err := checkChainConstraints(chain, opts); err != nil { + if err := checkChainConstraints(chain); err != nil { if constraintsHintErr == nil { - constraintsHintErr = err + constraintsHintErr = CertificateInvalidError{c, CANotAuthorizedForThisName, err.Error()} } return true } @@ -1182,106 +1007,6 @@ NextCert: return true } -func checkChainConstraints(chain []*Certificate, opts VerifyOptions) error { - maxConstraintComparisons := opts.MaxConstraintComparisions - if maxConstraintComparisons == 0 { - maxConstraintComparisons = 250000 - } - comparisonCount := 0 - - // Each time we do constraint checking, we need to check the constraints in - // the current certificate against all of the names that preceded it. We - // reverse these names using domainToReverseLabels, which is a relatively - // expensive operation. Since we check each name against each constraint, - // this requires us to do N*C calls to domainToReverseLabels (where N is the - // total number of names that preceed the certificate, and C is the total - // number of constraints in the certificate). By caching the results of - // calling domainToReverseLabels, we can reduce that to N+C calls at the - // cost of keeping all of the parsed names and constraints in memory until - // we return from isValid. - reversedDomainsCache := map[string][]string{} - reversedConstraintsCache := map[string][]string{} - - for i, c := range chain { - if !c.hasNameConstraints() { - continue - } - for _, sanCert := range chain[:i] { - if !sanCert.hasSANExtension() { - continue - } - 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) - } - - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "email address", name, mailbox, - func(parsedName, constraint any) (bool, error) { - return matchEmailConstraint(parsedName.(rfc2821Mailbox), constraint.(string), reversedDomainsCache, reversedConstraintsCache) - }, c.PermittedEmailAddresses, c.ExcludedEmailAddresses); err != nil { - return err - } - - case nameTypeDNS: - name := string(data) - if !domainNameValid(name, false) { - return fmt.Errorf("x509: cannot parse dnsName %q", name) - } - - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "DNS name", name, name, - func(parsedName, constraint any) (bool, error) { - return matchDomainConstraint(parsedName.(string), constraint.(string), reversedDomainsCache, reversedConstraintsCache) - }, c.PermittedDNSDomains, c.ExcludedDNSDomains); 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) - } - - if err := c.checkNameConstraints(&comparisonCount, maxConstraintComparisons, "URI", name, uri, - func(parsedName, constraint any) (bool, error) { - return matchURIConstraint(parsedName.(*url.URL), constraint.(string), reversedDomainsCache, reversedConstraintsCache) - }, c.PermittedURIDomains, c.ExcludedURIDomains); 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) - } - - 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 - } - - default: - // Unknown SAN types are ignored. - } - - return nil - }) - - if err != nil { - return err - } - } - } - - return nil -} - func mustNewOIDFromInts(ints []uint64) OID { oid, err := OIDFromInts(ints) if err != nil { diff --git a/src/crypto/x509/verify_test.go b/src/crypto/x509/verify_test.go index 17e7aaf897..6dadba3a56 100644 --- a/src/crypto/x509/verify_test.go +++ b/src/crypto/x509/verify_test.go @@ -1331,45 +1331,6 @@ func TestUnknownAuthorityError(t *testing.T) { } } -var nameConstraintTests = []struct { - constraint, domain string - expectError bool - shouldMatch bool -}{ - {"", "anything.com", false, true}, - {"example.com", "example.com", false, true}, - {"example.com.", "example.com", true, false}, - {"example.com", "example.com.", true, false}, - {"example.com", "ExAmPle.coM", false, true}, - {"example.com", "exampl1.com", false, false}, - {"example.com", "www.ExAmPle.coM", false, true}, - {"example.com", "sub.www.ExAmPle.coM", false, true}, - {"example.com", "notexample.com", false, false}, - {".example.com", "example.com", false, false}, - {".example.com", "www.example.com", false, true}, - {".example.com", "www..example.com", true, false}, -} - -func TestNameConstraints(t *testing.T) { - for i, test := range nameConstraintTests { - result, err := matchDomainConstraint(test.domain, test.constraint, map[string][]string{}, map[string][]string{}) - - if err != nil && !test.expectError { - t.Errorf("unexpected error for test #%d: domain=%s, constraint=%s, err=%s", i, test.domain, test.constraint, err) - continue - } - - if err == nil && test.expectError { - t.Errorf("unexpected success for test #%d: domain=%s, constraint=%s", i, test.domain, test.constraint) - continue - } - - if result != test.shouldMatch { - t.Errorf("unexpected result for test #%d: domain=%s, constraint=%s, result=%t", i, test.domain, test.constraint, result) - } - } -} - const selfSignedWithCommonName = `-----BEGIN CERTIFICATE----- MIIDCjCCAfKgAwIBAgIBADANBgkqhkiG9w0BAQsFADAaMQswCQYDVQQKEwJjYTEL MAkGA1UEAxMCY2EwHhcNMTYwODI4MTcwOTE4WhcNMjEwODI3MTcwOTE4WjAcMQsw -- 2.52.0