We present STeP-archives, a novel and practical data archival architecture, where an attacker who wants to censor or tamper with a data object must cause obvious collateral damage to a large number of other objects in the system. We use maximum distance separable erasure codes to entangle unrelated data blocks and provide redundancy against storage failures, which results in an archive with constant time read-write operations. We show a tradeoff for the attacker between attack complexity, irrecoverability, and collateral damage. We also show that the problem is asymmetric between attackers and defenders; while a defender can efficiently recover from imperfect attacks, an attacker must solve an NP-hard problem to find a perfect (irrecoverable) attack that minimizes collateral damage to other data objects, or even approximate its size. We then study efficient sample-heuristic attack algorithms that lead to irrecoverable but large damage and demonstrate how some strategies and parameter choices allow to resist these sample attacks. Finally, we provide empirical evidence that an attacker who wants to irrecoverably tamper with a document archived long enough must destroy a constant fraction of the archive.

We present STEP-archives, a model for censorship-resistant storage systems where an attacker cannot censor or tamper with data without causing a large amount of obvious collateral damage. MDS erasure codes are used to entangle unrelated data blocks, in addition to providing redundancy against storage failures. We show a tradeoff for the attacker between attack complexity, irrecoverability, and collateral damage. We also show that the system can efficiently recover from attacks with imperfect irrecoverability, making the problem asymmetric between attackers and defenders. Finally, we present sample heuristic attack algorithms that are efficient and irrecoverable (but not collateral-damage-optimal), and demonstrate how some strategies and parameter choices allow to resist these sample attacks.