Towards attack tolerant networks: Concurrent multipath routing and the butterfly network.

Abstract

It is crucial for large-scale communication networks such as the internet to be resilient against attacks such as censorship and surveillance, which pose a threat to free expression and free association. Self-organized networks such as the internet's router network typically have heavy-tailed degree distributions, making them highly vulnerable to targeted attacks against central nodes. While cryptographic solutions exist, they fail to address the underlying topological problem, and remain vulnerable to man-in-the-middle attacks and coercion. Coercion-resistant, topological approaches to attack tolerance are needed to address the current vulnerability of communications infrastructure to censorship and surveillance. We present a novel concurrent multipath routing (CMR) algorithm for the wraparound butterfly network topology, as well as a highly attack-tolerant Structured Multipath Fault Tolerance (SMFT) architecture which incorporates the butterfly CMR algorithm. We also identify a previously unexplored relationship between network topology, trust transitivity, and attack-tolerance, and provide a framework for further exploration of this relationship. Our work is the first theoretical demonstration of a point-to-point communication network architecture that can resist coercion and other non-technical attacks, without requiring infinitely transitive trust. To address cases where the network structure cannot be fully controlled, we demonstrate how a snapshot of the internet's router network can be partially rewired for greater attack-tolerance. More broadly, we hope that this work will serve as a starting point for the evelopment of additional topology-based attack-tolerant communication architectures to guard against the dangers of censorship and surveillance.