Information Leaks in Structured Peer-to-Peer Anonymous
Communication Systems
PRATEEK MITTAL and NIKITA BORISOV, University of Illinois at Urbana-Champaign

We analyze information leaks in the lookup mechanisms of structured peer-to-peer (P2P) anonymous communication systems and how these leaks can be used to compromise anonymity. We show that the techniques used to combat active attacks on the lookup mechanism dramatically increase information leaks andthe efficacy of passive attacks, resulting in a tradeoff between robustness to active and passive attacks.
We study this tradeoff in two P2P anonymous systems: Salsa and AP3. In both cases, we find that,by combining both passive and active attacks, anonymity can be compromised much more effectively thanpreviously thought, rendering these systems insecure for most proposed uses. Our results hold even if
security parameters are changed or other improvements to the systems are considered. Our study, therefore,shows the importance of considering these attacks in P2P anonymous communication.
Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]: General—Security
and protection; C.2.4 [Computer-Communication Networks]: Distributed Systems
General Terms: Security
Additional Key Words and Phrases: Anonymity, attacks, information leaks, peer-to-peer
ACM Reference Format:
Mittal, P. and Borisov, N. 2012. Information leaks in structured peer-to-peer anonymous communication
systems. ACM Trans. Inf. Syst. Secur. 15, 1, Article 5 (March 2012), 28 pages.
DOI = 10.1145/2133375.2133380 http://doi.acm.org/10.1145/2133375.2133380

5
1. INTRODUCTION

Anonymous communication hides the identity of communication partners from third
parties or hides user identity from the remote party. The Tor network [Dingledine
et al. 2004], deployed in 2003, now serves hundreds of thousands of users and carries
terabytes of traffic per day [The Tor Project]. Originally an experimental network
used by privacy enthusiasts, it is now entering mainstream use; for example, several
consulates use it to evade observation by their host country [Goodin 2007; Zetter 2010].
The capacity of Tor is already strained, and to support a growing population, a peerto-peer approach will likely be necessary, as P2P networks allow the network capacity
to scale with the number of users. Indeed, several proposals for peer-to-peer anonymous communication have been put forward [Freedman and Morris 2002; McLachlan
et al. 2009; Mislove et al. 2004; Mittal and Borisov 2009; Nambiar and Wright 2006;
Rennhard and Plattner 2002]. However, P2P networks present new challenges to anonymity, one of which is the ability to locate relays for anonymous traffic.
This material is based on work supported by the National Science Foundation under grants 0627671,
0831488, and 0953655.
Authors’ address: P. Mittal and N. Borisov, Coordinated Science Laboratory, University of Illinois at UrbanaChampaign, 1308 W. Main Street, Urbana, IL 61801; email: {mittal2, nikita}@illinois.edu.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights
for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of
this work in other works requires prior specific permission and/or a fee. Permissions may be requested fromthe Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701, USA, fax +1 (212)869-0481, or permissions@acm.org.
c 2012 ACM 1094-9224/2012/03-ART5 $10.00

DOI 10.1145/2133375.2133380 http://doi.acm.org/10.1145/2133375.2133380

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:2

P. Mittal and N. Borisov

In Tor, clients use a directory to retrieve a list of all the running routers. Sucha directory will not scale as the number of routers grows, since the traffic to update
the directory would become prohibitively expensive [McLachlan et al. 2009]. Instead,a peer-to-peer lookup is needed to locate an appropriate relay. Such a lookup, however, can be subject to attack: malicious nodes can misdirect it to find relays that arecolluding and violate the anonymity of the entire system. All of the P2P anonymous
communication designs therefore incorporate some defense against such attacks; forexample, AP3 [Mislove et al. 2004] uses secure routing techniques developed by Castro
et al. [2002], and Salsa uses redundant routing with bounds checks [Nambiar andWright 2006].
These defenses, however, come at a cost. They operate by performing extra checks
to detect incorrect results returned by malicious nodes. These checks cause many
messages to be exchanged between nodes in the network, some of which might beobserved by attackers. As a result, a relatively small fraction of attackers can makeobservations about a large fraction of lookups that occur in the P2P network, acting
as a near-global passive adversary. Modern anonymity networks are not designed toresist a global passive adversary, because such an attack is believed to be too difficult
to mount for all but the most powerful adversaries, and because defenses against a
global passive adversary are too costly for most users. Therefore, this small fraction of
attackers can successfully attack anonymity of the system.
We examine this problem through a case study of two P2P anonymous communication systems: Salsa and AP3. In both systems, defenses against active attacks create
new opportunities for passive attacks. Salsa and AP3 make heavy use of redundancy toaddress active attacks, rendering them vulnerable to passive information-leak attacks.
Further, increasing the levels of redundancy will improve passive attack performanceand will often make the system weaker overall. We find that even in the best case,
Salsa is much less secure than previously considered. Salsa was designed to tolerate
up to 20% of compromised nodes; however, our analysis shows that, in this case, overone quarter of all circuits will be compromised by using information leaks. Similarly,
conventional analysis of AP3 suggests that it provides probable innocence when up to
33% of nodes are compromised and can tolerate up to 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 be achieved by increasing thepath length or introducing a public key infrastructure (PKI). We found that these tools
offer only a limited defense against our attacks, and the system is still not secure forpractical purposes. Our results demonstrate that information leaks are an importantpart of anonymity analysis of a system.
The article is organized as follows. In Section 2 we present the state of low-latency
anonymous communication. We discuss information leaks from lookups in Section 3
and show the trade off between security and anonymity. In Sections 4 and 5, we present
attacks based on information leaks from lookups on AP3 and Salsa. In Section 6, we
present an entropy-based approach to computing-information leaks in Salsa. Section 7
contains related work, and we conclude in Section 8.

2. BACKGROUND

In this section, we present a brief overview of anonymous communication. We motivate
the need for decentralized and scalable solutions and discuss why structured peer-topeer systems have strong potential. We also describe our threat model.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:3

2.1. Low-Latency Anonymous Communication Systems

Anonymous communication systems can be classified into low-latency and highlatency systems. High-latency anonymous communication systems like Mixminion[Danezis et al. 2003] and Mixmaster [Möller et al. 2003] are designed to be secure
even against a powerful global passive adversary; however, the message transmission
times for such systems are typically on the order of several hours. This makes them
unsuitable for use in applications involving interactive traffic like Web browsing andinstant messaging. The focus of this article is on low-latency anonymous communication systems [Boucher et al. 2000; Clarke et al. 2001; Dingledine et al. 2004; I2P
2003].
Tor [Dingledine et al. 2004] is a popular low-latency anonymous communication system. Users (clients) download a list of servers from central directory authorities andbuild anonymous paths using onion routing [Syverson et al. 2000]. There are several
problems with Tor’s architecture. First, the reliance on central directory authorities
makes them an attractive target for the attackers. Second, Tor serves hundreds ofthousands of users, and the use of a relatively small number of servers to build anonymous paths becomes a performance bottleneck. Finally, Tor requires all users tomaintain a global view of all the servers. As the number of servers increases, maintaining a global view of the system becomes costly, since churn will cause frequent
updates and a large bandwidth overhead. In order to address these problems, a peerto-peer architecture will likely be necessary. However, peer-to-peer networks present
new challenges to anonymity, one of which is the ability to locate relays for anonymous
traffic.
Several designs for peer-to-peer low-latency anonymous communication have been
proposed. Tarzan [Freedman and Morris 2002] replaced the centralized directory authority with a gossip protocol that was used to distribute knowledge of all peers to allother peers. While decentralized, the requirement that each node maintain an up-todate global view of the system means that the system could scale only to about 10,000
nodes. MorphMix [Rennhard and Plattner 2002] was designed to scale to much larger
network sizes. It built an unstructured peer-to-peer overlay between all the relays andcreated paths along this overlay to forward anonymous communications. Nodes along
the path are queried for their neighbors in order to choose the next hop. To prevent a
node from providing malicious results, a scheme using witness nodes and a collusion
detection mechanism is used. However, the collusion detection mechanism can be circumvented by a set of colluding adversaries who model the internal state of each node,thus violating anonymity guarantees [Tabriz and Borisov 2006].
Several other designs have used so-called structured peer-to-peer topologies[Mislove et al. 2004; Nambiar and Wright 2006], also known as distributed hashtables (DHTs), as a foundation for anonymous peer-to-peer communication. Structured topologies assign neighbor relationships using a pseudorandom but deterministic mathematical formula based on the IP addresses or public keys of nodes. This
allows the relationships to be verified externally, presenting fewer opportunities for
attacks. AP3 [Mislove et al. 2004] used a secure lookup mechanism [Castro et al.
2002] in the Pastry DHT [Rowstron and Druschel 2001] to select random forwarders
and used them to build an anonymous communication path. The secure lookup techniques are based on a PKI and, thus, do not achieve a truly decentralized security
model. The lookup was also not designed to be anonymous, a property that we willshow to have important consequences for the security of AP3.
Salsa [Nambiar and Wright 2006] aimed to offer secure P2P anonymous communication in a system without a PKI. It designed a custom DHT structure and a custom secure lookup mechanism specifically tailored for the purposes of anonymous

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:4

P. Mittal and N. Borisov

communication. Its secure lookup and path construction mechanisms rely heavily on
redundancy to detect potential attacks. As we will show, such redundancy creates information leaks, and presents a trade-off between resisting active attacks and presenting
more opportunities for passive attacks.
2.2. Threat Model

