@ a94ce18dbaa3c27d01f1491d51ec12c5767daf6d | 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
}