constraints.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package x509
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"net"
    11  	"net/netip"
    12  	"net/url"
    13  	"slices"
    14  	"strings"
    15  )
    16  
    17  // This file contains the data structures and functions necessary for
    18  // efficiently checking X.509 name constraints. The method for constraint
    19  // checking implemented in this file is based on a technique originally
    20  // described by davidben@google.com.
    21  //
    22  // The basic concept is based on the fact that constraints describe possibly
    23  // overlapping subtrees that we need to match against. If sorted in lexicographic
    24  // order, and then pruned, removing any subtrees that overlap with preceding
    25  // subtrees, a simple binary search can be used to find the nearest matching
    26  // prefix. This reduces the complexity of name constraint checking from
    27  // quadratic to log linear complexity.
    28  //
    29  // A close reading of RFC 5280 may suggest that constraints could also be
    30  // implemented as a trie (or radix tree), which would present the possibility of
    31  // doing construction and matching in linear time, but the memory cost of
    32  // implementing them is actually quite high, and in the worst case (where each
    33  // node has a high number of children) can be abused to require a program to use
    34  // significant amounts of memory. The log linear approach taken here is
    35  // extremely cheap in terms of memory because we directly alias the already
    36  // parsed constraints, thus avoiding the need to do significant additional
    37  // allocations.
    38  //
    39  // The basic data structure is nameConstraintsSet, which implements the sorting,
    40  // pruning, and querying of the prefix sets.
    41  //
    42  // In order to check IP, DNS, URI, and email constraints, we need to use two
    43  // different techniques, one for IP addresses, which is quite simple, and one
    44  // for DNS names, which additionally compose the portions of URIs and emails we
    45  // care about (technically we also need some special logic for email addresses
    46  // as well for when constraints comprise of full email addresses) which is
    47  // slightly more complex.
    48  //
    49  // IP addresses use two nameConstraintsSets, one for IPv4 addresses and one for
    50  // IPv6 addresses, with no additional logic.
    51  //
    52  // DNS names require some extra logic in order to handle the distinctions
    53  // between permitted and excluded subtrees, as well as for wildcards, and the
    54  // semantics of leading period constraints (i.e. '.example.com'). This logic is
    55  // implemented in the dnsConstraints type.
    56  //
    57  // Email addresses also require some additional logic, which does not make use
    58  // of nameConstraintsSet, to handle constraints which define full email
    59  // addresses (i.e. 'test@example.com'). For bare domain constraints, we use the
    60  // dnsConstraints type described above, querying the domain portion of the email
    61  // address. For full email addresses, we also hold a map of email addresses with
    62  // the domain portion of the email lowercased, since it is case insensitive. When
    63  // looking up an email address in the constraint set, we first check the full
    64  // email address map, and if we don't find anything, we check the domain portion
    65  // of the email address against the dnsConstraints.
    66  
    67  type nameConstraintsSet[T *net.IPNet | string, V net.IP | string] struct {
    68  	set []T
    69  }
    70  
    71  // sortAndPrune sorts the constraints using the provided comparison function, and then
    72  // prunes any constraints that are subsets of preceding constraints using the
    73  // provided subset function.
    74  func (nc *nameConstraintsSet[T, V]) sortAndPrune(cmp func(T, T) int, subset func(T, T) bool) {
    75  	if len(nc.set) < 2 {
    76  		return
    77  	}
    78  
    79  	slices.SortFunc(nc.set, cmp)
    80  
    81  	if len(nc.set) < 2 {
    82  		return
    83  	}
    84  	writeIndex := 1
    85  	for readIndex := 1; readIndex < len(nc.set); readIndex++ {
    86  		if !subset(nc.set[writeIndex-1], nc.set[readIndex]) {
    87  			nc.set[writeIndex] = nc.set[readIndex]
    88  			writeIndex++
    89  		}
    90  	}
    91  	nc.set = nc.set[:writeIndex]
    92  }
    93  
    94  // search does a binary search over the constraints set for the provided value
    95  // s, using the provided comparison function cmp to find the lower bound, and
    96  // the match function to determine if the found constraint is a prefix of s. If
    97  // a matching constraint is found, it is returned along with true. If no
    98  // matching constraint is found, the zero value of T and false are returned.
    99  func (nc *nameConstraintsSet[T, V]) search(s V, cmp func(T, V) int, match func(T, V) bool) (lowerBound T, exactMatch bool) {
   100  	if len(nc.set) == 0 {
   101  		return lowerBound, false
   102  	}
   103  	// Look for the lower bound of s in the set.
   104  	i, found := slices.BinarySearchFunc(nc.set, s, cmp)
   105  	// If we found an exact match, return it
   106  	if found {
   107  		return nc.set[i], true
   108  	}
   109  
   110  	if i < 0 {
   111  		return lowerBound, false
   112  	}
   113  
   114  	var constraint T
   115  	if i == 0 {
   116  		constraint = nc.set[0]
   117  	} else {
   118  		constraint = nc.set[i-1]
   119  	}
   120  	if match(constraint, s) {
   121  		return constraint, true
   122  	}
   123  	return lowerBound, false
   124  }
   125  
   126  func ipNetworkSubset(a, b *net.IPNet) bool {
   127  	if !a.Contains(b.IP) {
   128  		return false
   129  	}
   130  	broadcast := make(net.IP, len(b.IP))
   131  	for i := range b.IP {
   132  		broadcast[i] = b.IP[i] | (^b.Mask[i])
   133  	}
   134  	return a.Contains(broadcast)
   135  }
   136  
   137  func ipNetworkCompare(a, b *net.IPNet) int {
   138  	i := bytes.Compare(a.IP, b.IP)
   139  	if i != 0 {
   140  		return i
   141  	}
   142  	return bytes.Compare(a.Mask, b.Mask)
   143  }
   144  
   145  func ipBinarySearch(constraint *net.IPNet, target net.IP) int {
   146  	return bytes.Compare(constraint.IP, target)
   147  }
   148  
   149  func ipMatch(constraint *net.IPNet, target net.IP) bool {
   150  	return constraint.Contains(target)
   151  }
   152  
   153  type ipConstraints struct {
   154  	// NOTE: we could store IP network prefixes as a pre-processed byte slice
   155  	// (i.e. by masking the IP) and doing the byte prefix checking using faster
   156  	// techniques, but this would require allocating new byte slices, which is
   157  	// likely significantly more expensive than just operating on the
   158  	// pre-allocated *net.IPNet and net.IP objects directly.
   159  
   160  	ipv4 *nameConstraintsSet[*net.IPNet, net.IP]
   161  	ipv6 *nameConstraintsSet[*net.IPNet, net.IP]
   162  }
   163  
   164  func newIPNetConstraints(l []*net.IPNet) interface {
   165  	query(net.IP) (*net.IPNet, bool)
   166  } {
   167  	if len(l) == 0 {
   168  		return nil
   169  	}
   170  	var ipv4, ipv6 []*net.IPNet
   171  	for _, n := range l {
   172  		// Subtrees may carry non-zero host bits. Sort and search need the masked
   173  		// network address, so use a copy and leave the parsed constraint as encoded.
   174  		if masked := n.IP.Mask(n.Mask); masked != nil && !masked.Equal(n.IP) {
   175  			n = &net.IPNet{IP: masked, Mask: n.Mask}
   176  		}
   177  		if len(n.IP) == net.IPv4len {
   178  			ipv4 = append(ipv4, n)
   179  		} else {
   180  			ipv6 = append(ipv6, n)
   181  		}
   182  	}
   183  	var v4c, v6c *nameConstraintsSet[*net.IPNet, net.IP]
   184  	if len(ipv4) > 0 {
   185  		v4c = &nameConstraintsSet[*net.IPNet, net.IP]{
   186  			set: ipv4,
   187  		}
   188  		v4c.sortAndPrune(ipNetworkCompare, ipNetworkSubset)
   189  	}
   190  	if len(ipv6) > 0 {
   191  		v6c = &nameConstraintsSet[*net.IPNet, net.IP]{
   192  			set: ipv6,
   193  		}
   194  		v6c.sortAndPrune(ipNetworkCompare, ipNetworkSubset)
   195  	}
   196  	return &ipConstraints{ipv4: v4c, ipv6: v6c}
   197  }
   198  
   199  func (ipc *ipConstraints) query(ip net.IP) (*net.IPNet, bool) {
   200  	var c *nameConstraintsSet[*net.IPNet, net.IP]
   201  	if len(ip) == net.IPv4len {
   202  		c = ipc.ipv4
   203  	} else {
   204  		c = ipc.ipv6
   205  	}
   206  	if c == nil {
   207  		return nil, false
   208  	}
   209  	return c.search(ip, ipBinarySearch, ipMatch)
   210  }
   211  
   212  // dnsHasSuffix case-insensitively checks if DNS name b is a label suffix of DNS
   213  // name a, meaning that example.com is not considered a suffix of
   214  // testexample.com, but is a suffix of test.example.com.
   215  //
   216  // dnsHasSuffix supports the URI "leading period" constraint semantics, which
   217  // while not explicitly defined for dNSNames in RFC 5280, are widely supported
   218  // (see errata 5997). In particular, a constraint of ".example.com" is
   219  // considered to only match subdomains of example.com, but not example.com
   220  // itself.
   221  //
   222  // a and b must both be non-empty strings representing (mostly) valid DNS names.
   223  func dnsHasSuffix(a, b string) bool {
   224  	lenA := len(a)
   225  	lenB := len(b)
   226  	if lenA > lenB {
   227  		return false
   228  	}
   229  	i := lenA - 1
   230  	offset := lenA - lenB
   231  	for ; i >= 0; i-- {
   232  		ar, br := a[i], b[i-(offset)]
   233  		if ar == br {
   234  			continue
   235  		}
   236  		if br < ar {
   237  			ar, br = br, ar
   238  		}
   239  		if 'A' <= ar && ar <= 'Z' && br == ar+'a'-'A' {
   240  			continue
   241  		}
   242  		return false
   243  	}
   244  
   245  	if a[0] != '.' && lenB > lenA && b[lenB-lenA-1] != '.' {
   246  		return false
   247  	}
   248  
   249  	return true
   250  }
   251  
   252  // dnsCompareTable contains the ASCII alphabet mapped from a characters index in
   253  // the table to its lowercased form.
   254  var dnsCompareTable [256]byte
   255  
   256  func init() {
   257  	// NOTE: we don't actually need the
   258  	// full alphabet, but calculating offsets would be more expensive than just
   259  	// having redundant characters.
   260  	for i := 0; i < 256; i++ {
   261  		c := byte(i)
   262  		if 'A' <= c && c <= 'Z' {
   263  			// Lowercase uppercase characters A-Z.
   264  			c += 'a' - 'A'
   265  		}
   266  		dnsCompareTable[i] = c
   267  	}
   268  	// Set the period character to 0 so that we get the right sorting behavior.
   269  	//
   270  	// In particular, we need the period character to sort before the only
   271  	// other valid DNS name character which isn't a-z or 0-9, the hyphen,
   272  	// otherwise a name with a dash would be incorrectly sorted into the middle
   273  	// of another tree.
   274  	//
   275  	// For example, imagine a certificate with the constraints "a.com", "a.a.com", and
   276  	// "a-a.com". These would sort as "a.com", "a-a.com", "a.a.com", which would break
   277  	// the pruning step since we wouldn't see that "a.a.com" is a subset of "a.com".
   278  	// Sorting the period before the hyphen ensures that "a.a.com" sorts before "a-a.com".
   279  	dnsCompareTable['.'] = 0
   280  }
   281  
   282  // dnsCompare is a case-insensitive reversed implementation of strings.Compare
   283  // that operates from the end to the start of the strings. This is more
   284  // efficient that allocating reversed version of a and b and using
   285  // strings.Compare directly (even though it is highly optimized).
   286  //
   287  // NOTE: this function treats the period character ('.') as sorting above every
   288  // other character, which is necessary for us to properly sort names into their
   289  // correct order. This is further discussed in the init function above.
   290  func dnsCompare(a, b string) int {
   291  	idxA := len(a) - 1
   292  	idxB := len(b) - 1
   293  
   294  	for idxA >= 0 && idxB >= 0 {
   295  		byteA := dnsCompareTable[a[idxA]]
   296  		byteB := dnsCompareTable[b[idxB]]
   297  		if byteA == byteB {
   298  			idxA--
   299  			idxB--
   300  			continue
   301  		}
   302  		ret := 1
   303  		if byteA < byteB {
   304  			ret = -1
   305  		}
   306  		return ret
   307  	}
   308  
   309  	ret := 0
   310  	if idxA < idxB {
   311  		ret = -1
   312  	} else if idxB < idxA {
   313  		ret = 1
   314  	}
   315  	return ret
   316  }
   317  
   318  type dnsConstraints struct {
   319  	// all lets us short circuit the query logic if we see a zero length
   320  	// constraint which permits or excludes everything.
   321  	all bool
   322  
   323  	// permitted indicates if these constraints are for permitted or excluded
   324  	// names.
   325  	permitted bool
   326  
   327  	constraints *nameConstraintsSet[string, string]
   328  
   329  	// parentConstraints contains a subset of constraints which are used for
   330  	// wildcard SAN queries, which are constructed by removing the first label
   331  	// from the constraints in constraints. parentConstraints is only populated
   332  	// if permitted is false.
   333  	parentConstraints map[string]string
   334  }
   335  
   336  func newDNSConstraints(l []string, permitted bool) interface{ query(string) (string, bool) } {
   337  	if len(l) == 0 {
   338  		return nil
   339  	}
   340  	for _, n := range l {
   341  		if len(n) == 0 {
   342  			return &dnsConstraints{all: true}
   343  		}
   344  	}
   345  	constraints := slices.Clone(l)
   346  
   347  	nc := &dnsConstraints{
   348  		constraints: &nameConstraintsSet[string, string]{
   349  			set: constraints,
   350  		},
   351  		permitted: permitted,
   352  	}
   353  
   354  	nc.constraints.sortAndPrune(dnsCompare, dnsHasSuffix)
   355  
   356  	if !permitted {
   357  		parentConstraints := map[string]string{}
   358  		for _, name := range nc.constraints.set {
   359  			name = strings.ToLower(name)
   360  			trimmedName := trimFirstLabel(name)
   361  			if trimmedName == "" {
   362  				continue
   363  			}
   364  			parentConstraints[trimmedName] = name
   365  		}
   366  		if len(parentConstraints) > 0 {
   367  			nc.parentConstraints = parentConstraints
   368  		}
   369  	}
   370  
   371  	return nc
   372  }
   373  
   374  func (dnc *dnsConstraints) query(s string) (string, bool) {
   375  	if dnc.all {
   376  		return "", true
   377  	}
   378  
   379  	constraint, match := dnc.constraints.search(s, dnsCompare, dnsHasSuffix)
   380  	if match {
   381  		return constraint, true
   382  	}
   383  
   384  	if !dnc.permitted && len(s) > 0 && s[0] == '*' {
   385  		s = strings.ToLower(s)
   386  		trimmed := trimFirstLabel(s)
   387  		if constraint, found := dnc.parentConstraints[trimmed]; found {
   388  			return constraint, true
   389  		}
   390  	}
   391  	return "", false
   392  }
   393  
   394  type emailConstraints struct {
   395  	dnsConstraints interface{ query(string) (string, bool) }
   396  
   397  	// fullEmails is map of rfc2821Mailboxs that are fully specified in the
   398  	// constraints, which we need to check for separately since they don't
   399  	// follow the same matching rules as the domain-based constraints. The
   400  	// domain portion of the rfc2821Mailbox has been lowercased, since the
   401  	// domain portion is case insensitive. When checking the map for an email,
   402  	// the domain portion of the query should also be lowercased.
   403  	fullEmails map[rfc2821Mailbox]struct{}
   404  }
   405  
   406  func newEmailConstraints(l []string, permitted bool) interface {
   407  	query(rfc2821Mailbox) (string, bool)
   408  } {
   409  	if len(l) == 0 {
   410  		return nil
   411  	}
   412  	exactMap := map[rfc2821Mailbox]struct{}{}
   413  	var domains []string
   414  	for _, c := range l {
   415  		if !strings.ContainsRune(c, '@') {
   416  			domains = append(domains, c)
   417  			continue
   418  		}
   419  		parsed, ok := parseRFC2821Mailbox(c)
   420  		if !ok {
   421  			// We've already parsed these addresses in parseCertificate, and
   422  			// treat failures as a hard failure for parsing. The only way we can
   423  			// get a parse failure here is if the caller has mutated the
   424  			// certificate since parsing.
   425  			continue
   426  		}
   427  		parsed.domain = strings.ToLower(parsed.domain)
   428  		exactMap[parsed] = struct{}{}
   429  	}
   430  	ec := &emailConstraints{
   431  		fullEmails: exactMap,
   432  	}
   433  	if len(domains) > 0 {
   434  		ec.dnsConstraints = newDNSConstraints(domains, permitted)
   435  	}
   436  	return ec
   437  }
   438  
   439  func (ec *emailConstraints) query(s rfc2821Mailbox) (string, bool) {
   440  	if len(ec.fullEmails) > 0 {
   441  		if _, ok := ec.fullEmails[s]; ok {
   442  			return fmt.Sprintf("%s@%s", s.local, s.domain), true
   443  		}
   444  	}
   445  	if ec.dnsConstraints == nil {
   446  		return "", false
   447  	}
   448  	constraint, found := ec.dnsConstraints.query(s.domain)
   449  	return constraint, found
   450  }
   451  
   452  type constraints[T any, V any] struct {
   453  	constraintType string
   454  	permitted      interface{ query(V) (T, bool) }
   455  	excluded       interface{ query(V) (T, bool) }
   456  }
   457  
   458  func checkConstraints[T string | *net.IPNet, V any, P string | net.IP | parsedURI | rfc2821Mailbox](c constraints[T, V], s V, p P) error {
   459  	if c.permitted != nil {
   460  		if _, found := c.permitted.query(s); !found {
   461  			return fmt.Errorf("%s %q is not permitted by any constraint", c.constraintType, p)
   462  		}
   463  	}
   464  	if c.excluded != nil {
   465  		if constraint, found := c.excluded.query(s); found {
   466  			return fmt.Errorf("%s %q is excluded by constraint %q", c.constraintType, p, constraint)
   467  		}
   468  	}
   469  	return nil
   470  }
   471  
   472  type chainConstraints struct {
   473  	ip    constraints[*net.IPNet, net.IP]
   474  	dns   constraints[string, string]
   475  	uri   constraints[string, string]
   476  	email constraints[string, rfc2821Mailbox]
   477  
   478  	index int
   479  	next  *chainConstraints
   480  }
   481  
   482  func (cc *chainConstraints) check(dns []string, uris []parsedURI, emails []rfc2821Mailbox, ips []net.IP) error {
   483  	for _, ip := range ips {
   484  		if err := checkConstraints(cc.ip, ip, ip); err != nil {
   485  			return err
   486  		}
   487  	}
   488  	for _, d := range dns {
   489  		if !domainNameValid(d, false) {
   490  			return fmt.Errorf("x509: cannot parse dnsName %q", d)
   491  		}
   492  		if err := checkConstraints(cc.dns, d, d); err != nil {
   493  			return err
   494  		}
   495  	}
   496  	for _, u := range uris {
   497  		if !domainNameValid(u.domain, false) {
   498  			return fmt.Errorf("x509: internal error: URI SAN %q failed to parse", u)
   499  		}
   500  		if err := checkConstraints(cc.uri, u.domain, u); err != nil {
   501  			return err
   502  		}
   503  	}
   504  	for _, e := range emails {
   505  		if !domainNameValid(e.domain, false) {
   506  			return fmt.Errorf("x509: cannot parse rfc822Name %q", e)
   507  		}
   508  		if err := checkConstraints(cc.email, e, e); err != nil {
   509  			return err
   510  		}
   511  	}
   512  	return nil
   513  }
   514  
   515  func checkChainConstraints(chain []*Certificate) error {
   516  	var currentConstraints *chainConstraints
   517  	var last *chainConstraints
   518  	for i, c := range chain {
   519  		if !c.hasNameConstraints() {
   520  			continue
   521  		}
   522  		cc := &chainConstraints{
   523  			ip:    constraints[*net.IPNet, net.IP]{"IP address", newIPNetConstraints(c.PermittedIPRanges), newIPNetConstraints(c.ExcludedIPRanges)},
   524  			dns:   constraints[string, string]{"DNS name", newDNSConstraints(c.PermittedDNSDomains, true), newDNSConstraints(c.ExcludedDNSDomains, false)},
   525  			uri:   constraints[string, string]{"URI", newDNSConstraints(c.PermittedURIDomains, true), newDNSConstraints(c.ExcludedURIDomains, false)},
   526  			email: constraints[string, rfc2821Mailbox]{"email address", newEmailConstraints(c.PermittedEmailAddresses, true), newEmailConstraints(c.ExcludedEmailAddresses, false)},
   527  			index: i,
   528  		}
   529  		if currentConstraints == nil {
   530  			currentConstraints = cc
   531  			last = cc
   532  		} else if last != nil {
   533  			last.next = cc
   534  			last = cc
   535  		}
   536  	}
   537  	if currentConstraints == nil {
   538  		return nil
   539  	}
   540  
   541  	for i, c := range chain {
   542  		if !c.hasSANExtension() {
   543  			continue
   544  		}
   545  		if i >= currentConstraints.index {
   546  			for currentConstraints.index <= i {
   547  				if currentConstraints.next == nil {
   548  					return nil
   549  				}
   550  				currentConstraints = currentConstraints.next
   551  			}
   552  		}
   553  
   554  		uris, err := parseURIs(c.URIs)
   555  		if err != nil {
   556  			return err
   557  		}
   558  		emails, err := parseMailboxes(c.EmailAddresses)
   559  		if err != nil {
   560  			return err
   561  		}
   562  
   563  		for n := currentConstraints; n != nil; n = n.next {
   564  			if err := n.check(c.DNSNames, uris, emails, c.IPAddresses); err != nil {
   565  				return err
   566  			}
   567  		}
   568  	}
   569  
   570  	return nil
   571  }
   572  
   573  type parsedURI struct {
   574  	uri    *url.URL
   575  	domain string
   576  }
   577  
   578  func (u parsedURI) String() string {
   579  	return u.uri.String()
   580  }
   581  
   582  func parseURIs(uris []*url.URL) ([]parsedURI, error) {
   583  	parsed := make([]parsedURI, 0, len(uris))
   584  	for _, uri := range uris {
   585  		host := strings.ToLower(uri.Host)
   586  		if len(host) == 0 {
   587  			return nil, fmt.Errorf("URI with empty host (%q) cannot be matched against constraints", uri.String())
   588  		}
   589  		if strings.Contains(host, ":") && !strings.HasSuffix(host, "]") {
   590  			var err error
   591  			host, _, err = net.SplitHostPort(uri.Host)
   592  			if err != nil {
   593  				return nil, fmt.Errorf("cannot parse URI host %q: %v", uri.Host, err)
   594  			}
   595  		}
   596  
   597  		// netip.ParseAddr will reject the URI IPv6 literal form "[...]", so we
   598  		// check if _either_ the string parses as an IP, or if it is enclosed in
   599  		// square brackets.
   600  		if _, err := netip.ParseAddr(host); err == nil || (strings.HasPrefix(host, "[") && strings.HasSuffix(host, "]")) {
   601  			return nil, fmt.Errorf("URI with IP (%q) cannot be matched against constraints", uri.String())
   602  		}
   603  
   604  		parsed = append(parsed, parsedURI{uri, host})
   605  	}
   606  	return parsed, nil
   607  }
   608  
   609  func parseMailboxes(emails []string) ([]rfc2821Mailbox, error) {
   610  	parsed := make([]rfc2821Mailbox, 0, len(emails))
   611  	for _, email := range emails {
   612  		mailbox, ok := parseRFC2821Mailbox(email)
   613  		if !ok {
   614  			return nil, fmt.Errorf("cannot parse rfc822Name %q", email)
   615  		}
   616  		mailbox.domain = strings.ToLower(mailbox.domain)
   617  		parsed = append(parsed, mailbox)
   618  	}
   619  	return parsed, nil
   620  }
   621  
   622  func trimFirstLabel(dnsName string) string {
   623  	firstDotInd := strings.IndexByte(dnsName, '.')
   624  	if firstDotInd < 0 {
   625  		// Constraint is a single label, we cannot trim it.
   626  		return ""
   627  	}
   628  	return dnsName[firstDotInd:]
   629  }
   630
View as plain text