TorPolice: Towards Enforcing Service-Defined Access Policies
for Anonymous Communication in the Tor Network
Zhuotao Liu∗ , Yushan Liu† , Philipp Winter† , Prateek Mittal† , Yih-Chun Hu∗∗ University of Illinois at Urbana-Champaign, † Princeton University∗ {zliu48, yihchun}@illinois.edu, † {yushan, pwinter, pmittal}@princeton.edu

Abstract—Tor is the most widely used anonymity network,
currently serving millions of users each day. However, there
is no access control in place for all these users, leaving the
network vulnerable to botnet abuse and attacks. For example,
criminals frequently use exit relays as stepping stones for attacks,
causing service providers to serve CAPTCHAs to exit relay IP
addresses or blacklisting them altogether, which leads to severe
usability issues for legitimate Tor users. To address this problem,
we propose TorPolice, the first privacy-preserving access control
framework for Tor. TorPolice enables abuse-plagued service
providers such as Yelp to enforce access rules to police andthrottle malicious requests coming from Tor while still providing
service to legitimate Tor users. Further, TorPolice equips Torwith global access control for relays, enhancing Tor’s resilience
to botnet abuse. We show that TorPolice preserves the privacyof Tor users, implement a prototype of TorPolice, and perform
extensive evaluations to validate our design goals.

I. I NTRODUCTIONCounting almost two million daily users, the Tor network
is among the most popular digital privacy tools. As of May
2017, the network consists of over 7,000 volunteer-run relays,
carrying over 100 Gbps of traffic [2]. Tor clients build a path
(also known as Tor circuit) consisting of three relays (guard,
middle and exit) to reach service providers such as Yelp
or WikiLeaks. Tor is used by law enforcement, intelligenceagencies, political dissidents, journalists, whistle-blowers, andordinary citizens to enhance their online privacy [3].
Today’s Tor network does not implement any access control
mechanism, meaning that anyone with a Tor client can use
the network without limitation. While the lack of access
control fosters network growth, it has also caused various
problems, most importantly botnet abuse [15]. In practice,botnets use Tor to attack third-party services, spam comment
sections on websites, scrape content, and scan services forvulnerabilities [27]. In response, many service providers andcontent delivery networks (CDNs) have started to treat Tor
users as “second-class” Web citizens [19], by either forcing
Tor users to solve numerous CAPTCHAs or blocking Tor exit
relay IP addresses altogether.
Another type of botnet-related abuse of Tor arises fromcommand and control (C&C) servers run as Tor onion services(used be to known as hidden services) [12, 15]. In thepast, such events caused a rapid spike in the number of
Tor clients [15]. Besides the reputational issue of Tor being
associated with botnet infrastructure, the massive number
978-1-5090-6501-1/17/$31.00 c 2017 IEEEof circuit creation requests from botnets is a heavy burden
on Tor relays, causing significant performance degradation
for legitimate Tor users (e.g., frequent Tor circuit failures).
Other types of botnet abuse include paralyzing Tor relays via
relay flooding attacks [4, 5] and performing large-scale traffic
analysis via throughput or congestion fingerprinting [23, 25].
Contributions. In this paper, we present TorPolice, the firstprivacy-preserving access control framework for the Tor network. Leveraging cryptographically computed network capabilities, TorPolice enables service providers to define accesspolicies for Tor connections, allowing them to throttle Toremitted abuse while still serving legitimate Tor users. Thus,
TorPolice offers a more viable alternative to abuse-plagued
service providers than simply blocking all Tor connections.
Further, TorPolice improves the Tor network’s resilience tovarious botnet abuses by enabling global access control for
Tor relays. Crucially, TorPolice achieves these benefits whilestill retaining Tor’s anonymity guarantees.
TorPolice’s design introduces a set of fully distributed andpartially trusted access authorities (AAs) to manage andcertify capabilities. To request capabilities from AAs, Torclients must first obtain anonymous capability seeds which
are types of resources that are costly to scale. Both service
providers and the Tor network provide differentiated service
to Tor clients that possess valid capabilities so to enforce
self-defined access rules. The AAs generate capabilities using
blind signatures [6] to break the linkability between capability
requesting and capability spending. We conduct a rigorous
security analysis to prove that TorPolice does not weaken
privacy guarantees offered by the current Tor network.
We implement a prototype of TorPolice to demonstrate
its practicality and evaluate the prototype extensively on our
testbed, in the Shadow simulator [17], and via simulations. Our
results show that TorPolice can effectively enforce serviceselected access policies and mitigate large-scale botnet abuses
against Tor at the cost of negligible overhead.
II. P ROBLEM F ORMULATION
A. Tor BackgroundTor clients anonymously connect to service providers (e.g.,
WikiLeaks) by building three-hop circuits consisting of aguard, middle, and exit relay. Tor’s use of layered encryption
ensures that each relay only knows the identities of its direct
neighbors (i.e., the previous and next hop in the circuit).
Clients randomly select these relays, weighted by the relays’

bandwidth and their positions in the circuit. A list of all
Tor relays—the network consensus—is published hourly bya set of nine globally-distributed directory authorities thatare run by volunteers trusted by the Tor Project. While thedirectory authorities and guard relays learn a Tor client’s
network identity (i.e., its IP address), they cannot observe theclient’s online activity. Exit relays, however, can monitor theclient’s activity, but do not know its identity. Tor’s anonymity
stems from unlinking network identity from activity.
Further, Tor allows servers to host their service anonymously over Tor onion services (OS). Once an OS is set up, it
creates circuits to at least three relays serving as its introduction points (IPs). Then, the OS publishes its descriptor—whichcontains the IPs—to a distributed hash table that consists ofa subset of all Tor relays. To connect to the OS, a Tor client
first fetches the OS’s descriptor using its onion address, andthen builds two circuits: one to an IP and another one to arandomly-selected relay called the rendezvous point (RP). The
client instructs the IP to send the identity of the RP to the OS,
which then creates a circuit to the RP to be able to finallycommunicate with the client.
B. Design Goals
TorPolice adds access control to the anonymous communication in Tor, benefiting both service providers and the Tor
network. Different from prior capability based schemes [20,21, 26, 31], TorPolice’s design needs to address a unique
combination of the following three challenges: (i) preserving
Tor’s anonymity guarantees, (ii) avoiding central points ofcontrol, and (iii) being incrementally deployable.
Service-defined Access Policies. Project Honey Pot lists
nearly 70% of all Tor exit relays as comment spammers [27],causing many service providers and CDNs to block and filter
traffic originating from the Tor network. To reduce this tension
between Tor users and service providers, TorPolice must allow
service providers to define and enforce access rules for Tor
connections, allowing them to effectively throttle Tor-emitted
abuse while still serving legitimate Tor users.
Mitigate Botnet Abuse Against Tor. Being a service provider
itself, the Tor network is also subject to botnet abuse, such
C&C servers hosted as onion services, and (D)DoS attacks
against (select) relays. TorPolice allows the Tor network tocontrol the network usage of Tor clients, making it possible
to throttle the abuse. In contrast to local rate limiting by eachrelay, TorPolice’s access control mechanism is global, meaningthat an adversary cannot circumvent our defense by simply
connecting to all Tor relays.
Preserving Tor User Privacy. TorPolice must not degrade
Tor’s anonymity guarantees. While we add a new layer offunctionality to Tor (access control), this layer—like Tor
itself—unlinks a client’s identity from its activity.
Fully Distributed and Partially Trusted Authorities. In
accordance with Tor’s design philosophy of distributing trust,
TorPolice relies on a set of fully distributed and partiallytrusted access authorities (AAs) to manage capabilities. An
AA is operated either by the Tor Project, a service provider,

