Nathan Evans
University of Denver
USA

Christian Grothoff
University of Denver
USA

Chris GauthierDickey
University of Denver
USA

In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks (darknets), direct communication between nodes is limited to specific neighbors. Often these networks have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks.

This paper is the first independent security analysis of Clarke and
Sandberg's routing algorithm. We show that a relatively weak
participating adversary can render the overlay ineffective without
being detected, resulting in significant data loss due to the
resulting load imbalance. We have measured the impact of the attack
in a testbed of 800 nodes using minor modifications to Clarke and
Sandberg's implementation of their routing algorithm in Freenet. Our
experiments show that the attack is highly effective, allowing a small
number of malicious nodes to cause rapid loss of data on the entire
network.

We also discuss various proposed countermeasures designed to
detect, thwart or limit the attack. While we were unable to find
effective countermeasures, we hope that the presented analysis will be a first step towards the design of secure distributed routing
algorithms for restricted-route topologies.

Keywords: privacy censorship resistant sharing file peer distributed system network restricted route DHT

Read Paper (in PDF)