Information Leaks in Structured Peer-to-Peer AnonymousCommunication SystemsPrateek Mittal Nikita BorisovDepartment of Electrical and ComputerEngineeringUniversity of Illinois at Urbana–Champaign{mittal2,nikita}@illinois.eduABSTRACTWe analyze information leaks in the lookup mechanisms ofstructured peer-to-peer anonymous communication systemsand how these leaks can be used to compromise anonymity.We show that the techniques that are used to combat activeattacks on the lookup mechanism dramatically increase in-formation leaks and increase the efficacy of passive attacks.Thus there is a trade-off between robustness to active andpassive attacks.We study this trade-off in two P2P anonymous systems,Salsa and AP3. In both cases, we find that, by combiningboth passive and active attacks, anonymity can be compro-mised much more effectively than previously thought, ren-dering these systems insecure for most proposed uses. Ourresults hold even if security parameters are changed or otherimprovements to the systems are considered. Our studytherefore motivates the search for new approaches to P2Panonymous communication.Categories and Subject DescriptorsC.2.0 [Computer-Communication Networks]: General—Security and protection; C.2.4 [Computer-CommunicationNetworks]: Distributed SystemsGeneral TermsSecurityKeywordsAnonymity, attacks, information-leaks, peer-to-peer1. INTRODUCTIONAnonymous communication hides the identity of commu-nication partners from third parties, or hides user identityfrom the remote party. The Tor network [16], deployed in2003, now serves hundreds of thousands of users and car-ries terabytes of traffic a day [35]. Originally an experimen-Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’08, October 27–31, 2008, Alexandria, Virginia, USA.Copyright 2008 ACM 978-1-59593-810-7/08/10 ...$5.00.tal network used by privacy enthusiasts, it is now enteringmainstream use; for example, several consulates were foundto be using it to evade observation by their host country [22].The capacity of Tor is already strained, and to supporta growing population a peer-to-peer approach will likely benecessary, as P2P networks allow the network capacity toscale with the number of users. Indeed, several proposalsfor peer-to-peer anonymous communication have been putforward [28, 34, 21, 39]. However, P2P networks presentnew challenges to anonymity, one of which is the ability tolocate relays for anonymous traffic.In Tor, clients use a directory to retrieve a list of all therunning routers. Such a directory will not scale as the num-ber of routers grows, since the traffic to update the directorywould become prohibitively exp ensive. Instead, a peer-to-peer lookup is needed to locate an appropriate relay. Such alookup, however, can be subject to attack: malicious nodescan misdirect it to find relays that are colluding and violatethe anonymity of the entire system. All of the P2P ano-nymous communication designs therefore incorporate somedefense against such attacks; e.g. AP3 [28] uses secure rout-ing techniques developed by Castro et al [7], and Salsa usesredundant routing with bounds checks [34].These defenses, however, come at a cost. They operate byperforming extra checks to detect incorrect results returnedby malicious nodes. These checks cause many messages tobe exchanged between nodes in the network, some of whichmight be observed by attackers. As a result, a relativelysmall fraction of attackers can make observations about alarge fraction of lookups that occur in the P2P network,acting as a near-global passive adversary. As most modernanonymity systems assume that a global passive adversaryis too costly, they are not designed to resist such attacks.Therefore, this small fraction of attackers can successfullyattack anonymity of the system.We examine this problem through a case study of twoP2P anonymous communication systems: Salsa and AP3.In both systems, defenses against active attacks create newopportunities for passive attacks. Salsa makes heavy use ofredundancy to address active attacks, rendering it vulnera-ble to passive information leak attacks. Further, increasingthe levels of redundancy will improve passive attack perfor-mance, and often make the system weaker overall. We findthat even in the best case, Salsa is much less secure than pre-viously considered. Salsa was designed to tolerate up to 20%of compromised nodes; however, our analysis shows that inthis case, over one quarter of all circuits will be compromisedby using information leaks. Similarly, conventional analysisof AP3 suggests that it provides probable innocence whenup to 33% of nodes are compromised, and can tolerate upto 50% of compromised nodes by increasing the path length.However, our analysis puts these numbers at 5% and 10%,respectively.We studied potential improvements to Salsa that can beachieved by increasing the path length or introducing a pub-lic key infrastructure (PKI). We found that these tools offeronly a limited defense against our attacks, and the systemis still not secure for practical purposes. Our results demon-strate that information leaks are an important part of anony-mity analysis of a system and that new advances in the stateof the art of P2P anonymous communication are needed.The rest of the paper is organized as follows. In Section 2we present the state of art in low-latency anonymous com-munication. We discuss information leaks from lookups inSection 3 and show the trade-off between security and ano-nymity. In Sections 4 and 5, we present attacks based oninformation leaks from lookups on AP3 and Salsa. Section6 contains the related work and we conclude in Section 7.2. BACKGROUNDIn this section, we present a brief overview of anonymouscommunication. We motivate the need for decentralized andscalable solutions, and discuss why structured peer-to-peersystems have strong potential. We also describe our adver-sarial threat model.2.1 Low-Latency Anonymous CommunicationSystemsAnonymous communication systems can be classified intolow-latency and high-latency systems. High latency anony-mous communication systems like Mixminion [12] and
View Full Document
Unlocking...