AA1

AA2

TTP AA…
1. Capability
Seed

2. Pre-capabilities

Fully-distributed AAs
5. Site-SpecificCapability Verification

TorPolice-enhanced
Service Provider

Tor
Client3. Site-SpecificCapability Computation

Tor
Client4. Site-Specific

Tor Network capability Spending

4. Relay-SpecificCapability Spending

3. Relay-SpecificCapability Computation

Tor Network
VanillaService Providers
5. Relay-SpecificCapability Verification

Fig. 1: The architecture of TorPolice. A Tor client (step 1)
anonymously sends its capability seed to an randomly selected
AA to request pre-capabilities (step 2), based on which the clientcomputes site(relay)-specific capabilities (step 3). The client thenspends capabilities on either service access or Tor circuit creation(step 4). The capability recipients validate capabilities before
allowing services (step 5).

or a trusted third party. Since Tor clients are free to choose
any AA to request capabilities using their capability seeds,
no single AA has a global view on all Tor clients. Further,each AA is only partially trusted and a service provider canblacklist any misbehaving or compromised AA.
Incrementally Deployable. TorPolice must be incrementally deployable. Up-to-date Tor clients, relays, and service
providers can benefit from a partially-deployed TorPolice immediately while outdated entities can continue their operations.
Elided Design Goals. Various attacks seek to break Tor’s
unlinkability. For instance, an AS-level adversary may deanonymize a Tor user’s Internet activities if the adversary
can monitor both ingress and egress traffic [30]. TorPolice is
not designed to mitigate attacks on unlinkability. Instead, we
preserve the unlinkability currently offered by Tor.
C. Adversary Model and Assumptions
We consider a Byzantine adversary that deviates from ourprotocol and abuses Tor in arbitrary ways. The adversary canuse Tor to abuse third-party services, e.g., by scraping content,
spamming comments, and scanning for vulnerabilities. The
adversary may also abuse the Tor network directly, e.g., byusing Tor OSes as C&C servers, performing traffic analysis,or launching (D)DoS attacks against Tor relays. The adversary
may control many bots, and hence a significant amount of
resources. The bots can act passively (e.g., monitor Tor traffic)
or actively (e.g., spoof and manipulate packets). We assume
that the AAs are well-connected to the Internet backbone sothat volumetric DDoS attacks against the whole set of AAs canbe mitigated. Tor’s existing directory authorities are subject
to the same assumption. In practice, one way to assure thisassumption is relying on DDoS prevention vendors [21].
III. D ESIGN OVERVIEW
In a nutshell, TorPolice is a generic access control framework based on capabilities. TorPolice enables both service
providers and the Tor network itself to enforce access control

