Skip to main content

second_brain_core/keys/
revocation.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use anyhow::{Context, Result, anyhow};
4use ed25519_dalek::{Signature, Signer, SigningKey, VerifyingKey};
5use rusqlite::{Connection, OptionalExtension, params};
6use serde::{Deserialize, Serialize};
7use sha2::{Digest, Sha256};
8
9use super::hex;
10use super::identity::IdentityTag;
11use super::record::{put_len, put_str};
12use crate::sqlite_store::SqliteStore;
13
14const REVOCATION_DOMAIN: &[u8] = b"second-brain device revocation v1";
15const REVOCATION_ID_DOMAIN: &[u8] = b"second-brain device revocation id v1";
16const FRAME_FLOOR_PREFIX: &str = "frame_floor:";
17
18/// The rule "`target`, and every device whose first row a revoked device
19/// signed, transitively, except the `keep` ids", signed by `revoker`. A
20/// countersigner of a first row counts as its signer; the target is
21/// revoked even when listed in `keep`.
22#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
23pub struct Revocation {
24    pub identity_tag: String,
25    pub revoker: String,
26    pub target: String,
27    pub keep: BTreeSet<String>,
28    pub created_at_micros: i64,
29}
30
31#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
32pub struct SignedRevocation {
33    pub revocation: Revocation,
34    #[serde(with = "super::record::hex_array")]
35    pub signature: [u8; 64],
36}
37
38impl Revocation {
39    pub fn signing_bytes(&self) -> Vec<u8> {
40        let mut out = Vec::with_capacity(128);
41        out.extend_from_slice(REVOCATION_DOMAIN);
42        put_str(&mut out, &self.identity_tag);
43        put_str(&mut out, &self.revoker);
44        put_str(&mut out, &self.target);
45        put_len(&mut out, self.keep.len());
46        for id in &self.keep {
47            put_str(&mut out, id);
48        }
49        out.extend_from_slice(&self.created_at_micros.to_be_bytes());
50        out
51    }
52
53    pub fn sign(self, key: &SigningKey) -> SignedRevocation {
54        let signature: Signature = key.sign(&self.signing_bytes());
55        SignedRevocation {
56            revocation: self,
57            signature: signature.to_bytes(),
58        }
59    }
60}
61
62impl SignedRevocation {
63    /// Names the revocation in epoch causes; the content fixes it, since
64    /// the revoker is part of the content.
65    pub fn id(&self) -> String {
66        let digest = Sha256::new()
67            .chain_update(REVOCATION_ID_DOMAIN)
68            .chain_update(self.revocation.signing_bytes())
69            .finalize();
70        hex(&digest[..16])
71    }
72
73    pub fn verify(&self, revoker_key: &VerifyingKey) -> Result<()> {
74        revoker_key
75            .verify_strict(
76                &self.revocation.signing_bytes(),
77                &Signature::from_bytes(&self.signature),
78            )
79            .map_err(|_| {
80                anyhow!(
81                    "the revocation of {} by {} does not verify under the revoker's key",
82                    self.revocation.target,
83                    self.revocation.revoker
84                )
85            })
86    }
87}
88
89/// The revocations, by id, and the recovery phrase retirements, by
90/// fingerprint, that caused an epoch. Empty for epoch 0 and epoch 1.
91#[derive(Serialize, Deserialize, Clone, Debug, Default, PartialEq, Eq)]
92pub struct EpochCause {
93    #[serde(default)]
94    pub revocations: BTreeSet<String>,
95    #[serde(default, skip_serializing_if = "BTreeSet::is_empty")]
96    pub retirements: BTreeSet<String>,
97}
98
99impl EpochCause {
100    pub fn is_empty(&self) -> bool {
101        self.revocations.is_empty() && self.retirements.is_empty()
102    }
103
104    pub fn to_json(&self) -> Result<String> {
105        serde_json::to_string(self).context("encoding an epoch cause")
106    }
107
108    /// A missing cause, from a key epoch stored without one, is empty.
109    pub fn from_stored(cause: Option<&str>) -> Result<Self> {
110        match cause {
111            None => Ok(Self::default()),
112            Some(text) => serde_json::from_str(text).context("decoding an epoch cause"),
113        }
114    }
115}
116
117/// Every machine id the revocations reach. `first_signers` maps each known
118/// device to the signers of its first row other than itself.
119pub fn revoked_by(
120    first_signers: &BTreeMap<String, BTreeSet<String>>,
121    revocations: &[&Revocation],
122) -> BTreeSet<String> {
123    let mut all = BTreeSet::new();
124    for revocation in revocations {
125        let mut reached = BTreeSet::from([revocation.target.clone()]);
126        loop {
127            let before = reached.len();
128            for (id, signers) in first_signers {
129                if !reached.contains(id)
130                    && !revocation.keep.contains(id)
131                    && signers.iter().any(|signer| reached.contains(signer))
132                {
133                    reached.insert(id.clone());
134                }
135            }
136            if reached.len() == before {
137                break;
138            }
139        }
140        all.extend(reached);
141    }
142    all
143}
144
145impl SqliteStore {
146    /// Keeps a revocation verified under its revoker's key on the target's
147    /// machine row, creating a bare row for a target this store has not
148    /// seen. Which revokers count is the caller's rule. Returns false when
149    /// it was already stored. `apply_revocations` marks the devices it
150    /// reaches.
151    pub fn put_revocation(
152        &self,
153        signed: &SignedRevocation,
154        revoker_key: &VerifyingKey,
155    ) -> Result<bool> {
156        signed.verify(revoker_key)?;
157        let id = signed.id();
158        let target = &signed.revocation.target;
159        self.with_txn(|tx| {
160            let stored: Option<Option<String>> = tx
161                .query_row(
162                    "SELECT revocation FROM machines WHERE id = ?1",
163                    params![target],
164                    |r| r.get(0),
165                )
166                .optional()?;
167            let mut held = parse_revocations(stored.flatten().as_deref())?;
168            if held.iter().any(|r| r.id() == id) {
169                return Ok(false);
170            }
171            held.push(signed.clone());
172            held.sort_by_key(SignedRevocation::id);
173            tx.execute(
174                "INSERT INTO machines (id, revocation) VALUES (?1, ?2) \
175                 ON CONFLICT(id) DO UPDATE SET revocation = excluded.revocation",
176                params![target, serde_json::to_string(&held)?],
177            )?;
178            Ok(true)
179        })
180    }
181
182    pub fn revocations(&self, tag: &IdentityTag) -> Result<Vec<SignedRevocation>> {
183        let conn = self.reader();
184        let mut stmt =
185            conn.prepare("SELECT revocation FROM machines WHERE revocation IS NOT NULL")?;
186        let rows = stmt.query_map([], |r| r.get::<_, String>(0))?;
187        let mut held = Vec::new();
188        for text in rows {
189            held.extend(
190                parse_revocations(Some(&text?))?
191                    .into_iter()
192                    .filter(|r| r.revocation.identity_tag == tag.as_str()),
193            );
194        }
195        held.sort_by_key(SignedRevocation::id);
196        Ok(held)
197    }
198
199    /// The devices of `tag` that its stored revocations reach, plus those
200    /// `extra` would reach, from the first rows held now.
201    pub fn revoked_by_rule(
202        &self,
203        tag: &IdentityTag,
204        extra: Option<&Revocation>,
205    ) -> Result<BTreeSet<String>> {
206        let first_signers = self.first_signers(tag)?;
207        let stored = self.revocations(tag)?;
208        let mut rules: Vec<&Revocation> = stored.iter().map(|s| &s.revocation).collect();
209        rules.extend(extra);
210        Ok(revoked_by(&first_signers, &rules))
211    }
212
213    /// The revokers of the stored revocations of `tag` whose rule reaches
214    /// `machine_id`.
215    pub fn revokers_of(&self, tag: &IdentityTag, machine_id: &str) -> Result<BTreeSet<String>> {
216        let first_signers = self.first_signers(tag)?;
217        Ok(self
218            .revocations(tag)?
219            .into_iter()
220            .filter(|s| revoked_by(&first_signers, &[&s.revocation]).contains(machine_id))
221            .map(|s| s.revocation.revoker)
222            .collect())
223    }
224
225    fn first_signers(&self, tag: &IdentityTag) -> Result<BTreeMap<String, BTreeSet<String>>> {
226        Ok(self
227            .device_records()?
228            .into_iter()
229            .filter(|row| row.first.record.identity_tag == tag.as_str())
230            .map(|row| {
231                let id = row.first.record.machine_id;
232                let signers = row
233                    .first
234                    .signatures
235                    .into_iter()
236                    .map(|s| s.signer)
237                    .filter(|signer| *signer != id)
238                    .collect();
239                (id, signers)
240            })
241            .collect())
242    }
243
244    /// Marks every device the stored revocations of `tag` reach as revoked,
245    /// which is sticky, drops their log floor acks and pins, and returns
246    /// those newly marked.
247    pub fn apply_revocations(&self, tag: &IdentityTag) -> Result<Vec<String>> {
248        let reached = self.revoked_by_rule(tag, None)?;
249        self.with_txn(|tx| {
250            let mut newly = Vec::new();
251            for id in reached {
252                for table in ["peer_acks", "peer_pins"] {
253                    tx.execute(
254                        &format!("DELETE FROM {table} WHERE peer_id = ?1"),
255                        params![id],
256                    )?;
257                }
258                let marked = tx.execute(
259                    "UPDATE machines SET revoked = 1 WHERE id = ?1 AND revoked = 0",
260                    params![id],
261                )?;
262                if marked > 0 {
263                    newly.push(id);
264                }
265            }
266            Ok(newly)
267        })
268    }
269
270    /// The lowest epoch number `peer` may still seal wire frames under.
271    pub fn frame_floor(&self, tag: &IdentityTag, peer: &str) -> Result<Option<u32>> {
272        read_frame_floor(&self.reader(), &frame_floor_key(tag, peer))
273    }
274
275    /// Raises the floor for `peer`, never lowering it; returns true when it
276    /// moved.
277    pub fn raise_frame_floor(&self, tag: &IdentityTag, peer: &str, number: u32) -> Result<bool> {
278        let key = frame_floor_key(tag, peer);
279        self.with_txn(|tx| {
280            if read_frame_floor(tx, &key)?.is_some_and(|floor| floor >= number) {
281                return Ok(false);
282            }
283            tx.execute(
284                "INSERT OR REPLACE INTO index_meta (key, value) VALUES (?1, ?2)",
285                params![key, number.to_string()],
286            )?;
287            Ok(true)
288        })
289    }
290}
291
292fn parse_revocations(text: Option<&str>) -> Result<Vec<SignedRevocation>> {
293    match text {
294        None => Ok(Vec::new()),
295        Some(text) => serde_json::from_str(text).context("decoding a stored revocation"),
296    }
297}
298
299fn frame_floor_key(tag: &IdentityTag, peer: &str) -> String {
300    format!("{FRAME_FLOOR_PREFIX}{}:{peer}", tag.as_str())
301}
302
303fn read_frame_floor(conn: &Connection, key: &str) -> Result<Option<u32>> {
304    let value: Option<String> = conn
305        .query_row(
306            "SELECT value FROM index_meta WHERE key = ?1",
307            params![key],
308            |r| r.get(0),
309        )
310        .optional()?;
311    value
312        .map(|v| v.parse().with_context(|| format!("stored {key} is {v:?}")))
313        .transpose()
314}
315
316#[cfg(test)]
317mod tests {
318    use super::*;
319    use crate::keys::record::DeviceRecord;
320
321    const TAG: &str = "f-tag";
322
323    fn key(seed: u8) -> SigningKey {
324        SigningKey::from_bytes(&[seed; 32])
325    }
326
327    fn revocation(revoker: &str, target: &str, keep: &[&str]) -> Revocation {
328        Revocation {
329            identity_tag: TAG.to_string(),
330            revoker: revoker.to_string(),
331            target: target.to_string(),
332            keep: keep.iter().map(|s| s.to_string()).collect(),
333            created_at_micros: 1_000,
334        }
335    }
336
337    fn signers(entries: &[(&str, &[&str])]) -> BTreeMap<String, BTreeSet<String>> {
338        entries
339            .iter()
340            .map(|(id, by)| (id.to_string(), by.iter().map(|s| s.to_string()).collect()))
341            .collect()
342    }
343
344    fn ids(set: &BTreeSet<String>) -> Vec<&str> {
345        set.iter().map(String::as_str).collect()
346    }
347
348    #[test]
349    fn a_signed_revocation_verifies_and_tampering_any_field_breaks_it() {
350        let revoker = key(1);
351        let signed = revocation("a", "c", &["b"]).sign(&revoker);
352        signed.verify(&revoker.verifying_key()).unwrap();
353        assert!(signed.verify(&key(2).verifying_key()).is_err());
354
355        let cases: [(&str, fn(&mut Revocation)); 6] = [
356            ("identity", |r| r.identity_tag = "f-other".into()),
357            ("revoker", |r| r.revoker = "b".into()),
358            ("target", |r| r.target = "b".into()),
359            ("keep added", |r| {
360                r.keep.insert("d".into());
361            }),
362            ("keep removed", |r| r.keep.clear()),
363            ("time", |r| r.created_at_micros += 1),
364        ];
365        for (field, tamper) in cases {
366            let mut edited = signed.clone();
367            tamper(&mut edited.revocation);
368            assert!(
369                edited.verify(&revoker.verifying_key()).is_err(),
370                "tampered {field} still verifies"
371            );
372            assert_ne!(edited.id(), signed.id(), "tampered {field} keeps the id");
373        }
374    }
375
376    #[test]
377    fn signed_revocations_round_trip_through_json() {
378        let signed = revocation("a", "c", &["b", "d"]).sign(&key(1));
379        let text = serde_json::to_string(&signed).unwrap();
380        let back: SignedRevocation = serde_json::from_str(&text).unwrap();
381        assert_eq!(back, signed);
382        assert_eq!(back.id(), signed.id());
383        back.verify(&key(1).verifying_key()).unwrap();
384    }
385
386    #[test]
387    fn the_rule_reaches_the_target_and_what_it_signed_transitively_except_kept_ids() {
388        let lineage = signers(&[
389            ("a", &[]),
390            ("b", &["a"]),
391            ("c", &["b"]),
392            ("d", &["c"]),
393            ("e", &["a"]),
394            ("f", &["b"]),
395            ("g", &["b", "e"]),
396            ("h", &["c", "f"]),
397        ]);
398        let cases: [(&str, Revocation, &[&str]); 7] = [
399            ("leaf", revocation("a", "d", &[]), &["d"]),
400            (
401                "transitive",
402                revocation("a", "b", &[]),
403                &["b", "c", "d", "f", "g", "h"],
404            ),
405            (
406                "a kept device stops the descent through it",
407                revocation("a", "b", &["c", "f"]),
408                &["b", "g"],
409            ),
410            (
411                "a device below a kept one is still reached by another path",
412                revocation("a", "b", &["c"]),
413                &["b", "f", "g", "h"],
414            ),
415            (
416                "the target is revoked even when kept",
417                revocation("a", "d", &["d"]),
418                &["d"],
419            ),
420            ("unknown target", revocation("a", "x", &[]), &["x"]),
421            (
422                "the founder reaches everything not kept",
423                revocation("b", "a", &["b"]),
424                &["a", "e", "g"],
425            ),
426        ];
427        for (name, rule, expected) in cases {
428            assert_eq!(
429                ids(&revoked_by(&lineage, &[&rule])),
430                expected.to_vec(),
431                "{name}"
432            );
433        }
434    }
435
436    #[test]
437    fn revocations_apply_as_a_union_whatever_revoked_their_revoker() {
438        let lineage = signers(&[("a", &[]), ("b", &["a"]), ("c", &["a"]), ("t", &["a"])]);
439        let thief = revocation("t", "a", &["t", "b", "c"]);
440        let owner = revocation("a", "t", &["a"]);
441        for order in [[&thief, &owner], [&owner, &thief]] {
442            assert_eq!(ids(&revoked_by(&lineage, &order)), ["a", "t"]);
443        }
444    }
445
446    fn row(id: &str, own: &SigningKey) -> DeviceRecord {
447        DeviceRecord {
448            machine_id: id.to_string(),
449            identity_tag: TAG.to_string(),
450            version: 1,
451            name: format!("{id}-name"),
452            age_recipient: "age1recipient".to_string(),
453            ssh_public_key: "ssh-ed25519 AAAA".to_string(),
454            signing_public_key: own.verifying_key().to_bytes(),
455            recovery_fingerprints: Vec::new(),
456            ssh_login: None,
457            ssh_port: None,
458            ssh_host_key: None,
459        }
460    }
461
462    fn store_with_chain() -> SqliteStore {
463        let store = SqliteStore::in_memory("a".to_string()).unwrap();
464        let (a, b, c) = (key(1), key(2), key(3));
465        store
466            .insert_first_device_record(&row("a", &a).sign("a", &a), "a", &a.verifying_key())
467            .unwrap();
468        store
469            .insert_first_device_record(&row("b", &b).sign("a", &a), "a", &a.verifying_key())
470            .unwrap();
471        store
472            .insert_first_device_record(&row("c", &c).sign("b", &b), "b", &b.verifying_key())
473            .unwrap();
474        store
475    }
476
477    fn revoked(store: &SqliteStore) -> Vec<String> {
478        store
479            .device_records()
480            .unwrap()
481            .into_iter()
482            .filter(|r| r.revoked)
483            .map(|r| r.current.record.machine_id)
484            .collect()
485    }
486
487    #[test]
488    fn a_stored_revocation_marks_its_reach_once_and_stays() {
489        let store = store_with_chain();
490        let tag = IdentityTag::from(TAG.to_string());
491        let signed = revocation("a", "b", &["a"]).sign(&key(1));
492        assert!(
493            store
494                .put_revocation(&signed, &key(9).verifying_key())
495                .is_err()
496        );
497        assert!(store.revocations(&tag).unwrap().is_empty());
498
499        assert!(
500            store
501                .put_revocation(&signed, &key(1).verifying_key())
502                .unwrap()
503        );
504        assert!(
505            !store
506                .put_revocation(&signed, &key(1).verifying_key())
507                .unwrap()
508        );
509        assert_eq!(store.revocations(&tag).unwrap(), vec![signed.clone()]);
510        assert!(
511            store
512                .revocations(&IdentityTag::from("f-other".to_string()))
513                .unwrap()
514                .is_empty()
515        );
516
517        assert_eq!(store.apply_revocations(&tag).unwrap(), ["b", "c"]);
518        assert!(store.apply_revocations(&tag).unwrap().is_empty());
519        assert_eq!(revoked(&store), ["b", "c"]);
520    }
521
522    #[test]
523    fn a_device_learned_after_the_revocation_is_reached_by_it() {
524        let store = store_with_chain();
525        let tag = IdentityTag::from(TAG.to_string());
526        store
527            .put_revocation(
528                &revocation("a", "c", &["a"]).sign(&key(1)),
529                &key(1).verifying_key(),
530            )
531            .unwrap();
532        store.apply_revocations(&tag).unwrap();
533
534        let (c, d) = (key(3), key(4));
535        store
536            .insert_first_device_record(&row("d", &d).sign("c", &c), "c", &c.verifying_key())
537            .unwrap();
538        assert_eq!(store.apply_revocations(&tag).unwrap(), ["d"]);
539        assert_eq!(revoked(&store), ["c", "d"]);
540    }
541
542    #[test]
543    fn a_revocation_of_an_unseen_device_waits_on_a_bare_row() {
544        let store = store_with_chain();
545        let tag = IdentityTag::from(TAG.to_string());
546        let signed = revocation("a", "x", &["a"]).sign(&key(1));
547        store
548            .put_revocation(&signed, &key(1).verifying_key())
549            .unwrap();
550        assert_eq!(store.apply_revocations(&tag).unwrap(), ["x"]);
551        assert!(store.device_record("x").unwrap().is_none());
552        assert_eq!(store.revocations(&tag).unwrap(), vec![signed]);
553
554        let x = key(5);
555        store
556            .insert_first_device_record(
557                &row("x", &x).sign("a", &key(1)),
558                "a",
559                &key(1).verifying_key(),
560            )
561            .unwrap();
562        assert!(store.device_record("x").unwrap().unwrap().revoked);
563    }
564
565    #[test]
566    fn revoked_by_rule_previews_an_extra_revocation_without_storing_it() {
567        let store = store_with_chain();
568        let tag = IdentityTag::from(TAG.to_string());
569        let extra = revocation("a", "b", &["a"]);
570        assert_eq!(
571            ids(&store.revoked_by_rule(&tag, Some(&extra)).unwrap()),
572            ["b", "c"]
573        );
574        assert!(store.revoked_by_rule(&tag, None).unwrap().is_empty());
575        assert!(revoked(&store).is_empty());
576    }
577
578    #[test]
579    fn a_frame_floor_only_rises_and_belongs_to_one_identity() {
580        let store = SqliteStore::in_memory("a".to_string()).unwrap();
581        let tag = IdentityTag::from(TAG.to_string());
582        let other = IdentityTag::from("f-other".to_string());
583        assert_eq!(store.frame_floor(&tag, "b").unwrap(), None);
584        assert!(store.raise_frame_floor(&tag, "b", 3).unwrap());
585        assert!(!store.raise_frame_floor(&tag, "b", 2).unwrap());
586        assert!(!store.raise_frame_floor(&tag, "b", 3).unwrap());
587        assert_eq!(store.frame_floor(&tag, "b").unwrap(), Some(3));
588        assert_eq!(store.frame_floor(&tag, "c").unwrap(), None);
589        assert_eq!(store.frame_floor(&other, "b").unwrap(), None);
590    }
591
592    #[test]
593    fn revoked_devices_lose_their_log_floor_acks_and_pins() {
594        let store = store_with_chain();
595        let tag = IdentityTag::from(TAG.to_string());
596        for peer in ["b", "c"] {
597            store.record_peer_ack(peer, 5, 1).unwrap();
598            store.pin_peer(peer, 5).unwrap();
599        }
600        store
601            .put_revocation(
602                &revocation("a", "c", &["a"]).sign(&key(1)),
603                &key(1).verifying_key(),
604            )
605            .unwrap();
606        store.apply_revocations(&tag).unwrap();
607        let peers = |table: &str| -> Vec<String> {
608            let conn = store.reader();
609            let mut stmt = conn
610                .prepare(&format!("SELECT peer_id FROM {table} ORDER BY peer_id"))
611                .unwrap();
612            stmt.query_map([], |r| r.get(0))
613                .unwrap()
614                .map(Result::unwrap)
615                .collect()
616        };
617        assert_eq!(peers("peer_acks"), ["b"]);
618        assert_eq!(peers("peer_pins"), ["b"]);
619    }
620
621    #[test]
622    fn revokers_of_names_whose_rules_reach_a_device() {
623        let store = store_with_chain();
624        let tag = IdentityTag::from(TAG.to_string());
625        store
626            .put_revocation(
627                &revocation("a", "b", &["a"]).sign(&key(1)),
628                &key(1).verifying_key(),
629            )
630            .unwrap();
631        assert_eq!(ids(&store.revokers_of(&tag, "c").unwrap()), ["a"]);
632        assert!(store.revokers_of(&tag, "a").unwrap().is_empty());
633    }
634
635    #[test]
636    fn an_epoch_cause_round_trips_and_a_missing_one_is_empty() {
637        let cause = EpochCause {
638            revocations: ["r1".to_string(), "r2".to_string()].into(),
639            retirements: Default::default(),
640        };
641        let text = cause.to_json().unwrap();
642        assert_eq!(text, r#"{"revocations":["r1","r2"]}"#);
643        assert_eq!(EpochCause::from_stored(Some(&text)).unwrap(), cause);
644        let retired = EpochCause {
645            retirements: ["0123456789abcdef".to_string()].into(),
646            ..Default::default()
647        };
648        assert!(!retired.is_empty());
649        let text = retired.to_json().unwrap();
650        assert_eq!(EpochCause::from_stored(Some(&text)).unwrap(), retired);
651        assert!(EpochCause::from_stored(None).unwrap().is_empty());
652        assert!(EpochCause::from_stored(Some("{")).is_err());
653    }
654}