Fundamental Design Issues in Anonymous Peer-to-peer Distributed Hash Table Protocols

Abstract

Anonymous communication protocols can be used to protect diminishing user privacy online. One family of those protocols is anonymous peer-to-peer (ANP2P) distributed hash table (DHT). These protocols are considered efficient, scalable, decentralized, and practical. However, the anonymity properties of these protocols are not well understood and difficult to quantify. As a result, users may have a false sense of anonymity when using these protocols. This motivates our study of the anonymity properties of ANP2P DHT protocols. In this study, we analyzed the Freenet and GNUnet systems.We cataloged the main design decisions and identified three vulnerabilities in these ANP2P DHT protocols. The first vulnerability was the Traceback attack, which enables an adversary to determine which subset of nodes routed a given message. The second vulnerability was the Routing Table Insertion attack, which can be used by an adversary to place themselves in a victim's routing table. We developed this attack to support the Traceback attack, and we present two potential mitigations - routing randomness and Look Ahead Hint. The third vulnerability was an attack on GNUnet's message bloom filter. Similar to the Traceback attack, the GNUnet bloom filter vulnerability can be used to determine which subset of nodes routed a given message. We then developed an empirical methodology for modeling a generic adversary and evaluating the performance and anonymity of ANP2P DHT design decisions. We created a novel adversarial model that uses protocol behaviors and shared states to sample the entropy in an ANP2P DHT system. The adversarial model implements a routing path Walk-back Ranking Algorithm that can be used to identify potential sender nodes for a given message. The methodology was then applied to an extension of the peer-to-peer network simulator PeerSim. We extended PeerSim to implement various ANP2P DHT design decisions. We then used the extended PeerSim and the methodology to evaluate anonymity and performance for structured, small-world, and random topologies using look ahead values of one-hop and two-hop. These experiments also validated the accuracy of the methodology. Next, we used the output of the methodology to provide a quantitative comparison of the performance and anonymity for the design decisions. The methodology was also able to identify several network sub-graphs that degraded anonymity in small-world topologies. Protocol designers can use our methodology to evaluate anonymity and performance of their protocols, and to identify the existence of network sub-graphs that degrade anonymity. Once these sub-graphs have been identified, protocol designers can create appropriate controls to prevent their formation. Future work includes applying our empirical methodology to the mitigations we proposed for the Routing Table Insertion attack and evaluating the methodology on a real-world protocol.