A Secure DHT via the Pigeonhole Principle

dc.contributor.authorBaden, Randy
dc.contributor.authorBender, Adam
dc.contributor.authorLevin, Dave
dc.contributor.authorSherwood, Rob
dc.contributor.authorSpring, Neil
dc.contributor.authorBhattacharjee, Bobby
dc.date.accessioned2007-09-27T17:52:34Z
dc.date.available2007-09-27T17:52:34Z
dc.date.issued2007-09-24
dc.description.abstractThe standard Byzantine attack model assumes no more than some fixed fraction of the participants are faulty. This assumption does not accurately apply to peer-to-peer settings, where Sybil attacks and botnets are realistic threats. We propose an attack model that permits an arbitrary number of malicious nodes under the assumption that each node can be classified based on some of its attributes, such as autonomous system number or operating system, and that the number of classes with malicious nodes is bounded (e.g., an attacker may exploit at most a few operating systems at a time). In this model, we present a secure DHT, evilTwin, which replaces a single, large DHT with sufficiently many smaller instances such that it is impossible for an adversary to corrupt every instance. Our system ensures high availability and low-latency lookups, is easy to implement, does not require a complex Byzantine agreement protocol, and its proof of security is a straightforward application of the pigeonhole principle. The cost of security comes in the form of increased storage and bandwidth overhead; we show how to reduce these costs by replicating data and adaptively querying participants who historically perform well. We use implementation and simulation to show that evilTwin imposes a relatively small additional cost compared to conventional DHTs.en
dc.format.extent273263 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/7136
dc.language.isoen_USen
dc.relation.ispartofseriesUM Computer Science Departmenten
dc.relation.ispartofseriesCS-TR-4884en
dc.titleA Secure DHT via the Pigeonhole Principleen
dc.typeTechnical Reporten

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR.pdf
Size:
266.86 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.81 KB
Format:
Item-specific license agreed upon to submission
Description: