government / policy / graph.go

@ 53308ffa01ed91d41c6657b16c77ee7a97ad8d3b | 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
}

func (n *Node) expects(p x509.OID) bool {
	return slices.ContainsFunc(n.Expected, p.Equal)
}

// 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
}

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) (*Graph, error) {
	root := &Node{Policy: AnyPolicy, Expected: []x509.OID{AnyPolicy}}
	g := &Graph{Levels: [][]*Node{{root}}}
	for i := 1; i < len(certs); i++ {
		if err := g.addCert(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)
	}
	parents := g.Levels[i-1]
	var level []*Node
	byPolicy := map[string]*Node{}
	add := func(p x509.OID, from []*Node) {
		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
	}
	expecting := func(p x509.OID) []*Node {
		var from []*Node
		for _, parent := range parents {
			if parent.expects(p) {
				from = append(from, parent)
			}
		}
		return from
	}

	// (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 {
			add(p, from)
		}
	}

	// (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 {
					add(p, expecting(p))
				}
			}
		}
	}

	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.
func (g *Graph) prune(i int) {
	for d := i - 1; d >= 0; d-- {
		kept := g.Levels[d][:0]
		for _, n := range g.Levels[d] {
			if len(n.Children) > 0 {
				kept = append(kept, n)
				continue
			}
			for _, parent := range n.Parents {
				parent.Children = slices.DeleteFunc(parent.Children, func(c *Node) bool { return c == n })
			}
		}
		g.Levels[d] = kept
	}
}

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)
}