crates/oxy-core/src/policy.rs at a42f9fb47e37 · andymccall/oxygen

# a42f9fb47e37 oxygen / crates / oxy-core / src / policy.rs

21.3 KiB · Rust · last changed Policies grant subjects an issuer certifies (keyless step 4a) 18 days ago source blame history raw

//! The trust policy (spec §14.5): who may update which references, signed
//! by a threshold of root keys. A repository without a policy is unverified.
//!
//! Encoding: `{0: version, 1: repo, 2: serial, 3: {0: root keys, 1: threshold},
//! 4: [rule], 5: [identity bytes], 6: [revoked], 7: expires}`; a rule is
//! `{0: pattern, 1: keys, 2: threshold, 3: require, 4: allow_conflicts}` with
//! `require` 0 = signed, 1 = sealed, 2 = any.

use crate::cbor::{self, Value};
use crate::hash::{hash_object, KeyId, ObjectRef, ObjectType};
use crate::identity::{self, Domain, Identity, Signature};
use crate::objects::{
    array, bytes, check_version, field, map, oref, text, uint, ObjectError, FORMAT_VERSION,
};
use std::collections::BTreeMap;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Require {
    Signed,
    Sealed,
    Any,
}

impl Require {
    fn tag(self) -> u64 {
        match self {
            Require::Signed => 0,
            Require::Sealed => 1,
            Require::Any => 2,
        }
    }
    fn from_tag(t: u64) -> Result<Require, ObjectError> {
        Ok(match t {
            0 => Require::Signed,
            1 => Require::Sealed,
            2 => Require::Any,
            _ => return Err(ObjectError::Schema(format!("unknown require {t}"))),
        })
    }
    pub fn name(self) -> &'static str {
        match self {
            Require::Signed => "signed",
            Require::Sealed => "sealed",
            Require::Any => "any",
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Rule {
    /// Glob over reference names; `*` matches any run of characters.
    pub pattern: String,
    pub keys: Vec<KeyId>,
    pub threshold: u32,
    pub require: Require,
    pub allow_conflicts: bool,
    /// Who else may sign, by what an issuer certified (§14.7): a short-lived
    /// key whose certificate is the issuer's, for a subject the pattern
    /// matches, counts as one signer within the scope given.
    pub subjects: Vec<SubjectGrant>,
}

/// A rule's grant to the holders of certificates an issuer gives (§14.7):
/// `repo:andy/demo:bookmark:main`, `agent:claude@andy`, with `*` as in
/// reference patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SubjectGrant {
    pub pattern: String,
    pub issuer: KeyId,
    pub scope: identity::Scope,
}

impl SubjectGrant {
    fn to_value(&self) -> Value {
        Value::map([
            (0, Value::Text(self.pattern.clone())),
            (1, Value::Bytes(self.issuer.0.to_vec())),
            (
                2,
                Value::Array(
                    self.scope
                        .names()
                        .into_iter()
                        .map(|n| Value::Text(n.to_string()))
                        .collect(),
                ),
            ),
        ])
    }

