Design and applications of a secure and decentralized Distributed Hash Table

Distributed Hash Tables (DHTs) are a powerful building block for highly scalable decentralized systems. They route requests over a structured overlay network to the node responsible for a given key. DHTs are subject to the well-known Sybil attack, in which an adversary creates many false identities in order to increase its influence and deny service to honest participants. Defending against this attack is challenging because (1) in an open network, creating many fake identities is cheap; (2) an attacker can subvert periodic routing table maintenance to increase its influence over time; and (3) specific keys can be targeted by clustering attacks. As a result, without centralized admission control, previously existing DHTs could not provide strong availability guarantees. This dissertation describes Whanau, a novel DHT routing protocol which is both efficient and strongly resistant to the Sybil attack. Whanau solves this long-standing problem by using the social connections between users to build routing tables that enable Sybilresistant one-hop lookups. The number of Sybils in the social network does not affect the protocol's performance, but links between honest users and Sybils do. With a social network of n well-connected honest nodes, Whanau provably tolerates up to O(n/ log n) such "attack edges". This means that an attacker must convince a large fraction of the honest users to make a social connection with the adversary's Sybils before any lookups will fail. Whanau uses techniques from structured DHTs to build routing tables that contain O(Vf log n) entries per node. It introduces the idea of layered identifiers to counter clustering attacks, which have proven particularly challenging for previous DHTs to handle. Using the constructed tables, lookups provably take constant time. Simulation results, using large-scale social network graphs from LiveJournal, Flickr, YouTube, and DBLP, confirm the analytic prediction that Whanau provides high availability in the face of powerful Sybil attacks. Experimental results using PlanetLab demonstrate that an implementation of the Whanau protocol can handle reasonable levels of churn.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2011

Author dc:creator

• Lesniewski-Laas, Christopher T. (Christopher Tur), 1980-

Advisor dc:contributor.advisor

• M. Frans Kaashoek.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/64582

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/64582