on Tor clients to mitigate various types of botnet abuse causedby the lack of access control. To this end, we consider two
types of capabilities: site-specific capabilities for accessing
TorPolice-enhanced service providers through Tor, and relayspecific capabilities for creating TorPolice-enhanced Tor circuits. Both types of capabilities are signed by a set of fullydistributed Access Authorities (AAs) that are deployed either
by the Tor Project, service providers, or trusted third parties.
To request capabilities from a particular AA, a Tor client isrequired to possess a capability seed—basically a costly-toscale resource—accepted by the AA. Each AA accepts onlya single type of capability seed. Since Tor clients are free
to choose their AAs, no single AA has a global view on all
Tor clients. TorPolice employs blind signatures [6] to unlink
the requesting and spending of capabilities. When requesting
capabilities from an AA, Tor clients express what kind of
capability they request because the issuing process for two
capability types differs. An AA maintains separate signingkeys and rate limiters for two capability types.
Figure 1 illustrates the capability requesting and spending
process. While both capability types have in common step one
and two, the subsequent steps differ. A site-specific capability
can only be spent at the service provider specified in thecapability to request service while a relay-specific capability
is spent at a specific Tor relay to build a TorPolice-enhanced
circuit through the relay. A Tor client can use both capability
types simultaneously by visiting a TorPolice-enhanced site via
a TorPolice-enhanced Tor circuit. In Figure 1, we intentionallyseparate our two capability use cases for clear presentation.
IV. T HE ACCESS AUTHORITIESTorPolice relies on fully distributed and partially trusted access authorities (AAs) to manage capabilities. We assume AAs
to be honest-but-curious, meaning that they follow protocol,
but seek to derive additional information about Tor clients.
An AA can be deployed by the Tor Project, service providers(e.g., large CDNs like Cloudflare), or third parties. Each AA
is a conceptually centralized entity, but it can distribute its
operations among multiple servers to achieve high availability.
A. Capability Seeds
AAs expect valid capability seeds from Tor clients to issue
pre-capabilities, which are the basis for deriving spendable
capabilities. For flexibility, we intentionally keep the definitionof capability seeds broad: any resource that is readily available
to Tor users, but costly to scale, can be adopted as capability
seeds. Reasonable choices include proof-of-work schemes(e.g., solutions to CAPTCHAs or computational puzzles) andanonymous monetary resources. TorPolice does not assume
that capability seeds can distinguish bots from humans. Rather,botnets can still obtain more capability seeds than legitimate
Tor users. Instead, TorPolice employs capability seeds asa form of anonymous identities that enable both service
providers and the Tor network to control access by each client.
In this paper, we elaborate on two types of capability seeds(i.e., solutions to CAPTCHAs and computational puzzles) andfurther discuss how TorPolice can incorporate more types ofseeds in § IV-D. One key challenge of using anonymous
capability seeds is to ensure that clients do not have to solve
endless challenges while browsing the web and meanwhile
ensure their activities are unlinkable. TorPolice proposes acapability renewal protocol to address this challenge (§ V-A).
Although CAPTCHAs are readily deployable using publicly
available libraries like Google’s reCAPTCHA, TorPolice needs
additional components to support computational puzzles. At avery high level, TorPolice’s puzzle system design is similar
to Portcullis [26]. However, TorPolice’s puzzle system does
make a great improvement over Portcullis: it can explicitly
bound the percentage of CPU cycles that any client can spend
on solving puzzles. Thus, the puzzle system can bring all
bots down to the percentage that normal clients prefer touse for puzzle computation, which significantly reduces thecomputation disparity between the normal clients and bots.
For more details, please refer to our technical report [22].
B. Per-seed Rate Limiting
Each AA accepts only one type of capability seed. The
rate at which a seed can request pre-capabilities is limited. In
particular, an AA publishes two rate limiters: one determines
the maximum rate at which a capability seed can request
pre-capabilities used for accessing TorPolice-enhanced service
providers and the other one determines the maximum rate at
which a seed can request pre-capabilities used for TorPoliceenhanced circuit creation. Based on these per-seed rate limiters
published by all AAs, both service providers and Tor can configure rules to fulfill their access policies. This paper presents
two concrete examples. In § V-C, we elaborate on a designthat enables a site to bound an adversary’s achievable service
request rate through Tor using self-defined parameters. In§ VI-A, we present a design that allows Tor to prevent botnets
from creating numerous Tor circuits to conduct various abuses.
To improve readability, detailed settings of these rate limiters
will be discussed when presenting these access policies.
C. Key Management
Each AA maintains two pairs of keys for signing precapabilities, and each of them is dedicated for one capability
type. Each AA must publish the public key of both key pairs,
for instance, via the Tor network consensus, to ensure otherentities (e.g., Tor clients, relays, and service providers) canverify the AA’s signatures. An AA can periodically renew
its keys, but at any time only two key pairs from the AA
are valid. After receiving signed pre-capabilities from an AA,
Tor clients must verify that the AA uses proper keys before
using the pre-capabilities for accessing service providers or
Tor. This prevents a malicious AA from using more keys
simultaneously to partition the anonymity set. Finally, each
AA is associated with a long-term fingerprint to uniquely
identity the AA, similar to the fingerprint of a Tor relay.
D. Extending the Access Authorities
Besides Tor, content delivery networks (e.g., Cloudflare or
Akamai) also have direct incentives to deploy and control theirown set of access authorities to mitigate Tor-emitted abuses
while serving anonymous connections. In fact, Cloudflare is
working on an independent implementation of a system whose
design goals are similar to our AAs [8], although they focus
on addressing the usability issues for Tor users when visiting
Cloudflare-powered websites.
Finally, semi-trusted third parties such as social network
operators (e.g., Google, Twitter, and Facebook), may also run
access authorities (shown as TTP AA in Figure 1) based on preagreed terms. To prevent account information leakage to Tor
and service providers, Tor users only authenticate themselvesto the social network operators. Service providers or Tor only
learn a single bit of information: whether a Tor client has avalid account (i.e., capability seed) or not.
V. T OR P OLICE -E NHANCED S ITE ACCESS
We now elaborate on the capability design for accessing
TorPolice-enhanced service providers such as websites. To
mitigate the tension between service providers and Tor users,
our key observation is that service providers should not treat
all connections from one Tor exit relay equally since each
exit relay is shared by many Tor users. Instead, accountability
should be enforced at the granularity of Tor clients so thateach service provider can throttle malicious Tor clients without
blocking legitimate Tor users. To this end, TorPolice designs
site-specific capabilities that allows a service provider to enforce self-selected access rules on anonymous Tor connections.
A. Pre-capability Design
Before visiting a TorPolice-enhanced site, a Tor client mustfirst request pre-capabilities from an AA. The client is free tochoose any AA based on what capability seed the client prefers
to give. To request a pre-capability, the client (i) provides
a valid capability seed to its selected AA and (ii) provides
blinded information for the AA to compute pre-capabilities.
The client can hide its network identity from the AA, forinstance, by using Tor.
Capability Seed Validation. Depending on the acceptedtype of capability seed, an AA performs corresponding seedverification. For instance, if an AA accepts proof-of-work
schemes, it needs to verify that solutions to the presented
challenge are correct. Further, an AA needs to ensure that the
pre-capability request rates by any capability seed does notexceed the two rate limiters discussed in § IV-B. Since each
AA maintains separate rate limiters and signing keys for two
pre-capability types (i.e., either for TorPolice-enhanced service
access or for TorPolice-enhanced Tor circuit creation), Torclients must specify the pre-capability type in their requests(in this section, it is for accessing service providers). In § V-C,
we will explain how a site defines its access policies based on
those pre-capability release rate limiters published by all AAs.
Information Required to Compute Pre-capabilities. To
request pre-capabilities, the client provides its selected AA
the following set of information {S, n, Ts , F}, where S is thedomain name of site that the client is going to visit, n is
a 128-bit cryptographic nonce generated by the client, Ts isa universally agreed timestamp to indicate the freshness of
the information and F is fingerprint of the selected AA. All
information is blinded [6] by the client to avoid information
leakage to the selected AA.
The set of information is designed to prevent abuse. In particular, S is used to make the capability site-specific to prevent
capability double-spending at different sites. The nonce n is
added to ensure the uniqueness of each pre-capability, which
in turn ensures the uniqueness of each capability. The Ts
indicates the freshness of pre-capabilities so that expired ones
are nullified automatically. The client is required to use Tor’s
daily generated fresh random number [13] as Ts such that at
any time all valid capabilities have the exact same timestamp.
This design eliminates the possibility of information leakage
cased by timestamp abuse. F is added to allow other entities(i.e., clients, Tor relays and service providers) to use correct
public keys to verify signatures.
Computation. Upon validation of the client’s pre-capability
request, the AA computes pre-capabilities using the blinded
information provided by the client. Pre-capabilities computedby an AA Ai are denoted by PAi . Then we haveb
PAi = {S | n | Ts | FAi }b | SA,ib
is Ai ’s fingerprint, SAi(1)

