government / policy / graph.go

@ 2dbe47969d09d4856796bbf662b4e11c74a7f4fe | history


package policy

import (
	"crypto/x509"
	"crypto/x509/pkix"
	"encoding/asn1"
	"slices"
)

var (
	// AnyPolicy is the wildcard: a cert asserting it accepts whatever its
	// issuer's nodes expect.
	AnyPolicy = mustOID("2.5.29.32.0")

	oidCertificatePolicies = asn1.ObjectIdentifier{2, 5, 29, 32}
)

func mustOID(s string) x509.OID {
	oid, err := x509.ParseOID(s)
	if err != nil {
		panic(err)
	}
	return oid
}

// Node is one node of the valid policy graph: a policy that holds along
// the path from the root down to its depth.
type Node struct {
	Policy x509.OID
	Depth  int
	// RFC 9618 lets a node have several parents, where RFC 5280's tree
	// would have copied it under each one.
	Parents  []*Node
	Children []*Node
	// Expected is the expected_policy_set: the policies the next cert may
	// assert under this node. It is the node's own policy unless a mapping
	// replaces it.
	Expected []x509.OID
	// Note is the user-notice text the cert attached to this policy, if
	// it named the policy itself. Nodes made by anyPolicy have none.
	Note string
}

// Graph is the valid policy graph after the whole path. Levels[0] holds the
// root, an anyPolicy node; Levels[i] holds the nodes made by cert i.
type Graph struct {
	Levels [][]*Node
	// budget is how many more nodes may be made.
	budget int
}

// DefaultMaxNodes caps the graph's size. Policy processing has caused real
// denial-of-service bugs (Go's CVE-2026-32281 among them): a small file
// can ask for a very large graph, so the budget is checked as nodes are
// made, not after.
const DefaultMaxNodes = 1_000_000

type Options struct {
	// MaxNodes is the most nodes the graph may hold, counting the
	// validator's copies. 0 means DefaultMaxNodes.
	MaxNodes int
}

func (o Options) maxNodes() int {
	if o.MaxNodes == 0 {
		return DefaultMaxNodes
	}
	return o.MaxNodes
}

func (g *Graph) spend(depth int) error {
	if g.budget == 0 {
		return errorf(ErrTooLarge, "the policy graph needs more than its node budget at depth %d (see --max-nodes)", depth)
	}
	g.budget--
	return nil
}

func (g *Graph) Depth() int { return len(g.Levels) - 1 }

// Process runs policy processing over a ratified chain, anchor first. The
// anchor is the trust anchor, not part of the path, so the path is
// certs[1:], and cert i is certs[i].
//
// The inputs are fixed by the design: user-initial-policy-set {anyPolicy},
// explicit policy required, anyPolicy and mappings not inhibited. Ratify
// already rejected policyConstraints and inhibitAnyPolicy, so the RFC's
// three counters never reach zero and are left out.
func Process(certs []*x509.Certificate, opts Options) (*Graph, error) {
	root := &Node{Policy: AnyPolicy, Expected: []x509.OID{AnyPolicy}}
	g := &Graph{Levels: [][]*Node{{root}}, budget: opts.maxNodes()}
	n := len(certs) - 1
	for i := 1; i <= n; i++ {
		if err := g.addCert(i, certs[i]); err != nil {
			return nil, err
		}
		// 6.1.4 prepares for the next cert, so it runs for certs 1..n-1
		// only; mappings in cert n would never be read.
		if i < n {
			if err := g.applyMappings(i, certs[i]); err != nil {
				return nil, err
			}
		}
	}
	return g, nil
}

// addCert is RFC 5280 6.1.3 (d)-(f) for cert i, in RFC 9618's graph form.
func (g *Graph) addCert(i int, c *x509.Certificate) error {
	// (e): a cert with no certificatePolicies extension empties the graph,
	// and (f): with explicit policy required, an empty graph is a failure.
	if !hasExtension(c, oidCertificatePolicies) {
		return errorf(ErrPolicy, "cert %d has no certificatePolicies, so no policy holds past depth %d", i, i-1)
	}
	notes, err := notesIn(c)
	if err != nil {
		return errorf(ErrPolicy, "cert %d: %v", i, err)
	}
	parents := g.Levels[i-1]
	var level []*Node
	byPolicy := map[string]*Node{}
	add := func(p x509.OID, from []*Node) error {
		if err := g.spend(i); err != nil {
			return err
		}
		n := &Node{Policy: p, Depth: i, Parents: from, Expected: []x509.OID{p}}
		for _, parent := range from {
			parent.Children = append(parent.Children, n)
		}
		level = append(level, n)
		byPolicy[key(p)] = n
		return nil
	}
	// Which parents expect each policy, built once: looking each policy up
	// by scanning every parent would make a wide level cost its width
	// squared, a denial of service the node budget alone does not stop.
	expectedBy := map[string][]*Node{}
	for _, parent := range parents {
		for _, p := range parent.Expected {
			k := key(p)
			expectedBy[k] = append(expectedBy[k], parent)
		}
	}
	expecting := func(p x509.OID) []*Node { return expectedBy[key(p)] }

	// (d)(1): each policy the cert names goes under every node that
	// expects it, or failing that under an anyPolicy node. A policy with
	// neither is dropped without a word; the strict check catches that.
	assertsAny := false
	for _, p := range c.Policies {
		if p.Equal(AnyPolicy) {
			assertsAny = true
			continue
		}
		if byPolicy[key(p)] != nil {
			continue
		}
		from := expecting(p)
		if len(from) == 0 {
			for _, parent := range parents {
				if parent.Policy.Equal(AnyPolicy) {
					from = append(from, parent)
				}
			}
		}
		if len(from) > 0 {
			if err := add(p, from); err != nil {
				return err
			}
			byPolicy[key(p)].Note = notes[key(p)]
		}
	}

	// (d)(2), RFC 9618's form: anyPolicy in the cert creates every policy
	// some parent expects that has no node yet. This is the rule that lets
	// certs 2..n list nothing but anyPolicy: it creates each mapped child,
	// and copies down each atom that expects only itself.
	if assertsAny {
		for _, parent := range parents {
			for _, p := range parent.Expected {
				if byPolicy[key(p)] == nil {
					if err := add(p, expecting(p)); err != nil {
						return err
					}
				}
			}
		}
	}

	g.Levels = append(g.Levels, level)
	g.prune(i)
	if len(level) == 0 {
		return errorf(ErrPolicy, "no policy holds at depth %d: cert %d asserts nothing its issuer expects", i, i)
	}
	return nil
}

