government / src / policy / strict.go

@ 9691322d33532d2feea494209d4df63e32ee99be | history


package policy

import (
	"crypto/x509"
	"strings"

	"nmyk.io/government/ast"
)

// Program runs policy processing the GOVERNMENT way: it checks the shape
// the compiler always writes, runs RFC processing with a node budget, then
// checks that processing kept everything the certs asked for.
//
// RFC processing is forgiving by design: a policy that attaches nowhere,
// or a mapping from a policy with no node, is silently dropped, because a
// relying party only needs to know which policies survive. For a program,
// every dropped policy is dropped code, so the strict check turns each one
// into an error.
func Program(certs []*x509.Certificate, opts Options) (*Graph, error) {
	if err := checkShape(certs); err != nil {
		return nil, err
	}
	g, err := Process(certs, opts)
	if err != nil {
		return nil, err
	}
	if err := g.checkKept(certs); err != nil {
		return nil, err
	}
	if err := g.checkIDs(); err != nil {
		return nil, err
	}
	return g, nil
}

// checkShape enforces what the compiler always writes: cert 1 lists the
// top-level nodes and never anyPolicy, certs 2..n assert anyPolicy, and
// cert n has no mappings, which RFC 5280 would never read.
func checkShape(certs []*x509.Certificate) error {
	n := len(certs) - 1
	for i := 1; i <= n; i++ {
		asserts := false
		for _, p := range certs[i].Policies {
			if p.Equal(AnyPolicy) {
				asserts = true
			}
		}
		switch {
		case i == 1 && asserts:
			return errorf(ErrPolicy, "cert 1 asserts anyPolicy; it must list the top-level forms only")
		case i > 1 && !asserts:
			return errorf(ErrPolicy, "cert %d does not assert anyPolicy, so nothing below depth %d can exist", i, i-1)
		}
	}
	if len(certs[n].PolicyMappings) > 0 {
		return errorf(ErrPolicy, "cert %d is the last and has mappings, which are never processed", n)
	}
	return nil
}

// checkKept checks that processing dropped nothing: every policy a cert
// names is a node at that cert's depth, and every mapping became an edge.
func (g *Graph) checkKept(certs []*x509.Certificate) error {
	for i := 1; i <= g.Depth(); i++ {
		for _, p := range certs[i].Policies {
			if !p.Equal(AnyPolicy) && g.find(i, p) == nil {
				return errorf(ErrPolicy, "orphaned policy %s at depth %d: it attaches to nothing", short(p), i)
			}
		}
		if i == g.Depth() {
			break
		}
		for _, m := range certs[i].PolicyMappings {
			parent := g.find(i, m.IssuerDomainPolicy)
			if parent == nil {
				return errorf(ErrPolicy, "orphaned mapping %s -> %s in cert %d: %s is not a node at depth %d",
					short(m.IssuerDomainPolicy), short(m.SubjectDomainPolicy), i, short(m.IssuerDomainPolicy), i)
			}
			if !hasChild(parent, m.SubjectDomainPolicy) {
				return errorf(ErrPolicy, "orphaned mapping %s -> %s in cert %d: no such child at depth %d",
					short(m.IssuerDomainPolicy), short(m.SubjectDomainPolicy), i, i+1)
			}
		}
	}
	return nil
}

// checkIDs checks that every node is a GOVERNMENT node and the program's
// node ids are exactly 1..N. The compiler numbers every node, so a gap
// means a subtree went missing between compiling and running, and a node
// whose mappings were lost would otherwise decode as a shorter program.
// One loss this cannot see is the subtree holding the highest ids, which
// leaves no gap; signatures rule out tampering, so only a compiler bug can
// cause it, and the round-trip tests are what catch that.
func (g *Graph) checkIDs() error {
	byID := map[uint64]string{}
	var maxID uint64
	for d := 1; d <= g.Depth(); d++ {
		for _, n := range g.Levels[d] {
			_, id, _, err := ast.DecodeOID(n.Policy)
			if err != nil {
				return errorf(ErrPolicy, "depth %d: %v", d, err)
			}
			if prev, ok := byID[id]; ok && prev != key(n.Policy) {
				return errorf(ErrPolicy, "depth %d: two different nodes use id %d", d, id)
			}
			byID[id] = key(n.Policy)
			maxID = max(maxID, id)
		}
	}
	for id := uint64(1); id <= maxID; id++ {
		if _, ok := byID[id]; !ok {
			return errorf(ErrPolicy, "node id %d is missing (ids run to %d): a subtree was lost", id, maxID)
		}
	}
	return nil
}

func (g *Graph) find(depth int, p x509.OID) *Node {
	for _, n := range g.Levels[depth] {
		if n.Policy.Equal(p) {
			return n
		}
	}
	return nil
}

func hasChild(n *Node, p x509.OID) bool {
	for _, c := range n.Children {
		if c.Policy.Equal(p) {
			return true
		}
	}
	return false
}

// short prints an OID with GOV in place of the root arc, as tools do.
func short(oid x509.OID) string {
	return strings.Replace(oid.String(), ast.Root, "GOV", 1)
}