where FAi
is Ai ’s blind signature
over the set of blinded information {S | n | Ts | FAi }b , and| represents concatenation throughout the paper.
Pre-capability Renewal. One key design challenge for precapabilities is to ensure that Tor clients do not have to repeatedly solve challenges when browsing the web. A strawman
design is that an AA can issue many (i.e., a few hundred) precapabilities for each solved challenge. However, this strawman
design has at least two shortcomings: (i) it breaks the sitespecific pre-capability design since the client may not beable to forecast the sites that it is going to visit so as toprovide these blinded information immediately after solving
challenges; (ii) the design makes it easier for automated botsto accumulate pre-capabilities, weakening the entire system.
To combat these problems, we propose a pre-capability
renewal protocol. In particular, when a client first presents
its challenge solution (i.e., capability seed) to an AA, the AA
issues the client an unforgeable pseudonym I = {r | φ} wherer is a random 128-bit nonce and φ is the AA’s signature overr. Later on, the client presents I as a proof of validation
when requesting new pre-capabilities from the AA, allowing
the client to bypass future challenges. Not only does the sitespecific pre-capability design hold with this design, but also
the AA can account each pre-capability request on a specificsolved challenge (i.e., capability seed) to enforce the perseed rate limiting described in § IV-B. Each pseudonym has avalidation period determined by the AA. Clients with expired
pseudonyms are required to solve new challenges to obtain
new pseudonyms that are unlinkable to previous ones.
Impact of the Pseudonym on Anonymity. Different fromprior pseudonym-based anonymous blacklisting systems [7],in which a user interacts with a service provider using apersistent pseudonym, the pseudonym in our pre-capability
renewal protocol is transient and never presented to service
providers and Tor relays. The pseudonym in our protocol is
only linked with a specific challenge solution served as ananonymous capability seed. Since a Tor client anonymously
sends its pseudonym to an AA using Tor, the AA cannot
link the pseudonym with the client. Further, since all siterelated information sent to the AA is blinded, the AA cannot
link the pseudonym with any site access as well. Thus, using
pseudonym in our protocol has no impact on user anonymity.
B. Site-Specific Capability Design
After obtaining PAi , the Tor client unblinds the signatureusing its secret blind factor to produce the unblinded versionof the pre-capability, which is the capability spendable at a
specific site. In particular, C = S | n | Ts | FAi | SAi . The
capability C contains a set of unblinded information that allows
the site S to perform capability verification when the client
presents C to access the site, as detailed in § V-C.
Employing blind signature is the key to ensure that TorPolice preserves Tor’s privacy guarantee. First, signatures fromthe AAs prevent unauthorized entities from issuing capabilities. Second, using blind signature avoids disclosing any siterelated information to the AAs since the blinded information
sent to the AAs is unlinkable with the “plain” information
produced by the client. Such unlinkability further ensures theunlinkability between the client and its capability spending
even if the AAs could collude with the site, which preserves
Tor users’ privacy. We provide a formal security proof in § VII.
C. Site-Specific Capability Spending
Capability Validation. Tor clients spend site-specific capabilities at TorPolice-enhanced sites to request services. Upon
receiving capabilities, a TorPolice-enhanced site first validates
them before subsequent processing. A site-specific capability
is valid if (i) it encloses an authentic signature from an AA;(ii) it encloses a domain name that is consistent with the site;(iii) the capability is not expired (i.e., Ts is the fresh random
number released by Tor); and (iv) the capability is not nullified
by the site. If any of these conditions does not hold, the site
rejects this capability to deny access. If a CDN provider (e.g.,
Cloudflare) processes capabilities on behalf of its poweredsites, the second rule is passed as long as the enclosed domain
is owned by one of the CDN provider’s customers. In the
fourth rule, whether a capability is nullified or not is decided
by the site’s access policies, as detailed below.
Site-Defined Access Policies. Once a site-specific capability isvalidated, the site accepts the Tor client’s service request. Since
the major form of Tor abuse is that automated bots use Tor to
conduct various malicious activities against the site [27] (e.g.,content scraping, vulnerability scanning, comment spammingand so forth), the site needs to further control the numberof service requests (e.g., HTTP requests) allowed by eachcapability. We clarify that each site can have its own definitionof service requests. Once a Tor client’s service request countexceeds a threshold, the site nullifies the current capability andrequires a new site-specific capability for subsequent service
requests. Recall that the pre-capability request rate by eachclient is limited by the AAs through the per-seed rate limiting
design in § IV-B. Thus, together with these rate limiters, it ispossible for the site to design access policies so as to bounda strategic adversary’s service request rate using self-selectedparameters, as detailed below.
Policy Definition. Assume the following set of accessauthorities {A0 , A1 , ..., An } are deployed, and each authority
accepts one type of capability seed. In this context, the site
defines its access policy as {w0 , w1 , ..., wn } where wi is thenumber of service requests allowed by one valid site-specificcapability issued by the access authority Ai .
We now formulate {w0 , w1 , ..., wn } mathematically. We denote the set of capability seeds by {s0 , s1 , ..., sn } and authority
Aj accepts seed sj . Let cj denote the cost of obtaining acapability seed sj . We denote the cost of obtaining a network
identity (i.e., IP address) by λ. Let rj denote the maximum rate
at which a seed sj can request pre-capabilities (for accessing
service providers) from authority Aj . Assume that for any
client connecting to the site directly without using Tor, thee before eithersite allows a maximum service request rate O
blocking the client or forcing the client to solve challenges.
Then to bound a strategic adversary’s service request rateby using Tor, the site derives {w0 , w1 , ..., wn } to ensure thatthe following condition is satisfied forPany set of parametersn[α0 , α1 , ..., αn ] where αi ∈ [0, 1] and i=0 αi = 1.
nXαi · λi=0ci

e· ri · wi ≤  · O,(2)

where  is a site-defined parameter.
Policy Correctness. The parameters [α0 , α1 , ..., αn ] represent the adversary’s strategy of purchasing various types ofcapability seeds. Thus, if formula (2) holds for any strategy,
the site can guarantee that the maximum Tor-emitted service
request rate achieved by an adversary when spending λ one Thus,purchasing capability seeds is no greater than  · O.
if an adversary that spends a certain amount of resources on
obtaining network identities can access the site with rate O
without using Tor, then the maximum rate that the adversary
can request service from the site by using Tor is no greaterthan  · O, given that the adversary spends the same amount of
resources on acquiring capability seeds. Equivalently, in orderto achieve the same service request rate, the adversary has tospend 1/ times as many resources when launching attacks
through Tor as it spends when launching attacks natively
without using Tor. To ensure that formula (2) holds for any
attacker strategy, we choose
wi ≤  ·eci · O, ∀i ∈ [0, n]
λ · ri(3)