Low-latency anonymous communication systems are not designed to to be secureagainst a global passive adversary. We consider a partial adversary who controls afraction f of all the nodes in the network. This set of malicious nodes colludes and canlaunch both passive and active attacks. We consider the set of colluding nodes static,
and the adversary cannot compromise nodes at will. In terms of the standard terminology introduced by Raymond [2000], our adversary is internal, active, and static.
Even in networks with large numbers of nodes, f can be a significant fraction of the
network size. Both Salsa and AP3 use mechanisms to prevent Sybil attacks [Douceur2002], which would otherwise allow an adversary to attain an f arbitrarily close to
1. However, powerful adversaries, such as governments or large organizations, canpotentially deploy enough nodes to gain a significant fraction of the network. Similarly,
botnets, whose size often measures in tens to hundreds of thousands of nodes [Cookeet al. 2005; Rajab et al. 2006; Holz et al. 2008], present a very real threat to anonymity.
In this work, we consider values of f up to 0.2.
3. INFORMATION LEAKS VIA SECURE LOOKUPS

It has been recognized that unprotected DHTs are extremely vulnerable to attacks on
the lookup mechanism. First, malicious nodes can perform a Sybil attack [Douceur2002] and join the network many times, increasing the fraction f . Second, they canintercept lookup requests and return incorrect results by listing a colluding malicious
node as the closest node to a key, thus increasing the fraction of lookups that return
malicious nodes. Finally, they can interfere with the routing table maintenance andcause the routing tables of honest nodes to contain a larger fraction of malicious nodes;
this will increase the chance that a lookup can be intercepted and the result can besubverted.
3.1. Castro et al.’s Secure Lookup

Castro et al. [2002] designed a suite of mechanisms to counter these attacks. We discuss their mechanisms in context of Pastry [Rowstron and Druschel 2001], a structured peer-to-peer overlay network, though they are applicable to other DHTs. They
proposed the following.
— Secure node identifier assignment. Each node is issued a certificate by a trusted
authority, which binds the node identifier with a public key. The authority limits
the number of certificates and prevents Sybil attacks.
— Secure routing table maintenance. Even with secure nodeID assignment, attackers
can maliciously influence routing table construction. The Pastry routing algorithms
allow flexibility in selecting a neighbor for each slot, which is used for optimizing latency or other metrics. Attackers can exploit this flexibility by suggesting malicious
choices for these slots. Secure routing table maintenance eliminates this flexibility
by creating a parallel, constrained routing table where each slot can have only asingle possible node, as verified by secure lookup. This solution ensures that, on
average, only a fraction f of a node’s neighbors will be malicious.
— Secure lookups (secure message forwarding). For secure lookups, a two-phase approach is employed. The message is routed via the normal routing table (optimized
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:5

Fig. 1. Salsa lookup mechanism.

for latency), and a routing failure test is applied. If the test detects a failure, redundant routing is used, and all messages are forwarded according to the constrained
routing table. The failure test makes use of the observation that the density of honest nodes is greater than the density of malicious nodes. The idea behind redundantrouting is to ensure that multiple copies of messages are sent to the key root via diverse routes. Note that Castro et al. [2002] consider the problem of securely routing
to the entire replica set, for which a neighbor anycast mechanism is also used.
Used together, these techniques are quite effective at ensuring that a lookup returns
the actual closest node to the randomly chosen identifier, which in turn suggests that
it is malicious with probability f . However, the secure lookup mechanism generates
many extra messages: the routing failure test involves contacting the entire root set ofa node (L immediate neighbors in the nodeID space), and redundant routing sends arequest across several paths. These messages let attackers detect when a lookup has
been performed between two honest nodes with high probability. The probability ofdetecting the lookup initiator can be approximated as 1 − (1 − f ) L+log2b N−1 , which isquite high for the typical values of L = 16 and b = 4. In Figure 1(a), we plot the probability of detection of the lookup initiator as a function of the fraction of compromised
nodes f using N = 1,000. We can see that a small fraction of 5% of compromised nodes
can detect the lookup initiator more than 60% of the time. Moreover, when the fractionof compromised nodes is about 10%, the lookup initiator is revealed 90% of the time.
This shows the fundamental tension that is encountered by a DHT lookup. The
default Pastry mechanisms provide little defense against active adversaries who try
to disrupt the lookup process, dramatically increasing the probability that a lookup
returns a compromised node. Castro et al.’s mechanisms solve this problem but introduce another, as the lookup is no longer anonymous and can be observed by malicious
nodes. A relatively small fraction of malicious nodes can, therefore, act as a nearglobal passive adversary and compromise the security of anonymous communication
systems. The secure lookup exposes nodes to increased surveillance; we note that thismay have consequences for protocols other than anonymous communication that are
built on top of secure lookup.
3.2. Salsa Secure Lookup

Salsa [Nambiar and Wright 2006] is based on a custom DHT that maps nodes to apoint in an ID space corresponding to the hash of their IP address. The ID space in
Salsa is divided into groups and organized into a binary tree structure. Each node
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:6

P. Mittal and N. Borisov

Fig. 2. Computing probability of a compromised lookup.

knows all the nodes in its group (local contacts) and a small number of nodes in othergroups (global contacts).
Similar to Pastry, nodes must rely on other nodes to perform a recursive lookup. A
malicious node that intercepts the request could return the identity of a collaborating
attacker node. Salsa makes use of redundant routing and bounds checks to reduce thelookup bias. The Salsa architecture is designed to ensure that redundant paths havevery few common nodes between them (unlike Pastry or Chord [Stoica et al. 2003]).
This reduces the likelihood that a few nodes will be able to modify the results for all
the redundant requests. A lookup initiator asks r local contacts (chosen at random)
to perform a lookup for a random key. The returned value that is closest to the key
is selected, and a bounds check is performed. If the distance between the prospective
owner and the key is greater than a threshold distance b , it is rejected, reasoning
once again that malicious nodes are less dense than honest ones and, thus, will failthe bounds check much more frequently. If the bounds check test fails, the resultof the lookup is discarded, and another lookup for a new random key is performed.
Redundant routing and the bounds check work together: an attacker would need toboth intercept all of the redundant lookups and have a malicious node that is closeenough to avoid the bounds check.
We first perform an analysis of the security of the Salsa lookup protocol. Let us
denote the initiator of the lookup by I and the target identifier by ID. We have to consider two possibilities: either the (actual) successor of ID is honest, or it is malicious(see Figure 2). For a random ID, the probability that a node is malicious will be f . The
next question is whether this malicious node will pass the bounds check; let us call 1
the probability that it fails. In the case of failure, the current lookup is aborted, and a
new one is initiated. If the test is passed, the malicious node is returned as the resultof the lookup.
If the successor of ID is honest, on the other hand, the lookup will return thathonest node if there is at least one lookup path composed of only honest nodes. Let us
say that this happens with probability g. In this case, the honest node must still pass
the bounds check to obtain an honest result of the lookup; so the lookup is aborted withprobability 1 . (Note that this is the same regardless of whether the successor of ID
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:7

is honest or malicious, since ID was picked uniformly at random in each case). If, on
the other hand, every path has a malicious node (with probability 1 − g), the malicious
nodes can suggest the malicious node closest to ID as the result. This malicious node
will also be subject to the bounds check. It is more likely to fail the test now, because it
is no longer the closest node to ID; so let us call the probability of failure 2 . A failed
bounds check will cause the lookup to be restarted. A successful check will result inthe malicious node being returned.
1 is the probability of false positives during a bounds check; that is, there is nonode with an identifier in the range between target ID and ID + b , where b is thebounds check parameter. If we consider the ID space to be the interval [0, 1), then 1
can be computed as
1 = (1 − b ) N .

(1)

2 is the probability of a false negative; that is, given that the target node is honest,
there is a malicious node within bounds. Suppose that the target node is at a distancea from ID. The cumulative density function (CDF) of this distance is given by F(a) =(1 − a) N , and the PDF is given by f (a) = N · (1 − a) N−1 . Now, we have
2 = P(malicious node within bounds| target node is honest),= 1 − P(malicious node outside bounds|target node is honest),


 b
 1
1 − b N· f
= 1−f (a) ·da −f (a) · 1 da,
1−a
a=0
a=b


 b
 1
1 − b N· f
N−1
= 1−
N · (1 − a)·da −N · (1 − a) N−1 da,
1−a
a=0
a=b
1 − (1 − b ) N−N· f− 1 .
= 1 − N · (1 − b ) N· f ·N− N· f

(2a)
(2b)
(2c)
(2d)
(2e)

g is the probability that there is at least one lookup path with all honest nodes. This
probability depends on the lookup path lengths. For simplicity, let us first consider
the case of a single lookup (r = 1). We shall later extend our analysis for redundant
lookups.
3.2.1. Single Lookup, r = 1. Let us denote the lookup path length by L. Given a particular lookup path length (L = l), we have

gl = P(Lookup is honest|L = l) = (1 − f )l.

(3)

Based on Figure 2, we have
P(Compromised Lookup|L = l) =f · (1 − 1 ) + (1 − f ) · (1 − gl ) · 2,f · (1 − 1 ) + (1 − f ) · (1 − gl ) · 2 + (1 − f ) · gl · (1 − 1 )(4)

where 1 , 2 , and gl have been computed in Equations (1), (2), and (3). Note that weneed to factor out aborted lookups, since we are interested in the fraction of successful
lookups that produce a malicious node.
Now we shall compute P(L = l). Let D denote the distance between the initiator
I’s group and target ID’s group, in terms of the number of levels of the binary tree
structure. This is illustrated in Figure 3. In order to compute P(L = l), we can first
condition the event D = d. Since I selects the target ID uniformly at random fromACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:8

P. Mittal and N. Borisov

