use std::collections::{BTreeMap, BTreeSet};
use anyhow::{Context, Result, anyhow};
use ed25519_dalek::{Signature, Signer, SigningKey, VerifyingKey};
use rusqlite::{Connection, OptionalExtension, params};
use serde::{Deserialize, Serialize};
use sha2::{Digest, Sha256};
use super::hex;
use super::identity::IdentityTag;
use super::record::{put_len, put_str};
use crate::sqlite_store::SqliteStore;
const REVOCATION_DOMAIN: &[u8] = b"second-brain device revocation v1";
const REVOCATION_ID_DOMAIN: &[u8] = b"second-brain device revocation id v1";
const FRAME_FLOOR_PREFIX: &str = "frame_floor:";
#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
pub struct Revocation {
pub identity_tag: String,
pub revoker: String,
pub target: String,
pub keep: BTreeSet<String>,
pub created_at_micros: i64,
}
#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
pub struct SignedRevocation {
pub revocation: Revocation,
#[serde(with = "super::record::hex_array")]
pub signature: [u8; 64],
}
impl Revocation {
pub fn signing_bytes(&self) -> Vec<u8> {
let mut out = Vec::with_capacity(128);
out.extend_from_slice(REVOCATION_DOMAIN);
put_str(&mut out, &self.identity_tag);
put_str(&mut out, &self.revoker);
put_str(&mut out, &self.target);
put_len(&mut out, self.keep.len());
for id in &self.keep {
put_str(&mut out, id);
}
out.extend_from_slice(&self.created_at_micros.to_be_bytes());
out
}
pub fn sign(self, key: &SigningKey) -> SignedRevocation {
let signature: Signature = key.sign(&self.signing_bytes());
SignedRevocation {
revocation: self,
signature: signature.to_bytes(),
}
}
}
impl SignedRevocation {
pub fn id(&self) -> String {
let digest = Sha256::new()
.chain_update(REVOCATION_ID_DOMAIN)
.chain_update(self.revocation.signing_bytes())
.finalize();
hex(&digest[..16])
}
pub fn verify(&self, revoker_key: &VerifyingKey) -> Result<()> {
revoker_key
.verify_strict(
&self.revocation.signing_bytes(),
&Signature::from_bytes(&self.signature),
)
.map_err(|_| {
anyhow!(
"the revocation of {} by {} does not verify under the revoker's key",
self.revocation.target,
self.revocation.revoker
)
})
}
}
#[derive(Serialize, Deserialize, Clone, Debug, Default, PartialEq, Eq)]
pub struct EpochCause {
#[serde(default)]
pub revocations: BTreeSet<String>,
#[serde(default, skip_serializing_if = "BTreeSet::is_empty")]
pub retirements: BTreeSet<String>,
}
impl EpochCause {
pub fn is_empty(&self) -> bool {
self.revocations.is_empty() && self.retirements.is_empty()
}
pub fn to_json(&self) -> Result<String> {
serde_json::to_string(self).context("encoding an epoch cause")
}
pub fn from_stored(cause: Option<&str>) -> Result<Self> {
match cause {
None => Ok(Self::default()),
Some(text) => serde_json::from_str(text).context("decoding an epoch cause"),
}
}
}
pub fn revoked_by(
first_signers: &BTreeMap<String, BTreeSet<String>>,
revocations: &[&Revocation],
) -> BTreeSet<String> {
let mut all = BTreeSet::new();
for revocation in revocations {
let mut reached = BTreeSet::from([revocation.target.clone()]);
loop {
let before = reached.len();
for (id, signers) in first_signers {
if !reached.contains(id)
&& !revocation.keep.contains(id)
&& signers.iter().any(|signer| reached.contains(signer))
{
reached.insert(id.clone());
}
}
if reached.len() == before {
break;
}
}
all.extend(reached);
}
all
}
impl SqliteStore {
pub fn put_revocation(
&self,
signed: &SignedRevocation,
revoker_key: &VerifyingKey,
) -> Result<bool> {
signed.verify(revoker_key)?;
let id = signed.id();
let target = &signed.revocation.target;
self.with_txn(|tx| {
let stored: Option<Option<String>> = tx
.query_row(
"SELECT revocation FROM machines WHERE id = ?1",
params![target],
|r| r.get(0),
)
.optional()?;
let mut held = parse_revocations(stored.flatten().as_deref())?;
if held.iter().any(|r| r.id() == id) {
return Ok(false);
}
held.push(signed.clone());
held.sort_by_key(SignedRevocation::id);
tx.execute(
"INSERT INTO machines (id, revocation) VALUES (?1, ?2) \
ON CONFLICT(id) DO UPDATE SET revocation = excluded.revocation",
params![target, serde_json::to_string(&held)?],
)?;
Ok(true)
})
}
pub fn revocations(&self, tag: &IdentityTag) -> Result<Vec<SignedRevocation>> {
let conn = self.reader();
let mut stmt =
conn.prepare("SELECT revocation FROM machines WHERE revocation IS NOT NULL")?;
let rows = stmt.query_map([], |r| r.get::<_, String>(0))?;
let mut held = Vec::new();
for text in rows {
held.extend(
parse_revocations(Some(&text?))?
.into_iter()
.filter(|r| r.revocation.identity_tag == tag.as_str()),
);
}
held.sort_by_key(SignedRevocation::id);
Ok(held)
}
pub fn revoked_by_rule(
&self,
tag: &IdentityTag,
extra: Option<&Revocation>,
) -> Result<BTreeSet<String>> {
let first_signers = self.first_signers(tag)?;
let stored = self.revocations(tag)?;
let mut rules: Vec<&Revocation> = stored.iter().map(|s| &s.revocation).collect();
rules.extend(extra);
Ok(revoked_by(&first_signers, &rules))
}
pub fn revokers_of(&self, tag: &IdentityTag, machine_id: &str) -> Result<BTreeSet<String>> {
let first_signers = self.first_signers(tag)?;
Ok(self
.revocations(tag)?
.into_iter()
.filter(|s| revoked_by(&first_signers, &[&s.revocation]).contains(machine_id))
.map(|s| s.revocation.revoker)
.collect())
}
fn first_signers(&self, tag: &IdentityTag) -> Result<BTreeMap<String, BTreeSet<String>>> {
Ok(self
.device_records()?
.into_iter()
.filter(|row| row.first.record.identity_tag == tag.as_str())
.map(|row| {
let id = row.first.record.machine_id;
let signers = row
.first
.signatures
.into_iter()
.map(|s| s.signer)
.filter(|signer| *signer != id)
.collect();
(id, signers)
})
.collect())
}
pub fn apply_revocations(&self, tag: &IdentityTag) -> Result<Vec<String>> {
let reached = self.revoked_by_rule(tag, None)?;
self.with_txn(|tx| {
let mut newly = Vec::new();
for id in reached {
for table in ["peer_acks", "peer_pins"] {
tx.execute(
&format!("DELETE FROM {table} WHERE peer_id = ?1"),
params![id],
)?;
}
let marked = tx.execute(
"UPDATE machines SET revoked = 1 WHERE id = ?1 AND revoked = 0",
params![id],
)?;
if marked > 0 {
newly.push(id);
}
}
Ok(newly)
})
}
pub fn frame_floor(&self, tag: &IdentityTag, peer: &str) -> Result<Option<u32>> {
read_frame_floor(&self.reader(), &frame_floor_key(tag, peer))
}
pub fn raise_frame_floor(&self, tag: &IdentityTag, peer: &str, number: u32) -> Result<bool> {
let key = frame_floor_key(tag, peer);
self.with_txn(|tx| {
if read_frame_floor(tx, &key)?.is_some_and(|floor| floor >= number) {
return Ok(false);
}
tx.execute(
"INSERT OR REPLACE INTO index_meta (key, value) VALUES (?1, ?2)",
params![key, number.to_string()],
)?;
Ok(true)
})
}
}
fn parse_revocations(text: Option<&str>) -> Result<Vec<SignedRevocation>> {
match text {
None => Ok(Vec::new()),
Some(text) => serde_json::from_str(text).context("decoding a stored revocation"),
}
}
fn frame_floor_key(tag: &IdentityTag, peer: &str) -> String {
format!("{FRAME_FLOOR_PREFIX}{}:{peer}", tag.as_str())
}
fn read_frame_floor(conn: &Connection, key: &str) -> Result<Option<u32>> {
let value: Option<String> = conn
.query_row(
"SELECT value FROM index_meta WHERE key = ?1",
params![key],
|r| r.get(0),
)
.optional()?;
value
.map(|v| v.parse().with_context(|| format!("stored {key} is {v:?}")))
.transpose()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::keys::record::DeviceRecord;
const TAG: &str = "f-tag";
fn key(seed: u8) -> SigningKey {
SigningKey::from_bytes(&[seed; 32])
}
fn revocation(revoker: &str, target: &str, keep: &[&str]) -> Revocation {
Revocation {
identity_tag: TAG.to_string(),
revoker: revoker.to_string(),
target: target.to_string(),
keep: keep.iter().map(|s| s.to_string()).collect(),
created_at_micros: 1_000,
}
}
fn signers(entries: &[(&str, &[&str])]) -> BTreeMap<String, BTreeSet<String>> {
entries
.iter()
.map(|(id, by)| (id.to_string(), by.iter().map(|s| s.to_string()).collect()))
.collect()
}
fn ids(set: &BTreeSet<String>) -> Vec<&str> {
set.iter().map(String::as_str).collect()
}
#[test]
fn a_signed_revocation_verifies_and_tampering_any_field_breaks_it() {
let revoker = key(1);
let signed = revocation("a", "c", &["b"]).sign(&revoker);
signed.verify(&revoker.verifying_key()).unwrap();
assert!(signed.verify(&key(2).verifying_key()).is_err());
let cases: [(&str, fn(&mut Revocation)); 6] = [
("identity", |r| r.identity_tag = "f-other".into()),
("revoker", |r| r.revoker = "b".into()),
("target", |r| r.target = "b".into()),
("keep added", |r| {
r.keep.insert("d".into());
}),
("keep removed", |r| r.keep.clear()),
("time", |r| r.created_at_micros += 1),
];
for (field, tamper) in cases {
let mut edited = signed.clone();
tamper(&mut edited.revocation);
assert!(
edited.verify(&revoker.verifying_key()).is_err(),
"tampered {field} still verifies"
);
assert_ne!(edited.id(), signed.id(), "tampered {field} keeps the id");
}
}
#[test]
fn signed_revocations_round_trip_through_json() {
let signed = revocation("a", "c", &["b", "d"]).sign(&key(1));
let text = serde_json::to_string(&signed).unwrap();
let back: SignedRevocation = serde_json::from_str(&text).unwrap();
assert_eq!(back, signed);
assert_eq!(back.id(), signed.id());
back.verify(&key(1).verifying_key()).unwrap();
}
#[test]
fn the_rule_reaches_the_target_and_what_it_signed_transitively_except_kept_ids() {
let lineage = signers(&[
("a", &[]),
("b", &["a"]),
("c", &["b"]),
("d", &["c"]),
("e", &["a"]),
("f", &["b"]),
("g", &["b", "e"]),
("h", &["c", "f"]),
]);
let cases: [(&str, Revocation, &[&str]); 7] = [
("leaf", revocation("a", "d", &[]), &["d"]),
(
"transitive",
revocation("a", "b", &[]),
&["b", "c", "d", "f", "g", "h"],
),
(
"a kept device stops the descent through it",
revocation("a", "b", &["c", "f"]),
&["b", "g"],
),
(
"a device below a kept one is still reached by another path",
revocation("a", "b", &["c"]),
&["b", "f", "g", "h"],
),
(
"the target is revoked even when kept",
revocation("a", "d", &["d"]),
&["d"],
),
("unknown target", revocation("a", "x", &[]), &["x"]),
(
"the founder reaches everything not kept",
revocation("b", "a", &["b"]),
&["a", "e", "g"],
),
];
for (name, rule, expected) in cases {
assert_eq!(
ids(&revoked_by(&lineage, &[&rule])),
expected.to_vec(),
"{name}"
);
}
}
#[test]
fn revocations_apply_as_a_union_whatever_revoked_their_revoker() {
let lineage = signers(&[("a", &[]), ("b", &["a"]), ("c", &["a"]), ("t", &["a"])]);
let thief = revocation("t", "a", &["t", "b", "c"]);
let owner = revocation("a", "t", &["a"]);
for order in [[&thief, &owner], [&owner, &thief]] {
assert_eq!(ids(&revoked_by(&lineage, &order)), ["a", "t"]);
}
}
fn row(id: &str, own: &SigningKey) -> DeviceRecord {
DeviceRecord {
machine_id: id.to_string(),
identity_tag: TAG.to_string(),
version: 1,
name: format!("{id}-name"),
age_recipient: "age1recipient".to_string(),
ssh_public_key: "ssh-ed25519 AAAA".to_string(),
signing_public_key: own.verifying_key().to_bytes(),
recovery_fingerprints: Vec::new(),
ssh_login: None,
ssh_port: None,
ssh_host_key: None,
}
}
fn store_with_chain() -> SqliteStore {
let store = SqliteStore::in_memory("a".to_string()).unwrap();
let (a, b, c) = (key(1), key(2), key(3));
store
.insert_first_device_record(&row("a", &a).sign("a", &a), "a", &a.verifying_key())
.unwrap();
store
.insert_first_device_record(&row("b", &b).sign("a", &a), "a", &a.verifying_key())
.unwrap();
store
.insert_first_device_record(&row("c", &c).sign("b", &b), "b", &b.verifying_key())
.unwrap();
store
}
fn revoked(store: &SqliteStore) -> Vec<String> {
store
.device_records()
.unwrap()
.into_iter()
.filter(|r| r.revoked)
.map(|r| r.current.record.machine_id)
.collect()
}
#[test]
fn a_stored_revocation_marks_its_reach_once_and_stays() {
let store = store_with_chain();
let tag = IdentityTag::from(TAG.to_string());
let signed = revocation("a", "b", &["a"]).sign(&key(1));
assert!(
store
.put_revocation(&signed, &key(9).verifying_key())
.is_err()
);
assert!(store.revocations(&tag).unwrap().is_empty());
assert!(
store
.put_revocation(&signed, &key(1).verifying_key())
.unwrap()
);
assert!(
!store
.put_revocation(&signed, &key(1).verifying_key())
.unwrap()
);
assert_eq!(store.revocations(&tag).unwrap(), vec![signed.clone()]);
assert!(
store
.revocations(&IdentityTag::from("f-other".to_string()))
.unwrap()
.is_empty()
);
assert_eq!(store.apply_revocations(&tag).unwrap(), ["b", "c"]);
assert!(store.apply_revocations(&tag).unwrap().is_empty());
assert_eq!(revoked(&store), ["b", "c"]);
}
#[test]
fn a_device_learned_after_the_revocation_is_reached_by_it() {
let store = store_with_chain();
let tag = IdentityTag::from(TAG.to_string());
store
.put_revocation(
&revocation("a", "c", &["a"]).sign(&key(1)),
&key(1).verifying_key(),
)
.unwrap();
store.apply_revocations(&tag).unwrap();
let (c, d) = (key(3), key(4));
store
.insert_first_device_record(&row("d", &d).sign("c", &c), "c", &c.verifying_key())
.unwrap();
assert_eq!(store.apply_revocations(&tag).unwrap(), ["d"]);
assert_eq!(revoked(&store), ["c", "d"]);
}
#[test]
fn a_revocation_of_an_unseen_device_waits_on_a_bare_row() {
let store = store_with_chain();
let tag = IdentityTag::from(TAG.to_string());
let signed = revocation("a", "x", &["a"]).sign(&key(1));
store
.put_revocation(&signed, &key(1).verifying_key())
.unwrap();
assert_eq!(store.apply_revocations(&tag).unwrap(), ["x"]);
assert!(store.device_record("x").unwrap().is_none());
assert_eq!(store.revocations(&tag).unwrap(), vec![signed]);
let x = key(5);
store
.insert_first_device_record(
&row("x", &x).sign("a", &key(1)),
"a",
&key(1).verifying_key(),
)
.unwrap();
assert!(store.device_record("x").unwrap().unwrap().revoked);
}
#[test]
fn revoked_by_rule_previews_an_extra_revocation_without_storing_it() {
let store = store_with_chain();
let tag = IdentityTag::from(TAG.to_string());
let extra = revocation("a", "b", &["a"]);
assert_eq!(
ids(&store.revoked_by_rule(&tag, Some(&extra)).unwrap()),
["b", "c"]
);
assert!(store.revoked_by_rule(&tag, None).unwrap().is_empty());
assert!(revoked(&store).is_empty());
}
#[test]
fn a_frame_floor_only_rises_and_belongs_to_one_identity() {
let store = SqliteStore::in_memory("a".to_string()).unwrap();
let tag = IdentityTag::from(TAG.to_string());
let other = IdentityTag::from("f-other".to_string());
assert_eq!(store.frame_floor(&tag, "b").unwrap(), None);
assert!(store.raise_frame_floor(&tag, "b", 3).unwrap());
assert!(!store.raise_frame_floor(&tag, "b", 2).unwrap());
assert!(!store.raise_frame_floor(&tag, "b", 3).unwrap());
assert_eq!(store.frame_floor(&tag, "b").unwrap(), Some(3));
assert_eq!(store.frame_floor(&tag, "c").unwrap(), None);
assert_eq!(store.frame_floor(&other, "b").unwrap(), None);
}
#[test]
fn revoked_devices_lose_their_log_floor_acks_and_pins() {
let store = store_with_chain();
let tag = IdentityTag::from(TAG.to_string());
for peer in ["b", "c"] {
store.record_peer_ack(peer, 5, 1).unwrap();
store.pin_peer(peer, 5).unwrap();
}
store
.put_revocation(
&revocation("a", "c", &["a"]).sign(&key(1)),
&key(1).verifying_key(),
)
.unwrap();
store.apply_revocations(&tag).unwrap();
let peers = |table: &str| -> Vec<String> {
let conn = store.reader();
let mut stmt = conn
.prepare(&format!("SELECT peer_id FROM {table} ORDER BY peer_id"))
.unwrap();
stmt.query_map([], |r| r.get(0))
.unwrap()
.map(Result::unwrap)
.collect()
};
assert_eq!(peers("peer_acks"), ["b"]);
assert_eq!(peers("peer_pins"), ["b"]);
}
#[test]
fn revokers_of_names_whose_rules_reach_a_device() {
let store = store_with_chain();
let tag = IdentityTag::from(TAG.to_string());
store
.put_revocation(
&revocation("a", "b", &["a"]).sign(&key(1)),
&key(1).verifying_key(),
)
.unwrap();
assert_eq!(ids(&store.revokers_of(&tag, "c").unwrap()), ["a"]);
assert!(store.revokers_of(&tag, "a").unwrap().is_empty());
}
#[test]
fn an_epoch_cause_round_trips_and_a_missing_one_is_empty() {
let cause = EpochCause {
revocations: ["r1".to_string(), "r2".to_string()].into(),
retirements: Default::default(),
};
let text = cause.to_json().unwrap();
assert_eq!(text, r#"{"revocations":["r1","r2"]}"#);
assert_eq!(EpochCause::from_stored(Some(&text)).unwrap(), cause);
let retired = EpochCause {
retirements: ["0123456789abcdef".to_string()].into(),
..Default::default()
};
assert!(!retired.is_empty());
let text = retired.to_json().unwrap();
assert_eq!(EpochCause::from_stored(Some(&text)).unwrap(), retired);
assert!(EpochCause::from_stored(None).unwrap().is_empty());
assert!(EpochCause::from_stored(Some("{")).is_err());
}
}