Policy Enforcement. If wi = 1, then each capability is
usable for exactly one service request. The site can enforce thisby suppressing service requests with duplicate capabilities, forexample, through the use of a Bloom filter. If wi > 1, thenstatistically more than one service request should be allowed
for each capability. To enforce this, the site stops accepting acapability with probability 1/wi , and then adds the capability
to the duplicate suppressor. However, multiple service requests
carrying the same capability can trivially be linked by thesite. We discuss how to address this issue through systemparameterization below. Finally, if wi < 1, then each capability
is accepted with probability wi , and exactly one service request
is allowed for each accepted capability.
Policy Parameterization. We now discuss the parameterization of wi . First, to compute wi , the site does not needto exactly know ci . Instead, the site simply assigns specificweights to all types of capability seeds based on its policies.
Further, with an ideal parameterization, wi should be exactly
one since (i) no capability is spendable on more than one
service request to ensure unlinkability and (ii) no additional
capabilities are required for a single service request to avoid
extra overhead. However, it is difficult to reach the ideal
parameterization since ri is chosen by the authority Ai thate In addition,is unaware of the site’s configurations  and O.
configurations may vary among different sites so that an ideal
parameterization for one site could be undesirable for others.
To address the above problem, TorPolice sets ri suchthat (with high probability) a Tor client can obtain enoughcapabilities so that it is feasible for the client to present
a unique capability for each TCP connection to the site.
This ensures that the client can achieve the highest level of
unlinkability offered by Tor, i.e., service providers only see
TCP connections from Tor exit relays. We clarify that it is theclient who determines how to spend its capabilities across TCP
connections (as described below). The above parameterizationis adopted only to ensure that spending a unique capability
for each TCP connection is a feasible strategy for the client.
A reasonable setting of ri can be estimated based on thelive Tor measurement in [18], which finds that during a 10minute interval, each Tor client opens about 24 web streams.
In practice, the authority Ai should enforce ri over a longer
period of time (e.g., few hours) to accommodate usage burst.
Note that when an AA Ak is deployed by the site itself, system parameterization for Ak is easier since the site determines
the rate limiters for issuing pre-capabilities.
Capability Spending by Tor Clients. Given ri , some sites
may end up with rules wi > 1, i.e., one capability is allowed
for multiple service requests. In this case, the site needs tosend a response to indicate whether a capability is nullified
or not. Tor clients are free to determine their capability
spending strategies. For instance, a Tor client can send wi
service requests using the same capability within a single TCP
connection (due to HTTP keep-alive), which still ensures thehighest level of unlinkability. Or the client may choose tospend one capability across multiple TCP connections to allow
trans-TCP linkability. We note that if a Tor client uses thedefault setting of Tor Browser, it already allows trans-TCP
linkability since the Tor Browser uses session cookies. Fora site that has wi less than 1, it can enforce such policies
by accepting one capability with probability wi and for eachaccepted capability, the site allows only one service request.
VI. T OR P OLICE -E NHANCED T OR ACCESSIn this section, we detail the capability design for creating
TorPolice-enhanced Tor circuits. The current Tor network
suffers from a variety of botnet abuses such as large scale
C&C abuse [12, 15], relay flooding attacks [4, 5] and traffic
analysis [23, 25]. These abuses lead to various bad results,
including poor system performance for legitimate Tor users,
de-anonymization threats and bad reputation for Tor. The root
cause of these attacks is that botnets can create an arbitrary
number of Tor circuits without any limitation. Enforcing local
rate limiting for circuit creation at each relay is unlikely to stopthese attacks since a strategic botnet can instruct each bot toenumerate all relays to circumvent the local rate limiting.
With TorPolice, Tor can globally control circuit creations by
any client. In particular, when TorPolice is activated, clientsare required to possess valid capabilities in order to create
TorPolice-enhanced circuits (to be incrementally deployable,
circuit creation requests without valid capabilities are deprioritized in case of congestion). Then, by controlling the rate
at which a client can obtain capabilities, the Tor network cancontrol the client’s circuit creation rate, as described below.
A. Relay-Specific Capability Design
To create a three-hop TorPolice-enhanced circuit, a Tor
client U needs to obtain three capabilities, each of them being
specific to a relay on the circuit. The design of relay-specificcapabilities is similar to that of site-specific capabilities, except
for the following. (i) During pre-capability requesting, theclient specifies the proper pre-capability type, i.e., it is for Torenhanced circuit creations. Further, to request a pre-capability
specific to a relay R, the client encloses the fingerprint of relay
R (rather than any site domain) in the blinded information sent
to its selected AA. (ii) Relay-specific capabilities are spendable
at TorPolice-enhanced relays (not at any sites) for creating Torenhanced circuits through the relays. The relays first validate
received capabilities (based on a set of rules similar to thosedefined in § V-C) before extending circuits.
We clarify that to request pre-capabilities, Tor clients do
not have to use TorPolice-enhanced circuits to reach the AAs.
Thus, there is no deadlock for bootstrapping TorPolice. Another alternative is pre-installing few relay-specific capabilities
on Tor clients so that using TorPolice-enhanced circuits tobootstrap the system is viable.
Policy Definition. Relay-specific capabilities enable Tor to
enforce access rules for its relays. In this paper, we propose touse capabilities to control the circuit creation rate by any Tor
client so as to mitigate those aforementioned botnet abuses
against Tor. In particular, assume the following set of AAs{A0 , A1 , ..., An } are deployed and authority Ai accepts a typeof capability seed si . In this context, Tor defines its accesspolicies as {q0 , q1 , ..., qn }, where qi is the maximum rate at
which a capability seed si can request pre-capabilities (forcreating Tor-enhanced circuits) from authority Ai . Then in order to bound a Tor client’s circuit creation rate, {q0 , q1 , ..., qn }should satisfy the following condition for
Pnany attacker strategy[α0 , α1 , ..., αn ] where αi ∈ [0, 1] and i=0 αi = 1.
nXαi · λ · qi
i=0

3 · ci≤T,(4)where λ is the cost of getting one network identity, ci isthe cost for obtaining one capability seed si and T is the
maximum circuit creation rate allowed for a client, which isa parameter controlled by Tor. We note that the constant 3
appears in above formula since a standard Tor circuit contains
3 relays and each of them consumes a relay-specific capability.
To ensure the correctness of formula (4) for any attacker
strategy, we choose qi ≤ 3·cλi ·T , ∀i ∈ [0, n].
Parameterization. To compute qi , the Tor Project assigns
certain weight to each type of capability seed. Further, Tor
can properly configure T based on the live Tor measurements in [18]. In particular, during an 10-minute interval,
PrivCount [18] estimates that a Tor client opens about 4 Tor
circuits. Thus, the maximum rate T at which one Tor client cancreate circuits should be around 4 per 10 minutes. In practice,each AA should enforce qi over a longer period of time (e.g.,
few hours) to accommodate usage bursts and relay churn.
Please refer to our technical report [22] for the capability
exchange protocol designed for Tor onion services.
VII. S ECURITY A NALYSIS
In this section, we perform a formal security analysis for the
impact of TorPolice on Tor users’ anonymity. Let NT denotethe set of Tor clients that request pre-capabilities from theAAs, and subsequently present capabilities to access service
providers or Tor relays. We first present two useful lemmas.
A. Lemmas
Lemma 1. Consider any client U ∈ NT . By colluding witheach other, both the AAs and a service provider W gain only
negligible advantage over random guessing when trying to linka specific Tor-emitted site access with the client U.
Proof. We first specify the notations used in the proof. Let
V denote a Tor-emitted site access to W initiated by the Tor
client U. Note that the definition of a site access is decided by
W. Let C denote the service-specific capability that U sends to
W to support the site access V. Let P denote the pre-capability
used by U to compute C.
Since the client U can use Tor to connect to the AAs
when requesting the pre-capability P, in the ideal case, U
is unlinkable with P. However, to ensure that our lemma stillholds in the worst case when Tor’s unlinkability is broken by
adversaries, we assume the AA Ã that issues P can link P
with the client U. Thus, the service provider W and other AAs
can have such linkability as well by colluding with Ã.
Next, we prove the lemma by contradiction. Assume that
the AAs and W can design an algorithm K that enables the
AAs and W to link the site access V with the client U. Since
the site access V is linkable with the capability C (as C ispresented to the site to support the access V) and the client U is

