government / src / lisp2gov / openssl_test.go

@ 761f3b207460ae5814dd76a326ce14777e29e659 | history


package lisp2gov

import (
	"bytes"
	"cmp"
	"crypto/rand"
	"crypto/x509"
	"encoding/pem"
	"math/big"
	"os"
	"os/exec"
	"path/filepath"
	"slices"
	"strconv"
	"strings"
	"testing"
	"time"

	"government/internal/lisptest"
	"government/program"
)

// OpenSSL is an independent implementation of the same RFC 5280 path
// validation, so it should agree with GOVERNMENT on which programs are
// lawful. These tests compare decisions, not trees: openssl verify prints
// only the top-level policies. They are skipped when openssl is absent.
//
// They also pin down where the two disagree, each for a stated reason, so
// a change on either side shows up here.
//
// $GOVERNMENT_OPENSSL names the binary to use, for a machine whose openssl
// is something else: macOS ships LibreSSL as openssl, and older LibreSSL
// cannot verify Ed25519 certificates at all.

var opensslBinary = cmp.Or(os.Getenv("GOVERNMENT_OPENSSL"), "openssl")

func needOpenSSL(t *testing.T) {
	t.Helper()
	if _, err := exec.LookPath(opensslBinary); err != nil {
		t.Skipf("%s not installed", opensslBinary)
	}
	out, err := exec.Command(opensslBinary, "version").Output()
	if err != nil {
		t.Skipf("%s version: %v", opensslBinary, err)
	}
	version := strings.TrimSpace(string(out))
	if !strings.HasPrefix(version, "OpenSSL ") {
		t.Skipf("%s is %s, not OpenSSL; set GOVERNMENT_OPENSSL to an OpenSSL binary", opensslBinary, version)
	}
	t.Log(version)
}

type verdict struct {
	ok  bool
	out string
}

// opensslVerify runs openssl verify on a chain with the inputs DESIGN.md
// fixes for GOVERNMENT: explicit policy, anyPolicy as the acceptable set,
// strict X.509 checks. The anchor is the only trusted cert, the last cert
// is the one verified, and the rest are untrusted intermediates. With
// CRLs, every cert in the path is checked, so each issuer needs one.
func opensslVerify(t *testing.T, anchor *x509.Certificate, path []*x509.Certificate, at time.Time, crls [][]byte) verdict {
	t.Helper()
	dir := t.TempDir()
	write := func(name string, ders ...[]byte) string {
		var b bytes.Buffer
		for _, der := range ders {
			pem.Encode(&b, &pem.Block{Type: "CERTIFICATE", Bytes: der})
		}
		p := filepath.Join(dir, name)
		if err := os.WriteFile(p, b.Bytes(), 0o644); err != nil {
			t.Fatal(err)
		}
		return p
	}
	args := []string{"verify", "-x509_strict", "-policy_check", "-explicit_policy",
		"-policy", "2.5.29.32.0", "-policy_print", "-verify_depth", "1000",
		"-attime", strconv.FormatInt(at.Unix(), 10),
		"-CAfile", write("anchor.pem", anchor.Raw)}
	if len(path) > 1 {
		var mid [][]byte
		for _, c := range path[:len(path)-1] {
			mid = append(mid, c.Raw)
		}
		args = append(args, "-untrusted", write("chain.pem", mid...))
	}
	if len(crls) > 0 {
		p := filepath.Join(dir, "crls.pem")
		if err := os.WriteFile(p, bytes.Join(crls, nil), 0o644); err != nil {
			t.Fatal(err)
		}
		args = append(args, "-crl_check_all", "-CRLfile", p)
	}
	args = append(args, write("leaf.pem", path[len(path)-1].Raw))
	out, err := exec.Command(opensslBinary, args...).CombinedOutput()
	return verdict{ok: err == nil, out: string(out)}
}

