Distributed hash table routing security

Distributed hash tables (DHTs) have been investigated as a revolutionary platform for building large-scale distributed systems, ranging from commercial applications to academic projects. Many of the applications have direct financial or security implications. As they continue to become more popular, they will be targeted by adversaries who can control a significant fraction of nodes in the system. Therefore, the security of DHTs is fundamental requirement to realize the value of DHT based applications. The security of DHT routing protocols is a key component of the security of DHT based applications and is the focus of this dissertation.;There is not a one-fit-all solution to provide security to the rich spectrum of applications. Hence we divide the applications into two categories: the managed applications and unmanaged applications. The Myrmic project aims to provide a secure and practical routing protocol to managed applications, while the Kad network related projects are the first step we take to design secure routing protocol for unmanaged applications.;Myrmic is a novel DHT routing protocol designed to be secure against a large percentage of malicious nodes. A key feature distinguishing Myrmic from other DHT implementations is a root verification protocol that allows anyone to verify that the node responding to a query for key k is indeed the correct holder of the key. We report the analytical and experimental results that indicate that Myrmic provides strong robustness and efficiency guarantees, even under attack, while incurring minimal network and CPU overhead.;The Kad network, an implementation of the Kademlia DHT protocol, supports the popular eDonkey peer-to-peer file sharing network. We describe several attacks that exploit critical design and implementation weaknesses in Kad to allow an attacker with modest resources to cause a significant fraction of all keyword searches to fail. We measure the cost and effectiveness of these attacks against a set of several thousand nodes connected to the operational Kad network. These measurements show that our attacks are much more cost effective than previously known attacks. The lessons we learned will help designers to secure their DHT based applications.