Practical Anonymity for the Masses with Mix-NetworksMarc Rennhard and Bernhard PlattnerSwiss Federal Institute of Technology, Computer Engineering and Networks Laboratory, Zurich, Switzerland{rennhard|plattner}@tik.ee.ethz.chAbstractDesigning mix-networks for low-latency applicationsthat offer acceptable performance and provide good resis-tance against attacks without introducing too much over-head is very difficult. Good performance and small over-heads are vital to attract users and to be able to supportmany of them, because with only a few users, there is noanonymity at all. In this paper, we analyze how well dif-ferent kinds of mix-networks are suited to p rovide practicalanonymity for a very large number of users.1 IntroductionMix-networks [5] are the most promising approach toanonymize communication in the Internet. Originally de-signed to anonymize e-mail communication, variations ofthe basic design have led to systems that provide anonymityfor low-latency applications such as web browsing. Low-latency mix-networks transport data through the systemwith at most a few seconds delay, while mix-networks forapplications such as e-mail can potentially delay a messagein the system for hours. This is the main reason why itis much more difficult to make low-latency mix-networksresistant to an attacker that wants to break the anonymityof the users. In this paper, we focus on low-latency mix-networks, although many results apply to mix-networks ingeneral. Figure 1 depicts the basic idea of a mix-network.s1c6c11c2c10c9s10c5c4c7s7s13s8s2s3s11s9c13c8c1c12s4s6s5m5m1m2m4m6m3c3s12Figure 1. Basic mix-network.Mix-networks are made up of independent mixes (m1–m6) that are distributed in the Internet. Low-latency mix-networks are also called circuit-based mix-networks be-cause to access a server (si), a client (ci) chooses a subsetof the mixes an d establishes a circuit along them. As anexample, we assume c1communicates with s1via m1,m6,m2,andm3. We name this sequence of mixes c1’s chain ofmixes. All data sent from c1to s1are first sent to m1,thenfrom m1to m6, and so on until the last mix in the chain(m3) forwards them to s1. The same chain of mixes is usedin opposite order to send data back to c1. The goal of amix-network is to make it difficult for an adversary to learnwhich client cicommunicates with which server si.Todoso, all messages exchanged between two mixes or clientsand the first mix in their chains have the same length, areencrypted or decrypted to change their encoding as they tra-verse a mix, and are reordered in a mix. In addition, dummytraffic can be used to further complicate the task for an at-tacker. Traditionally, mix-networks consist of relatively fewand well known mixes that are used by a much larger num-ber of users, as shown in figure 1. We name this type staticmix-networks. Recently, mix-networks where every clientis also a mix at the same time have been proposed. Sincethe mixes in these peer-to-peer based systems can show upand disappear again at any time, we name this type dynamicmix-networks.Mix-networks introduce overhead, which grows with thestrength of the threat model the system should be resistantto. Especially the overhead introduced by cover traffic canbe huge and keeping the overhead as small as possible isclosely related to the anonymity a mix-network provides: agiven mix-network with a fixed number of mixes can han-dle a certain amount of data. If lots of cover traffic is used,less real data can be handled, and fewer people can be sup-ported. This implies that the anonymity set, i.e. the numberof people among which one is anonymous, is smaller.The motivation for this paper is to find the golden meanbetween the people defining theoretical systems againstpowerful adversaries that introduce vast amounts of over-head and those implementing practical mix-networks thatare often only resistant to weak threat models. Our goal isnot to define a system that provides perfect anonymity, andwe will point out in section 3 that perfect anonymity in prac-tical mix-networks for low latency applications that supporta large number of users is simply not possible. Our goal isProceedings of the Twelfth IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE’03)1080-1383/03 $17.00 © 2003 IEEEto analyze how mix-networks have to be operated to providepractical anonymity for a very large number (e.g. millions)of u sers. With practical, we mean that th e quality of the ser-vice a mix-netwo rk offers should be good enough such thatusers actually use the system. We also mean that the num-ber of users a static mix-network can handle per mix mustbe reasonably large. Finally, with practical we mean thatthe mix-network should protect from a realistic adversaryand not from an extremely powerful, theoretical attacker.In the next section, we briefly discuss related work. Insection 3, we analyze why anonymity in the Internet is sucha hard problem and in section 4, we examine the overheadof different cover traffic mechanisms. In section 5, we givearguments for what we call a realistic threat model and insection 6, we discuss how well different approaches to op-erate mix-networks are suited to support a large number ofusers. Section 7 concludes our work.2 Related WorkSeveral static mix-networks have been operational:Onion Routing [7], Freedom [4], Web Mixes [1], and theAnonymity Network [10]. Onion Routing and Freedom arevery similar in their design and do not make use of anycover traffic mechanism. Web Mixes is supposed to defeata very strong adversary, but until now, no such mechanismshave been included in the prototype. The Anonymity Net-work employs a relatively efficient cover traffic mechanism,which makes it resistant against certain passive attackers.The first representative of dynamic mix-networks wasCrowds [8], which offered a low level of anonymity. Re-cent developments include Tarzan [6], which makes use ofcover traffic and MorphMix [9], which employs a collusiondetection mechanism to detect colluding mixes.3 Why Anonymity is so HardWe distinguish between passive and active attackers.Passive attackers can monitor all or parts of the traffic andtry to combine the data observed at various mixes. Activeattackers have all the abilities o f a passive attacker; in addi-tion they can insert, delete, or modify any data, block links,and control a subset of all mixes. To illustrate the attack s,we use figure 2.
View Full Document
Unlocking...