    fn from_value(v: &Value) -> Result<SubjectGrant, ObjectError> {
        let m = map(v, "subject")?;
        let mut scope = identity::Scope::NONE;
        for n in array(field(m, 2, "subject scope")?, "subject scope")? {
            let n = text(n, "subject scope")?;
            scope = scope
                | identity::Scope::named(n)
                    .ok_or_else(|| ObjectError::Schema(format!("subject: unknown scope {n:?}")))?;
        }
        Ok(SubjectGrant {
            pattern: text(field(m, 0, "subject pattern")?, "subject pattern")?.to_owned(),
            issuer: oref(field(m, 1, "subject issuer")?, "subject issuer")?,
            scope,
        })
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Policy {
    pub repo: [u8; 16],
    pub serial: u64,
    pub roots: Vec<KeyId>,
    pub root_threshold: u32,
    pub rules: Vec<Rule>,
    /// Embedded so verification needs no fetch.
    pub identities: Vec<Identity>,
    pub revoked: Vec<KeyId>,
    pub expires: u64,
}

/// `*` matches any run of characters (including `/`); everything else is literal.
pub fn glob_matches(pattern: &str, name: &str) -> bool {
    fn rec(p: &[u8], n: &[u8]) -> bool {
        match p.first() {
            None => n.is_empty(),
            Some(b'*') => (0..=n.len()).any(|i| rec(&p[1..], &n[i..])),
            Some(c) => n.first() == Some(c) && rec(&p[1..], &n[1..]),
        }
    }
    rec(pattern.as_bytes(), name.as_bytes())
}

impl Policy {
    fn keys_value(keys: &[KeyId]) -> Value {
        Value::Array(keys.iter().map(|k| Value::Bytes(k.0.to_vec())).collect())
    }
    fn keys_from(v: &Value, what: &str) -> Result<Vec<KeyId>, ObjectError> {
        let mut ks = array(v, what)?
            .iter()
            .map(|k| oref(k, what))
            .collect::<Result<Vec<_>, _>>()?;
        ks.sort();
        ks.dedup();
        Ok(ks)
    }

    pub fn to_value(&self) -> Value {
        Value::map([
            (0, Value::Uint(FORMAT_VERSION)),
            (1, Value::Bytes(self.repo.to_vec())),
            (2, Value::Uint(self.serial)),
            (
                3,
                Value::map([
                    (0, Self::keys_value(&self.roots)),
                    (1, Value::Uint(self.root_threshold as u64)),
                ]),
            ),
            (
                4,
                Value::Array(
                    self.rules
                        .iter()
                        .map(|r| {
                            let mut v = Value::map([
                                (0, Value::Text(r.pattern.clone())),
                                (1, Self::keys_value(&r.keys)),
                                (2, Value::Uint(r.threshold as u64)),
                                (3, Value::Uint(r.require.tag())),
                                (4, Value::Bool(r.allow_conflicts)),
                            ]);
                            // Only when there are any, so a policy without
                            // them encodes, and hashes, as before.
                            if !r.subjects.is_empty() {
                                if let Value::Map(m) = &mut v {
                                    m.insert(
                                        5,
                                        Value::Array(
                                            r.subjects.iter().map(SubjectGrant::to_value).collect(),
                                        ),
                                    );
                                }
                            }
                            v
                        })
                        .collect(),
                ),
            ),
            (
                5,
                Value::Array(
                    self.identities
                        .iter()
                        .map(|i| Value::Bytes(i.encode()))
                        .collect(),
                ),
            ),
            (6, Self::keys_value(&self.revoked)),
            (7, Value::Uint(self.expires)),
        ])
    }

    pub fn encode(&self) -> Vec<u8> {
        cbor::encode(&self.to_value())
    }

    pub fn hash(&self) -> ObjectRef {
        hash_object(ObjectType::Policy, &self.encode())
    }

    pub fn decode(b: &[u8]) -> Result<Policy, ObjectError> {
        let v = cbor::decode(b)?;
        let m = map(&v, "policy")?;
        check_version(m)?;
        let roots = map(field(m, 3, "roots")?, "roots")?;
        let mut rules = Vec::new();
        for r in array(field(m, 4, "rules")?, "rules")? {
            let rm = map(r, "rule")?;
            rules.push(Rule {
                pattern: text(field(rm, 0, "pattern")?, "pattern")?.to_owned(),
                keys: Self::keys_from(field(rm, 1, "rule keys")?, "rule keys")?,
                threshold: uint(field(rm, 2, "threshold")?, "threshold")? as u32,
                require: Require::from_tag(uint(field(rm, 3, "require")?, "require")?)?,
                allow_conflicts: field(rm, 4, "allow_conflicts")?
                    .as_bool()
                    .ok_or_else(|| ObjectError::Schema("allow_conflicts: expected bool".into()))?,
                subjects: match rm.get(&5) {
                    None => vec![],
                    Some(v) => array(v, "subjects")?
                        .iter()
                        .map(SubjectGrant::from_value)
                        .collect::<Result<_, _>>()?,
                },
            });
        }
        let identities = array(field(m, 5, "identities")?, "identities")?
            .iter()
            .map(|i| Identity::decode(bytes(i, "identity")?))
            .collect::<Result<Vec<_>, _>>()?;
        let p = Policy {
            repo: bytes(field(m, 1, "repo")?, "repo")?
                .try_into()
                .map_err(|_| ObjectError::Schema("repo: expected 16 bytes".into()))?,
            serial: uint(field(m, 2, "serial")?, "serial")?,
            roots: Self::keys_from(field(roots, 0, "root keys")?, "root keys")?,
            root_threshold: uint(field(roots, 1, "root threshold")?, "root threshold")? as u32,
            rules,
            identities,
            revoked: Self::keys_from(field(m, 6, "revoked")?, "revoked")?,
            expires: uint(field(m, 7, "expires")?, "expires")?,
        };
        if p.root_threshold == 0 || p.root_threshold as usize > p.roots.len() {
            return Err(ObjectError::Schema(
                "root threshold must be between 1 and the number of root keys".into(),
            ));
        }
        for r in &p.rules {
            if r.threshold == 0 || r.threshold as usize > r.keys.len() + r.subjects.len() {
                return Err(ObjectError::Schema(format!(
                    "rule {:?}: threshold must be between 1 and the number of keys and subjects",
                    r.pattern
                )));
            }
        }
        Ok(p)
    }

    pub fn identity(&self, key: &KeyId) -> Option<&Identity> {
        self.identities.iter().find(|i| i.hash() == *key)
    }

    pub fn is_revoked(&self, key: &KeyId) -> bool {
        self.revoked.contains(key)
    }

    pub fn is_expired(&self, now_ms: u64) -> bool {
        now_ms > self.expires
    }

    /// The first rule whose pattern matches `reference`.
    pub fn rule_for(&self, reference: &str) -> Option<&Rule> {
        self.rules
            .iter()
            .find(|r| glob_matches(&r.pattern, reference))
    }

    /// Whether the rule for `reference` lets a certificate from `issuer`
    /// for `subject` sign within `scope` (§14.7). The certificate itself,
    /// and the time it is checked at, are the caller's to verify.
    pub fn subject_grant(
        &self,
        reference: &str,
        issuer: &KeyId,
        subject: &str,
        scope: identity::Scope,
    ) -> bool {
        !self.is_revoked(issuer)
            && self.rule_for(reference).is_some_and(|r| {
                r.subjects.iter().any(|g| {
                    g.issuer == *issuer && g.scope.has(scope) && glob_matches(&g.pattern, subject)
                })
            })
    }

    /// Whether `key` may update `reference`: listed in the matching rule and not revoked.
    pub fn authorizes(&self, key: &KeyId, reference: &str) -> bool {
        !self.is_revoked(key)
            && self
                .rule_for(reference)
                .is_some_and(|r| r.keys.contains(key))
    }

    /// Verify that `sigs` over this policy's hash meet `trusted`'s root
    /// threshold (`trusted` is the previous policy, or this one when
    /// bootstrapping). Returns the signing root keys.
    pub fn verify_signatures(
        &self,
        sigs: &[Signature],
        trusted: &Policy,
    ) -> Result<Vec<KeyId>, String> {
        let target = self.hash();
        let mut signers = Vec::new();
        for sig in sigs {
            if !trusted.roots.contains(&sig.key) || trusted.is_revoked(&sig.key) {
                continue;
            }
            let Some(id) = trusted
                .identity(&sig.key)
                .or_else(|| self.identity(&sig.key))
            else {
                continue;
            };
            if identity::verify(id, sig, Domain::Policy, &target).is_ok()
                && !signers.contains(&sig.key)
            {
                signers.push(sig.key);
            }
        }
        if (signers.len() as u32) < trusted.root_threshold {
            return Err(format!(
                "policy needs {} root signature(s), has {}",
                trusted.root_threshold,
                signers.len()
            ));
        }
        Ok(signers)
    }

    /// Bootstrap check for the first policy a repository sees (trust on
    /// first use): at least one valid signature by one of its own roots.
    /// The full threshold applies only to updates from a trusted policy,
    /// whose signers are the previous roots and need not be the new ones.
    pub fn verify_bootstrap(&self, sigs: &[Signature]) -> Result<KeyId, String> {
        let target = self.hash();
        for sig in sigs {
            if !self.roots.contains(&sig.key) || self.is_revoked(&sig.key) {
                continue;
            }
            if let Some(id) = self.identity(&sig.key) {
                if identity::verify(id, sig, Domain::Policy, &target).is_ok() {
                    return Ok(sig.key);
                }
            }
        }
        Err("policy carries no valid signature by one of its own root keys".into())
    }

    /// A single-root policy letting `root` do everything on every reference.
    pub fn single_root(repo: [u8; 16], root: Identity, expires: u64) -> Policy {
        let key = root.hash();
        Policy {
            repo,
            serial: 1,
            roots: vec![key],
            root_threshold: 1,
            rules: vec![Rule {
                pattern: "*".into(),
                keys: vec![key],
                threshold: 1,
                require: Require::Any,
                allow_conflicts: true,
                subjects: vec![],
            }],
            identities: vec![root],
            revoked: vec![],
            expires,
        }
    }

    /// Whether `key` appears anywhere in the policy (roots, rules, identities).
    pub fn mentions(&self, key: &KeyId) -> bool {
        self.roots.contains(key)
            || self.rules.iter().any(|r| r.keys.contains(key))
            || self.identity(key).is_some()
    }

    /// Whether `key` is `rule_key` or one of its predecessors in the
    /// rotation chain (`previous` links, spec §14.2), so that changes signed
    /// before a rotation remain authorized. Revoked keys never qualify.
    pub fn succeeds(&self, rule_key: &KeyId, key: &KeyId) -> bool {
        if self.is_revoked(key) {
            return false;
        }
        let mut cur = Some(*rule_key);
        for _ in 0..32 {
            match cur {
                Some(k) if k == *key => return true,
                Some(k) => cur = self.identity(&k).and_then(|i| i.previous),
                None => return false,
            }
        }
        false
    }

    /// Replace `old` by `new` in the roots and every rule and embed `new`'s
    /// identity (a rotation, spec §14.2). The old identity stays embedded so
    /// signatures made before the rotation still verify; it is superseded,
    /// not revoked.
    pub fn substitute_key(&mut self, old: &KeyId, new: Identity) {
        let nk = new.hash();
        for k in self
            .roots
            .iter_mut()
            .chain(self.rules.iter_mut().flat_map(|r| r.keys.iter_mut()))
        {
            if k == old {
                *k = nk;
            }
        }
        for r in &mut self.rules {
            r.keys.sort();
            r.keys.dedup();
        }
        self.roots.sort();
        self.roots.dedup();
        if self.identity(&nk).is_none() {
            self.identities.push(new);
        }
    }

    /// Identities keyed by KeyId.
    pub fn identity_map(&self) -> BTreeMap<KeyId, &Identity> {
        self.identities.iter().map(|i| (i.hash(), i)).collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::identity::SecretKey;

    fn sk(n: u8) -> SecretKey {
        SecretKey {
            ed_seed: [n; 32],
            ml_seed: [n + 100; 32],
        }
    }

    #[test]
    fn globs() {
        assert!(glob_matches("*", "main"));
        assert!(glob_matches("release/*", "release/1.0"));
        assert!(!glob_matches("release/*", "main"));
        assert!(glob_matches("main", "main"));
        assert!(!glob_matches("main", "main2"));
        assert!(glob_matches("*-rc*", "1.0-rc2"));
        assert!(glob_matches("", ""));
    }

    /// Subjects an issuer certifies (oxygenhub#241): kept through
    /// encoding, absent from a policy without them, and granted only for
    /// their issuer, pattern and scope, and not when the issuer is revoked.
    #[test]
    fn a_rule_grants_certified_subjects() {
        use crate::identity::Scope;
        let root = sk(1).identity("Root", "r@x", 0);
        let hub = sk(3).identity("Hub", "h@x", 0);
        let mut p = Policy::single_root([9; 16], root.clone(), 10);
        let plain = p.encode();
        p.rules[0].subjects.push(SubjectGrant {
            pattern: "repo:andy/demo:bookmark:main".into(),
            issuer: hub.hash(),
            scope: Scope::REFS | Scope::CHANGES,
        });
        p.rules[0].subjects.push(SubjectGrant {
            pattern: "agent:*@andy".into(),
            issuer: hub.hash(),
            scope: Scope::CHANGES,
        });
        let back = Policy::decode(&p.encode()).unwrap();
        assert_eq!(back, p);
        let mut again = back.clone();
        again.rules[0].subjects.clear();
        assert_eq!(
            again.encode(),
            plain,
            "no subjects, the same bytes as before"
        );

        let main = "repo:andy/demo:bookmark:main";
        assert!(p.subject_grant("main", &hub.hash(), main, Scope::REFS));
        assert!(p.subject_grant("main", &hub.hash(), "agent:claude@andy", Scope::CHANGES));
        assert!(
            !p.subject_grant("main", &hub.hash(), "agent:claude@andy", Scope::REFS),
            "not its scope"
        );
        assert!(
            !p.subject_grant(
                "main",
                &hub.hash(),
                "repo:andy/demo:bookmark:dev",
                Scope::REFS
            ),
            "not its pattern"
        );
        assert!(
            !p.subject_grant("main", &root.hash(), main, Scope::REFS),
            "not its issuer"
        );
        p.revoked.push(hub.hash());
        assert!(
            !p.subject_grant("main", &hub.hash(), main, Scope::REFS),
            "a revoked issuer grants nothing"
        );

        // A rule of subjects alone is a rule.
        let mut only = Policy::single_root([9; 16], root, 10);
        only.rules[0].keys.clear();
        only.rules[0].subjects.push(SubjectGrant {
            pattern: "*".into(),
            issuer: hub.hash(),
            scope: Scope::REFS,
        });
        assert!(Policy::decode(&only.encode()).is_ok());
        only.rules[0].subjects.clear();
        assert!(Policy::decode(&only.encode()).is_err(), "nobody to sign");
    }

    #[test]
    fn round_trip_and_rules() {
        let root = sk(1).identity("Root", "r@x", 0);
        let dev = sk(2).identity("Dev", "d@x", 0);
        let mut p = Policy::single_root([9; 16], root.clone(), 10);
        p.rules.insert(
            0,
            Rule {
                pattern: "release/*".into(),
                keys: vec![root.hash()],
                threshold: 1,
                require: Require::Signed,
                allow_conflicts: false,
                subjects: vec![],
            },
        );
        p.rules[1].keys.push(dev.hash());
        p.identities.push(dev.clone());
        p.revoked.push(ObjectRef([7; 32]));
        let d = Policy::decode(&p.encode()).unwrap();
        assert_eq!(d.rules.len(), 2);
        assert_eq!(d.rules[0].require, Require::Signed);
        assert_eq!(d.identity(&dev.hash()), Some(&dev));
        assert!(d.authorizes(&dev.hash(), "main"));
        assert!(!d.authorizes(&dev.hash(), "release/1"));
        assert!(d.authorizes(&root.hash(), "release/1"));
        assert!(d.is_expired(11) && !d.is_expired(10));
        assert_eq!(d.hash(), p.hash());

        let mut bad = p.clone();
        bad.root_threshold = 5;
        assert!(Policy::decode(&bad.encode()).is_err());
    }

    #[test]
    fn signatures_need_root_threshold() {
        let r1 = sk(1);
        let r2 = sk(2);
        let i1 = r1.identity("a", "a", 0);
        let i2 = r2.identity("b", "b", 0);
        let mut p = Policy::single_root([1; 16], i1.clone(), 100);
        p.roots.push(i2.hash());
        p.roots.sort();
        p.root_threshold = 2;
        p.identities.push(i2.clone());
        let h = p.hash();
        let s1 = r1.sign(Domain::Policy, &i1.hash(), &h);
        let s2 = r2.sign(Domain::Policy, &i2.hash(), &h);
        assert!(p.verify_signatures(std::slice::from_ref(&s1), &p).is_err());
        assert_eq!(
            p.verify_signatures(&[s1.clone(), s2.clone()], &p)
                .unwrap()
                .len(),
            2
        );
        // Duplicates do not count twice; a non-root signer does not count.
        assert!(p.verify_signatures(&[s1.clone(), s1.clone()], &p).is_err());
        let stranger = sk(3);
        let si = stranger.identity("s", "s", 0);
        let s3 = stranger.sign(Domain::Policy, &si.hash(), &h);
        assert!(p.verify_signatures(&[s1.clone(), s3], &p).is_err());
        // A successor policy is verified against the previous roots.
        let mut next = p.clone();
        next.serial = 2;
        next.revoked.push(i2.hash());
        let nh = next.hash();
        let n1 = r1.sign(Domain::Policy, &i1.hash(), &nh);
        let n2 = r2.sign(Domain::Policy, &i2.hash(), &nh);
        assert_eq!(next.verify_signatures(&[n1, n2], &p).unwrap().len(), 2);
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	//! The trust policy (spec §14.5): who may update which references, signed
2	//! by a threshold of root keys. A repository without a policy is unverified.
3	//!
4	//! Encoding: `{0: version, 1: repo, 2: serial, 3: {0: root keys, 1: threshold},
5	//! 4: [rule], 5: [identity bytes], 6: [revoked], 7: expires}`; a rule is
6	//! `{0: pattern, 1: keys, 2: threshold, 3: require, 4: allow_conflicts}` with
7	//! `require` 0 = signed, 1 = sealed, 2 = any.
8
9	use crate::cbor::{self, Value};
10	use crate::hash::{hash_object, KeyId, ObjectRef, ObjectType};
11	use crate::identity::{self, Domain, Identity, Signature};
12	use crate::objects::{
13	array, bytes, check_version, field, map, oref, text, uint, ObjectError, FORMAT_VERSION,
14	};
15	use std::collections::BTreeMap;
16
17	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18	pub enum Require {
19	Signed,
20	Sealed,
21	Any,
22	}
23
24	impl Require {
25	fn tag(self) -> u64 {
26	match self {
27	Require::Signed => 0,
28	Require::Sealed => 1,
29	Require::Any => 2,
30	}
31	}
32	fn from_tag(t: u64) -> Result<Require, ObjectError> {
33	Ok(match t {
34	0 => Require::Signed,
35	1 => Require::Sealed,
36	2 => Require::Any,
37	_ => return Err(ObjectError::Schema(format!("unknown require {t}"))),
38	})
39	}
40	pub fn name(self) -> &'static str {
41	match self {
42	Require::Signed => "signed",
43	Require::Sealed => "sealed",
44	Require::Any => "any",
45	}
46	}
47	}
48
49	#[derive(Clone, Debug, PartialEq, Eq)]
50	pub struct Rule {
51	/// Glob over reference names; `*` matches any run of characters.
52	pub pattern: String,
53	pub keys: Vec<KeyId>,
54	pub threshold: u32,
55	pub require: Require,
56	pub allow_conflicts: bool,
57	/// Who else may sign, by what an issuer certified (§14.7): a short-lived
58	/// key whose certificate is the issuer's, for a subject the pattern
59	/// matches, counts as one signer within the scope given.
60	pub subjects: Vec<SubjectGrant>,
61	}
62
63	/// A rule's grant to the holders of certificates an issuer gives (§14.7):
64	/// `repo:andy/demo:bookmark:main`, `agent:claude@andy`, with `*` as in
65	/// reference patterns.
66	#[derive(Clone, Debug, PartialEq, Eq)]
67	pub struct SubjectGrant {
68	pub pattern: String,
69	pub issuer: KeyId,
70	pub scope: identity::Scope,
71	}
72
73	impl SubjectGrant {
74	fn to_value(&self) -> Value {
75	Value::map([
76	(0, Value::Text(self.pattern.clone())),
77	(1, Value::Bytes(self.issuer.0.to_vec())),
78	(
79	2,
80	Value::Array(
81	self.scope
82	.names()
83	.into_iter()
84	.map(\|n\| Value::Text(n.to_string()))
85	.collect(),
86	),
87	),
88	])
89	}
90
91	fn from_value(v: &Value) -> Result<SubjectGrant, ObjectError> {
92	let m = map(v, "subject")?;
93	let mut scope = identity::Scope::NONE;
94	for n in array(field(m, 2, "subject scope")?, "subject scope")? {
95	let n = text(n, "subject scope")?;
96	scope = scope
97	\| identity::Scope::named(n)
98	.ok_or_else(\|\| ObjectError::Schema(format!("subject: unknown scope {n:?}")))?;
99	}
100	Ok(SubjectGrant {
101	pattern: text(field(m, 0, "subject pattern")?, "subject pattern")?.to_owned(),
102	issuer: oref(field(m, 1, "subject issuer")?, "subject issuer")?,
103	scope,
104	})
105	}
106	}
107
108	#[derive(Clone, Debug, PartialEq, Eq)]
109	pub struct Policy {
110	pub repo: [u8; 16],
111	pub serial: u64,
112	pub roots: Vec<KeyId>,
113	pub root_threshold: u32,
114	pub rules: Vec<Rule>,
115	/// Embedded so verification needs no fetch.
116	pub identities: Vec<Identity>,
117	pub revoked: Vec<KeyId>,
118	pub expires: u64,
119	}
120
121	/// `*` matches any run of characters (including `/`); everything else is literal.
122	pub fn glob_matches(pattern: &str, name: &str) -> bool {
123	fn rec(p: &[u8], n: &[u8]) -> bool {
124	match p.first() {
125	None => n.is_empty(),
126	Some(b'*') => (0..=n.len()).any(\|i\| rec(&p[1..], &n[i..])),
127	Some(c) => n.first() == Some(c) && rec(&p[1..], &n[1..]),
128	}
129	}
130	rec(pattern.as_bytes(), name.as_bytes())
131	}
132
133	impl Policy {
134	fn keys_value(keys: &[KeyId]) -> Value {
135	Value::Array(keys.iter().map(\|k\| Value::Bytes(k.0.to_vec())).collect())
136	}
137	fn keys_from(v: &Value, what: &str) -> Result<Vec<KeyId>, ObjectError> {
138	let mut ks = array(v, what)?
139	.iter()
140	.map(\|k\| oref(k, what))
141	.collect::<Result<Vec<_>, _>>()?;
142	ks.sort();
143	ks.dedup();
144	Ok(ks)
145	}
146
147	pub fn to_value(&self) -> Value {
148	Value::map([
149	(0, Value::Uint(FORMAT_VERSION)),
150	(1, Value::Bytes(self.repo.to_vec())),
151	(2, Value::Uint(self.serial)),
152	(
153	3,
154	Value::map([
155	(0, Self::keys_value(&self.roots)),
156	(1, Value::Uint(self.root_threshold as u64)),
157	]),
158	),
159	(
160	4,
161	Value::Array(
162	self.rules
163	.iter()
164	.map(\|r\| {
165	let mut v = Value::map([
166	(0, Value::Text(r.pattern.clone())),
167	(1, Self::keys_value(&r.keys)),
168	(2, Value::Uint(r.threshold as u64)),
169	(3, Value::Uint(r.require.tag())),
170	(4, Value::Bool(r.allow_conflicts)),
171	]);
172	// Only when there are any, so a policy without
173	// them encodes, and hashes, as before.
174	if !r.subjects.is_empty() {
175	if let Value::Map(m) = &mut v {
176	m.insert(
177	5,
178	Value::Array(
179	r.subjects.iter().map(SubjectGrant::to_value).collect(),
180	),
181	);
182	}
183	}
184	v
185	})
186	.collect(),
187	),
188	),
189	(
190	5,
191	Value::Array(
192	self.identities
193	.iter()
194	.map(\|i\| Value::Bytes(i.encode()))
195	.collect(),
196	),
197	),
198	(6, Self::keys_value(&self.revoked)),
199	(7, Value::Uint(self.expires)),
200	])
201	}
202
203	pub fn encode(&self) -> Vec<u8> {
204	cbor::encode(&self.to_value())
205	}
206
207	pub fn hash(&self) -> ObjectRef {
208	hash_object(ObjectType::Policy, &self.encode())
209	}
210
211	pub fn decode(b: &[u8]) -> Result<Policy, ObjectError> {
212	let v = cbor::decode(b)?;
213	let m = map(&v, "policy")?;
214	check_version(m)?;
215	let roots = map(field(m, 3, "roots")?, "roots")?;
216	let mut rules = Vec::new();
217	for r in array(field(m, 4, "rules")?, "rules")? {
218	let rm = map(r, "rule")?;
219	rules.push(Rule {
220	pattern: text(field(rm, 0, "pattern")?, "pattern")?.to_owned(),
221	keys: Self::keys_from(field(rm, 1, "rule keys")?, "rule keys")?,
222	threshold: uint(field(rm, 2, "threshold")?, "threshold")? as u32,
223	require: Require::from_tag(uint(field(rm, 3, "require")?, "require")?)?,
224	allow_conflicts: field(rm, 4, "allow_conflicts")?
225	.as_bool()
226	.ok_or_else(\|\| ObjectError::Schema("allow_conflicts: expected bool".into()))?,
227	subjects: match rm.get(&5) {
228	None => vec![],
229	Some(v) => array(v, "subjects")?
230	.iter()
231	.map(SubjectGrant::from_value)
232	.collect::<Result<_, _>>()?,
233	},
234	});
235	}
236	let identities = array(field(m, 5, "identities")?, "identities")?
237	.iter()
238	.map(\|i\| Identity::decode(bytes(i, "identity")?))
239	.collect::<Result<Vec<_>, _>>()?;
240	let p = Policy {
241	repo: bytes(field(m, 1, "repo")?, "repo")?
242	.try_into()
243	.map_err(\|_\| ObjectError::Schema("repo: expected 16 bytes".into()))?,
244	serial: uint(field(m, 2, "serial")?, "serial")?,
245	roots: Self::keys_from(field(roots, 0, "root keys")?, "root keys")?,
246	root_threshold: uint(field(roots, 1, "root threshold")?, "root threshold")? as u32,
247	rules,
248	identities,
249	revoked: Self::keys_from(field(m, 6, "revoked")?, "revoked")?,
250	expires: uint(field(m, 7, "expires")?, "expires")?,
251	};
252	if p.root_threshold == 0 \|\| p.root_threshold as usize > p.roots.len() {
253	return Err(ObjectError::Schema(
254	"root threshold must be between 1 and the number of root keys".into(),
255	));
256	}
257	for r in &p.rules {
258	if r.threshold == 0 \|\| r.threshold as usize > r.keys.len() + r.subjects.len() {
259	return Err(ObjectError::Schema(format!(
260	"rule {:?}: threshold must be between 1 and the number of keys and subjects",
261	r.pattern
262	)));
263	}
264	}
265	Ok(p)
266	}
267
268	pub fn identity(&self, key: &KeyId) -> Option<&Identity> {
269	self.identities.iter().find(\|i\| i.hash() == *key)
270	}
271
272	pub fn is_revoked(&self, key: &KeyId) -> bool {
273	self.revoked.contains(key)
274	}
275
276	pub fn is_expired(&self, now_ms: u64) -> bool {
277	now_ms > self.expires
278	}
279
280	/// The first rule whose pattern matches `reference`.
281	pub fn rule_for(&self, reference: &str) -> Option<&Rule> {
282	self.rules
283	.iter()
284	.find(\|r\| glob_matches(&r.pattern, reference))
285	}
286
287	/// Whether the rule for `reference` lets a certificate from `issuer`
288	/// for `subject` sign within `scope` (§14.7). The certificate itself,
289	/// and the time it is checked at, are the caller's to verify.
290	pub fn subject_grant(
291	&self,
292	reference: &str,
293	issuer: &KeyId,
294	subject: &str,
295	scope: identity::Scope,
296	) -> bool {
297	!self.is_revoked(issuer)
298	&& self.rule_for(reference).is_some_and(\|r\| {
299	r.subjects.iter().any(\|g\| {
300	g.issuer == *issuer && g.scope.has(scope) && glob_matches(&g.pattern, subject)
301	})
302	})
303	}
304
305	/// Whether `key` may update `reference`: listed in the matching rule and not revoked.
306	pub fn authorizes(&self, key: &KeyId, reference: &str) -> bool {
307	!self.is_revoked(key)
308	&& self
309	.rule_for(reference)
310	.is_some_and(\|r\| r.keys.contains(key))
311	}
312
313	/// Verify that `sigs` over this policy's hash meet `trusted`'s root
314	/// threshold (`trusted` is the previous policy, or this one when
315	/// bootstrapping). Returns the signing root keys.
316	pub fn verify_signatures(
317	&self,
318	sigs: &[Signature],
319	trusted: &Policy,
320	) -> Result<Vec<KeyId>, String> {
321	let target = self.hash();
322	let mut signers = Vec::new();
323	for sig in sigs {
324	if !trusted.roots.contains(&sig.key) \|\| trusted.is_revoked(&sig.key) {
325	continue;
326	}
327	let Some(id) = trusted
328	.identity(&sig.key)
329	.or_else(\|\| self.identity(&sig.key))
330	else {
331	continue;
332	};
333	if identity::verify(id, sig, Domain::Policy, &target).is_ok()
334	&& !signers.contains(&sig.key)
335	{
336	signers.push(sig.key);
337	}
338	}
339	if (signers.len() as u32) < trusted.root_threshold {
340	return Err(format!(
341	"policy needs {} root signature(s), has {}",
342	trusted.root_threshold,
343	signers.len()
344	));
345	}
346	Ok(signers)
347	}
348
349	/// Bootstrap check for the first policy a repository sees (trust on
350	/// first use): at least one valid signature by one of its own roots.
351	/// The full threshold applies only to updates from a trusted policy,
352	/// whose signers are the previous roots and need not be the new ones.
353	pub fn verify_bootstrap(&self, sigs: &[Signature]) -> Result<KeyId, String> {
354	let target = self.hash();
355	for sig in sigs {
356	if !self.roots.contains(&sig.key) \|\| self.is_revoked(&sig.key) {
357	continue;
358	}
359	if let Some(id) = self.identity(&sig.key) {
360	if identity::verify(id, sig, Domain::Policy, &target).is_ok() {
361	return Ok(sig.key);
362	}
363	}
364	}
365	Err("policy carries no valid signature by one of its own root keys".into())
366	}
367
368	/// A single-root policy letting `root` do everything on every reference.
369	pub fn single_root(repo: [u8; 16], root: Identity, expires: u64) -> Policy {
370	let key = root.hash();
371	Policy {
372	repo,
373	serial: 1,
374	roots: vec![key],
375	root_threshold: 1,
376	rules: vec![Rule {
377	pattern: "*".into(),
378	keys: vec![key],
379	threshold: 1,
380	require: Require::Any,
381	allow_conflicts: true,
382	subjects: vec![],
383	}],
384	identities: vec![root],
385	revoked: vec![],
386	expires,
387	}
388	}
389
390	/// Whether `key` appears anywhere in the policy (roots, rules, identities).
391	pub fn mentions(&self, key: &KeyId) -> bool {
392	self.roots.contains(key)
393	\|\| self.rules.iter().any(\|r\| r.keys.contains(key))
394	\|\| self.identity(key).is_some()
395	}
396
397	/// Whether `key` is `rule_key` or one of its predecessors in the
398	/// rotation chain (`previous` links, spec §14.2), so that changes signed
399	/// before a rotation remain authorized. Revoked keys never qualify.
400	pub fn succeeds(&self, rule_key: &KeyId, key: &KeyId) -> bool {
401	if self.is_revoked(key) {
402	return false;
403	}
404	let mut cur = Some(*rule_key);
405	for _ in 0..32 {
406	match cur {
407	Some(k) if k == *key => return true,
408	Some(k) => cur = self.identity(&k).and_then(\|i\| i.previous),
409	None => return false,
410	}
411	}
412	false
413	}
414
415	/// Replace `old` by `new` in the roots and every rule and embed `new`'s
416	/// identity (a rotation, spec §14.2). The old identity stays embedded so
417	/// signatures made before the rotation still verify; it is superseded,
418	/// not revoked.
419	pub fn substitute_key(&mut self, old: &KeyId, new: Identity) {
420	let nk = new.hash();
421	for k in self
422	.roots
423	.iter_mut()
424	.chain(self.rules.iter_mut().flat_map(\|r\| r.keys.iter_mut()))
425	{
426	if k == old {
427	*k = nk;
428	}
429	}
430	for r in &mut self.rules {
431	r.keys.sort();
432	r.keys.dedup();
433	}
434	self.roots.sort();
435	self.roots.dedup();
436	if self.identity(&nk).is_none() {
437	self.identities.push(new);
438	}
439	}
440
441	/// Identities keyed by KeyId.
442	pub fn identity_map(&self) -> BTreeMap<KeyId, &Identity> {
443	self.identities.iter().map(\|i\| (i.hash(), i)).collect()
444	}
445	}
446
447	#[cfg(test)]
448	mod tests {
449	use super::*;
450	use crate::identity::SecretKey;
451
452	fn sk(n: u8) -> SecretKey {
453	SecretKey {
454	ed_seed: [n; 32],
455	ml_seed: [n + 100; 32],
456	}
457	}
458
459	#[test]
460	fn globs() {
461	assert!(glob_matches("*", "main"));
462	assert!(glob_matches("release/*", "release/1.0"));
463	assert!(!glob_matches("release/*", "main"));
464	assert!(glob_matches("main", "main"));
465	assert!(!glob_matches("main", "main2"));
466	assert!(glob_matches("-rc", "1.0-rc2"));
467	assert!(glob_matches("", ""));
468	}
469
470	/// Subjects an issuer certifies (oxygenhub#241): kept through
471	/// encoding, absent from a policy without them, and granted only for
472	/// their issuer, pattern and scope, and not when the issuer is revoked.
473	#[test]
474	fn a_rule_grants_certified_subjects() {
475	use crate::identity::Scope;
476	let root = sk(1).identity("Root", "r@x", 0);
477	let hub = sk(3).identity("Hub", "h@x", 0);
478	let mut p = Policy::single_root([9; 16], root.clone(), 10);
479	let plain = p.encode();
480	p.rules[0].subjects.push(SubjectGrant {
481	pattern: "repo:andy/demo:bookmark:main".into(),
482	issuer: hub.hash(),
483	scope: Scope::REFS \| Scope::CHANGES,
484	});
485	p.rules[0].subjects.push(SubjectGrant {
486	pattern: "agent:*@andy".into(),
487	issuer: hub.hash(),
488	scope: Scope::CHANGES,
489	});
490	let back = Policy::decode(&p.encode()).unwrap();
491	assert_eq!(back, p);
492	let mut again = back.clone();
493	again.rules[0].subjects.clear();
494	assert_eq!(
495	again.encode(),
496	plain,
497	"no subjects, the same bytes as before"
498	);
499
500	let main = "repo:andy/demo:bookmark:main";
501	assert!(p.subject_grant("main", &hub.hash(), main, Scope::REFS));
502	assert!(p.subject_grant("main", &hub.hash(), "agent:claude@andy", Scope::CHANGES));
503	assert!(
504	!p.subject_grant("main", &hub.hash(), "agent:claude@andy", Scope::REFS),
505	"not its scope"
506	);
507	assert!(
508	!p.subject_grant(
509	"main",
510	&hub.hash(),
511	"repo:andy/demo:bookmark:dev",
512	Scope::REFS
513	),
514	"not its pattern"
515	);
516	assert!(
517	!p.subject_grant("main", &root.hash(), main, Scope::REFS),
518	"not its issuer"
519	);
520	p.revoked.push(hub.hash());
521	assert!(
522	!p.subject_grant("main", &hub.hash(), main, Scope::REFS),
523	"a revoked issuer grants nothing"
524	);
525
526	// A rule of subjects alone is a rule.
527	let mut only = Policy::single_root([9; 16], root, 10);
528	only.rules[0].keys.clear();
529	only.rules[0].subjects.push(SubjectGrant {
530	pattern: "*".into(),
531	issuer: hub.hash(),
532	scope: Scope::REFS,
533	});
534	assert!(Policy::decode(&only.encode()).is_ok());
535	only.rules[0].subjects.clear();
536	assert!(Policy::decode(&only.encode()).is_err(), "nobody to sign");
537	}
538
539	#[test]
540	fn round_trip_and_rules() {
541	let root = sk(1).identity("Root", "r@x", 0);
542	let dev = sk(2).identity("Dev", "d@x", 0);
543	let mut p = Policy::single_root([9; 16], root.clone(), 10);
544	p.rules.insert(
545	0,
546	Rule {
547	pattern: "release/*".into(),
548	keys: vec![root.hash()],
549	threshold: 1,
550	require: Require::Signed,
551	allow_conflicts: false,
552	subjects: vec![],
553	},
554	);
555	p.rules[1].keys.push(dev.hash());
556	p.identities.push(dev.clone());
557	p.revoked.push(ObjectRef([7; 32]));
558	let d = Policy::decode(&p.encode()).unwrap();
559	assert_eq!(d.rules.len(), 2);
560	assert_eq!(d.rules[0].require, Require::Signed);
561	assert_eq!(d.identity(&dev.hash()), Some(&dev));
562	assert!(d.authorizes(&dev.hash(), "main"));
563	assert!(!d.authorizes(&dev.hash(), "release/1"));
564	assert!(d.authorizes(&root.hash(), "release/1"));
565	assert!(d.is_expired(11) && !d.is_expired(10));
566	assert_eq!(d.hash(), p.hash());
567
568	let mut bad = p.clone();
569	bad.root_threshold = 5;
570	assert!(Policy::decode(&bad.encode()).is_err());
571	}
572
573	#[test]
574	fn signatures_need_root_threshold() {
575	let r1 = sk(1);
576	let r2 = sk(2);
577	let i1 = r1.identity("a", "a", 0);
578	let i2 = r2.identity("b", "b", 0);
579	let mut p = Policy::single_root([1; 16], i1.clone(), 100);
580	p.roots.push(i2.hash());
581	p.roots.sort();
582	p.root_threshold = 2;
583	p.identities.push(i2.clone());
584	let h = p.hash();
585	let s1 = r1.sign(Domain::Policy, &i1.hash(), &h);
586	let s2 = r2.sign(Domain::Policy, &i2.hash(), &h);
587	assert!(p.verify_signatures(std::slice::from_ref(&s1), &p).is_err());
588	assert_eq!(
589	p.verify_signatures(&[s1.clone(), s2.clone()], &p)
590	.unwrap()
591	.len(),
592	2
593	);
594	// Duplicates do not count twice; a non-root signer does not count.
595	assert!(p.verify_signatures(&[s1.clone(), s1.clone()], &p).is_err());
596	let stranger = sk(3);
597	let si = stranger.identity("s", "s", 0);
598	let s3 = stranger.sign(Domain::Policy, &si.hash(), &h);
599	assert!(p.verify_signatures(&[s1.clone(), s3], &p).is_err());
600	// A successor policy is verified against the previous roots.
601	let mut next = p.clone();
602	next.serial = 2;
603	next.revoked.push(i2.hash());
604	let nh = next.hash();
605	let n1 = r1.sign(Domain::Policy, &i1.hash(), &nh);
606	let n2 = r2.sign(Domain::Policy, &i2.hash(), &nh);
607	assert_eq!(next.verify_signatures(&[n1, n2], &p).unwrap().len(), 2);
608	}
609	}

Keyboard