Fig. 3. Salsa binary tree structure.

the ID space, the probability that the target is d levels away from the initiator in thebinary tree structure is
 d−1
2
d≥1
|G|
P(D = d) =,(5)
1
|G| d = 0
where |G| is the number of groups in Salsa.
Under the event D = d, we shall compute the probability of lookup path length being
l hops, that is, P(L = l|D = d). The lookup from I to ID can proceed along several
different paths, depending on local contact chosen by the initiator. Note that the firsthop is always a local contact in the initiators group, and the last hop is always in thetarget group. Thus we need to select l − 2 more hops from among the d − 1 possible
subgroup levels relative to the target ID. Subgroup level refers to a set of nodes who
have the same binary tree distance (levels) from the target ID. The probability of
selecting any subgroup level is 1/2. Thus, given D = d, the total number of possible, where the probability of selecting any individual pathlookup paths of length l is d−1
l−2
1 d−1
is ( 2 ) . From the above, we have⎧    d−1
d−1
1
⎪
d≥1
⎨ l−2 2
P(L = l|D = d) = 1(6)
d = 0, l = 1 .
⎪⎩0
d = 0, l > 1
Using Equations (5) and (6), we can compute P(L = l) as follows.
log2 |G|P(L = l|D = d) · P(D = d),P(L = l) =d=0P(L = l) =log2 |G| d−1
1
d=1
l−2 · |G|

1
|G|

l≥2
.
l=1

(7a)

(7b)

Finally, using Equations (4) and (7) we can compute the probability of a compromised
lookup as(log2 |G|)+1

P(Compromised Lookup|L = l) · P(L = l).

P(Compromised Lookup) =l=1

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

(8)

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:9

3.2.2. Redundant Lookups. Let us denote the r lookup path lengths by L 1 , . . . , L r.
Given particular lookup path lengths (L 1 = l1 , . . . , L r = lr ), we haveg = P(at least one lookup path is honest),= 1 − P(all lookup paths have a malicious node),
r



=1−
1 − (1 − f )l j .

(9a)
(9b)
(9c)

j=1

Based on Figure 2, we have
P(Compromised Lookup|L 1 = l1 , . . . , L r = lr) =f · (1 − 1 ) + (1 − f ) · (1 − g) · 2,f · (1 − 1 ) + (1 − f ) · (1 − g) · 2 + (1 − f ) · g · (1 − 1 )(10)

where 1 , 2 , and g have been computed in Equations (1), (2), and (9). Now we shallcompute P(L 1 = l1 , . . . , L r = lr ) by conditioning on the event D = d. Note that conditioned on D = d, the redundant lookups are independent. Thus, we haveP(L 1 = l1 , . . . , L r = lr|D = d) =rP(L j = l j|D = d).

(11)

j=1

Using Equation (11), we can compute P(L 1 = l1 , . . . , L r = lr) as
log2 |G|P(L 1 = l1 , . . . , L r = lr ) =P(L 1 = l1 , . . . , L r = lr |D = d) · P(D = d),

(12a)

d=0
log2 |G|

=

(
d=0

r


P(L j = l j|D = d)) · P(D = d),

(12b)

j=1

where P(L = l|D = d) and P(D = d) are given by Equations (6) and (5). Finally, using
Equations (10) and (12), we can compute the probability of a compromised lookup as
P(Compromised Lookup) =(log2 |G|)+1(log2 |G|)+1

···
l1 =1

P(Compromised Lookup|L 1 = l1 , . . . , L r = lr)·lr =1

P(L 1 = l1 , . . . , L r = lr).

(13)

To validate our mathematical model, we used a simulator developed by the authorsof Salsa [Nambiar and Wright 2007].1 The simulator was configured to simulate 1,000
topologies, and in each topology, results were averaged over 1,000 random lookups. The
lookup bias is sensitive to the average lookup path length, which in turn is sensitive
about log2 |G|, where |G| is the number of groups. This is because longer path lengths
give attackers more opportunities to intercept the lookup and subvert the result. We
therefore used 128 groups, which would be a typical number in a large network, and
1,000 nodes in our simulation. Salsa is resistant to conventional attacks that target
the lookup mechanism as long as the fraction of malicious nodes in the system is lessthan 20%. Since Salsa does not provide adequate security for higher values of f , we
1 Our results differ slightly from those shown in Nambiar and Wright [2006] because of a bug in the original
simulator that we fixed. We have communicated the bug to the authors who have confirmed it.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:10

P. Mittal and N. Borisov

shall limit our analysis to f ≤ 0.2. In Figure 1(b), we study the effect of varying redundancy on the lookup bias. The curve y = f is shown as a reference for an optimal secure
lookup protocol. Note that the simulation results closely match our analytic calculations. We can also see that increasing r clearly reduces the fraction of compromised
lookups, thus increasing security. For f = 0.2, the fraction of compromised lookups
drops from 37% to 24% when r is increased from 2 to 6. The initiator of a lookup canbe identified by the attackers if any of the local contacts used for redundant lookups
are compromised. The probability of detecting the lookup initiator is 1 − (1 − f )r, as depicted in Figure 1(a). Clearly, increasing r increases the chance that a lookup initiator
is detected. This illustrates the tradeoff between security and anonymity of a lookup.
In this section, we observed that secure lookups leak information about the lookup
initiator. Furthermore, we observed a tradeoff between the security and anonymityof a lookup. A relatively small fraction of malicious nodes are able to observe a large
fraction of lookups. Next, we will use this to break the anonymity of AP3 and Salsa.
4. AP3AP3 [Mislove et al. 2004] is an anonymous communication system built on top of
Pastry [Rowstron and Druschel 2001]. The essence of AP3 operation is similar to
Crowds [Reiter and Rubin 1998], where a random walk over all of the nodes in thesystem is used to forward requests while concealing the initiator’s identity. In bothAP3 and Crowds, a node A that wants to send a message to a node B first picks arandom relay F1 to forward the message. F1 then flips a weighted coin, and with probability p, it chooses another relay, F2 , and forwards the request there. With probability
1 − p, F1 delivers the message directly to the recipient B.
Therefore, a message is forwarded through a path of nodes, all of which are selected
randomly. The path length follows a geometric distribution, with the expected length
being 1−1 p . We can assume that some of the relays will be malicious and will try to guessthe identity of the initiator. However, due to the stochastic nature of the forwarding,such relays will have a hard time telling whether they received a message from theinitiator directly, or from another relay. Reiter and Rubin first analyzed the probability
that the initiator is correctly identified [1998]; we review the terminology used in theiranalysis here, as we will extend it in later sections.
Let Hk denote the event that the first attacker in the forwarding path occupies
the kth position, where the initiator is at the 0th. Let Hk+ = Hk ∨ Hk+1 ∨ Hk+2 ∨... and let I denote the event that attackers identified the initiator correctly (as thepredecessor). Then, given that an attacker intercepts a message, the chance that theinitiator guessed correctly is P(I|H1+ ). This can be further decomposed as
P(I|H1+ ) =P(I ∧ H1+ ) P(H1 )P(I|H1 ) + P(H2+ )P(I|H2+ )=.
P(H1+ )
P(H1+ )

(14)

Note that P(I|H1 ) = 1, since in this case the initiator is identified correctly, andP(I|H2+ ) = 0. If we let f represent the fraction of nodes that are compromised, then
P(I|H1+ ) =P(H1 )=
P(H1+ )

f

i−1
∞ 
f
i=1 p(1 − f ).

Reiter and Rubin proposed the notion of probable innocence as happening whenever
the true initiator is identified with a probability less than 1/2. By solving P(I|H1+ ) <1/2 for f , we can see that as long as f < 1 − 21p , probable innocence will be assured.
For example, with p = 0.75, up to 33% nodes can be malicious without compromisingprobable innocence. By increasing p, even larger fractions of compromised nodes can
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:11

Fig. 4. Information leak in AP3.

be tolerated, up to the limit of 50%, when p = 1. (Of course, larger p results in longer
paths.)
4.1. The E 1 Attack

The chief difference between AP3 and Crowds is the manner in which the relays arechosen. Both aim to pick a relay at random out of all the nodes in the system, but
Crowds assumes that all nodes know about all other nodes, which does not scale. AP3
uses the secure lookup due to Castro et al. to locate relays. To pick a relay, a node
performs a secure lookup in the Pastry DHT for a random key. This, in turn, can beused to break probable innocence. In addition to the base observation—node A used
malicious node B as a relay—the malicious nodes have an extra observation point:
whether any other node has performed a lookup for node A. We will define the event
E1 as the case when no lookups for A have been detected. (E1 implies H1+ .) We canthen calculate the probability P(I|E1 ), such that
P(I|E1 ) =P(I ∧ E1 ).
P(E1 )

To calculate P(E1 ), we need to consider two cases: either A is, in fact, the initiator(H1 ), or some other node, Q, forwarded the request to A (H2+ ). In the former case,
E1 will be true unless there is another spurious lookup (false positive) for A, due toanother request that is detected by the attackers. We call the spurious lookup event
FP. In the latter scenario, we need two things to happen: first, no spurious lookup has
happened, and second, the lookup from Q to A was not detected. We call this second
event Q. Figure 4 represents the analysis of the two cases.
Therefore, we can express E1 as
E1 ≡ (H1 ∧ ¬FP) ∨ (H2+ ∧ Q ∧ ¬FP)
Because H1 and H2+ are mutually exclusive, and FP and Q are independent from H1 ,H2+ , and each other, we can writeP(E1 ) = P(H1 )P(¬FP) + P(H2+ )P(¬FP)P(Q).
Therefore,P(H1 )P(¬FP),
P(H1 )P(¬FP) + P(H2+ )P(¬FP)P(Q)P(H1 )=.
P(H1 ) + P(H2+ )P(Q)P(I|E1 ) =(15)

