Anonymity v.s. Information Leakage in Anonymity Systems∗Ye Zhu Riccardo BettatiDepartment of Computer ScienceTexas A&M UniversityCollege Station TX 77843-3112, [email protected] [email protected] for anonymity in systems must be on one handsimple and concise, and on the other hand reflect the real-ities of real systems. Such systems are heterogeneous, asare the ways they are used, the deployed anonymity mea-sures, and finally the possible attack methods. Implementa-tion quality and topologies of the anonymity measures mustbe considered as well. We therefore propose a new measurefor the anonymity degree, which takes into account possibleheterogeneity. We model the effectiveness of single mixes orof mix networks in terms of information leakage and mea-sure it in terms of covert channel capacity. The relationshipbetween the anonymity degree and information leakage isdescribed, and an example is shown.Keywords: Anonymity, Mix Networks, Covert Channels1 IntroductionThis paper studies the relationship between theanonymity degree and information leakage from ananonymity network.Since Chaum [2] proposed the mix network, researchershave developed various anonymity systems for differentapplications. Examples include Crowds [22] for anony-mous web transaction, Freenet [4] for distributed anony-mous information storage and retrieval, Onion Router [12]for anonymous routing, and Tarzan [11] for p2p network-ing.How to quantify the anonymity provided by a wholeanonymity system? Researchers proposed various defin-itions to quantify anonymity, such as anonymity set size[15], effective anonymity set size [23], and entropy-basedanonymity degree [8]. While the metrics led to an increas-ingly better understanding of anonymity, they tend to fo-cus on the anonymity of a single message under a singleanonymity attack. In practice however, metrics are neededthat take into account realities of today’s use of networks:Communication settings in real systems range from singlemessages, to message groups, to streams and FTP trans-fers. In addition, sophisticated attacks can resort to a variety∗This work is supported in part by the Texas Information Technologyand Telecommunication Task Force.of techniques to break anonymity: flow correlation attacks[27], intersection attacks [7], trickle attacks [24], and so on.A measure for the anonymity degree should satisfy anumber of requirements: First, the anonymity degree shouldcapture the quality of an anonymity system. It has beenshown for example that information theoretical means, suchas entropy, are more accurate for comparing anonymity sys-tems than, say, anonymity sets. Second, the anonymitydegree should take into account the topology of the net-work, or that of any overlay defined by the anonymity sys-tem. The topology influences how much information canbe gathered by an attacker, and thus has an impact on thesystem anonymity degree. For example, a system of fully-connected nodes will have a different anonymity degreefrom a chain of nodes. Third, the anonymity degree, as mea-sure of the effectiveness of the anonymity system should beindependent of the number of users. While a large numberof users clearly contributes to anonymity, this not necessaryreflects on the quality of the anonymity system. Finally,the anonymity measure must be independent of the threatmodel, as attackers may use a variety of attack techniques,or combinations thereof, to break the anonymity.Since the goal of anonymity attacks is to infer the com-munication relations in a system despite countermeasures,it is natural to model such attacks as covert channels, andinterest has focused on the interdependence of anonymityand covert channels [20]. The designer of an anonymitysystem generally faces the question of how much informa-tion may leak from the anonymity network given the un-avoidable imperfectness of the anonymity network and howthis may affect the anonymity degree. The imperfectness ofan anonymity system will result in the information leakingfrom the system. This information leakage can be evaluatedin form of a covert channel.The major contributions of our study are summarized asfollows: First, we propose an anonymity degree to quan-tify the anonymity provided by an anonymity network. Thisdefinition generalizes the information theoretic definitionspreviously proposed in [23, 8]. Then, we propose a newclass of covert channels, which we call anonymity-basedcovert channels. We formally prove how to establish covertchannels of maximum capacity over a single mix based onanonymity attacks on the mix. Finally, we use anonymity-Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICSCS’05) 1063-6927/05 $20.00 © 2005 IEEEbased covert channels to assess the performance of mixnetworks. We show how the capacity of anonymity-basedcovert channels can be used to provide simple descriptionsof non-perfect mix networks, and can be used to formulatebounds on the provided anonymity.The rest of the paper is organized as follows: Section 2reviews the related work. Section 3 describes the proposedanonymity degree and the relationship with other entropy-based anonymity degree definitions. In section 4, we de-fine the anonymity based covert channel. Section 5, Sec-tion 6, and Section 7 present the relationship between thecovert channel capacity and anonymity degree for a single-mix case and mix-network case. We conclude this paperand discuss the future work in Section 9.2 Related WorkChaum [2] pioneered the idea of anonymity in 1981.Since then, researchers have applied the idea to differentapplications, such as message-based email and flow-basedlow-latency communications, and they have invented newdefense techniques as more attacks have been proposed. Foranonymous email applications, Chaum proposed to use re-lay servers, called mixes, that re-route messages. Messagesare encrypted to prevent their tracking by simple payloadinspection.Helsingius [14] implemented the first Internet anony-mous remailer, which is a single application proxy andreplaces the original email’s source address with the re-mailer’s address. G¨ulc¨u and Tsudik [13] developed a rel-atively complete anonymous email system, called Babel.Cottrell [17] developed Mixmaster, which counters a globalpassive attack by using message padding. It counters trickleand flood attacks [13, 24] by using a pool batching strat-egy. Danezis, Dingledine and Mathewson [6]
View Full Document
Unlocking...