diff options
Diffstat (limited to 'src/federation/attacks.rs')
| -rw-r--r-- | src/federation/attacks.rs | 1182 |
1 files changed, 1182 insertions, 0 deletions
diff --git a/src/federation/attacks.rs b/src/federation/attacks.rs new file mode 100644 index 0000000..80c9f9c --- /dev/null +++ b/src/federation/attacks.rs @@ -0,0 +1,1182 @@ +//! The attacks of `docs/federation.md` marked unit, each a test named by its row +//! (`docs/federation-tests.md`), on the federation's fold and the store in memory. A test +//! checks that every such row has its test, or waits for a later stage. + +use std::collections::{BTreeMap, BTreeSet}; + +use super::event::Checkpoint; +use super::fold::Federation; +use super::harness::{self, Party, Spec}; +use super::jcs::Json; +use super::store::memory::{Offered, Refusal, Store}; +use super::store::{Fold, Id}; +use super::version::Version; + +/// Rows marked unit whose tests wait for a later stage: what a node, a party's client or +/// a tool does (stage 3), and what a node tells of a fork (stage 4). +const LATER: &[u32] = &[35, 36, 39, 45, 51, 58, 63, 65, 68]; + +fn tv() -> Party { + Party::new("tv", 1) +} + +fn lass() -> Party { + Party::new("lass", 2) +} + +fn makefu() -> Party { + Party::new("makefu", 3) +} + +/// A federation's store, from the first version it started with. +struct Fed { + store: Store<Federation>, + first: Spec, +} + +fn root_of(spec: &Spec) -> Vec<u8> { + Checkpoint { + at: Vec::new(), + keeps: Vec::new(), + version: Version::read(&spec.json()).expect("a version"), + } + .bytes() +} + +fn fed(parties: &[&Party], rules: &[(&str, Json)]) -> Fed { + let first = Spec::first(parties, rules); + Fed { + store: Store::new(root_of(&first), Vec::new()).expect("a root"), + first, + } +} + +/// tv, lass and makefu, each with a namespace. +fn three() -> Fed { + fed(&[&tv(), &lass(), &makefu()], &[]) +} + +impl Fed { + fn root(&self) -> Id { + self.store.id() + } + + fn take(&mut self, bytes: Vec<u8>) -> Id { + match self.store.offer(bytes) { + Offered::Taken(ids) => ids[0], + other => panic!("not taken: {other:?}"), + } + } + + fn refused(&mut self, bytes: Vec<u8>) -> Refusal { + match self.store.offer(bytes) { + Offered::Refused(why) => why, + other => panic!("not refused: {other:?}"), + } + } + + fn judged(&mut self, bytes: Vec<u8>) { + let why = self.refused(bytes); + assert!(matches!(why, Refusal::Judged(_)), "{why:?}"); + } + + fn value(&self, path: &str) -> Option<Json> { + self.store.state().value(path).cloned() + } + + /// `proposer` proposes `next` on `deps`, `voters` back it on `on`, and a version event + /// writes it: the IDs of the proposal and of the version event. + fn pass( + &mut self, + deps: &[Id], + proposer: &Party, + next: &Spec, + on: Id, + voters: &[&Party], + ) -> (Id, Id) { + let proposal = self.take(proposer.propose(deps, &next.json())); + let votes: Vec<Id> = voters + .iter() + .map(|voter| self.take(voter.vote(&[proposal], on, next.hash(), true))) + .collect(); + let written = self.take(harness::version_event(&votes, next.hash())); + (proposal, written) + } +} + +fn s(text: &str) -> Json { + harness::str(text) +} + +#[test] +fn every_row_marked_unit_has_its_test() { + let doc = include_str!("../../docs/federation.md"); + let source = include_str!("attacks.rs"); + let rows: BTreeMap<u32, String> = doc + .lines() + .filter_map(|line| { + let cells: Vec<&str> = line.split('|').map(str::trim).collect(); + let n = cells.get(1)?.parse().ok()?; + Some((n, cells.get(4)?.to_string())) + }) + .collect(); + let tested: BTreeSet<u32> = source + .lines() + .filter_map(|line| { + line.trim() + .strip_prefix("fn federation_attack_")? + .split('(') + .next()? + .parse() + .ok() + }) + .collect(); + let missing: Vec<&u32> = rows + .iter() + .filter(|(n, kind)| kind.starts_with("unit") && !tested.contains(n) && !LATER.contains(n)) + .map(|(n, _)| n) + .collect(); + assert!(missing.is_empty(), "rows without their test: {missing:?}"); + for n in &tested { + assert!(rows.contains_key(n), "a test of row {n}, which isn't there"); + } + for n in LATER { + assert!(!tested.contains(n), "row {n} has its test now"); + assert!(rows[n].starts_with("unit"), "row {n} isn't marked unit"); + } +} + +#[test] +fn federation_attack_1() { + let mut fed = three(); + let root = fed.root(); + let thief = Party::new("tv", 4); + fed.judged(thief.write(&[root], "home/tv/a", s("1"))); + // A write no party signs is none. + let unsigned = harness::object(vec![ + ("deps", harness::ids(&[root])), + ( + "write", + harness::object(vec![("path", s("home/tv/a")), ("value", s("1"))]), + ), + ]); + assert_eq!(fed.refused(unsigned.bytes()), Refusal::None); +} + +#[test] +fn federation_attack_2() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let event = String::from_utf8(tv.write(&[root], "home/tv/a", s("1"))).expect("UTF-8"); + assert_eq!( + fed.refused(event.replacen("{", "{ ", 1).into_bytes()), + Refusal::None + ); + let large = "x".repeat(super::event::LARGEST); + assert_eq!( + fed.refused(tv.write(&[root], "home/tv/a", s(&large))), + Refusal::None + ); + let more = tv.sign( + &[root], + ( + "keys", + Json::Array((1..=17).map(|seed| s(&harness::key_line(seed))).collect()), + ), + ); + assert_eq!(fed.refused(more), Refusal::None); +} + +#[test] +fn federation_attack_3() { + let mut fed = three(); + let other = fed_with_rule("names/x"); + let tv = tv(); + let elsewhere = tv.write(&[other.root()], "home/tv/a", s("1")); + assert_eq!(fed.store.offer(elsewhere), Offered::Waiting); + let root = fed.root(); + let here = fed.take(tv.write(&[root], "home/tv/a", s("1"))); + let mut fork = fed.first.after(fed.first.hash()); + fork.parties[0].nodes_since = 1; + let (fork_root, kept) = fed + .store + .fork(&[here], &fork.json().bytes()) + .expect("a fork"); + let forked: Store<Federation> = Store::new(fork_root, kept).expect("its root"); + let after = tv.write(&[forked.id()], "home/tv/b", s("2")); + assert_eq!(fed.store.offer(after), Offered::Waiting); +} + +fn fed_with_rule(path: &str) -> Fed { + fed(&[&tv(), &lass(), &makefu()], &[(path, s("tv"))]) +} + +#[test] +fn federation_attack_4() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let old = tv.write(&[root], "home/tv/a", s("1")); + let first = fed.take(old.clone()); + fed.take(tv.write(&[first], "home/tv/a", s("2"))); + assert_eq!(fed.store.offer(old), Offered::Held); + assert_eq!(fed.value("home/tv/a"), Some(s("2"))); +} + +#[test] +fn federation_attack_5() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = fed(&[&tv, &lass, &makefu], &[("names/r/x", s("tv"))]); + let root = fed.root(); + let mut next = fed.first.after(fed.first.hash()); + next.rules[1].1 = s("lass"); + let on = fed.first.hash(); + let (_, written) = fed.pass(&[root], &lass, &next, on, &[&lass, &makefu]); + // Written where tv held the place: taken there, and counts no more. + fed.take(tv.write(&[root], "names/r/x", s("tv's"))); + assert_eq!(fed.value("names/r/x"), None); + fed.take(lass.write(&[written], "names/r/x", s("lass's"))); + assert_eq!(fed.value("names/r/x"), Some(s("lass's"))); +} + +#[test] +fn federation_attack_6() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let other = Party::new("tv", 9); + fed.judged(other.keys(&[root], &[other.key_line()])); + // A version names tv's keys anew; tv's old key signs a set at a history from before. + let mut next = fed.first.after(fed.first.hash()); + next.parties[0].keys = vec![other.key_line()]; + next.parties[0].keys_since = 1; + let on = fed.first.hash(); + fed.pass(&[root], &lass, &next, on, &[&lass, &makefu]); + fed.take(tv.keys(&[root], &[tv.key_line(), harness::key_line(10)])); + let state = fed.store.state(); + assert_eq!(state.keys_of("tv", state.current()), vec![other.key_line()]); +} + +#[test] +fn federation_attack_7() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + fed.take(tv.keys(&[root], &[harness::key_line(9)])); + let state = fed.store.state(); + assert_eq!( + state.keys_of("tv", state.current()), + vec![harness::key_line(9)] + ); +} + +#[test] +fn federation_attack_8() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = fed_with_rule("names/x"); + let root = fed.root(); + let on = fed.first.hash(); + let mut next = fed.first.after(on); + next.rules.push(("names/y".to_owned(), s("lass"))); + let proposal = fed.take(tv.propose(&[root], &next.json())); + fed.judged(harness::version_event(&[proposal], next.hash())); + // A proposal on version 0, after version 1 was written: not on the current version. + let mut other = fed.first.after(on); + other.rules.push(("names/z".to_owned(), s("lass"))); + let (_, written) = fed.pass(&[root], &lass, &other, on, &[&lass, &makefu]); + let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + let also = fed.take(makefu.vote(&[proposal], on, next.hash(), true)); + // Valid at its history; a node that took version 1 refuses it as its own. + assert_eq!( + fed.refused(harness::version_event(&[yes, also], next.hash())), + Refusal::Own + ); + // And at a history holding version 1, it is no version event. + fed.judged(harness::version_event(&[yes, also, written], next.hash())); +} + +#[test] +fn federation_attack_9() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + for rule in ["_continuum/x", "*/x", "names/**/x", "names/{party}/{party}"] { + let mut next = fed.first.after(on); + next.rules.push((rule.to_owned(), s("{party}"))); + let proposal = fed.take(tv.propose(&[root], &next.json())); + let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + let also = fed.take(lass.vote(&[proposal], on, next.hash(), true)); + fed.judged(harness::version_event(&[yes, also], next.hash())); + // Free the backers for the next one: nays make it dead. + let no = fed.take(makefu().vote(&[proposal], on, next.hash(), false)); + fed.take(tv.vote(&[no], on, next.hash(), false)); + } +} + +#[test] +fn federation_attack_10() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let text = String::from_utf8(next.json().bytes()) + .expect("UTF-8") + .replace(r#""federation":1"#, r#""federation":2"#); + let unknown = super::jcs::read(text.as_bytes()).expect("JCS"); + let proposal = fed.take(tv.propose(&[root], &unknown)); + let hash = Id::of(&unknown.bytes()); + let yes = fed.take(tv.vote(&[proposal], on, hash, true)); + let also = fed.take(lass.vote(&[proposal], on, hash, true)); + fed.judged(harness::version_event(&[yes, also], hash)); +} + +#[test] +fn federation_attack_11() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let one = fed.first.after(on); + let mut two = fed.first.after(on); + two.rules.push(("names/x".to_owned(), s("tv"))); + let p1 = fed.take(tv.propose(&[root], &one.json())); + let p2 = fed.take(lass.propose(&[root], &two.json())); + let yes = fed.take(tv.vote(&[p1, p2], on, one.hash(), true)); + fed.judged(tv.vote(&[yes], on, two.hash(), true)); +} + +/// Two proposals on version 0, each backed by tv and one other, neither tv's `true` +/// seeing the other: two version events changing version 0. +fn twice() -> (Fed, Vec<Vec<u8>>, Vec<Vec<u8>>) { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let one = fed.first.after(on); + let mut two = fed.first.after(on); + two.rules.push(("names/x".to_owned(), s("tv"))); + let p1 = tv.propose(&[root], &one.json()); + let p2 = lass.propose(&[root], &two.json()); + let (i1, i2) = (Id::of(&p1), Id::of(&p2)); + let votes = vec![ + tv.vote(&[i1], on, one.hash(), true), + lass.vote(&[i1], on, one.hash(), true), + tv.vote(&[i2], on, two.hash(), true), + makefu.vote(&[i2], on, two.hash(), true), + ]; + let v1 = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], one.hash()); + let v2 = harness::version_event(&[Id::of(&votes[2]), Id::of(&votes[3])], two.hash()); + let mut before = vec![p1, p2]; + before.extend(votes); + (fed, before, vec![v1, v2]) +} + +#[test] +fn federation_attack_12() { + let (fed, before, versions) = twice(); + let first = fed.first.clone(); + for flip in [false, true] { + for backwards in [false, true] { + let mut store: Store<Federation> = + Store::new(root_of(&first), Vec::new()).expect("a root"); + let mut order: Vec<Vec<u8>> = before.clone(); + let mut written = versions.clone(); + if flip { + written.reverse(); + } + order.extend(written.clone()); + if backwards { + order.reverse(); + } + for bytes in order { + store.offer(bytes); + } + let ids: Vec<Id> = written.iter().map(|bytes| Id::of(bytes)).collect(); + let took: Vec<&Id> = ids.iter().filter(|id| store.taken().contains(id)).collect(); + assert_eq!(took.len(), 1, "flip {flip}, backwards {backwards}"); + let other = ids + .iter() + .find(|id| !store.taken().contains(id)) + .expect("one"); + assert_eq!(store.refusal(other), Some(&Refusal::Own)); + } + } +} + +#[test] +fn federation_attack_13() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let proposal = tv.propose(&[root], &next.json()); + let p = Id::of(&proposal); + let votes = [ + tv.vote(&[p], on, next.hash(), true), + tv.vote(&[p], on, next.hash(), false), + lass.vote(&[p], on, next.hash(), true), + makefu.vote(&[p], on, next.hash(), false), + ]; + let ids: Vec<Id> = votes.iter().map(|vote| Id::of(vote)).collect(); + // A node that saw only tv's `true` and lass's writes the version; one holding every + // vote counts tv for both, and the proposal is passed there too. + let seen_one = harness::version_event(&[ids[0], ids[2]], next.hash()); + let seen_all = harness::version_event(&ids, next.hash()); + let mut orders: Vec<Vec<usize>> = Vec::new(); + permutations(&mut (0..4).collect(), 0, &mut orders); + for order in orders { + let mut store: Store<Federation> = + Store::new(root_of(&fed.first), Vec::new()).expect("a root"); + store.offer(proposal.clone()); + for i in order { + store.offer(votes[i].clone()); + } + assert!(matches!(store.offer(seen_one.clone()), Offered::Taken(_))); + assert_eq!( + store.offer(seen_all.clone()), + Offered::Taken(vec![Id::of(&seen_all)]) + ); + } +} + +fn permutations(items: &mut Vec<usize>, k: usize, all: &mut Vec<Vec<usize>>) { + if k == items.len() { + all.push(items.clone()); + return; + } + for i in k..items.len() { + items.swap(k, i); + permutations(items, k + 1, all); + items.swap(k, i); + } +} + +#[test] +fn federation_attack_14() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let made = fed.take(tv.propose(&[root], &next.json())); + fed.judged(lass.vote(&[root], on, next.hash(), true)); + fed.take(lass.vote(&[made], on, next.hash(), true)); +} + +#[test] +fn federation_attack_15() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let proposal = fed.take(tv.propose(&[root], &next.json())); + let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + let again = fed.take(tv.vote(&[proposal, yes], on, next.hash(), true)); + fed.judged(harness::version_event(&[yes, again], next.hash())); + let also = fed.take(lass.vote(&[proposal], on, next.hash(), true)); + fed.take(harness::version_event(&[again, also], next.hash())); +} + +#[test] +fn federation_attack_16() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let proposal = fed.take(tv.propose(&[root], &next.json())); + let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + // tv's key set changes after its vote, and lass's beside its vote. + let after = fed.take(tv.keys(&[yes], &[harness::key_line(9)])); + let beside = fed.take(lass.keys(&[proposal], &[harness::key_line(10)])); + let also = fed.take(lass.vote(&[proposal], on, next.hash(), true)); + fed.take(harness::version_event(&[after, beside, also], next.hash())); + assert_eq!(fed.store.state().current().number, 1); +} + +#[test] +fn federation_attack_17() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let one = fed.first.after(on); + let mut two = fed.first.after(on); + two.rules.push(("names/x".to_owned(), s("lass"))); + let p1 = fed.take(tv.propose(&[root], &one.json())); + let p2 = fed.take(lass.propose(&[root], &two.json())); + let a = fed.take(tv.vote(&[p1, p2], on, one.hash(), true)); + let b = fed.take(lass.vote(&[p1, p2], on, two.hash(), true)); + fed.judged(harness::version_event(&[a, b], one.hash())); + fed.judged(harness::version_event(&[a, b], two.hash())); + // Nays make the first dead; its backer is free, and the second passes. + let no = fed.take(makefu.vote(&[a, b], on, one.hash(), false)); + let nay = fed.take(lass.vote(&[no], on, one.hash(), false)); + let yes = fed.take(tv.vote(&[nay], on, two.hash(), true)); + fed.take(harness::version_event(&[yes], two.hash())); +} + +#[test] +fn federation_attack_18() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let proposal = fed.take(tv.propose(&[root], &next.json())); + let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + let no = fed.take(lass.vote(&[proposal], on, next.hash(), false)); + let nay = fed.take(makefu.vote(&[proposal], on, next.hash(), false)); + fed.judged(harness::version_event(&[yes, no, nay], next.hash())); +} + +#[test] +fn federation_attack_19() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let mut next = fed.first.after(on); + next.parties.retain(|party| party.name != "makefu"); + // The version event names no writer: who put it changes nothing. + let (_, written) = fed.pass(&[root], &tv, &next, on, &[&tv, &lass]); + assert_eq!(fed.store.state().current().parties.len(), 2); + fed.judged(makefu.write(&[written], "home/makefu/a", s("1"))); +} + +#[test] +fn federation_attack_20() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + fed.pass(&[root], &tv, &next, on, &[&tv, &makefu]); + // tv's and lass's keys of version 0 pass another proposal on it, at a history from + // before version 1. + let mut other = fed.first.after(on); + other.rules.push(("names/x".to_owned(), s("tv"))); + let proposal = fed.take(lass.propose(&[root], &other.json())); + let a = fed.take(tv.vote(&[proposal], on, other.hash(), true)); + let b = fed.take(lass.vote(&[proposal], on, other.hash(), true)); + assert_eq!( + fed.refused(harness::version_event(&[a, b], other.hash())), + Refusal::Own + ); + assert_eq!(fed.store.state().current().hash, next.hash()); +} + +#[test] +fn federation_attack_21() { + let (mut fed, before, versions) = twice(); + for bytes in before { + fed.store.offer(bytes); + } + fed.take(versions[0].clone()); + assert_eq!(fed.refused(versions[1].clone()), Refusal::Own); +} + +#[test] +fn federation_attack_22() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let thief = Party::new("tv", 9); + let set = fed.take(tv.keys(&[root], &[tv.key_line(), thief.key_line()])); + fed.take(thief.write(&[set], "home/tv/a", s("stolen"))); + assert_eq!(fed.value("home/tv/a"), Some(s("stolen"))); + fed.take(tv.keys(&[set], &[tv.key_line()])); + assert_eq!(fed.value("home/tv/a"), None); +} + +#[test] +fn federation_attack_23() { + let (lass, makefu) = (lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + // tv's key, stolen, writes tv's set: it counts while version 0 is current. + let thief = Party::new("tv", 1); + let stolen = Party::new("tv", 9); + fed.take(thief.keys(&[root], &[stolen.key_line()])); + let state = fed.store.state(); + assert_eq!( + state.keys_of("tv", state.current()), + vec![stolen.key_line()] + ); + let mut next = fed.first.after(on); + next.parties[0].keys = vec![harness::key_line(10)]; + next.parties[0].keys_since = 1; + fed.pass(&[root], &lass, &next, on, &[&lass, &makefu]); + let state = fed.store.state(); + assert_eq!( + state.keys_of("tv", state.current()), + vec![harness::key_line(10)] + ); +} + +#[test] +fn federation_attack_24() { + let (tv, lass) = (tv(), lass()); + let mut fed = fed(&[&tv, &lass, &makefu()], &[("names/r/wiki", s("lass"))]); + let root = fed.root(); + fed.judged(tv.write(&[root], "home/lass/a", s("1"))); + fed.judged(tv.write(&[root], "names/r/wiki", s("1"))); + fed.judged(tv.write(&[root], "nowhere/a", s("1"))); + fed.judged(tv.write(&[root], "home/lass/a", Json::Null)); +} + +#[test] +fn federation_attack_25() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let dropped = Party::new("tv", 9); + let both = fed.take(tv.keys(&[root], &[tv.key_line(), dropped.key_line()])); + let good = fed.take(tv.write(&[both], "home/tv/a", s("good"))); + fed.take(tv.keys(&[good], &[tv.key_line()])); + fed.take(dropped.write(&[good], "home/tv/a", s("evil"))); + assert_eq!(fed.value("home/tv/a"), Some(s("good"))); +} + +#[test] +fn federation_attack_26() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let a = fed.take(tv.write(&[root], "home/tv/a", s("a"))); + let b = fed.take(tv.write(&[root], "home/tv/a", s("b"))); + let lower = if a < b { "a" } else { "b" }; + assert_eq!(fed.value("home/tv/a"), Some(s(lower))); + fed.take(tv.write(&[a, b], "home/tv/a", s("chosen"))); + assert_eq!(fed.value("home/tv/a"), Some(s("chosen"))); +} + +#[test] +fn federation_attack_27() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let mut next = fed.first.after(on); + next.parties.retain(|party| party.name != "makefu"); + fed.pass(&[root], &tv, &next, on, &[&tv, &lass]); + fed.take(makefu.write(&[root], "home/makefu/a", s("1"))); + assert_eq!(fed.value("home/makefu/a"), None); +} + +#[test] +fn federation_attack_31() { + let mut fed = three(); + let root = fed.root(); + let (tv, lass) = (tv(), lass()); + let node = harness::node_id(7); + let listed = fed.take(lass.nodes(&[root], std::slice::from_ref(&node))); + fed.take(tv.nodes(&[root], &[harness::node_id(0), node.clone()])); + let members = fed.store.state().members(); + assert!(members.contains(&(node.clone(), "lass".to_owned()))); + // Dropped by its party: listed by another, it is no member as its own party's. + fed.take(lass.nodes(&[listed], &[])); + let members = fed.store.state().members(); + assert!(!members.contains(&(node.clone(), "lass".to_owned()))); + assert!(members.contains(&(node, "tv".to_owned()))); +} + +#[test] +fn federation_attack_32() { + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let here = fed.take(tv.write(&[root], "home/tv/a", s("1"))); + let mut fork = fed.first.after(fed.first.hash()); + fork.parties[0].nodes_since = 1; + let (fork_root, kept) = fed + .store + .fork(&[here], &fork.json().bytes()) + .expect("a fork"); + let mut forked: Store<Federation> = Store::new(fork_root, kept).expect("its root"); + let stayed = fed.take(tv.write(&[here], "home/tv/a", s("2"))); + let brought = fed.store.get(&stayed).expect("held").to_vec(); + assert_eq!(forked.offer(brought), Offered::Refused(Refusal::NotAbove)); + let after = tv.write(&[stayed], "home/tv/b", s("3")); + assert_ne!( + forked.offer(after.clone()), + Offered::Taken(vec![Id::of(&after)]) + ); +} + +#[test] +fn federation_attack_34() { + let mut fed = three(); + let root = fed.root(); + let here = fed.take(tv().write(&[root], "home/tv/a", s("1"))); + let first = fed.first.clone(); + assert!(fed.store.fork(&[here], &first.json().bytes()).is_err()); + let mut skipping = first.after(first.hash()); + skipping.number = 2; + assert!(fed.store.fork(&[here], &skipping.json().bytes()).is_err()); + let mut elsewhere = first.after(Id::of(b"another version")); + elsewhere.parties[0].nodes_since = 1; + assert!(fed.store.fork(&[here], &elsewhere.json().bytes()).is_err()); +} + +#[test] +fn federation_attack_37() { + let mut fed = three(); + let root = fed.root(); + let here = fed.take(tv().write(&[root], "home/tv/a", s("1"))); + let mut fork = fed.first.after(fed.first.hash()); + fork.parties[0].nodes_since = 1; + let spec = fork.json().bytes(); + let one = fed.store.fork(&[here], &spec).expect("a fork"); + let two = fed.store.fork(&[here], &spec).expect("a fork"); + assert_eq!(one, two); + assert!(fed.store.checks_fork(&[here], &spec, &one.0)); + // One first version, one federation. + assert_eq!(root_of(&fed.first), root_of(&fed.first.clone())); + assert_eq!(Id::of(&root_of(&fed.first)), root); +} + +#[test] +fn federation_attack_38() { + let (tv, lass) = (tv(), lass()); + let mut fed = fed(&[&tv, &lass], &[]); + let root = fed.root(); + let here = fed.take(tv.write(&[root], "home/tv/a", s("1"))); + let mut fork = fed.first.after(fed.first.hash()); + fork.parties[1].nodes = vec![harness::node_id(8)]; + fork.parties[1].nodes_since = 1; + let (fork_root, kept) = fed + .store + .fork(&[here], &fork.json().bytes()) + .expect("a fork"); + let forked: Store<Federation> = Store::new(fork_root, kept).expect("its root"); + assert!( + forked + .state() + .members() + .contains(&(harness::node_id(8), "lass".to_owned())) + ); +} + +#[test] +fn federation_attack_40() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let proposal = fed.take(tv.propose(&[root], &next.json())); + let a = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + let b = fed.take(lass.vote(&[proposal], on, next.hash(), true)); + let tv_set = fed.take(tv.keys(&[b], &[harness::key_line(9)])); + let lass_set = fed.take(lass.keys(&[a], &[harness::key_line(10)])); + fed.take(harness::version_event( + &[a, b, tv_set, lass_set], + next.hash(), + )); +} + +#[test] +fn federation_attack_41() { + let (tv, lass) = (tv(), lass()); + let first = Spec::first(&[&tv, &lass], &[]); + let version = Version::read(&first.json()).expect("a version"); + let event = tv.write(&[Id::of(b"x")], "home/tv/a", s("1")); + let keeping = Checkpoint { + at: Vec::new(), + keeps: vec![Id::of(&event)], + version: version.clone(), + }; + assert!(Store::<Federation>::new(keeping.bytes(), vec![event]).is_err()); + let mut later = first.after(first.hash()); + later.parties[0].nodes_since = 1; + let not_first = Checkpoint { + at: Vec::new(), + keeps: Vec::new(), + version: Version::read(&later.json()).expect("a version"), + }; + assert!(Store::<Federation>::new(not_first.bytes(), Vec::new()).is_err()); + // A first version listing no node: a store no node is a member of. + let mut nobody = first.clone(); + nobody.parties[0].nodes.clear(); + let store: Store<Federation> = Store::new(root_of(&nobody), Vec::new()).expect("a root"); + assert!(store.state().members().is_empty()); +} + +#[test] +fn federation_attack_42() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let listed = fed.take(lass.nodes(&[root], &[harness::node_id(5)])); + let mut next = fed.first.after(on); + for (i, party) in next.parties.iter_mut().enumerate() { + party.keys = vec![harness::key_line(20 + i as u8)]; + party.keys_since = 1; + } + fed.pass(&[listed], &tv, &next, on, &[&tv, &makefu]); + assert!( + fed.store + .state() + .members() + .contains(&(harness::node_id(5), "lass".to_owned())) + ); +} + +#[test] +fn federation_attack_43() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let mut next = fed.first.after(on); + next.parties[0].keys_since = 5; + let mut changed = fed.first.after(on); + changed.parties[1].keys = vec![harness::key_line(9)]; + for (i, bad) in [next, changed].into_iter().enumerate() { + let proposal = fed.take(tv.propose(&[root], &bad.json())); + let yes = fed.take(tv.vote(&[proposal], on, bad.hash(), true)); + let also = fed.take(lass.vote(&[proposal], on, bad.hash(), true)); + fed.judged(harness::version_event(&[yes, also], bad.hash())); + if i == 0 { + let no = fed.take(makefu().vote(&[proposal], on, bad.hash(), false)); + fed.take(tv.vote(&[no], on, bad.hash(), false)); + } + } +} + +#[test] +fn federation_attack_44() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let one = fed.first.after(on); + let proposal = fed.take(tv.propose(&[root], &one.json())); + let a = fed.take(tv.vote(&[proposal], on, one.hash(), true)); + let b = fed.take(lass.vote(&[proposal], on, one.hash(), true)); + let written = fed.take(harness::version_event(&[a, b], one.hash())); + let two = one.after(one.hash()); + fed.pass(&[written], &lass, &two, one.hash(), &[&lass, &makefu]); + // Version 1 written again, at a history from before version 2: one the node took. + let c = fed.take(makefu.vote(&[proposal], on, one.hash(), true)); + fed.take(harness::version_event(&[a, c], one.hash())); + assert_eq!(fed.store.state().current().number, 2); +} + +#[test] +fn federation_attack_46() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let next = fed.first.after(on); + let proposal = fed.take(tv.propose(&[root], &next.json())); + let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); + let no = fed.take(tv.vote(&[proposal], on, next.hash(), false)); + let also = fed.take(lass.vote(&[proposal], on, next.hash(), true)); + let nay = fed.take(makefu.vote(&[proposal], on, next.hash(), false)); + // Passed and dead, both: a history holding more votes takes back neither. + fed.take(harness::version_event(&[yes, no, also, nay], next.hash())); +} + +#[test] +fn federation_attack_47() { + let (tv, lass) = (tv(), lass()); + let mut fed = fed( + &[&tv, &lass], + &[("names/r/{party}", s("{party}")), ("names/**", s("lass"))], + ); + let root = fed.root(); + fed.take(tv.write(&[root], "names/r/tv", s("1"))); + fed.judged(tv.write(&[root], "names/r/foo", s("1"))); + fed.take(lass.write(&[root], "names/r/foo", s("1"))); +} + +#[test] +fn federation_attack_48() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let mut bad = fed.first.after(on); + bad.rules.push(("_continuum/x".to_owned(), s("tv"))); + let proposal = fed.take(tv.propose(&[root], &bad.json())); + let yes = fed.take(tv.vote(&[proposal], on, bad.hash(), true)); + let also = fed.take(lass.vote(&[proposal], on, bad.hash(), true)); + fed.judged(harness::version_event(&[yes, also], bad.hash())); + // It can't die either: its backers are bound. + let next = fed.first.after(on); + let other = fed.take(makefu().propose(&[root], &next.json())); + fed.judged(tv.vote(&[yes, other], on, next.hash(), true)); +} + +#[test] +fn federation_attack_50() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let one = fed.first.after(on); + let mut two = fed.first.after(on); + two.rules.push(("names/x".to_owned(), s("tv"))); + let p1 = fed.take(tv.propose(&[root], &one.json())); + let p2 = fed.take(lass.propose(&[root], &two.json())); + let first = fed.take(tv.vote(&[p1, p2], on, one.hash(), true)); + let no = fed.take(lass.vote(&[first], on, one.hash(), false)); + let nay = fed.take(makefu.vote(&[no], on, one.hash(), false)); + // tv backs the second once the first is dead. + fed.take(tv.vote(&[nay], on, two.hash(), true)); +} + +#[test] +fn federation_attack_52() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let old = fed.take(makefu.nodes(&[root], &[harness::node_id(6)])); + let mut out = fed.first.after(on); + out.parties.retain(|party| party.name != "makefu"); + let (_, written) = fed.pass(&[old], &tv, &out, on, &[&tv, &lass]); + let mut back = fed.first.clone(); + back.number = 2; + back.changes = Some(out.hash()); + back.parties[2].keys_since = 2; + back.parties[2].nodes_since = 2; + fed.pass(&[written], &tv, &back, out.hash(), &[&tv, &lass]); + let members = fed.store.state().members(); + assert!(!members.contains(&(harness::node_id(6), "makefu".to_owned()))); +} + +#[test] +fn federation_attack_53() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let head = fed.take(tv.write(&[root], "home/tv/a", s("1"))); + let mut next = fed.first.after(on); + next.checkpoint = Some(vec![head]); + // Its proposal beside the heads: no version event is above them. + let proposal = fed.take(tv.propose(&[root], &next.json())); + let yes = fed.take(tv.vote(&[proposal, head], on, next.hash(), true)); + let also = fed.take(lass.vote(&[proposal, head], on, next.hash(), true)); + fed.judged(harness::version_event(&[yes, also], next.hash())); +} + +/// tv, lass and makefu, moved to a checkpoint at a write of lass's built on two of tv's; +/// a write of makefu's beside it: the store, the heads' write, the forgotten write, the +/// one beside, and the version event. +fn moved() -> (Fed, Id, Id, Id, Id) { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let gone = fed.take(tv.write(&[root], "home/tv/a", s("1"))); + let kept = fed.take(tv.write(&[gone], "home/tv/a", s("2"))); + let head = fed.take(lass.write(&[kept], "home/lass/b", s("3"))); + let beside = fed.take(makefu.write(&[root], "home/makefu/c", s("4"))); + let mut next = fed.first.after(on); + next.checkpoint = Some(vec![head]); + let (_, written) = fed.pass(&[head], &tv, &next, on, &[&tv, &lass]); + (fed, head, gone, beside, written) +} + +#[test] +fn federation_attack_54() { + let (mut fed, head, gone, beside, written) = moved(); + let tv = tv(); + assert_eq!(fed.store.refusal(&beside), Some(&Refusal::NotAbove)); + assert_eq!( + fed.refused(tv.write(&[gone], "home/tv/x", s("1"))), + Refusal::NotAbove + ); + assert_eq!( + fed.refused(tv.write(&[beside], "home/tv/y", s("1"))), + Refusal::BuiltOn(beside) + ); + assert_eq!( + fed.refused(tv.write(&[written, gone], "home/tv/z", s("1"))), + Refusal::NotAbove + ); + fed.take(tv.write(&[head], "home/tv/w", s("1"))); +} + +#[test] +fn federation_attack_55() { + let (fed, _, _, _, _) = moved(); + let checkpoint = fed.store.checkpoint().to_vec(); + let kept = fed.store.kept(); + assert!(Store::<Federation>::pinned(fed.root(), checkpoint.clone(), kept.clone()).is_ok()); + // Handed other events than it keeps: not taken. + assert!(Store::<Federation>::pinned(fed.root(), checkpoint, kept[1..].to_vec()).is_err()); +} + +#[test] +fn federation_attack_56() { + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let a = tv.write(&[root], "home/tv/a", s("1")); + let b = lass.write(&[root], "home/lass/b", s("2")); + let (ia, ib) = (Id::of(&a), Id::of(&b)); + let mut one = fed.first.after(on); + one.checkpoint = Some(vec![ia]); + let mut two = fed.first.after(on); + two.checkpoint = Some(vec![ib]); + let p1 = tv.propose(&[ia], &one.json()); + let p2 = lass.propose(&[ib], &two.json()); + let votes = [ + tv.vote(&[Id::of(&p1)], on, one.hash(), true), + lass.vote(&[Id::of(&p1)], on, one.hash(), true), + tv.vote(&[Id::of(&p2)], on, two.hash(), true), + makefu.vote(&[Id::of(&p2)], on, two.hash(), true), + ]; + let v1 = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], one.hash()); + let v2 = harness::version_event(&[Id::of(&votes[2]), Id::of(&votes[3])], two.hash()); + for (first, heads) in [(&v1, ia), (&v2, ib)] { + let mut store: Store<Federation> = + Store::new(root_of(&fed.first), Vec::new()).expect("a root"); + for bytes in [&a, &b, &p1, &p2] { + store.offer(bytes.clone()); + } + for vote in &votes { + store.offer(vote.clone()); + } + assert!(matches!(store.offer(first.clone()), Offered::Taken(_))); + assert_eq!( + Federation::parts(store.checkpoint()).map(|(at, _)| at), + Some(vec![heads]) + ); + let other = if *first == v1 { &v2 } else { &v1 }; + assert!(matches!(store.offer(other.clone()), Offered::Refused(_))); + } +} + +#[test] +fn federation_attack_57() { + let (tv, lass) = (tv(), lass()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let backup = Party::new("tv", 9); + let both = fed.take(tv.keys(&[root], &[tv.key_line(), backup.key_line()])); + let signed = fed.take(backup.write(&[both], "home/tv/a", s("1"))); + let dropped = fed.take(tv.keys(&[signed], &[tv.key_line()])); + assert_eq!(fed.value("home/tv/a"), None); + let mut next = fed.first.after(on); + next.checkpoint = Some(vec![dropped]); + let (_, written) = fed.pass(&[dropped], &tv, &next, on, &[&tv, &lass]); + // The key added back after the checkpoint brings back nothing it signed before. + fed.take(tv.keys(&[written], &[tv.key_line(), backup.key_line()])); + assert_eq!(fed.value("home/tv/a"), None); +} + +#[test] +fn federation_attack_61() { + let (lass, makefu) = (lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + // The key tv's version names, stolen from the node voting for it, votes. + let thief = Party::new("tv", 1); + let next = fed.first.after(on); + let proposal = fed.take(lass.propose(&[root], &next.json())); + let stolen = fed.take(thief.vote(&[proposal], on, next.hash(), true)); + let also = fed.take(makefu.vote(&[proposal], on, next.hash(), true)); + fed.take(harness::version_event(&[stolen, also], next.hash())); +} + +#[test] +fn federation_attack_62() { + use base64::{Engine, engine::general_purpose::STANDARD as BASE64}; + let mut fed = three(); + let root = fed.root(); + let tv = tv(); + let event = tv.write(&[root], "home/tv/a", s("1")); + let json = super::jcs::read(&event).expect("JCS"); + let sig = json + .get("sig") + .and_then(Json::as_str) + .expect("a sig") + .to_owned(); + let with_sig = |sig: String| { + let Json::Object(mut members) = json.without("sig") else { + unreachable!() + }; + members.push(("sig".to_owned(), Json::Str(sig))); + Json::object(members).expect("an object").bytes() + }; + // Its S made larger by the group's order: the same signature, spelled anew. + let mut blob = BASE64.decode(&sig).expect("base64"); + let order: [u8; 32] = [ + 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, + 0x14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10, + ]; + let at = blob.len() - 32; + let mut carry = 0u16; + for (byte, add) in blob[at..].iter_mut().zip(order) { + let sum = u16::from(*byte) + u16::from(add) + carry; + *byte = sum as u8; + carry = sum >> 8; + } + assert_eq!(fed.refused(with_sig(BASE64.encode(&blob))), Refusal::None); + // Its base64 spelled otherwise. + let unpadded = sig.trim_end_matches('=').to_owned(); + if unpadded != sig { + assert_eq!(fed.refused(with_sig(unpadded)), Refusal::None); + } + // Its key spelled with a comment. + let commented = tv.signed_as( + &tv.key, + &format!("{} tv", tv.key_line()), + &[root], + ( + "write", + harness::object(vec![("path", s("home/tv/b")), ("value", s("1"))]), + ), + ); + assert_eq!(fed.refused(commented), Refusal::None); +} + +#[test] +fn federation_attack_64() { + let (mut fed, head, gone, _, written) = moved(); + let (tv, lass) = (tv(), lass()); + let on = fed.store.state().current().hash; + let current = fed.first.after(fed.first.hash()); + let mut base = current.clone(); + base.checkpoint = Some(vec![head]); + let after_first = base.after(on); + // Heads before the current checkpoint. + let mut before = after_first.clone(); + before.checkpoint = Some(vec![gone]); + // Heads above it that don't hold the version naming it. + let beside = fed.take(tv.write(&[head], "home/tv/x", s("1"))); + let mut not_current = after_first.clone(); + not_current.checkpoint = Some(vec![beside]); + // Two heads, one in the other's history. + let later = fed.take(tv.write(&[written], "home/tv/y", s("2"))); + let latest = fed.take(tv.write(&[later], "home/tv/z", s("3"))); + let mut nested = after_first; + nested.checkpoint = Some(vec![later, latest]); + for (i, bad) in [before, not_current, nested].into_iter().enumerate() { + let proposal = fed.take(tv.propose(&[latest, beside], &bad.json())); + let yes = fed.take(tv.vote(&[proposal], on, bad.hash(), true)); + let also = fed.take(lass.vote(&[proposal], on, bad.hash(), true)); + let why = fed.refused(harness::version_event(&[yes, also], bad.hash())); + assert!(matches!(why, Refusal::Judged(_)), "{i}: {why:?}"); + let no = fed.take(makefu().vote(&[proposal], on, bad.hash(), false)); + fed.take(tv.vote(&[no], on, bad.hash(), false)); + fed.take(lass.vote(&[no], on, bad.hash(), false)); + } +} |
