IEEE TRANSACTIONS ON RELIABILITY, VOL. 53, NO. 1, MARCH 2004 103A Quantitative Analysis of AnonymousCommunicationsYong Guan, Xinwen Fu, Riccardo Bettati, and Wei ZhaoAbstract—This paper quantitatively analyzes anonymous com-munication systems (ACS) with regard to anonymity properties.Various ACS have been designed & implemented. However, thereare few formal & quantitative analyzes on how these systems per-form. System developers argue the security goals which their sys-tems can achieve. Such results are vague & not persuasive. Thispaper uses a probabilistic method to investigate the anonymity be-havior of ACS.In particular, this paper studies the probability that the trueidentity of a sender can be discovered in an ACS, given that somenodes have been compromised. It is through this analysis thatdesign guidelines can be identified for systems aimed at providingcommunication anonymity. For example, contrary to what onewould intuitively expect, these analytic results show that the proba-bility that the true identity of a sender can be discovered might notalways decrease as the length of communication path increases.Index Terms—Anonymous communication, network security,rerouting, sender/receiver anonymity.I. ACRONYMS &NAMES1ACS anonymous communication systemAnonymizer a web proxy to achieve web-browsing anonymityAnonymous Remailer anonymous e-mail serviceDARPA USA Defense Advanced ResearchProjects AgencyDC-net an approach to achieve anonymityL1 strategy of selecting paths withfixed lengthL2 strategy of selecting paths with vari-able length of geometric distribu-tionL3 strategy of selecting paths with vari-able length of uniform distributionLPWA Lucent Personalized Web AssistantMix an approach to achieve anonymityPipeNet an anonymous protocolT1 strategy of selecting paths withoutcyclesManuscript received July 19, 2002. This work was supported in part byNSF under Contract Number EIA-0081761, DARPA under Contract NumberF30602-99-1-0531, and Texas Higher Education Coordinating Board under itsAdvanced Technology Program. Responsible Editor: N. Ye.Y. Guan is with the Department of Electrical and Computer Engineering, IowaState University, Ames, IA 50011 USA (e-mail: [email protected]).X. Fu, R. Bettati and W. Zhao are with the Department of Computer Science,Texas A&M University, College Station, TX 77843-3112, USA (e-mail: [email protected]; [email protected]; [email protected]).Digital Object Identifier 10.1109/TR.2004.8248261The singular & plural of an acronym are always spelled the same.T3 strategy of selecting paths with dis-joint cyclesT3 strategy of selecting paths with ar-bitrary nonreflective cyclesNOTATIONnumber of nodes in the system: set of nodes in thesystemnumber of compromised nodes, forpath lengthguessed by the adversarynumber of compromised nodes onthe rerouting path,true sender of the messagereceiver of the messageimmediate predecessor of the re-ceiverset of nodes which are definitely notthe true senderset of nodes which are likely to bethe true senderset of compromised nodes on thererouting pathset of compromised nodes whichare not on the rerouting pathinformation reported from the com-promised node,time instant when the message tra-versesimmediate predecessor ofimmediate successor ofall possible event, , that the adver-sary may observeforwarding probabilitycompletely identified path-frag-mentsthe true sender can be identi-fied for instancethat there arecompromised nodes on the pathwith lengththe fact that the adversary col-lected, including path segmentsand the order thereof0018-9529/04$20.00 © 2004 IEEE104 IEEE TRANSACTIONS ON RELIABILITY, VOL. 53, NO. 1, MARCH 2004II. INTRODUCTIONTHIS paper quantitatively analyzes ACS with regard toanonymity properties. With the rapid growth and publicacceptance of the Internet as a means of communication and in-formation dissemination, concerns about privacy & security onthe Internet have grown. Anonymity becomes a basic require-ment for many on-line Internet applications, such as E-Voting,E-Banking, E-Commerce, and E-Auctions. Anonymity protectsthe identity of a participant in a networked application. ManyACS have been developed, which protect the identity of theparticipants in various forms; sender anonymity protects theidentity of the sender, while receiver anonymity does this forthe receiver. Mutual anonymity guarantees that both parties of acommunication remain anonymous to each other. Finally, somesystems provide unlinkability-of-sender-and-receiver. In suchsystems, no one can infer the communication relation betweenthe sender & receiver, except the sender & receiver themselves.Among these various forms of anonymity, sender anonymityis most demanded in the current Internet applications. InE-Voting, for example, a cast vote should not be traceableback to the voter. Similarly, payments using E-Cash should benontraceable. Finally, users may generally not want to disclosetheir identities when visiting web sites. Thus, this paper focusesprimarily on sender anonymity.Sender anonymity is most commonly achieved by transmit-ting the message to its destination through one or more interme-diate nodes, to hide the true identity of the sender. The messageis effectively rerouted along what is called the rerouting path.This paper studies rerouting-based anonymous communicationsystems in terms of their ability to provide sender anonymity.The selection of rerouting paths is critical for this kind of ACS.The 2 key issues in path selection are:1) how to choose the path length, and2) how to choose the path topology.This paper studies how different ‘path selection strategies’ affectthe ability to provide sender anonymity. For a given anonymouscommunication system, this ability is measured as the proba-bility that the true identity of a sender can be discovered.This investigation assumes a passive adversary model. An ad-versary can compromise one or more nodes in the system. Anadversary agent at such a compromised node can gather infor-mation about messages that traverse the node. If the compro-mised node is involved in the message rerouting, it might beable to discover and report the immediate predecessor and suc-cessor node for each message traversing the compromised node.The adversary is assumed to collect all the information from thecompromised nodes, and to attempt to derive the identity of thesender of a message.The following sections describe several insightful resultsbased on a quantitative analysis of ACS.• Contrary to
View Full Document
Unlocking...