@ 675167640370859e58d24a1f76126760c2e61968 | history
package lisp2gov
import (
"bytes"
"cmp"
"crypto/rand"
"crypto/x509"
"encoding/pem"
"math/big"
"os"
"os/exec"
"path/filepath"
"slices"
"strconv"
"strings"
"testing"
"time"
"nmyk.io/government/internal/lisptest"
"nmyk.io/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)
}
})
}
}