// prune is (d)(3): delete every node at depth i-1 or above that has no
// children, repeatedly, since each deletion can leave its parents
// childless. Going up one level at a time does it in one pass, and the
// pass stops at the first level where nothing died: after the previous
// cert's prune only the newest level can hold childless nodes, so the
// levels above it are untouched unless a deletion reaches them. Each
// affected parent's children are filtered once, so the cost is the number
// of edges removed, not deletions times siblings or certs times levels.
func (g *Graph) prune(i int) {
	for d := i - 1; d >= 0; d-- {
		kept := g.Levels[d][:0]
		dead := map[*Node]bool{}
		for _, n := range g.Levels[d] {
			if len(n.Children) > 0 {
				kept = append(kept, n)
			} else {
				dead[n] = true
			}
		}
		g.Levels[d] = kept
		if len(dead) == 0 {
			return
		}
		done := map[*Node]bool{}
		for n := range dead {
			for _, parent := range n.Parents {
				if !done[parent] {
					done[parent] = true
					parent.Children = slices.DeleteFunc(parent.Children, func(c *Node) bool { return dead[c] })
				}
			}
		}
	}
}

func hasExtension(c *x509.Certificate, id asn1.ObjectIdentifier) bool {
	return slices.ContainsFunc(c.Extensions, func(e pkix.Extension) bool { return e.Id.Equal(id) })
}

// key makes an OID usable as a map key. x509.OID is a byte slice inside,
// so it cannot be one directly.
func key(oid x509.OID) string {
	b, _ := oid.MarshalBinary()
	return string(b)
}

// applyMappings is RFC 5280 6.1.4 (a)-(b) for cert i, with mappings
// allowed. A mapping says "my policy P is equivalent to your policy Q":
// the next cert may then assert Q where this one asserted P. So each node
// at depth i whose policy is an issuerDomainPolicy now expects the mapped
// subjectDomainPolicy values instead of itself. For GOVERNMENT a mapping is
// a parent->child edge, and the expected set is a list node's elements.
func (g *Graph) applyMappings(i int, c *x509.Certificate) error {
	if len(c.PolicyMappings) == 0 {
		return nil
	}
	mapped := map[string][]x509.OID{}
	var issuers []x509.OID
	for _, m := range c.PolicyMappings {
		// (a): anyPolicy may not appear on either side of a mapping.
		if m.IssuerDomainPolicy.Equal(AnyPolicy) || m.SubjectDomainPolicy.Equal(AnyPolicy) {
			return errorf(ErrPolicy, "cert %d maps anyPolicy, which RFC 5280 forbids", i)
		}
		k := key(m.IssuerDomainPolicy)
		if _, seen := mapped[k]; !seen {
			issuers = append(issuers, m.IssuerDomainPolicy)
		}
		if !slices.ContainsFunc(mapped[k], m.SubjectDomainPolicy.Equal) {
			mapped[k] = append(mapped[k], m.SubjectDomainPolicy)
		}
	}

	level := g.Levels[i]
	byPolicy := map[string][]*Node{}
	for _, n := range level {
		k := key(n.Policy)
		byPolicy[k] = append(byPolicy[k], n)
	}
	for _, p := range issuers {
		nodes := byPolicy[key(p)]
		for _, n := range nodes {
			n.Expected = mapped[key(p)]
		}
		if len(nodes) > 0 {
			continue
		}
		// (b)(1), second half: with no node for P but an anyPolicy node at
		// this depth, P is taken to hold under it, as a new node with the
		// anyPolicy node's parents. GOVERNMENT never asserts anyPolicy in
		// cert 1, so this only matters for chains built by other tools.
		for _, anyNode := range level {
			if !anyNode.Policy.Equal(AnyPolicy) {
				continue
			}
			if err := g.spend(i); err != nil {
				return err
			}
			n := &Node{Policy: p, Depth: i, Parents: slices.Clone(anyNode.Parents), Expected: mapped[key(p)]}
			for _, parent := range n.Parents {
				parent.Children = append(parent.Children, n)
			}
			g.Levels[i] = append(g.Levels[i], n)
			break
		}
	}
	return nil
}