// authorityPolicies is the policy set openssl verify -policy_print reports:
// the policies of the first level of its tree, GOVERNMENT's top-level forms.
func authorityPolicies(out string) []string {
	_, after, _ := strings.Cut(out, "Authority Policies:")
	section, _, _ := strings.Cut(after, "User Policies:")
	var oids []string
	for _, line := range strings.Split(section, "\n") {
		if oid, ok := strings.CutPrefix(strings.TrimSpace(line), "Policy: "); ok {
			oids = append(oids, oid)
		}
	}
	slices.Sort(oids)
	return oids
}

func topLevelPolicies(cert1 *x509.Certificate) []string {
	var oids []string
	for _, p := range cert1.Policies {
		oids = append(oids, p.String())
	}
	slices.Sort(oids)
	return oids
}

func ours(data []byte, at time.Time, crls [][]byte) error {
	_, err := program.Load(data, program.Options{At: at, CRLs: crls})
	return err
}

// TestOpenSSLAcceptsEveryProgram: every test program and example, shared
// and not, passes OpenSSL's path validation, and OpenSSL finds the same
// top-level policies the first cert lists.
func TestOpenSSLAcceptsEveryProgram(t *testing.T) {
	needOpenSSL(t)
	paths, _ := lisptest.Files()
	examples, _ := lisptest.Examples()
	paths = append(append(paths, examples...), "testdata/golden.gov.lisp")
	at := time.Date(2028, 1, 1, 0, 0, 0, 0, time.UTC)
	for _, path := range paths {
		src, err := os.ReadFile(path)
		if err != nil {
			t.Fatal(err)
		}
		for _, noShare := range []bool{false, true} {
			name := strings.TrimSuffix(filepath.Base(path), ".gov.lisp")
			if noShare {
				name += "/no-share"
			}
			t.Run(name, func(t *testing.T) {
				opts := goldenOpts
				opts.Name, opts.NoShare = name, noShare
				data, err := Compile(string(src), opts)
				if err != nil {
					t.Fatal(err)
				}
				certs := parsePEM(t, data)
				if err := ours(data, at, nil); err != nil {
					t.Fatalf("GOVERNMENT refuses it: %v", err)
				}
				v := opensslVerify(t, certs[0], certs[1:], at, nil)
				if !v.ok {
					t.Fatalf("OpenSSL refuses it:\n%s", v.out)
				}
				if got, want := authorityPolicies(v.out), topLevelPolicies(certs[1]); !slices.Equal(got, want) {
					t.Errorf("OpenSSL's top-level policies %v, want %v", got, want)
				}
			})
		}
	}
}

// TestOpenSSLRejectsBrokenPrograms: the mutations GOVERNMENT refuses,
// OpenSSL refuses too.
func TestOpenSSLRejectsBrokenPrograms(t *testing.T) {
	needOpenSSL(t)
	data, err := Compile("(define sq (lambda (n) (* n n)))\n(sq (+ 1 2))", goldenOpts)
	if err != nil {
		t.Fatal(err)
	}
	certs := parsePEM(t, data)
	inForce := time.Date(2028, 1, 1, 0, 0, 0, 0, time.UTC)
	other := [32]byte{'o', 't', 'h', 'e', 'r'}
	foreignData, err := Compile("1", Options{Seed: &other})
	if err != nil {
		t.Fatal(err)
	}
	foreign := parsePEM(t, foreignData)

	flipped := slices.Clone(certs)
	raw := bytes.Clone(certs[2].Raw)
	raw[len(raw)-2] ^= 1 // inside the signature
	if flipped[2], err = x509.ParseCertificate(raw); err != nil {
		t.Fatal(err)
	}

	tests := []struct {
		name    string
		anchor  *x509.Certificate
		path    []*x509.Certificate
		at      time.Time
		code    string // GOVERNMENT's refusal
		openssl string // OpenSSL's
	}{
		{"flipped signature byte", certs[0], flipped[1:], inForce, "E-TAMPERED", "certificate signature failure"},
		{"missing depth", certs[0], append(slices.Clone(certs[1:2]), certs[3:]...), inForce, "E-CHAIN", "unable to get local issuer certificate"},
		{"another author's anchor", foreign[0], certs[1:], inForce, "E-FOREIGN", "unable to get local issuer certificate"},
		{"before it takes effect", certs[0], certs[1:], goldenOpts.NotBefore.Add(-time.Second), "E-NOT-IN-FORCE", "certificate is not yet valid"},
		{"after it expires", certs[0], certs[1:], goldenOpts.NotAfter.Add(time.Second), "E-LAPSED", "certificate has expired"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			// GOVERNMENT gets the same chain as one file, and is pinned to
			// the anchor OpenSSL trusts.
			var file []byte
			for _, c := range append([]*x509.Certificate{certs[0]}, tt.path...) {
				file = append(file, pem.EncodeToMemory(&pem.Block{Type: "CERTIFICATE", Bytes: c.Raw})...)
			}
			_, err := program.Load(file, program.Options{At: tt.at, Pin: pinOf(t, tt.anchor)})
			if err == nil || !strings.Contains(err.Error(), tt.code) {
				t.Errorf("GOVERNMENT: %v, want %s", err, tt.code)
			}
			if v := opensslVerify(t, tt.anchor, tt.path, tt.at, nil); v.ok || !strings.Contains(v.out, tt.openssl) {
				t.Errorf("OpenSSL: ok %v, want %q:\n%s", v.ok, tt.openssl, v.out)
			}
		})
	}
}