Note that P(I|E1 ) can be computed independently of P(FP); this is because weare conditioning on E1 , which implies that no spurious lookups have occurred. Note,
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:12

P. Mittal and N. Borisov

Fig. 5. AP3 attacks.

also, that as P(Q) grows smaller, the fraction approaches closer to 1. As we noted in
the Section 3.1, with the Castro et al’s. secure lookup, P(Q) is quite small, even forsmall f .
Figure 5(a) shows the attacker confidence as a function of the fraction of the nodes
that are compromised for varying p, using N = 1, 000, b = 4, L = 16. Our calculations show that to achieve P(I|E1 ) < 1/2, we require that f < 0.05, which is muchsmaller than the previously computed limit of f < 0.33. Furthermore, the theoreticallimit for the fraction of attackers that AP3 can tolerate can be computed by letting
p → 1, which is approximately 10% attackers. Again, this limit is much smaller thanthe conventional figure of 50%. This shows the fundamental tension that is encountered by AP3. The default Pastry mechanisms provide little defense against active
adversaries who will try to disrupt the lookup process, dramatically increasing P(H1 )and thus P(I|H1+ ). Castro et al.’s suggested mechanisms solve this problem, but introduced another, as the lookup is no longer anonymous and can be observed by malicious
nodes.
4.2. The E i Attack

In addition to E1 , the adversary can use the observation that if there is a chain of
lookups leading to the predecessor node, then the first node in the chain is more likely
to be the initiator than any other node. For instance, we can define E2 as the case, inwhich attackers observe a lookup by some node Q of the previous hop (P), but do notdetect a lookup for Q. Furthermore, the previous hop (P) should not have looked up any
other nodes. We now compute P(I|E2 ). Depending on the probabilities of P(E2 ∧ H1 )and P(E2 ∧ H2 ), the attacker may guess that P or Q is the initiator of the path.
These probabilities will depend on the chance of a false-positive lookup detection,
which in turn depends on the amount of lookup traffic elsewhere in the network. We
define x to be the number of paths that are being constructed (by all nodes) at thesame time as this one. A reasonable number for x is N/100, which means that during
this path construction, 1% of all nodes also performed a concurrent path construction.
A number much larger than this (e.g., N/10) would mean that nodes are spending asignificant fraction of their time (10%) constructing paths, rather than using them foranonymous communication. Also, if any nodes in the network are not in active use,
this will decrease x.
Given x, we can compute the false-positive probability α using the equation
α = 1−

N−1N

x 1−(1− f )L+log2b N

.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:13

It is easy to see that as long as the false positive detection probability is small,P(E2 ∧ H2 ). Therefore, the attacker strategy here would be to guess theP(E2 ∧ H1 )node (Q) looking up the previous hop to be the initiator. Therefore, P(I|E2 ∧ H1 ) = 0
and P(I|E2 ∧ H3+ ) = 0.
P(I|E2 ) =P(I|E2 ∧ H2 )P(E2 ∧ H2 ).
P(E2 ∧ H1 ) + P(E2 ∧ H2 ) + P(E2 ∧ H3+ )(16)

