| Abstract | The standard Byzantine attack model assumes no more than some fixedfraction 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.
|