func pinOf(t *testing.T, anchor *x509.Certificate) []byte {
	t.Helper()
	return anchor.RawSubjectPublicKeyInfo
}

// emptyCRL is a CRL from the cert at depth that revokes nothing. With
// -crl_check_all OpenSSL wants one from every issuer in the path before
// it will accept, where GOVERNMENT checks only the lists it is given.
func emptyCRL(t *testing.T, certs []*x509.Certificate, depth int, seed [32]byte, last, next time.Time) []byte {
	t.Helper()
	der, err := x509.CreateRevocationList(rand.Reader, &x509.RevocationList{
		Number: big.NewInt(last.Unix()), ThisUpdate: last, NextUpdate: next,
	}, certs[depth], keyForDepth(seed, depth))
	if err != nil {
		t.Fatal(err)
	}
	return pem.EncodeToMemory(&pem.Block{Type: "X509 CRL", Bytes: der})
}

// TestOpenSSLRepeals compares repeal decisions, including the two places
// GOVERNMENT departs from RFC 5280 on purpose (DESIGN.md, Repeal).
func TestOpenSSLRepeals(t *testing.T) {
	needOpenSSL(t)
	data, err := Compile("(+ 1 (* 2 3))", goldenOpts)
	if err != nil {
		t.Fatal(err)
	}
	certs := parsePEM(t, data)
	n := len(certs) - 1
	jan, mar, jun := time.Date(2030, 1, 1, 0, 0, 0, 0, time.UTC), time.Date(2030, 3, 1, 0, 0, 0, 0, time.UTC), time.Date(2030, 6, 1, 0, 0, 0, 0, time.UTC)
	never := time.Date(9999, 12, 31, 23, 59, 59, 0, time.UTC)

	// The issuers below the anchor publish nothing to repeal. OpenSSL needs
	// their (empty) lists all the same.
	var quiet [][]byte
	for d := 1; d < n; d++ {
		quiet = append(quiet, emptyCRL(t, certs, d, goldenSeed, jan, never))
	}
	repeal := func(at, last, next time.Time) [][]byte {
		crl, err := Repeal(certs, RepealOptions{Seed: &goldenSeed, Reason: 4, At: at, LastUpdate: last, NextUpdate: next})
		if err != nil {
			t.Fatal(err)
		}
		return append([][]byte{crl}, quiet...)
	}
	noRepeal := append([][]byte{emptyCRL(t, certs, 0, goldenSeed, jan, never)}, quiet...)

	tests := []struct {
		name          string
		crls          [][]byte
		at            time.Time
		ours, openssl string // "" means accepted
	}{
		{"nothing repealed", noRepeal, mar, "", ""},
		{"repealed", repeal(jan, jan, never), mar, "E-REPEALED", "certificate revoked"},
		{"repeal list gone stale", repeal(jan, jan, mar), jun, "E-STALE-REPEALS", "CRL has expired"},

		// Disagreement 1: GOVERNMENT reads a future revocation time as a
		// scheduled repeal. RFC 5280 says the field is when revocation
		// occurred, and OpenSSL ignores it: listed means revoked.
		{"scheduled, before its date", repeal(jun, jan, never), mar, "", "certificate revoked"},
		{"scheduled, after its date", repeal(jun, jan, never), jun.Add(time.Hour), "E-REPEALED", "certificate revoked"},

		// Disagreement 2: GOVERNMENT has no lower bound on a list's
		// thisUpdate, so a newer list can answer for an earlier time.
		// OpenSSL refuses a list issued after the time it is asked about.
		{"list issued after the check time", repeal(jun, jun, never), mar, "", "CRL is not yet valid"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			err := ours(data, tt.at, tt.crls)
			switch {
			case tt.ours == "" && err != nil:
				t.Errorf("GOVERNMENT refuses: %v", err)
			case tt.ours != "" && (err == nil || !strings.Contains(err.Error(), tt.ours)):
				t.Errorf("GOVERNMENT: %v, want %s", err, tt.ours)
			}
			v := opensslVerify(t, certs[0], certs[1:], tt.at, tt.crls)
			switch {
			case tt.openssl == "" && !v.ok:
				t.Errorf("OpenSSL refuses:\n%s", v.out)
			case tt.openssl != "" && (v.ok || !strings.Contains(v.out, tt.openssl)):
				t.Errorf("OpenSSL: ok %v, want %q:\n%s", v.ok, tt.openssl, v.out)
			}
		})
	}
}