Figure 5(b) plots P(I|E2 ) as a function of f for varying p. The trend for P(I|E2 ) isvery similar to our analysis of P(I|E1 ). Again, we can see that for p = 0.75, the maximum fraction of attackers that AP3 can handle while maintaining P(I|E2 ) < 1/2 isonly 5%. Due to lack of space, we have limited our analysis to only P(I|E1 ) and P(I|E2 ).
In this sense, ours is a conservative analysis and the attackers can utilize many more
observation points. For instance, one could define a general event Ei analogous to E2 .
If the false positives are small, P(I|Ei) can be approximated as
P(I|Ei) =P(Hi).
P(Hi) + P(H(i+1)+ )P(Q)This formulation neglects false positives and is only an approximation. However, inpractice, the approximation works quite well. In Figure 5(b), we can see that theresults of the approximate model are quite close to the actual formulation that takes
false positives into account.
Note that the metrics P(I|E1 ) and P(I|E2 ) are only indicative of the attacker confidence in identifying the initiator, given the observations E1 and E2 . They do not consider the likelihood of the attackers observing E1 and E2 . We use the entropy metricof anonymity [Diaz et al. 2002; Serjantov and Danezis 2002] to take this into account.
The metric relies on computing the entropy of the distribution of possible initiatorsof a path. In the case of Ei, the probability that the identified node is the initiatori) 2. Let H(Ei) be
is P(I|Ei), and the probability assigned to any other node is 1−P(I|E
N−1
the entropy of the system under the observation Ei. Then, the average entropy can becomputed as
H = P(E1 )H(E1 ) + P(E2 )H(E2 ) + (1 − P(E1 ) − P(E2 )) log2 N.
Figure 6 plots the entropy as a function of f , for varying p, using N = 1, 000. Notethat higher values of p have lower entropy, and can thus be considered to provide
worse anonymity under the entropy metric. With higher path lengths, the observation E2 (and E3 , E4 , . . .) is more frequent, even though each observation has lower
confidence. The latter effect dominates, highlighting one of the open questions in anonymity analysis: is it better to have an anonymity system that allows weak attacks
frequently, or strong attacks rarely?
5. SALSA

We shall now analyze Salsa’s path-building mechanism. For anonymous communication, a path is built between the initiator and the recipient via proxy routers (nodes).
Layered encryption ensures that each node knows only its previous and next hop in thepath. The nodes used for the paths are randomly selected from the global pool of nodes,
even though each node has only local knowledge of a small subset of the network.
2 This is a slight simplification; the entropy metric can take into account that, for example, in the case of E ,2

P is more likely to be the initiator than a random node.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:14

P. Mittal and N. Borisov

Fig. 6. Entropy as a function of f .

Fig. 7. Information leak attacks on Salsa.

5.1. Salsa Path-Building

To build a circuit, the initiator chooses r random IDs (Nambiar and Wright [2006], set
r = 3) and redundantly looks up the corresponding nodes (called the first set/stage ofnodes). Keys are established with each of these nodes. Each of the first set of nodes
does a single lookup for r additional nodes (second set of nodes). A circuit is built toeach of the nodes in the second group, relayed through one of the nodes in the firstgroup. Again, the initiator instructs the second set of nodes (via the circuits) to do a
lookup for a final node. One of the paths created between the first and the second setof nodes is selected, and the final node is added to the circuit. We use the parameter l
to refer to the number of stages in the circuit (Nambiar and Wright [2006], set l = 3).
Figure 7(a) depicts the Salsa path-building mechanism for r = 3 and l = 3. Note that
redundant lookups are used only to look up the nodes in the first stage; later lookups
rely on the redundancy in the path-building mechanism itself.
5.2. Active Path Compromise Attacks on Salsa

Active attacks on the lookup mechanism can bias the probability that nodes involvedin Salsa’s path-building mechanism are compromised. Borisov et al. [2007] noted that
Salsa path-building is also subject to a public key modification attack.3 If all the nodes
3

Their analysis did not take into account the lookup bias.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:15

in a particular stage are compromised, they can modify the public keys of the next
set of nodes being looked up. This attack defeats Salsa’s bounds check algorithm that
ensures the IP address is within the right range, since it cannot detect an incorrect
public key. Also, since the traffic toward the node whose public key has been modified
is forwarded via corrupt nodes, the attackers are guaranteed to intercept the messages.
They can then complete the path-building process by emulating all remaining stages(and hence, the last node). The public key modification attack and attacks on Salsa
lookup mechanism are active attacks. By end-to-end timing analysis, the path will becompromised if the first and last nodes in the circuit are compromised. Conventional
analysis of anonymous communication typically focuses on minimizing the chance ofpath compromise attacks. By increasing the redundancy in the path-building mechanism, this chance can be minimized, as increasing r decreases the chance of both active
attacks on lookups, as well as public key modification attacks.
We now describe three types of passive information leak attacks on Salsa. We also
show that increasing redundancy increases the effectiveness of the information leakattacks, resulting in a tradeoff between robustness against active attacks and passive
information leak attacks.
5.3. Conventional Continuous Stage Attack

A path in Salsa can be compromised if there is at least one attacker node in every stageof the path. Suppose that there are attacker nodes A 1 , A 2 , A 3 in the three stages, respectively. In the path-building mechanism, a node performs a lookup for all r nodes
in the following stage implying that A 1 would have looked up A 2 , and A 2 would havelooked up A 3 . Hence the attacker can easily (passively) bridge the first and last stages,
thereby compromising the anonymity of the system. (This attack was mentioned byNambiar and Wright [2006]). Note that if we increase redundancy as per conventional
analysis, the effectiveness of the continuous stage attack also increases. This is because increasing redundancy increases the chance that attackers are present in eachstage (which is 1−(1− f )r), giving them more opportunities to launch this attack. Next,
we describe two new bridging attacks also based on information leaks from lookups.
5.4. Bridging an Honest First Stage

This attack is based on the observation that an initiator performs redundant lookups
for the nodes in the first stage. If the adversary can deduce the identities of the nodes
in the first stage (they need not be compromised) and can detect any of the initiator’s
redundant lookups for nodes in the first stage, the anonymity of the system is compromised. Consider the Figure 7(a); malicious nodes, are depicted in black. The first stage( A 1 , B1 , C1 ) is comprised solely of honest nodes, the second stage (A 2 , B2 , C2 ) has all
malicious nodes; and the third stage, node A 3 , is also compromised. The attackers
know the identities of A 1 , B1 , and C1 because of key establishment with them. If theydetect a node performing a lookup for either A 1 , B1 , or C1 , they can identify that nodeas the initiator. Since the initiator performs nine lookups for the first-stage nodes,
the probability of detecting this initiator is 1 − (1 − f )9 , which translates into a probability of 0.87 for f = 0.2. A similar attack strategy is applicable when only two, oreven one, node in the second stage is compromised. In the latter scenario, the second
stage knows the identity of only a single node in the first stage, and if the initiator is
detected looking up that node, then the path is compromised. This occurs with probability 1 − (1 − f )3 , which is 0.49 for f = 0.2. Similar to the continuous stage attack,notice that an increase in r increases the probability that attackers can detect a lookup
by the initiator for the first node.
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:16

P. Mittal and N. Borisov

Fig. 8. False positives in bridging an honest first stage.

It is important to note that there are some false positives in the attack. The false
positives occur when a node (say A 1 ) in the first stage is involved in building more than
one path. In such a scenario, more than one node will lookup A 1 , and the attackers
may detect a lookup for A 1 not done by the actual initiator. Using the variable x tomodel the amount of lookup traffic by other nodes, as in Section 4.2, we can computethe false positive probability asr
N − 1 x(1−(1− f ) ).
1−
NFigure 8 depicts the false-positive probability for varying r, using f = 0.2, N = 1,000.
N
Note that for x < 100, the false positive probability is less than 0.1%.
5.5. Bridging an Honest Stage

Salsa is also vulnerable to a bridging attack in which attacker nodes separated by astage with all honest nodes are able to deduce that they are on the same path. Consider
the arrangement of nodes depicted in Figure 7(b). The first stage has one malicious
node A 1 ; the second stage consists solely of honest nodes; and the last node A 3 iscompromised. A 1 knows the identities of all three nodes in the second stage, as it has
performed a lookup for them. Also, as part of the path-building mechanism, one of thenodes in the second stage will establish a key with the compromised third-stage node,A 3 . In such a scenario, A 1 and A 3 can deduce that they are part of the same path,as they both observe a common honest node. Similarly, if any of the nodes in the firststage are compromised and the last node is compromised, the path is compromised. Insuch an attack, the compromised nodes in the first stage need not be selected as relays.
Again, recall that increasing r increases the chance of an attacker being present in astage, resulting in a higher probability of bridging an honest
x stage. The probability of, which for x = N/100 andfalse positives in this scenario can be analyzed as 1 − N−1
N
N = 1,000 is less than 1%.
5.6. Results

We now present experimental results for active path compromise attacks and information leak attacks on Salsa. Our results have been computed by modeling the
Salsa path-building mechanism as a stochastic activity network in the Möbius framework [Daly et al. 2000]. For a fixed f and r, the input to the model is the lookup bias,
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:17

Fig. 9. Conventional path compromise attacks: increasing redundancy counters active attacks.

Fig. 10. Information leak attacks: increasing redundancy makes the passive adversary stronger.

which was computed using the Salsa simulator [Nambiar and Wright 2007], with simulation parameters N = 1,000, |G| = 128.
Figure 9 shows the chance of active path compromise attacks on Salsa for varying
levels of redundancy. It is easy to see that increasing r reduces the fraction of compromised paths. For instance, at f = 0.2, 17% paths are compromised using r = 3. The
corresponding value for r = 6 is approximately 8%. This is not surprising, as increasing
r reduces the chance of both active attacks on lookups and attacks involving public-key
modification.
The continuous stage attack and both our bridging attacks are examples of passive
attacks. Figure 10 shows the fraction of compromised paths under the passive attacks.
We can see that an increase in r increases the effectiveness of the passive attacks andis detrimental to anonymity. For 20% of attackers, even for a small value of r = 3, theinitiator can be identified with probability 0.125. Higher values of r can increase theprobability of identifying the initiator to over 0.15. Note also that the bridging attack
significantly improves upon the previous attacks on Salsa: using only the continuous
stage attack for r = 3, f = 0.2, anonymity is broken with a probability of only 0.048—
less than half of what is possible with bridging.
The active path compromise attacks can be combined with passive information leakattacks. Figure 11 shows the fraction of compromised paths for all passive and active
attacks. An interesting trend is observed in which increasing redundancy (beyondr = 2) is detrimental to security for small values of f . This is in sharp contrast to
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:18

P. Mittal and N. Borisov

Fig. 11. All conventional and information leak attacks: for maximal anonymity, r = 3 is optimal for small
f . Note that there is a crossover point at f = 0.1, when r = 6 becomes optimal.

Fig. 12. Comparison of all attacks with conventional active attacks: note that for f > 0.12, fraction ofcompromised paths is greater than f .

conventional analysis; the inclusion of information leak attacks have made the effectof passive attacks more dominant over the effect of active attacks. There is a crossover
point at about 10% malicious nodes, after which increasing r reduces the probabilityof path compromise. This is because active attacks are dominant for higher values off . Note that r = 2 results in significantly worse security because of poor resilience toboth lookup attacks and public key modification attacks.
This shows the tension between passive and active attacks. There is an inherent redundancy in Salsa path-building mechanisms to counter active attacks. However, theredundancy makes the passive adversary stronger and provides more opportunities for
attack. From Figure 12 we can see that by conventional analysis, security provided by
Salsa is close to that of Tor ( f 2 ). With our information leak attacks taken into account,
for f > 0.12, the security provided by Salsa is even worse than f .
5.7. Improvements to Salsa

We next consider whether simple changes to Salsa’s mechanisms would provide a defense against our attacks. First, we consider Salsa using a PKI, as in AP3. The public key modification attack would no longer work; however, other active attacks on
the lookup mechanism and our passive information leak attacks would still apply.
Figure 13 depicts the probability of identifying the initiator under all active and
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:19

Fig. 13. Salsa with a PKI—All conventional and information leak attacks. Even with a PKI, the security of
Salsa is much worse as compared to conventional analysis.

Fig. 14. Effect of varying the path length: note that there is only limited benefit of increasing path length.

passive attacks in Salsa with PKI. Again, we can see the tension between active andpassive attacks. With the public key modification attack gone, r = 2 becomes a morereasonable parameter, but even with a PKI, the fraction of compromised paths increases from 8% under conventional active attacks to more than 30% with our information leak attacks taken into account.
Finally, we explore the effect of increasing the path length (l) on the anonymity of
Salsa. Figure 14 depicts the probability of identifying the initiator for varying valuesof l. There is an interesting tradeoff in increasing the path length. On one hand, increasing l reduces the chance of information leak attacks, because the attacker needs
to bridge all stages. On the other hand, increasing l gives attackers more opportunities
to launch active attacks, thereby increasing the probability that the last node is compromised, which in turn gives attackers more observation points. This is basically acascading effect: the presence of a malicious node in each stage increases the probability of the presence of malicious nodes in the next stage. For small values of f , passive
attacks are stronger, therefore increasing l increases security, but for higher f , theactive attacks and the cascading affect are dominant, therefore increasing l decreases
security.
We have proposed passive bridging attacks on Salsa that are based on information
leaks from lookups, and can be launched by a partial adversary. Moreover, we haveshown a tradeoff between defenses against active and passive attacks. Even at the
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:20

P. Mittal and N. Borisov

optimal point in the tradeoff, the anonymity provided by the system is significantly
worse than what was previously thought. This tradeoff is present even in Salsa witha PKI. Moreover, increasing path length in Salsa has only a limited benefit on user
anonymity.
6. AN ENTROPY-BASED APPROACH FOR INFORMATION LEAKS

So far we had considered lookup anonymity in Salsa to be compromised only if the firsthop (local contact) is malicious. However, information leaks also exist when any of thenodes in the lookup path are malicious, not just the first hop. The difference is thatwhen the first hop is malicious, the lookup initiator is precisely identified, whereas inother cases, the attacker only learns some probabilistic information. We now present
an analysis of this information leak, where instead of using a binary metric of identifying the lookup initiator, we use an entropy-based anonymity metric. This metricconsiders the distribution of potential initiators of the lookup (as computed by the attackers) and computes its Shannon entropy as
H Shannon(I) = −pi log2 pi,

(17)

i

where pi is the probability that node i was the initiator of the lookup. Under someobservation o, we can compute the probability distribution, given o, and compute thecorresponding entropy H(I|o). To model the entropy of the lookup as a whole, we
compute a weighted average of the entropy for each observation (including the null
observation), such that
H(I|O) =P(o)H(I|o),

(18)

o∈O

where P(o) is the probability of observation o occurring, and O is the set of all observations. This is also known as the conditional entropy of I based on observing O.
6.1. Single Lookup

When the lookup is not intercepted by the adversary (null observation), the attacker
clearly does not learn any information and the entropy is log(1 − f )N. Now, let us
consider the case when the lookup is intercepted by the adversary. The adversary canapproximate the identity of the initiator by using the observation o that the previous
hop p in the lookup path is y levels away from it in the binary tree structure. Thus wehave
H(I|O) =P(O = y, p)H(I|O = y, p).

(19)

y, p

To compute the entropy of the lookup, we need to compute P(O = y, p) andH(I|O = y, p). Let us first focus on P(O = y, p). We can decompose P(O = y, p) byconditioning on the the event I = i. We haveP(O = y, p|I = i) · P(I = i),P(O = y, p) =(20)

i honest

where P(I = i) is the prior probability of node I being the initiator, given by
P(I = i) =1.
(1 − f )N(21)

Note that in this analysis, we have conservatively assumed that all users have noa priori linkability to their traffic. We now compute P(O = y, p|I = i). Let us denote
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:21

the distance between node i and the target, in terms of binary tree levels, as D = di.
In the case when y = 0, P(O = y, p|I = i) is simply equal to the probability of the firsthop being malicious ( f ) when p = i.
Next, we have the observation that a jump of size y relative to the malicious hop
has a previous hop which is y levels away from the target node. This means that whendi = y, then P(O = y, p|I = i) is equivalent to a jump from the initiator’s group being
intercepted by a malicious node. The probability of a particular node p being selected
as the first hop in the initiator’s group is N·(1−|G|f )−|G| (considering only honest nodes andexcluding the initiator). The probability of the jump being intercepted at the second
y−1
hop is f , and the probability of observing y under these constraints is 2|G| . To sum up,this event happens with probability N·(1−|G|f )−|G| · f · 2|G| when p is in the initiators group,
and with probability 0 otherwise.
Lastly, let us consider the case y < di. If we suppose that the lookup has traversed lnodes so far (not including the final malicious hop), then we require that these l nodes
be honest, and the final node is malicious. This occurs with probability (1 − f )l · f . We
know that the first hop is always in the initiator’s group, and to get a jump of y, thelookup also traverses the subtree which is y levels away from the target (the selection
probability of which is 12 ). Furthermore, the probability of selecting a particular node|G|1
p in this subtree is 2 y−1· N(1−. With these constraints, the probability of the lookup
f)traversing the remaining l− 2 hops can be computed as a selection problem of choosingl − 2 subtrees out of the possible d − y − 1, where the probability of selection is 12 .
  1 d−y−1· 2This is a binomial distribution with probability d−y−1. Combining all this,l−2
we havey−1

P(O = y, p|I = i) =

⎧
⎪
f
⎪
⎪
⎪
⎨

|G|
2 y−1
N·(1− f )−|G| · f · |G|
d−y+1
|G|
1
⎪
(1 − f )l · f · 12 · 2 y−1· N(1−·⎪
f)⎪ l=2

⎪
y−1
d−y−1
⎩
1 d−y−1 2
· (2)
· |G|
l−2

y = 0, i = p
i, p ∈ same group(22)

otherwise.

Using P(I = i) and P(O = y, p|I = i) from Equations (21) and (22), we can now
compute P(O = y, p) from Equation (20).
Let us now compute H(I|O = y, p). By definition, we have
H(I|O = y, p) = −P(I = i|O = y, p) log P(I = i|O = y, p).

(23)

i honest

Since we have already computed P(O = y, p|I = i), P(I = i), and P(O = y, p) in
Equations (22), (21), and (20), respectively, we can use Bayesian inference to compute
P(I = i|O = y, p) as
P(I = i|O = y, p) =P(O = y, p|I = i) · P(I = i).
P(O = y, p)(24)

By using P(O = y, p) from Equation (20) and H(I|O = y, p) from Equation (23),
we can compute the entropy of the lookup from Equation (19).
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:22

P. Mittal and N. Borisov

Fig. 15. Lookup entropy.

6.2. Redundant Lookups

Let us denote the attackers’ observations for the r redundant lookups as o 1 =y1 , p1 , . . . , o r = yr, pr .
···

H(I|O) =y1 , p1P({o j = y j, p j}rj=1 )H(I|{o j = y j, p j}rj=1 )(25)

yr , prSimilar to the case of single lookup, we can condition the probability P({o j =y j, p j}rj=1 ) on the event I = i. Using the observation that the redundant lookups are
independent, given I = i, we can compute P({o j = y j, p j}rj=1 ) asP({o j = y j, p j}rj=1 ) =P({o j = y j, p j}rj=1 |I = i) · P(I = i),(26a)i honest

P({o j = y j, p j}rj=1 ) =rP(o k = yk , pk |I = i) · P(I = i),(26b)i honest k=1

where P(O = y, p|I = i) and P(I = i) are given by Equations (22) and (21). Let us now
compute H(I|{o j = y j, p j}rj=1 ).
H(I|{o j = y j, p j}rj=1 ) =−P(I = i|{o j = y j, p j}rj=1 ) log P(I = i|{o j = y j, p j}rj=1 ).

(27)

i honest

Again, we make use of Bayesian inference to combine information from multiple
observations as follows.
P({o j = y j, p j}rj=1 |I = i) · P(I = i)r
P(I = i|{o j = y j, p j} j=1 ) =,(28a)
P({o j = y j, p j}rj=1 )r
P(o k = yk , pk |I = i) · P(I = i)
= k=1
.
(28b)
P({o j = y j, p j}rj=1 )Finally, we can use Equation (25) to compute the entropy of redundant lookups.
Figure 15(a) plots the entropy of the lookup as a function of the fraction of compromised nodes in the system, for varying values of redundancy. The input parameters
for our model were N = 1,000, |G| = 128. We can see that by considering the all possible information leaks from the lookup, the lookup entropy is considerably reduced,
as compared to the scenario where we considered information leaks only from the first
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:23

Fig. 16. Path entropy.

hop. When the fraction of compromised nodes is 20% and the redundancy level is r = 3,
then using the complete information reduces the lookup entropy from about 5 bits to
3.2 bits (Shannon entropy). In addition to Shannon entropy, Figure 15(a) also presents
results for min-entropy. The min-entropy is computed as
H Min(I) = − log2 max pi.

(29)

We can see that for f = 0.2, r = 3, using complete information reduces the minentropy by more than half from 5 bits to 2.4 bits. Finally, we also present the guessing
entropy for the Salsa lookup in Figure 15(b). The guessing entropy can be computedby first arranging the nodes in decreasing order of probability pi and then using theequation
HGuessing (I) = i pi · i.

(30)

We can see that f = 0.2, r = 3, using complete information reduces the guessing
entropy by more than a third from 210 guesses to only 66 guesses. Our analysis illustrates that our security evaluation for Salsa’s path-building mechanism is a conservative analysis, and the actual anonymity loss due to information leaks via lookups
would be even greater than our results suggest.
6.3. Path Construction

Our entropy-based analysis of lookups suggests that the anonymity provided by thepath-construction mechanism is likely to be even lower than our results shown in
Section 5. This is because our earlier results on path construction considered only
scenarios where exact identification of the initiator is possible and ignored the significant amount of probabilistic information that an adversary has.
Consider our attack that involves bridging an honest first stage. In this setting, theadversary controls the final node and has knowledge of at least one node in the firststage. In our earlier results, we had considered the user anonymity to be compromised
if the adversary is able to exactly identify the initiators based on its lookups for thenode(s) in the first stage. Instead, we can now compute the initiator entropy based on
its lookups for the first-stage nodes. If the adversary knows x < r nodes in the firststage (and the last node is compromised), then the initiator entropy is equivalent to
the lookup entropy with redundancy parameter x · r.
Figure 16 shows the reduction in the anonymity (Shannon entropy) based on the
additional probabilistic information, while bridging the first honest stage alone. We
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:24

P. Mittal and N. Borisov

have left a complete analysis of Salsa’s path-building mechanism using the entropy
based metric as part of future work.

7. RELATED WORK

Secure routing in peer-to-peer networks has been the subject of much research [Castro
et al. 2002; Kapadia and Triandopoulos 2008; Nambiar and Wright 2006; Sit andMorris 2002; Wallach 2002]. We studied lookup mechanisms proposed by Castro et al.
[2002] and Nambiar and Wright [2006], focusing on the information leak from lookups,
and observed a tradeoff between security and anonymity of a lookup. Kapadia andTriandopoulos recently proposed Halo [2008], which is also based on redundant routing and exhibits a similar tradeoff. Moreover, it uses very high redundancy levels, ascompared to Salsa, and would make our information leak attacks more effective. There
have been some attempts to add anonymity to a lookup. Borisov [2005] proposed ananonymous DHT based on Koorde [Kaashoek and Karger 2003], which performs a
randomized routing phase before an actual lookup. Ciaccio [2006] proposed the use ofimprecise routing in DHTs to improve sender anonymity. These lookups were designed
to be anonymous but not secure: an active adversary could easily subvert the path ofthe lookup. As such, neither lookup mechanism can be used to build anonymous circuits. Recently, Panchenko et al. [2009] proposed to build anonymity into a secure
lookup mechanism, but Wang et al. [2010] showed that it is possible to compromise
lookup anonymity.
Danezis and Clayton [2006] studied attacks on peer discovery and route setup inanonymous peer-to-peer networks. They show that if the attacker learns the subset
of nodes known to the initiator (by observing lookups, for example), its routes canbe fingerprinted, unless the initiator knows about the vast majority of the network.
Danezis and Syverson [2007] extend this work to observe that an attacker who learns
that certain nodes are unknown to the initiator can carry out attacks, as well, andseparate traffic going through a relay node. These attacks are similar in spirit to theones we propose, but rather than absolute knowledge of the initiator’s routing state, we
use probabilistic inferences based on observed lookups. Recently, Bauer et al. [2007]
proposed a bridging attack in Tor where attacker nodes sandwiching an honest nodecan correlate the path, even before a packet is sent. This attack is similar to ourbridging attack on Salsa, except that we also utilize information leaks from lookups
and consider the issue of false positives.
Reiter and Rubin [1998] proposed the predecessor attack, which was later extended
by Wright et al. [2002, 2003, 2004]. In this attack, an attacker tracks an identifiable
stream of communication over multiple communication rounds and logs the preceding node on the path. To identify the initiator, the attacker uses the observation thatthe initiator is more likely to be the predecessor than any other node in the network.
For peer-to-peer anonymous communication systems like Salsa, the number of rounds
required by predecessor attacks to identify the initiator with high probability is inversely proportional to the probability of success of end-to-end timing analysis. Thismeans that defenses that minimize the chance of both first and last nodes being attackers also increase resilience against predecessor attacks. In this article, we only
analyzed the scenario in which an initiator constructs a single communication path tothe destination. We leave a complete analysis for multiple communication rounds aspart of future work.
Similar to predecessor attacks, there is a thread of research that deals with degradation of anonymity over a period of time. Berthold et al. [2000] and Raymond [2000]
propose intersection attacks that aim to compromise sender anonymity by intersecting
ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:25

sets of user’s that were active at the time the intercepted message was sent, over multiple communication rounds. Similarly, Kesdogan et al. [2002] use intersection to findrecipients of a given users message. A statistical version of this attack was proposed byDanezis [2003] and later extended by Mathewson and Dingledine [2004]. Information
leaks in P2P systems can allow even a partial adversary to make observations about alarge fraction of lookups and path-building, and can, therefore, form a basis of effective
statistical intersection and disclosure attacks.
An important point of our article is that, when building anonymous systems, it isimportant not to abstract away the properties of the system that can affect anonymity.
Our analysis of AP3 is an example of how composition of two designs that are secureindividually [Castro et al. 2002; Reiter and Rubin 1998] creates new vulnerabilities.
Similar in spirit to ours, a lot of recent research has focused on details abstracted away
by conventional analysis models to break the anonymity of the system. Such details
include congestion and interference [Back et al. 2001; Murdoch and Danezis 2005],
clock skew [Murdoch 2006], heterogeneous path latency [Back et al. 2001; Hopper et al.
2007], the ability to monitor Internet exchanges [Murdoch and Zieliński 2007], andreliability [Borisov et al. 2007].
8. CONCLUSION

We have analyzed information leaks in the lookup mechanisms of peer-to-peer anonymous communications systems. Existing defenses against active attacks typically use
redundant messages, which enable a relatively small fraction of attackers to observe alarge number of lookups in the network. Attackers are thus able to act as a near-global
passive adversary and use this to break the anonymity of the system.
We have shown how attacks based on information leaks from lookups can be used tobreak the probable innocence guarantees in AP3. We computed the limit on the number of attackers that AP3 can handle while providing probable innocence as only 5% in
the typical case, while the theoretical limit with increased path lengths is 10%. This
is in contrast to the conventional analysis, which puts these figures at 33% and 50%,
respectively. A small fraction of malicious nodes can therefore compromise the securityof AP3. An important lesson learned from the AP3 analysis is that the composition of
a secure DHT lookup mechanism with an anonymous communication protocol (as has
been considered in other work [Sherr et al. 2007]) should be carefully analyzed, as it
is likely to introduce additional vulnerabilities.
We have also analyzed the security of Salsa under both active and passive attacks.
We have demonstrated the tension that exists between defending against both active
and passive adversaries. Defending against active adversaries requires higher redundancy, which increases the threat of passive attacks. Salsa was previously reported
to tolerate up to 20% compromised nodes, but our results show that, with information
leaks taken into account, over a quarter of all tunnels are compromised. Moreover,
we show that the tension between active and passive attacks exists even if Salsa wereto use a PKI. Also, increasing path lengths to counter our passive attacks only has alimited benefit, and in some cases, it even reduces anonymity.
Our results demonstrate that information leaks are an important part of anonymity
analysis of a system.
ACKNOWLEDGMENTS
We would like to thank Arjun Nambiar, Nayantara Malesh, and Matthew Wright for providing us with
the Salsa simulator and for helpful discussions about the Salsa algorithms. We are also grateful to George
Danezis and Matthew Wright for their comments on earlier versions of this paper.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:26

P. Mittal and N. Borisov

REFERENCESB ACK , A., M ÖLLER , U., AND S TIGLIC, A. 2001. Traffic analysis attacks and trade-offs in anonymity providing systems. In Proceedings of the Information Hiding Workshop. I. S. Moskowitz Ed., Lecture Notes in
Computer Science, vol. 2137. Springer, 245–247.
B AUER , K., M C C OY, D., G RUNWALD, D., K OHNO, T., AND S ICKER , D. 2007. Low-resource routing attacks
against Tor. In Proceedings of the ACM Workshop on Privacy in the Electronic Society. T. Yu Ed., ACM,
New York, NY, 11–20.
B ELLOVIN, S. M. AND WAGNER , D. A., Eds. 2003. In Proceedings of the IEEE Symposium on Security andPrivacy. IEEE Computer Society Press, Los Alamitos, CA.
B ERTHOLD, O., F EDERRATH , H., AND K ÖHNTOPP, M. 2000. Project “anonymity and unobservability in theInternet”. In Proceedings of the 10th Conference on Computers, Freedom and Privacy. L. Cranor Ed.,
ACM, New York, NY, 57–65.
B ORISOV, N. 2005. Anonymous routing in structured peer-to-peer overlays. Ph.D. thesis, UC Berkeley.
B ORISOV, N., D ANEZIS, G., M ITTAL , P., AND T ABRIZ , P. 2007. Denial of service or denial of security? How
attacks on reliability can compromise anonymity. In Proceedings of the 14th ACM Conference on Computer and Communications Security. 92–102.
B OUCHER , P., S HOSTACK , A., AND G OLDBERG, I. 2000. Freedom systems 2.0 architecture. White paper,
Zero Knowledge Systems, Inc.
C ASTRO, M., D RUSCHEL , P., G ANESH , A., R OWSTRON, A., AND WALLACH , D. S. 2002. Secure routing
for structured peer-to-peer overlay networks. In Proceedings of the USENIX Symposium on Operating
Systems Design and Implementation. D. Culler and P. Druschel Eds., USENIX, Berkeley, CA, 299–314.
C IACCIO, G. 2006. Improving sender anonymity in a structured overlay with imprecise routing. In Proceedings of the 6th Workshop on Privacy Enhancing Technologies. 190–207.
C LARKE , I., S ANDBERG, O., W ILEY, B., AND H ONG, T. W. 2001. Freenet: A distributed anonymous
information storage and retrieval system. In Proceedings of the International Workshop on Designing
Privacy Enhancing Technologies: Design Issues in Anonymity and Unobservability. Springer Verlag,
Berlin, 46–66.
C OOKE , E., J AHANIAN, F., AND M C P HERSON, D. 2005. The zombie roundup: Understanding, detecting, anddisrupting botnets. In Proceedings of the Steps to Reducing Unwanted Traffic on the Internet Workshop.
USENIX Association, Berkeley, CA, 6–6.
D ALY, D., D EAVOURS, D. D., D OYLE , J. M., W EBSTER , P. G., AND S ANDERS, W. H. 2000. Möbius: An extensible tool for performance and dependability modeling. In Computer Performance Evaluation. ModellingTechniques and Tools. B. R. Haverkort, H. C. Bohnenkamp, and C. U. Smith Eds., Lecture Notes in
Computer Science, vol. 1786. Springer, 332–336.
D ANEZIS, G. 2003. Statistical disclosure attacks: Traffic confirmation in open environments. In Proceedings of the IFIP TC11 18th International Conference on Information Security (SEC). D. Gritzalis,
S. di Vimercati, P. Samarati, and S. Katsikas Eds., 421–426.
D ANEZIS, G. AND C LAYTON, R. 2006. Route fingerprinting in anonymous communications. In Proceedingsof the IEEE Conference on Peer-to-Peer Computing. IEEE Computer Society, Los Alamitos, CA, 69–72.
D ANEZIS, G. AND G OLLE , P., Eds. 2006. In Proceedings of the Privacy Enhancing Technologies. Lecture
Notes in Computer Science, vol. 4258. Springer, Berlin.
D ANEZIS, G. AND S YVERSON, P. 2007. Bridging and fingerprinting: Epistemic attacks on route selection.
In Proceedings of the Privacy Enhancing Technologies Symposium. N. Borisov and I. Goldberg Eds.,
Lecture Notes in Computer Science, vol. 5134. Springer, Berlin, 151–166.
D ANEZIS, G., D INGLEDINE , R., AND M ATHEWSON, N. 2003. Mixminion: Design of a Type III anonymous
remailer protocol. In Proceedings of the IEEE Symposium on Security and Privacy. 2–15.
D IAZ , C., S EYS, S., C LAESSENS, J., AND P RENEEL , B. 2002. Towards measuring anonymity. In Proceedingsof the Workshop on Privacy Enhancing Technologies. 184–188.
D INGLEDINE , R. AND S YVERSON, P., Eds. 2002. In Proceedings of the Workshop on Privacy Enhancing
Technologies. Lecture Notes in Computer Science, vol. 2482. Springer.
D INGLEDINE , R., M ATHEWSON, N., AND S YVERSON, P. 2004. Tor: The second-generation onion router. In
Proceedings of the USENIX Security Symposium. M. Blaze Ed., USENIX Association, Berkeley, CA,
303–320.
D OUCEUR , J. 2002. The sybil attack. In Proceedings of the 1st Workshop on Peer-to-Peer Systems. 251–260.
D RUSCHEL , P., K AASHOEK , F., AND R OWSTRON, A., Eds. 2002. In Proceedings of the 1st International
Workshop on Peer-to-Peer Systems (IPTPS). Lecture Notes in Computer Science, vol. 2429. Springer,
Berlin.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems

5:27

F EDERRATH , H., Ed. 2000. In Proceedings of the International Workshop on Design Issues in Anonymity andUnobservability. Lecture Notes in Computer Science, vol. 2009. Springer, Berlin.
F REEDMAN, M. J. AND M ORRIS, R. 2002. Tarzan: A peer-to-peer anonymizing network layer. In Proceedingsof the ACM Conference on Computer and Communications Security. R. Sandhu Ed., ACM, New York,NY, 193–206.
G OODIN, D. 2007. Tor at heart of embassy passwords leak. The Register.
H OLZ , T., S TEINER , M., D AHL , F., B IERSACK , E., AND F REILING, F. 2008. Measurements and mitigationof peer-to-peer-based botnets: A case study on storm worm. In Proceedings of the 1st USENIX Workshop
on Large-scale Exploits and Emergent Threats. F. Monrose Ed., USENIX Association, Berkeley, CA.
H OPPER , N., VASSERMAN, E. Y., AND C HAN -T IN, E. 2007. How much anonymity does network latency
leak? In Proceedings of the 14th ACM Conference on Computer and Communications Security. 82–91.
I2P. 2003. I2P anonymous network. http://www.i2p2.de/index.html.
K AASHOEK , M. F. AND K ARGER , D. R. 2003. Koorde: A simple degree-optimal distributed hash table. In
Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS). F. Kaashoek and I. Stoica
Eds., Lecture Notes in Computer Science, vol. 2735. Springer, Berlin, 98–107.
K APADIA , A. AND T RIANDOPOULOS, N. 2008. Halo: High-assurance locate for distributed hash tables. In
Proceedings of the Network and Distributed System Security Symposium. C. Cowan and G. Vigna Eds.,
Internet Society, Reston, VA, 61–79.
K ESDOGAN, D., A GRAWAL , D., AND P ENZ , S. 2002. Limits of anonymity in open environments. In Proceedings of the Information Hiding Workshop. F. A. Petitcolas Ed., Lecture Notes in Computer Science,
vol. 2578. Springer, Berlin, 53–69.
M ATHEWSON, N. AND D INGLEDINE , R. 2004. Practical traffic analysis: Extending and resisting statistical disclosure. In Proceedings of the Workshop on Privacy Enhancing Technologies. D. Martin and
A. Serjantov Eds., Lecture Notes in Computer Science, vol. 3424. Springer, Berlin, 17–24.
M C L ACHLAN, J., T RAN, A., H OPPER , N., AND K IM , Y. 2009. Scalable onion routing with torsk. In Proceedings of the 16th ACM Conference on Computer and Communications Security (CCS’09). ACM, New York,NY, 590–599.
M ISLOVE , A., O BEROI , G., P OST, A., R EIS, C., D RUSCHEL , P., AND WALLACH , D. S. 2004. AP3: Cooperative, decentralized anonymous communication. In Proceedings of the ACM SIGOPS European Workshop.
M. Castro Ed., ACM, New York, NY, 30.
M ITTAL , P. AND B ORISOV, N. 2009. Shadowwalker: Peer-to-peer anonymous communication using redundant structured topologies. In Proceedings of the 16th ACM Conference on Computer and Communications Security (CCS’09). ACM, New York, NY, 161–172.
M ÖLLER , U., C OTTRELL , L., PALFRADER , P., AND S ASSAMAN, L. 2003. Mixmaster Protocol—version 2.
IETF Internet Draft.
M URDOCH , S. J. 2006. Hot or not: Revealing hidden services by their clock skew. In Proceedings of the 13th
ACM Conference on Computer and Communications Security. 27–36.
M URDOCH , S. J. AND D ANEZIS, G. 2005. Low-cost traffic analysis of Tor. In Proceedings of the IEEE Symposium on Security and Privacy. V. Paxson and M. Waidner Eds., IEEE Computer Society Press, Los
Alamitos, CA, 183–195.
M URDOCH , S. J. AND Z IELI ŃSKI , P. 2007. Sampled traffic analysis by Internet-exchange-level adversaries.
In Proceedings of the Privacy Enhancing Technologies Symposium. N. Borisov and P. Golle Eds., Lecture
Notes in Computer Science, vol. 4776. Springer, 167–183.
N AMBIAR , A. AND W RIGHT, M. 2006. Salsa: A structured approach to large-scale anonymity. In Proceedingsof the 13th ACM Conference on Computer and Communications Secuity. 17–26.
N AMBIAR , A. AND W RIGHT, M. 2007. The Salsa simulator.
http://ranger.uta.edu/~ mwright/code/salsa-sims.zip.
PANCHENKO, A., R ICHTER , S., AND R ACHE , A. 2009. Nisan: Network information service for anonymization networks. In Proceedings of the 16th ACM Conference on Computer and Communications Security(CCS’09). ACM, New York, NY, 141–150.
R AJAB, M., Z ARFOSS, J., M ONROSE , F., AND T ERZIS, A. 2006. A multifaceted approach to understanding
the botnet phenomenon. In Proceedings of the Internet Measurement Conference. P. Barford Ed., ACM,
New York, NY, 41–52.
R AYMOND, J.-F. 2000. Traffic analysis: Protocols, attacks, design issues, and open problems. In Proceedingsof the International Workshop on Design Issues in Anonymity and Unobservability. 10–29.
R EITER , M. AND R UBIN, A. 1998. Crowds: Anonymity for Web transactions. ACM Trans. Inf. Syst. Sec. 1, 1,
66–92.

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.

