Fighting Spam with the NeighborhoodWatch DHT

TitleFighting Spam with the NeighborhoodWatch DHT
Publication TypeConference Papers
Year of Publication2009
AuthorsBender A, Sherwood R, Monner D, Goergen N, Spring N, Bhattacharjee B
Conference NameIEEE INFOCOM 2009
Date Published2009/04/19/25
ISBN Number978-1-4244-3512-8
KeywordsCommunications Society, computer crime, cryptography, Databases, IP addresses, IP networks, on-line trusted authority, Peer to peer computing, peer-to-peer computing, peer-to-peer distributed hash table, Postal services, Relays, Resilience, Routing, Security, table size routing, Unsolicited electronic mail

In this paper, we present DHTBL, an anti-spam blacklist built upon a novel secure distributed hash table (DHT). We show how DHTBL can be used to replace existing DNS-based blacklists (DNSBLs) of IP addresses of mail relays that forward spam. Implementing a blacklist on a DHT improves resilience to DoS attacks and secures message delivery, when compared to DNSBLs. However, due to the sensitive nature of the blacklist, storing the data in a peer-to-peer DHT would invite attackers to infiltrate the system. Typical DHTs can withstand fail-stop failures, but malicious nodes may provide incorrect routing information, refuse to return published items, or simply ignore certain queries. The neighborhoodwatch DHT is resilient to malicious nodes and maintains the O(logiV) bounds on routing table size and expected lookup time. NeighborhoodWatch depends on two assumptions in order to make these guarantees: (1) the existence of an on-line trusted authority that periodically contacts and issues signed certificates to each node, and (2) for every sequence of k + 1 consecutive nodes in the ID space, at least one is alive and non-malicious. We show how NeighborhoodWatch maintains many of its security properties even when the second assumption is violated. Honest nodes in NeighborhoodWatch can detect malicious behavior and expel the responsible nodes from the DHT.