linkable with the pre-capability P (based on the above worstcase assumption), designing the algorithm K is equivalent todesigning another algorithm K0 that enables the AAs and W
to link the capability C with the pre-capability P.
In TorPolice’s design, P is the blinded message signedby the AA Ã (i.e., the blind-signer), and C is the unblindedversion of P produced by the client U using a secret factor
unknown to the blind-signer. Thus, the problem of designing
K0 to link P with C is the same as designing another algorithm
K00 that allows a blind-signer to link the blinded message itsigns to the unblinded message without knowing the secretfactor, which is impossible in a blind signature [6]. This
contradiction proves that the hypothetical algorithm K does
not exist, indicating both AAs and W gain only negligible
advantages of linking the site access V with client U.
Similarly, we can prove the following lemma.
Lemma 2. Consider any client U ∈ NT . By colluding witheach other, both the AAs and Tor relays gain only negligible
advantage over random guessing when trying to link a specificrelay access (i.e., TorPolice-enhanced circuit creation) with U.
B. Information Leakage Analysis
Given the above two lemmas, we now analyze the impactof TorPolice on Tor user anonymity. We measure the possible
information leakage to an arbitrary service provider W basedon degree of anonymity [9, 28]. Our analysis uses informationtheoretic entropy [29] as the measure of information containedin a probability distribution. Recall that NT denotes the set of
TorPolice-upgraded Tor clients. Given an arbitrary capabilityenhanced site access (i.e., an access supported by a valid
capability), W believes that with probability pi , the accessoriginates from client i in NT . Thus, W maintains a probability
distribution I for all anonymous accesses. Then, the entropy(i.e., the information
contained in the distribution I) is definedP
as HW = − i∈NT pi · log2 (pi ).
Based on the unlinkability proven in Lemma 1, we havepi = N1T , where NT is the size of the anonymity set NT . Thus,
the entropy after introducing TorPolice is HW = log2 NT .
Next, we analyze the entropy before introducing TorPolice.
Let N denote the entire set of anonymous Tor clients. Noticethat the current Tor network protects W from linking a (native)
site access with a specific Tor client. Thus, given the entire
anonymous client set N, the maximum entropy HM is HM =log2 N , where N is the size of the anonymity set N. Then,based on the definition in [9, 28], the degree of anonymity dW
2 NTafter introducing TorPolice is d = 1 − HMH−H= log
log2 N .
M
Anonymous Set Analysis. Given the above anonymity degree,
information leakage is affected by the size of the anonymous
client set before and after TorPolice is introduced. Thus, once
all Tor clients are upgraded to support TorPolice, there isno information leakage at all. Thus, eventually, TorPolice
completely preserves the privacy guarantee offered by the
Tor network. To mitigate the one-time privacy issue during
the early deployment phase of TorPolice, the Tor Project can

The CAA

Client (CapJS)

Site

TABLE I: The computational time for capability-related cryptographic operations.
Operation

Language

Mean (µs)

Median (µs)

Std. Dev. (µs)

Generation

C
PythonJavaScript

232.0
253.7
27,320.0

232.0
253.6
27,240.0

0.1
0.3
245.5

Verification

C
PythonJavaScript

25.6
32.0
355.5

25.6
32.0
354.3

0.0
0.1
5.3

Blinding

C
PythonJavaScript

3.5
46.3
18.1

3.5
46.3
18.1

0.0
0.1
0.3

Unblinding

C
PythonJavaScript

2.4
7.0
64.8

2.4
7.0
64.7

0.0
0.0
6.8

Access-Control-Allow-Headers:
X-Capability
AJAX GET X-Capability: I | {S | n | Ts | F }bAccess-Control-Allow-Headers:
X-Capability

Validate the pseudonym
AJAX Response data: {S | n | Ts | F}

b

b
| SA

Unblind the pre-capability
HTTP(s) Request X-Capability: S | n | Ts | F | SA
Validate the capability
Response

Fig. 2: Site access by a client with CapJS installed.

require mandatory client upgrades from a certain time point
to “force” all active clients to serve as TorPolice initiators.
VIII. I MPLEMENTATION
For better readability, we cover the high-level implementation of TorPolice in this section and defer details to ourtechnical report [22].
Capability Implementation. We implement capability-related
computation using C, Python and JavaScript to consider
various usage scenarios. For instance, the capability design canbe directly built into the Tor software written in C, or it can be
implemented as a plugin for the Tor browser, which executes
capability-related computation in JavaScript. Websites may
compute capabilities using any language. Thus, we use Python
as an example due to its popularity in web applications. We use
the RSA algorithm to perform capability-related cryptographic
operations such as blind signing.
AA Implementation. For an AA accepts CAPTCHAs as capability seeds (referred to as CAA), we implement it as a web
server that deploys Google’s reCAPTCHA service. For an AA
accepts computational puzzles (referred to as PAA), it accepts
puzzle solutions over HTTP requests. These AA servers definea customized HTTP header (X-Capability) to carry TorPolicerelated cryptographic tokens such as pseudonyms and precapabilities. To make the implementation transparent to clients,
the AA servers add X-Capability in the Access-ControlAllow-Headers HTTP header option. Although the PAA canbe accessed using native HTTP libraries, the CAA needs tobe accessed using browsers. Thus, we implement a Firefox
add-on (referred to as CapJS) to execute TorPolice-related
cryptographic operations in browsers. We discuss the detailed
design of CapJS in our technical report [22].
TorPolice-enhanced Site Access. To use our capability
scheme, the deployment required at websites is lightweight:
a site only needs to add X-Capability in its Access-ControlAllow-Headers HTTP header option to allow CapJS topass site-specific capabilities in the header. Upon receiving
capabilities, the site verifies them using the rules defined in§V-C to fulfill its access policies. Figure 2 depicts a site accessby a client with CapJS installed on its browser.
TorPolice-enhanced Tor Circuit Creation. We modify the
Tor software source code to directly integrate our capability
design into Tor circuit creation. In particular, besides these
original cells sent for circuit creation, the modified onion

proxy (OP) on a Tor client further sends a valid relayspecific capability to each hop. Each relay first verifies thereceived capability before processing the onionskin carried in
the remaining payload. To validate our implementation, we
test the modified Tor source code in Shadow [17], a safe
development environment to run real Tor source code in a
private Tor network. Via log analysis, our test experiments
show that our implementation properly embeds relay-specificcapabilities into the workflow of Tor circuit creation.
IX. E VALUATION
A. Capability Computation OverheadThis section benchmarks the overhead of capability-related
computation. All results are obtained using a single 3.30 GHz
Intel i3-3120 core. We perform 10, 000 runs to learn the mean,
median, and standard deviation of the computation times
for a single capability generation, verification, information
blinding and unblinding. Results shown in Table I are obtained
when the RSA key length is 1024. The overall computational
overhead is small. For instance, in C, it takes ∼230 µs tocompute a pre-capability and ∼25 µs to verify a capability. A
blinding and an unblinding operation can be finished in ∼3 µs
and ∼2 µs, respectively, in C. The implementations in C andPython have comparable performance. Although it is more
expensive to perform signing and verifying in JavaScript, theoverhead of blinding and unblinding operations (performed by
Tor clients) in JavaScript is comparable with other languages.
The AAs, relays and service providers can adopt more efficientlanguages (e.g., C) to perform signing and verifying.
B. Enforcing Site-Defined Policies
In this section, we show that TorPolice enables a site toenforce site-defined access policies.
Access Policies. For evaluation purpose, we assume that thesite assigns equal weights to both types of capability seeds, i.e.,c0 (for CAPTCHAs) and c1 (for puzzles) in Equation (3) are
the same. However, the actual costs, denoted by c00 and c01 , canbe different from c0 and c1 . Further, base on the measurements
in [10, 24], we assume c00 is close to λ (the cost for obtaining
one network identity).
We evaluate three strategies that a site may use in its accesspolicies. The first strategy (referred to as basic strategy) is