5:28

P. Mittal and N. Borisov

R ENNHARD, M. AND P LATTNER , B. 2002. Introducing MorphMix: Peer-to-peer based anonymous Internet
usage with collusion detection. In Proceedings of the Workshop on Privacy in Electronic Society. ACM,
New York, NY, 91–102.
R OWSTRON, A. AND D RUSCHEL , P. 2001. Pastry: Scalable, distributed object location and routing for largescale peer-to-peer systems. In Proceedings of the IFIP/ACM International Conference on Distributed
Systems Platforms (Middleware). G. Goos, J. Hartmanis, and J. van Leeuwen Eds., Lecture Notes in
Computer Science, vol. 2218. Springer, Berlin, 329–350.
S ERJANTOV, A. AND D ANEZIS, G. 2002. Towards an information theoretic metric for anonymity. In Proceedings of the Workshop on Privacy Enhancing Techonologies. 259–263.
S HERR , M., L OO, B. T., AND B LAZE , M. 2007. Towards application-aware anonymous routing. In
Proceedings of the 2nd USENIX Workshop on Hot Topics in Security. USENIX Association, Berkeley, CA,
4:1–4:5.
S IT, E. AND M ORRIS, R. 2002. Security considerations for peer-to-peer distributed hash tables. In Proceedings of the 1st International Workshop on Peer-to-Peer System. 261–269.
S TOICA , I., M ORRIS, R., L IBEN -N OWELL , D., K ARGER , D. R., K AASHOEK , M. F., D ABEK , F., AND B ALAKR ISHNAN, H. 2003. Chord: A scalable peer-to-peer lookup protocol for Internet applications. IEEE/ACM
Trans. Netw. 11, 1, 17–32.
S YVERSON, P., T SUDIK , G., R EED, M., AND L ANDWEHR , C. 2000. Towards an analysis of onion routing security. In Proceedings of the International Workshop on Design Issues in Anonymity and Unobservability.
96–114.
T ABRIZ , P. AND B ORISOV, N. 2006. Breaking the collusion detection mechanism of MorphMix. In Proceedings of the 6th Workshop on Privacy Enhancing Techonologies. 368–383.
T HE T OR P ROJECT. Tor metrics portal, http://metrics.torproject.org/ (last accessed 2/11).
WALLACH , D. 2002. A survey of peer-to-peer security issues. In Proceedings of the International Symposium
on Software Security. M. Okada, B. Pierce, A. Scedrov, H. Tokuda, and A. Yonezawa Eds., Lecture Notes
in Computer Science, vol. 2609. Springer, Berlin, 253–258.
WANG, Q., M ITTAL , P., AND B ORISOV, N. 2010. In search of an anonymous and secure lookup: Attacks on
structured peer-to-peer anonymous communication systems. In Proceedings of the ACM Conference on
Computer and Communications Security (CCS’10). A. D. Keromytis and V. Shmatikov Eds., ACM.
W RIGHT, M., A DLER , M., L EVINE , B. N., AND S HIELDS, C. 2002. An analysis of the degradation of anonymous protocols. In Proceedings of the Network and Distributed System Security Symposium. P. vanOorschot and V. Gligor Eds., The Internet Society, Reston, VA, 39–50.
W RIGHT, M., A DLER , M., L EVINE , B. N., AND S HIELDS, C. 2003. Defending anonymous communication
against passive logging attacks. In Proceedings of the IEEE Symposium on Security and Privacy. 28–41.
W RIGHT, M., A DLER , M., L EVINE , B. N., AND S HIELDS, C. 2004. The predecessor attack: An analysis of athreat to anonymous communications systems. ACM Trans. Inf. Syst. Secur. 4, 7, 489–522.
W RIGHT, R. AND DI V IMERCATI , S. D. C., Eds. 2006. In Proceedings of the The 13th ACM Conference on
Computer and Communications Security. ACM, New York, NY.
W RIGHT, R. AND S YVERSON, P., Eds. 2007. In Proceedings of the 14th ACM Conference on Computer andCommunications Security. ACM, New York, NY.
Z ETTER , K. 2010. Wikileaks and Tor. http://www.wired.com/threatlevel/2010/06/wikileaks-documents/.
Received March 2009; revised February 2011; accepted June 2011

ACM Transactions on Information and System Security, Vol. 15, No. 1, Article 5, Publication date: March 2012.