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