0.9ε
0.8ε
0.7ε
0.6ε
0.5ε
0.4ε
E0
2E0
3E0
4E0
Adversary’s cost for capability seeds

Fig. 3: With TorPolice, a site can bound an
adversary’s service request rate by Θ().
E0 is the adversary’s cost at the point ofdiminishing returns.

Without TorPolice
With TorPolice

60

Circuit creation failure rate (%)ε

Circuit creation failure rate (%)

Normalized service request rate ra

70
Basic Strategy
Rate Limiting Strategy
WFQ Strategy

50
40
30
20
10

Consensus on Sep 1st 2013; Without TorPolice
Consensus on May 1st 2017; Without TorPolice
Consensus on Sep 1st 2013; With TorPolice
Consensus on May 1st, 2017; With TorPolice

60
50
40
30
20
10
0

0
0

5

10

15
Date

20

25

30

Fig. 4: Circuit creation failure rates when
Tor faced a multi-million node botnet C&C
abuse. TorPolice can reduce the average
circuit creation failure rate by ∼74%.

that the site accepts all Tor-emitted service requests withvalid capabilities. In the second strategy (referred to as rate
limiting strategy), the site enforces a maximum service request
rate rmax for all valid requests. In the third strategy, besides
rate limiting, the site further performs weighted fair queuing(WFQ) to serve requests: rather than serving all valid requests
in one FIFO queue, requests with capabilities obtained using
CAPTCHA solutions and puzzle solutions are served in two
separate FIFO queues weighted equally. The third strategy(referred to as WFQ strategy) prevents one type of seed fromoverwhelming the other one.
Policy Enforcement. We study an adversary’s service request
rate through Tor when it invests a certain amount of money on
acquiring capability seeds. Define k = c00 /c01 . We first present
evaluation results for k = 0.5 in Figure 3 and then extend our
discussion to arbitrary k. For any amount of investment, theadversary’s service request rate through Tor (denoted by ra )is normalized to the service request rate obtained when theadversary connects to the site directly without using Tor.
Since c00 <c01 given k=0.5, the adversary’s optimal strategy
is spending all investment on solving CAPTCHA. Thus, wehave ra =, where  is the site-configurable parameter definedin Equation (2). When the site adopts the basic strategy, raremains the same as the adversary’s investment increases.
However, for the other two strategies, ra will reach a pointof diminishing returns as the adversary’s investment further
increases (as shown in Figure 3). In particular, when thesite adopts the rate limiting strategy, the point of diminishingreturns is reached when the collective service request rate fromthe adversary and all legitimate Tor clients exceeds rmax . In
Figure 3, we denote the adversary’s cost at this point by 2E0 .
After that, further increasing investment actually reduces rasince no more Tor-emitted requests are allowed by the site.
When the WFQ strategy is adopted, ra experiences twopoints of diminishing returns as the adversary’s cost increases,
as shown in Figure 3. The first one happens when the collective
service request rate from all Tor clients using the optimal seed
(CAPTCHAs in our evaluation) exceeds rmax
2 . After this point,
the adversary has to use sub-optimal seeds in order to further
get services. As a result, ra starts to decline from the optimalrate . The second point of diminishing returns is reached when

10

100
1000
The number of bots (thousand)Fig. 5: Without TorPolice, an adversary
can paralyze Tor by cell flooding attacks.
TorPolice can effectively mitigate this vulnerability.

the collective Tor-emitted service request rate exceeds rmax .
General Results. Our further analysis in [22] proves that for
any k, ra ≤  if k ≤ 1 and ra ≤ k · if k ≥ 1. Thus, regardlessof the actual cost of obtaining capability seeds, the adversary’s
service request rate is bounded by Θ(). This result holds nomatter which strategy the site adopts and how many types ofcapability seeds are accepted.
C. Mitigating Botnet Abuse Against Tor
We now perform Tor-scale evaluations to demonstrate (i)TorPolice effectively mitigates large-scale botnet C&C abuseagainst Tor by reducing circuit failure ratios by ∼74%(§ IX-C1) and (ii) TorPolice significantly increases Tor’s
resilience against cell flooding attacks (§ IX-C2).
Tor-scale Simulator. We aim to show that TorPolice canmitigate the harm that a multi-million botnet can do to Tor.
While we have a TorPolice prototype that runs on Shadow [17](§ VIII), we would run into scalability issues with simulating
millions of Tor clients. Further, Shadow is unable to help
us simulate the cryptographic overhead that botnets would
impose on Tor relays [16]. Due to these shortcomings, wedevelop our own simulator. We faithfully implement Tor’s
path selection algorithm in our simulator and validate its
correctness by comparing relays’ selection probabilities withthe ones published by Tor [1]. The computational capacity ofrelays are sampled from live Tor measurement results in [4].
1) Mitigating Botnet C&C Abuse: Based on the historical
data from the botnet C&C abuse happened during Aug-Sep
2013, we show TorPolice can effectively mitigate the abuse.
We use the data collected by Tor to estimate the amounts ofcircuit creations initiated by the botnet during the C&C abuse.
To improve readability, we defer detailed modeling in [22].
Due to the massive circuit creations by the botnet, computeresources of many relays are exhausted, resulting in very highcircuit creation failure rates, as depicted in Figure 4. Suchhigh failure rates are caused by the following vicious cycle.
When the abuse starts, Tor relays begin to drop requests dueto the lack of compute resources. These initial failures force
the bot clients to keep sending requests until their circuits are
successfully created, which further increases the network load.
The resulting consequences are that the botnet still managed

