| Abstract |
|
In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, 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 al- gorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient rout- ing 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 sig- nificant 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, allow- ing a small number of malicious nodes to cause rapid loss of data on the entire network. We also discuss various proposed countermeasures de- signed 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.
|
 Additional Information
|
Citation:
Nathan S. Evans, Chris GauthierDickey, Christian Grothoff,
"Routing in the Dark: Pitch Black,"
acsac,
pp. 305-314,
Twenty-Third Annual Computer Security Applications Conference (ACSAC 2007),
2007
|