// TestOpenSSLTreeLimit is the third disagreement, and the largest. Since
// CVE-2023-0464, OpenSSL refuses any policy tree over 1,000 nodes, a limit
// fixed when OpenSSL is built. It still builds RFC 5280's tree, which
// unfolds shared nodes, and every atom above the bottom is copied down
// once per cert, so a program's tree grows roughly as depth times width.
// GOVERNMENT's graph holds a million. Past the limit OpenSSL is no oracle.
//
// Under the limit OpenSSL must accept. Over it, it may refuse, but only
// for the size of its tree; a build without the limit accepts, and the
// test logs that. make oracle builds such an OpenSSL and runs these tests
// with it, which makes OpenSSL a full oracle for these programs too.
func TestOpenSSLTreeLimit(t *testing.T) {
	needOpenSSL(t)
	doubling := func(k int) string {
		e := "1"
		for range k {
			e = "(+ (* 1 " + e + ") (- " + e + " 0))"
		}
		return e
	}
	deep := func(d int) string {
		return strings.Repeat("(+ 1 ", d-1) + "0" + strings.Repeat(")", d-1)
	}
	at := time.Date(2028, 1, 1, 0, 0, 0, 0, time.UTC)
	tests := []struct {
		name, src  string
		underLimit bool
	}{
		{"31 deep, 961 nodes", deep(31), true},
		{"32 deep, 1,024 nodes", deep(32), false},
		{"200 deep", deep(200), false},
		{"1,000 arguments, 1,002 nodes", "(+" + strings.Repeat(" 1", 1000) + ")", false},
		{"4 levels of shared doubling", doubling(4), true},
		{"6 levels of shared doubling, small as a graph", doubling(6), false},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			data, err := Compile(tt.src, goldenOpts)
			if err != nil {
				t.Fatal(err)
			}
			if err := ours(data, at, nil); err != nil {
				t.Fatalf("GOVERNMENT refuses: %v", err)
			}
			certs := parsePEM(t, data)
			v := opensslVerify(t, certs[0], certs[1:], at, nil)
			switch {
			case v.ok && !tt.underLimit:
				t.Log("OpenSSL accepts it: this build has no 1,000-node policy tree limit")
			case !v.ok && tt.underLimit:
				t.Errorf("OpenSSL refuses a program under its limit:\n%.300s", v.out)
			case !v.ok && !strings.Contains(v.out, "check_policy"):
				// OpenSSL reports the limit as a failed allocation in its
				// policy check; anything else is a real disagreement.
				t.Errorf("OpenSSL refused for a reason other than its tree limit:\n%.300s", v.out)
			}
		})
	}
}