to use Tor as its primary C&C channel after numerous trials
whereas Tor is less usable for legitimate Tor users since it
could take tens of trials to finally create a circuit.
The root cause of such high circuit creation failure ratios
is that bot clients can request circuit creations without any
limitation. With TorPolice, Tor can rely on the access policies
discussed in § VI-A to counter this abuse. We plot the resulting
circuit creation failure rates after enforcing the access rulesin Figure 4: TorPolice reduces the average failure rate from
∼41% to ∼10%, a ∼74% reduction.
In response to the C&C abuse, Tor released a new version(0.2.4.17-rc) that prioritizes the processing of onionskins using
the ntor [11] protocol since the bot clients used an older version without ntor support. Tor’s countermeasure reduced theaverage circuit failure rate to ∼20% [15]. However, a strategic
botnet could circumvent Tor’s defense by changing adaptively(e.g., upgrading software). On the contrary, TorPolice offers
long-term countermeasures that can handle strategic botnets.
2) Mitigating Tor-targeted DDoS Attacks: Via cell flooding
attacks [4], a botnet can easily paralyze Tor via excessive
circuit creation requests. As shown in Figure 5, a moderatesized botnet with hundreds of thousands of bots is enough tocause very high circuit failure rates via cell flooding attacks.
When Tor is protected by TorPolice, however, even a multimillion node botnet can only cause very limited failure rates
for the current Tor network (represented by the consensus
published on May 1st 2017).
X. R ELATED W ORK
We now briefly discuss some closely related work.
Capabilities in the Internet. Capability schemes [20, 21, 31]
have been proposed to protect the Internet from DDoS attacks.
In these approaches, capabilities specify certain traffic policing
rules and meanwhile carry cryptographic signatures to ensure
correctness. Victims (e.g., servers or congested routers) police
traffic based on received capabilities to stop attacks. Different
from TorPolice, these designs do not consider privacy.
Anonymous Blacklisting Systems. Anonymous blacklisting
systems [14] allow service providers to maintain a “blacklist”
to block abusive users without breaking anonymity. Thesesystems either offer pseudonymity instead of full anonymity
or require a trusted or semi-trusted authority to provide
anonymity. TorPolice is not designed to be a new anonymous
blacklisting system. Rather, TorPolice is explicitly designed for
Tor, focusing on proposing a capability-based access control
framework that allows service providers and Tor to enforce
access rules to throttle various botnet abuses while still serving
legitimate Tor users properly.
XI. C ONCLUSION
In this paper, we present TorPolice, the first privacypreserving access control framework that allows service
providers and Tor to enforce self-selectable access policies
on anonymous Tor connections so as to throttle various botnet
abuses while still providing service to legitimate Tor users.
TorPolice leverages blindly signed network capabilities topreserve the privacy of Tor users. We implement a prototypeof TorPolice, and perform extensive evaluations to validate
TorPolice’s design goals.
XII. ACKNOWLEDGEMENTS
We want to thank the anonymous reviewers for insightfulcomments. This research was partially supported by the Center
for Information Technology Policy at Princeton University and
NSF under Contract No. CNS-0953600, CNS-1423139, CNS1553437, CNS-1540066 and CNS-1602399.
R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]

[12]

[13]

[14]
[15]
[16]
[17]
[18]
[19]

[20]
[21]
[22]

[23]

[24]

[25]
[26]

[27]
[28]
[29]
[30]

[31]

Tor Atlas. https://atlas.torproject.org.
Tor Metrics. https://metrics.torproject.org.
Who Uses Tor? https://www.torproject.org/about/torusers.html.en.
BARBERA , M. V., K EMERLIS , V. P., PAPPAS , V., AND K EROMYTIS , A. D.
CellFlood: Attacking Tor onion routers on the cheap. In ESORICS (2013).
B ORISOV, N., DANEZIS , G., M ITTAL , P., AND TABRIZ , P. Denial of service ordenial of security? In ACM CCS (2007).
C HAUM , D. Blind signatures for untraceable payments. In Advances in Cryptology(1983), Springer.
C HEN , L. Access with pseudonyms. In Cryptography: Policy and Algorithms(1996).
C LOUDFLARE. Challenge bypass specification. https://github.com/cloudflare/
challenge-bypass-specification, 2016.
D ÍAZ , C., S EYS , S., C LAESSENS , J., AND P RENEEL , B. Towards measuring
anonymity. In International Workshop on Privacy Enhancing Technologies (2002).
D ONOHUE , B. How Much Does A Botnet Cost? https://threatpost.com/how-muchdoes-botnet-cost-022813/77573/.
G OLDBERG , I., S TEBILA , D., AND U STAOGLU , B. Anonymity and one-way
authentication in key exchange protocols. Designs, Codes and Cryptography(2013).
G OTTESMAN , G. RSA Uncovers New POS Malware Operation Stealing Payment Card & Personal Information. https://blogs.rsa.com/rsa-uncovers-new-posmalware-operation-stealing-payment-card-personal-information/, 2014.
G OULET, D., AND K ADIANAKIS , G. Random number generation during Tor
voting. https://gitweb.torproject.org/torspec.git/tree/proposals/250-commit-revealconsensus.txt, 2015.
H ENRY, R., AND G OLDBERG , I. Formalizing anonymous blacklisting systems. In
IEEE S&P (2011).
H OPPER , N. Protecting Tor from botnet abuse in the long term. Tech. rep., Tech.
Rep. 2013-11-001, The Tor Project, 2013.
JANSEN , R. Notes and FAQs of Shadow simulator. https://github.com/shadow/
shadow/wiki/4-Notes-and-FAQs, accessed on 2017.
JANSEN , R., AND H OPPER , N. Shadow: Running Tor in a box for accurate andefficient experimentation. In NDSS (2012).
JANSEN , R., AND J OHNSON , A. Safely measuring Tor. In ACM CCS (2016).
K HATTAK , S., F IFIELD , D., A FROZ , S., JAVED , M., S UNDARESAN , S., PAXSON ,V., M URDOCH , S. J., AND M C C OY, D. Do you see what I see? differential
treatment of anonymous users. In NDSS (2016).
L IU , X., YANG , X., AND X IA , Y. NetFence: Preventing Internet denial of service
from inside out. ACM SIGCOMM CCR (2011).
L IU , Z., H AO , J., H U , Y.-C., AND BAILEY, M. MiddlePolice: Toward enforcing
destination-defined policies in the middle of the Internet. In ACM CCS (2016).
L IU , Z., L IU , Y., W INTER , P., M ITTAL , P., AND H U , Y.-C. TorPolice: Towards
Enforcing Service-Defined Access Policies for Anonymous Systems. https://arxiv.
org/abs/1708.08162, 2017.
M ITTAL , P., K HURSHID , A., J UEN , J., C AESAR , M., AND B ORISOV, N. Stealthy
traffic analysis of low-latency anonymous communication using throughput fingerprinting. In ACM CCS (2011).
M OTOYAMA , M., L EVCHENKO , K., K ANICH , C., M C C OY, D., VOELKER , G. M.,
AND S AVAGE , S. Re: CAPTCHAs-understanding CAPTCHA-solving services inan economic context. In USENIX Security Symposium (2010).
M URDOCH , S. J., AND DANEZIS , G. Low-cost Traffic Analysis of Tor. In IEEE
S&P (2005).
PARNO , B., W ENDLANDT, D., S HI , E., P ERRIG , A., M AGGS , B., AND H U , Y.-C.
Portcullis: Protecting connection setup from denial-of-capability attacks. In ACM
SIGCOMM (2007).
P RINCE , M. The trouble with Tor. https://blog.cloudflare.com/the-trouble-withtor/, 2016.
S ERJANTOV, A., AND DANEZIS , G. Towards an information theoretic metric foranonymity. In PETs (2003).
S HANNON , C. E. A mathematical theory of communication. ACM SIGMOBILE
Mobile Computing and Communications Review (2001).
S UN , Y., E DMUNDSON , A., VANBEVER , L., L I , O., R EXFORD , J., C HIANG , M.,
AND M ITTAL , P. RAPTOR: Routing attacks on privacy in Tor. In USENIX Security
Symposium (2015).
YAAR , A., P ERRIG , A., AND S ONG , D. SIFF: A stateless Internet flow filter tomitigate DDoS flooding attacks. In IEEE S&P (2004).