An Optimal Strategy for Anonymous Communication ProtocolsYong Guan, Xinwen Fu, Riccardo Bettati, Wei ZhaoDepartment of Computer ScienceTexas A&M UniversityCollege Station, TX 77843-3112E-mail:fyguan, xinwenfu, bettati, [email protected] many Internet applications, the ability to protect theidentity of participants in a distributed applications is criti-cal. For such applications, a number of anonymous commu-nication systems have been realized over the recent years.The effectiveness of these systems relies greatly on the waymessages are routed among the participants. (We call thisthe route selection strategy.) In this paper, we describe howto select routes so as to maximize the ability of the anony-mous communication systems to protect anonymity. To mea-sure this ability, we define a metric (anonymity degree), andwe design and evaluate an optimal route selection strategythat maximizes the anonymity degree of a system. Our ana-lytical and experimental data shows that the anonymity de-gree may not always monotonically increase as the lengthof communication paths increase. We also found that vari-able path-length strategies perform better than fixed-lengthstrategies.1 IntroductionThis paper addresses issues related to design and imple-mentation of an optimal strategy for anonymous commu-nications. This optimal strategy is based on a quantitativeanalysis of the behavior of the anonymous communicationsystems.With the rapid growth and public acceptance of the Inter-net as a means of communication and information dissemi-nation, concerns about privacy and security on the Internethave grown. Anonymity becomes a essential requirementfor many on-line Internet applications, such as E-Voting, E-Banking, E-Commerce, and E-Auctions. Anonymity pro-tects the identity of a participant in a networked applica-tion. Many anonymous communication systems have beendeveloped, which protect the identity of the participants invarious forms: sender anonymity protects the identity of thesender, while receiver anonymity does this for the receiver.Mutual anonymity guarantees that both parties of a commu-nication remain anonymous to each other.Among these various forms of anonymity, senderanonymity is most critical in many current Internet appli-cations. In E-Voting, for example, a cast vote should not betraceable back to the voter. Similarly, users may generallynot want to disclose their identities when visiting web sites.In this paper, we will therefore focus primarily on senderanonymity.Sender anonymity is most commonly achieved by trans-mitting a message to its destination through one or moreintermediate nodes in order to hide the true identity of thesender. The message thus is effectively rerouted along whatis called a rerouting path. In this paper, we study rerouting-based anonymous communication systems in terms of theirability to protect sender anonymity. The selection of rerout-ing paths is critical for this kind of systems. We study howdifferent path selection strategies affect the ability to protectsender anonymity. For a given anonymous communicationsystem, we measure this ability by determining how muchuncertainty this system can provide to hide the true identityof a sender. We call this measure the anonymity degree.In our investigation, we assume a passive adversarymodel: The adversary can compromise one or more nodesin the system. An adversary agent at such a compromisednode can gather information about messages that traversethe node. If the compromised node is involved in the mes-sage rerouting, it can discover and report the immediate pre-decessor and successor node for each message traversingthe compromised node. We assume that the adversary col-lects all the information from its agents at the compromisednodes and attempts to derive the identity of the sender of amessage.In the following sections, we will elaborate on two ob-servations that we made based on a quantitative analysis ofthe anonymity degree of systems.Common sense indicates that the anonymity degree in-creases with increasing number of intermediate nodesbetween the sender and the receiver. (We call thisnumber of intermediate nodes the path length of thererouting path.) There is a point, however, beyondwhich increasing the path length actually decreases theanonymity degree. We will give a quantitative analysisof how path length affects the anonymity degree.Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS’02) 1063-6927/02 $17.00 © 2002 IEEERerouting schemes give rise to either paths with fixedlength (where messages are forwarded to the receiverafter traversing a fixed number of intermediate nodes)or variable length (where every intermediate node ran-domly decides whether to forward the message to thereceiver directly or to another intermediate node, forexample.). We will show that variable path lengthstrategies perform better than fixed path length strate-gies in term of anonymity degree. However, when theexpected path length is sufficiently large, the differ-ence of anonymity degree is relatively small betweendifferent variable and fixed path length strategies.As a result of this study, we found that several well-known anonymous communication systems are not usingthe best path selection strategies. We therefore believe thatour results are greatly helpful for the current and future de-velopment of anonymous communication systems. We pro-pose an optimal method to select path lengths. We will showthat path selection problem can be cast as an optimizationproblem, whose solution yields an optimal path length dis-tribution that maximizes the anonymity degree.The remainder of this paper is organized as follows. Sec-tion 2 gives an overview of the previous work on anony-mous communication systems. In Section 3, we present thesystem model and discuss the key issues in path selection insuch systems. In Section 4, we describe the threat model.In Section 5, we define a security metric, called anonymitydegree, to evaluate the anonymity behavior of anonymouscommunication systems. In Section 6, we report our nu-merical results. Finally, in Section 7, we present our con-clusions.2 Overview of Anonymous CommunicationSystemsIn this section, we survey the past work related toanonymity, including DC-Net [4, 22], Mixes [3, 10, 11],Anonymizer [1], Anonymous Remailer [2], LPWA [6],Onion Routing [8, 17, 19, 20], Crowds [14], Hordes [15],Freedom [7], and PipeNet [5].Many existing anonymous
View Full Document
Unlocking...