RAPTOR: Routing Attacks on Privacy in Tor

Yixin Sun and Anne Edmundson, Princeton University; Laurent Vanbever, ETH Zürich;
Oscar Li, Jennifer Rexford, Mung Chiang, and Prateek Mittal, Princeton University
https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/sun

This paper is included in the Proceedings of the

24th USENIX Security Symposium
August 12–14, 2015 • Washington, D.C.
ISBN 978-1-939133-11-3

Open access to the Proceedings of

the 24th USENIX Security Symposium
is sponsored by USENIX
 RAPTOR: Routing Attacks on Privacy in Tor

Yixin Sun Anne Edmundson Laurent Vanbever Oscar Li

Princeton University Princeton University ETH Zurich Princeton University
Jennifer Rexford Mung Chiang Prateek Mittal
Princeton University Princeton University Princeton University

Abstract journalists, businesses and ordinary citizens concerned

about the privacy of their online communications [9].
The Tor network is a widely used system for anony-
Along with anonymity, Tor aims to provide low la-
mous communication. However, Tor is known to be
tency and, as such, does not obfuscate packet timings
vulnerable to attackers who can observe traffic at both
or sizes. Consequently, an adversary who is able to ob-
ends of the communication path. In this paper, we show
serve traffic on both segments of the Tor communication
that prior attacks are just the tip of the iceberg. We
channel (i.e., between the server and the Tor network,
present a suite of new attacks, called Raptor, that can
and between the Tor network and the client) can corre-
be launched by Autonomous Systems (ASes) to com-
late packet sizes and packet timings to deanonymize Tor
promise user anonymity. First, AS-level adversaries can
clients [45, 46].
exploit the asymmetric nature of Internet routing to in-
There are essentially two ways for an adversary to
crease the chance of observing at least one direction of
gain visibility into Tor traffic, either by compromising
user traffic at both ends of the communication. Second,
(or owning enough) Tor relays or by manipulating the
AS-level adversaries can exploit natural churn in Inter-
underlying network communications so as to put herself
net routing to lie on the BGP paths for more users over
on the forwarding path for Tor traffic. Regarding net-
time. Third, strategic adversaries can manipulate Inter-
work threats, large Autonomous Systems (ASes) such as
net routing via BGP hijacks (to discover the users using
Internet Service Providers (ISPs) can easily eavesdrop on
specific Tor guard nodes) and interceptions (to perform
a portion of all links, and observe any unencrypted infor-
traffic analysis). We demonstrate the feasibility of Rap-
mation, packet headers, packet timing, and packet size.
tor attacks by analyzing historical BGP data and Tracer-
Recent declarations by Edward Snowden have confirmed
oute data as well as performing real-world attacks on the
that ASes poses a real threat. Among others, the NSA has
live Tor network, while ensuring that we do not harm real
a program called Marina which stores meta information
users. In addition, we outline the design of two monitor-
about user communications for up to a year [15], while
ing frameworks to counter these attacks: BGP monitor-
the GCHQ has a program called Tempora that stores
ing to detect control-plane attacks, and Traceroute moni-
meta-information for 30 days and buffers data for three
toring to detect data-plane anomalies. Overall, our work
days [36]. Also, and maybe more importantly, it has been
motivates the design of anonymity systems that are aware
shown that Tor was targeted by such adversaries in col-
of the dynamics of Internet routing.
lusion with ASes [10, 12, 11].
In this paper, we present Raptor, a suite of novel traffic
1 Introduction analysis attacks that deanonymize Tor users more effec-
tively than previously thought possible. To do so, and
Anonymity systems aim to protect user identities from unlike previous studies on AS-level adversaries [28, 26,
untrusted destinations and third parties on the Internet. 40], Raptor leverages the dynamic aspects of the Inter-
Among all of them, the Tor network [25] is the most net routing protocol, i.e. the Border Gateway Protocol
widely used. As of February 2015, the Tor network com- (BGP).
prises of 7,000 relays or proxies which together carry Raptor attacks are composed of three individual at-
terabytes of traffic every day [8]. Tor serves millions tacks whose effects are compounded (§2). First, Raptor
of users and is often publicized by political dissidents, exploits the asymmetric nature of Internet routing: the
whistle-blowers, law-enforcement, intelligence agencies, BGP path from a sender to a receiver can be different

USENIX Association 24th USENIX Security Symposium 271

 Traffic Analysis BGP Churn BGP Hijack BGP Interception
Symmetric Known [45, 46]
Novel (§4) Novel (§5) Novel (§5)
Asymmetric Novel (§3)

Table 1: This paper describes Raptor, a suite of previously unknown attacks on the Tor Network

than the BGP path from the receiver to the sender. In- Countermeasures: We present a comprehensive taxon-
ternet routing asymmetry increases the chance of an AS- omy of countermeasures against Raptor attacks (§6). In
level adversary observing at least one direction of both particular, we outline the design of a monitoring frame-
communication endpoints, enabling a novel asymmetric work for the Tor network that aims to detect suspicious
traffic analysis attack. Second, Raptor exploits natural AS-level path changes towards Tor prefixes using both
churn in Internet routing: BGP paths change over time BGP and Traceroute monitoring.
due to link or router failures, setup of new Internet links
or peering relationships, or changes in AS routing poli-
cies. Changes in BGP paths allow ASes to observe ad- 2 Raptor Attacks
ditional Tor traffic, enabling them to deanonymize an in-
To communicate with a destination, Tor clients establish
creasing number of Tor clients over time. Third, Rap-
layered circuits through three subsequent Tor relays. The
tor exploits the inherent insecurity of Internet routing:
three relays are referred to as: entry (or guard) for the
strategic adversaries can manipulate Internet routing via
first one, middle for the second one, and exit relay for
BGP hijack and BGP interception attacks against the Tor
the last one. To load balance its traffic, Tor clients se-
network. These attacks enable the adversary to observe
lect relays with a probability that is proportional to their
user communications, and to deanonymize clients via
network capacity. Encryption is used to ensure that each
traffic analysis.
relay learns the identity of only the previous hop and the
Raptor attacks were briefly discussed in a preliminary next hop in the communications, and no single relay can
and short workshop paper [48]. In this paper, we go fur- link the client to the destination server.
ther by measuring the importance of the attacks using It is well known that if an attacker can observe the
real-world Internet control- and data-plane data. We also traffic from the destination server to the exit relay as well
demonstrate the attacks feasibility by performing them as from the entry relay to the client (or traffic from the
on the live Tor network—with success. No real Tor users client to the entry relay and from the exit relay to the
were harmed in our experiments (§7). Finally, we also destination server), then it can leverage correlation be-
describe efficient countermeasures to restore a good level tween packet timing and sizes to infer the network iden-
of anonymity. To summarize, we make the following key tities of clients and servers (end-to-end timing analysis).
contributions: This timing analysis works even if the communication is
Asymmetric Traffic Analysis and BGP Churn: Us- encrypted.
ing live experiments on the Tor network, we showed In the rest of the section, we present the three Raptor
that Raptor’s asymmetric traffic analysis attacks can attacks and how they contrast to conventional symmetric
deanonymize a user with a 95% accuracy, without any traffic analysis. We start by discussing how seeing just
false positives (§3). Using historical BGP and Tracer- one direction of the traffic for each segment (between
oute data, we showed that by considering routing asym- the sender and the guard, and between the last relay and
metry and routing churn, the threat of AS-level attacks the destination) is sufficient for the adversary (§2.1). We
increases by 50% and 100%, respectively (§4). then explain how ASes can exploit natural BGP dynam-
BGP Hijacks and Interceptions: We analyzed known ics (§2.2), or even launch active attacks (§2.3), to com-
BGP hijacks and interception attacks on the Internet and promise the anonymity of Tor users.
show multiple instances where Tor relays were among
the target prefixes (§5). As an illustration, the recent Bit- 2.1 Asymmetric Traffic Analysis
coin Hijack attack [1] in 2014, as well as Indosat Hijack
attacks [3, 2] in 2014 and 2011 involved multiple Tor re- We propose asymmetric traffic analysis, a novel form of
lays. To demonstrate the feasibility of such attacks for end-to-end timing analysis that allows AS-level adver-
the purpose of deanonymizing Tor clients, we success- saries to compromise the anonymity of Tor users. Let
fully performed an interception attack against a live Tor us suppose that a Tor client is uploading a large file to a
relay. Overall, we found that more than 90% of Tor re- Web server. Conventional traffic analysis considers only
lays are vulnerable to our attacks. one scenario where adversaries observe traffic from the

2
272 24th USENIX Security Symposium USENIX Association
 dest-to-exit dest dest
entry entry the TCP acknowledgment packets. We overcome this
AS2 AS3
AS4 AS2
AS3

AS4
hurdle by observing that Tor (and other anonymity sys-
entry-to-client tems) use SSL/TLS for encryption, which leaves the TCP
AS5 AS5
header unencrypted. Our attack inspects TCP headers in
AS6 AS6 the observed traffic to retrieve the TCP sequence number
AS1 AS1

exit-to-dest
field and TCP acknowledgment number field, and ana-
client-to-entry
client exit client exit lyzes the correlation between these fields of both ends
over time. Our experimental results in Section 3 show
the feasibility of asymmetric traffic analysis, with a de-
Figure 1: Asymmetric routing increases the power of
tection accuracy of 95%. Furthermore, asymmetric traf-
AS-level adversaries. When considering forward traf-
fic analysis can be combined with other Raptor attacks,
fic, i.e., client-to-entry and exit-to-destination flows, only
such as exploiting natural churn and BGP interception
AS5 can compromise anonymity. When considering
attack, which we discuss next.
both forward and backward traffic though, AS3, AS4
and AS5 can compromise anonymity. Our measurements
confirm that asymmetric traffic analysis is feasible. 2.2 Natural Churn

client-to-entry exit-to-server
client to the entry relay, and from the exit relay to the connection connection dest dest
entry entry
Web server (same direction as the flow of traffic)1 . AS3 AS3

However, Internet paths are often asymmetric: the AS2 AS4 AS2 AS4

path from the exit relay to the Web server may be dif-
ferent than the path from the Web server to the exit relay. AS5 AS5

AS6 AS6
Thus it is possible that an adversary may not be able to AS1
potentially
AS1

observe the data traffic on the path from the exit relay client
compromising AS
exit client exit
to the server, but it observes the TCP acknowledgment
traffic on the path from the server to the exit relay.
We introduce an asymmetric traffic analysis attack that Figure 2: BGP churn increases the number of ASes that
allows an adversary to deanonymize users as long as the can deanonymize Tor traffic. Initially, only AS5 can
adversary is able to observe any direction of the traffic, at deanonymize the client, seeing both direction of the traf-
both ends of the communication. Note that we can view fic (left). After the failure of link (AS4, AS5), both AS5
the conventional end-to-end timing analysis as a special and AS3 can deanonymize Tor traffic (right).
case of our attack, in which the adversary is able to ob-
serve traffic at both ends of the anonymous path, and in When users communicate with recipients over multi-
the same direction as the flow of traffic. Routing asym- ple time instances, then there is a potential for compro-
metry increases the number of ASes who can observe at mise of anonymity at every communication instance [49,
least one direction of traffic at both communication end- 42]. Thus anonymity can degrade over time. Tor consid-
points. We illustrate this scenario in Figure 1. ers this threat from the perspective of adversarial relays
More concretely, our attack is applicable to four sce- (but not adversarial ASes).Tor clients use a fixed entry
narios where an adversary observes (a) data traffic from relay (guard relay) for a period of time (Dingledine et al.
the client to entry relay, and data traffic from exit relay to recommend 9 months [24]) to mitigate this threat with
the server, or (b) data traffic from the client to entry re- respect to adversarial relays. We note that the threat of
lay, and TCP acknowledgment traffic from the server to AS-level adversaries still persists, because even though
exit relay, or (c) TCP acknowledgment traffic from guard the entry relay is fixed, the set of ASes on the path be-
relay to the client, and data traffic from exit relay to the tween the client and the guard relay may change over
server, or (d) TCP acknowledgment traffic from guard re- time. Next, we discuss such attacks that rely on natural
lay to the client, and TCP acknowledgment traffic from churn in BGP paths.
the server to the exit relay. The underlying Internet paths between a client and
A key hurdle in asymmetric traffic correlation is that guard relay vary over time due to changes in the phys-
TCP acknowledgments are cumulative, and there is not ical topology (e.g., failures, recoveries, and the rollout
a one-to-one correspondence between data packets and of new routers and links) and AS-level routing policies
1 If the traffic is flowing from the server to the client, then end-to-
(e.g., traffic engineering and new business relationships).
These changes give a malicious AS surveillance power
end timing analysis considers a scenario where the adversary observes
traffic from the Web server to the exit relay and from the entry relay to that increases over time. For example, AS 3 in Figure 2
the client. does not lie on the original path from the exit to the des-

3
USENIX Association 24th USENIX Security Symposium 273
 dest dest
tination, but a BGP routing change can put AS 3 on the entry entry
10.0.0.0/16
Path: 3 2 5 6

path, allowing it to perform traffic analysis. AS2

AS3
AS4
AS2
AS3
AS4

In Section 4, we show that the surveillance capability 10.0.0.0/16 10.0.0.0/16

of an AS-level adversary can increase up to 50% when AS5
Path: 6
AS5
Path: 6

considering BGP churn over a period of one month. AS1

AS6
AS1
AS6

10.0.0.1 10.0.0.1
client exit client exit

2.3 BGP Hijack

So far, we discussed Raptor attacks that were pas- Figure 3: BGP interception attack enables ASes to selec-
sive. Strategic AS-level adversaries are also capable of tively put themselves on some path. Here, AS3 only sees
launching active attacks, that deviate from honest routing traffic between the client and the entry relay (left). By
behavior. Internet routing is vulnerable to attacks which intercepting the prefix containing the exit relay (right),
enable an AS to manipulate inter-domain routing by ad- AS3 also sees traffic towards the exit relay, enabling it to
vertising incorrect BGP control messages. While these deanonymize the Tor communication.
attacks are well known in the networking community, we
are the first to apply these attacks to anonymity systems
such as Tor.
in the connecting being dropped. Next, we discuss a
AS-level adversaries can hijack an IP prefix [51] by
more sophisticated routing attack called BGP intercep-
advertising the prefix as its own. The attack causes a
tion attack [16], that allows adversaries to perform exact
fraction of Internet traffic destined to the prefix to be
deanonymization of Tor users.
captured by the adversary. Tor relay nodes can ob-
serve a large amount of client traffic. For example, a A prefix interception attack allows the malicious AS to
Tor guard relay observes information about client IP ad- become an intermediate AS in the path towards the guard
dresses. Thus, the IP prefixes corresponding to Tor guard relay, i.e., after interception, the traffic is routed back to
relays presents an attractive target for BGP hijack. the actual guard relay. Such an interception attack al-
As a concrete attack example, we consider a scenario lows the connection to be kept alive, enabling the ma-
where an AS-level adversary aims to deanonymize the licious AS to exactly deanonymize the client via asym-
user associated with a connection to a sensitive Web metric traffic analysis.
server (say a whistleblowing website). The adversary can Similar to the previous discussion, let us consider an
first use existing attacks on the Tor network to uncover adversary trying to deanonymize the user connecting to
the identity of the client’s guard relay [39, 37, 31, 42]. a sensitive website (the adversary already sees the traf-
Next, the adversary can launch a BGP hijack attack fic towards the website). The adversary can first uncover
against the Tor relay. This allows the adversary to see the identity of the guard relay using existing attacks [39]
traffic destined to the guard relay. BGP hijack thus en- (as before), and then launch a prefix interception attack
ables an adversary to learn the set of all client IP ad- against the guard relay. Since the adversary routes the
dresses (anonymity set) associated with a guard relay traffic back to the guard relay, the client’s connection is
(and the target connection to the sensitive Web server). kept alive, allowing the adversary to launch asymmetric
We note that in a prefix-hijack attack, the captured traffic correlation attacks. Note that in contrast to BGP
traffic is blackholed, and the client’s connection to the hijack attacks, BGP interception attacks can perform ex-
guard is eventually dropped. Thus, it may not be pos- act deanonymization of Tor clients.
sible to perform fine-grained traffic analysis to infer the
true client identity from this anonymity set. However, the These attacks enable malicious ASes to deanonymize
identification of a reduced anonymity set (as opposed to user identity corresponding to a monitored target connec-
the entire set of Tor users) is already a significant amount tion. Similarly, ASes that already see the client’s traffic
of information leakage, and can be combined with other to its guard can position themselves to observe the traffic
contextual information to break user anonymity [18]. In between the server and the exit relay by launching inter-
Section 5, we uncover several real-world BGP hijack at- ception attacks against exit relays. Figure 3 illustrates
tacks in which Tor relays were among the target prefixes. this attack scenario.
Finally, we note that a remote adversary can launch in-
2.4 BGP Interception terception attacks against both guard relays and exit re-
lays simultaneously, to perform general surveillance of
Our BGP hijack attack discussed above allows adver- the Tor network. In Section 5, we demonstrate a real-
saries to capture traffic destined towards a target Tor world BGP interception attack against a live Tor relay by
prefix, but the captured traffic is blackholed, resulting collaborating with autonomous system operators.

4
274 24th USENIX Security Symposium USENIX Association
3 Asymmetric Traffic Analysis

4
client client
server server

3
In this section, we experimentally show that asymmet-

Data (MB)

Data (MB)
2

2
ric traffic analysis attacks are feasible. We use the live
Tor network for our experiments. To protect the safety

1
of real Tor users, we generate our own traffic through the

0
0 50 100 150 200 250 300 0 50 100 150 200 250 300

Tor network. Our goal is to investigate the accuracy of

Time (s) Time (s)

asymmetric traffic analysis in deanonymizing our gener- (a) Client: ACK, Server: ACK (b) Client: ACK, Server: Data
ated traffic.

4
Experimental Setup: In order to generate our own
client client
server server

3
traffic through the live Tor network, we use Planet-

Data (MB)

Data (MB)
2

2
Lab nodes as clients and Web servers. PlanetLab is an
open platform for networking research, that provides ac-

1
cess to hundreds of geographically distributed machines.

0
0 50 100 150 200 250 300 0 50 100 150 200 250 300

We randomly pick 100 machines on PlanetLab, located

Time (s) Time (s)

across United States, Europe, and Asia. We installed Tor (c) Client: Data, Server: ACK (d) Client: Data, Server: Data
clients on 50 of those machines, and used the Privoxy
tool (www.privoxy.org) to configure wget requests to Figure 4: Asymmetric traffic analysis shows high corre-
tunnel over Tor. The remaining 50 machines were setup lation between a matched client/server pair
to be Web servers, each containing a 100MB image file.
We use the default Tor configuration on the 50 client
has insignificant correlation coefficients with all servers,
machines. We launch wget requests on the 50 clients
so it fails to be matched to any servers. We did not ob-
at the same time, each requesting a 100MB image file
serve any false positives in our results.
from one of the 50 web servers, respectively. We use
tcpdump to capture data for 300 seconds at the clients
Client ACK/ Client ACK/ Client Data/ Client Data/
and the servers during this process. Server ACK Server Data Server ACK Server Data
Asymmetric correlation analysis: In each packet trace, Overall 96% 94% 96% 94%
we first extract the TCP sequence number and TCP ac- False negative 4% 6% 4% 6%
knowledgment number fields in the TCP header. Us- False positive 0% 0% 0% 0%

ing the TCP sequence and acknowledgment numbers, we

next compute the number of transmitted data bytes per Table 2: Asymmetric traffic analysis accuracy rate
unit time. For each pair of observed traces, we com-
pute the correlation between the vector of transmitted In addition to the actual observed error rate above, we
data bytes over time. For our analysis, we use the Spear- also performed a statistical tests to compute the 95% con-
man’s rank correlation coefficient (other correlation met- fidence interval on our error rate, given our sample size
rics could also be applicable). For each client, our asym- of 50 client machines and 50 server machines. Table 3
metric traffic analysis attack selects the server trace with illustrates the confidence intervals on our error rates.
the highest correlation as the best match.
Client ACK/ Client ACK/ Client Data/ Client Data/
Results: Figure 4 illustrates our asymmetric analysis Server ACK Server Data Server ACK Server Data
computed between a client server pair that is commu-
0.48% – 1.25% – 0.48% – 1.25% –
nicating. We can see high correlation in all four ob- False negative
13.71% 16.54% 13.71% 16.54%
servation scenarios discussed in Section 2. Figure 5 il- False positive
0% – 0% – 0% – 0% –
0.15% 0.15% 0.15% 0.15%
lustrates our asymmetric analysis computed between a
client server pair that is not communicating with each
other. We can see that incorrectly matched pairs have Table 3: Asymmetric traffic analysis error rate confi-
poor correlation in all four observation scenarios. Fig- dence interval
ure 6 illustrates the detection accuracy rate grows as the
duration of attack increases, especially in the first 30 sec-
onds. 4 Natural Churn
We computed the detection accuracy of our asymmet-
ric traffic analysis attacks in all four scenarios after 300 In this section, we study and evaluate how routing dy-
seconds (by selecting the highest correlated pair), and namics, or churn, increase the power of AS-level adver-
obtained an average accuracy of 95% (Table 2). The er- saries in anonymity systems such as Tor. We start with
ror matches are all false negatives, for which the client an exhaustive control-plane analysis using collected BGP

5
USENIX Association 24th USENIX Security Symposium 275
 taining to 550,000 IP prefixes collected by six RIPE-
4

4
maintained BGP Looking Glass (rrc00, rrc01, rrc03,
client client
3 server server

3
rrc04, rrc11, rrc14) [6] in January 2015 over 250+ BGP
Data (MB)

Data (MB)
2

2
sessions. We processed the dataset to remove any arti-
facts caused by session resets [20]. In parallel, we also
1

1
collected Tor-related data (IP address, flags and band-
0

0
0 50 100 150 200 250 300 0 50 100 150 200 250 300

width) of about 6755 Tor relays active during the same

Time (s) Time (s)

(a) Client: ACK, Server: ACK (b) Client: ACK, Server: Data period of time [4]. Among all Tor relays, 1459 (resp.
1182) of them were listed as guards (resp. exits) and 338
4

4
relays were listed as both guard and exit.
client client
server server
3

3
We considered each BGP session as a proxy for Tor
Data (MB)

Data (MB)
2

2
clients and destinations. Note that analysis implicitly ac-
counts for any Internet host reachable directly or indi-
1

rectly through these BGP sessions. Our dataset contains

0

0 50 100 150 200 250 300 0 50 100 150 200 250 300

sessions belonging to major Internet transit providers

Time (s) Time (s)

(c) Client: Data, Server: ACK (d) Client: Data, Server: Data such as Level-3, ATT, NTT, etc. that provide transit to
millions of hosts.
Figure 5: Asymmetric traffic analysis shows low corre- Static baseline. We computed a static baseline by con-
lation between an unmatched client/server pair sidering the amount of compromising ASes at the be-
ginning of our dataset, without considering any updates.
On each BGP session si , we computed and maintained
1.0

the routing table used to forward Tor traffic by consid-

0.8

ering all the BGP announcements and withdrawals re-

Accuracy Rate (%)
0.6

ceived over si . More precisely, we kept track of the most-

specific routing table entry that was used to forward traf-
0.4

fic to any Tor guard or exit relays. We refer to those as

0.2

Tor prefixes. In this context, a routing table entry for a

0.0

0 50 100 150
Time (s)
200 250 300
relay r is a five-tuple (ti ,t f , p, e, L) composed of: i) the
initial time ti at which the entry started to be used by
Figure 6: The accuracy of the attack quickly increases the router for forwarding traffic to r; ii) the final time t f
with time, reaching 80% within a minute, 95% after five at which the entry stopped to be used by the router; iii)
minutes. the corresponding IP prefix p; iv) a boolean e denoting
whether the r is an entry or an exit relay; and v) the list
of all the ASes L that will see the traffic en-route to reach
data (§4.1). Our results show that churn can increase the r (i.e., the AS-PATH).
amount of compromised Tor circuits by up to 50% over
a period of one month. We then confirmed our results by “on-path” AS

performing targeted data-plane measurements on the Tor g1 e1

network (§4.2). Again, churn significantly increased the s1 s1
s2 ASX g2 s2
percentage of vulnerable Tor circuits, nearly tripling it. ASX
…

e2
…

4.1 Control-plane Evaluation sn ASY sn

gk el
We quantified the impact of churn by measuring how it
sources guard exit destinations
increased the probability of a single AS (say AS X) to (BGP sessions) relays relays (BGP sessions)

end up simultaneously on the path between a client and

a guard relay and on the path between a destination and Figure 7: Control-plane evaluation setup
an exit relay. When this happens, we considered AS X
as (potentially) compromising for the pair (client, desti- Using the routing-table data, we accounted, for each
nation) using the corresponding Tor circuit. Observe that AS X, the number of pairs ((si , gi ), (s j , e j )) for which it
our analysis leverages asymmetric traffic analysis (§3) as appeared simultaneously in the AS-PATH. Here, si (resp.
it only requires X to be on-path for two publicly-known s j ) refers to a client (resp. destination) session, while gi
prefixes, covering the guard and the exit relay. (resp. e j ) refers to a Tor guard (resp. exit) relay. To
Datasets We collected 612+ million BGP updates per- ensure meaningful results, we only considered cases in

6
276 24th USENIX Security Symposium USENIX Association
which si and s j are in different ASes to ensure enough Name ASN Tor circuits (%) seen Country
diversity in the paths seen. As illustration, in Fig. 7, NTT 2914 91 US
ASX is a compromising AS for the pair ((s1 , g1 ), (s2 , IIJ 2497 91 Japan
BroadbandONE 19151 91 US
e2 )), meaning it can deanonymize any clients connected Inet7 13030 91 CH
beyond s1 and exchanging data with a destination con- Level3 3356 88 US
nected beyond s2 which uses g1 (resp. e2 ) as a guard Tinet 3257 86 DE
Cogent 174 63 US
(resp. exit) relay. Level3/GBLX 3549 58 US
TATA AMERICA 6453 53 US
TeliaSonera 1299 50 SWE
100 100

Table 4: A few well-established ASes simultaneously see

80 80

60
some traffic for up to 90% of all (entry, exit) relays pairs.
CCDF

60
CCDF

40
40

20
20

0
0
0 10 20 30 40
1 2 3 4
ratio between the # of compromised circuits
5 jority of the Tor circuits. Due to their central position
% of compromised Tor circuits per (src,dst) pairs
when considering churn and without in the Internet, a few ASes naturally tend to see a lot of
(a) Static baseline (b) Churn-induced increase Tor traffic crossing them. To account for this effect, we
compute how many Tor circuits crossed each AS from
Figure 8: Without considering churn, more than 5% of at least one (src,dst) pair. The top 10 ASes in terms
all the possible Tor circuits are compromised by at least of compromised circuits are listed in Table 4. Large net-
one AS in 20% of the cases (left). The amount of com- works such as NTT or Level3 are able to see Tor traffic
promised circuits increase for the majority of the (src, for up to 90% of Tor circuits.
dest) pairs (60%) when considering churn, by up to 50%
in 20% of the cases (right).
4.2 Data-plane Evaluation
Fig. 8a depicts the percentage of compromised Tor cir- Next, we aim to quantify the impact of churn using data-
cuits for each source and destination as a Complemen- plane information collected via traceroute.
tary Cumulative Distribution Function (CCDF). A point Datasets We ran traceroute between 70 RIPE Atlas
(x, y) on the curve means that x% of all Tor circuits, i.e. probes [5] to measure the actual forwarding path taken
(guard,exit) pairs, are compromised for at least y% by packets entering and exiting the Tor network. We se-
of all the (src,dst) pairs. We see that, for 50% of all lected one probe in 70 different ASes, split in the follow-
the (src,dst) pairs, at least 0.75% of the Tor circuits ing four sets:
are compromised by at least one AS. This number grows
to 6% and 13% of the Tor circuits considering the 75th - • S1 : 10 ASes that contain the most Tor clients [35];
and 95th -percentile, respectively. • S2 : 25 ASes that cumulatively contained ∼50% of all
Measuring the effect of churn. We computed the num- guard relay bandwidth;
ber of extra Tor circuits that got compromised by at least • S3 : 25 ASes that cumulatively contained ∼50% of all
one AS over one month. To be fair, we only considered a exit relay bandwidth;
Tor circuit as compromised if it crossed the same AS for
• S4 : 10 ASes that contain the most Tor destina-
at least 30 seconds as it is unlikely that a time-correlation
tions [35].
attack can be performed in shorter timescale. Fig. 8b
plots the ratio between the amount of compromised Tor We then ran daily traceroutes over a 3 weeks period be-
circuits for each (src,dst) pair at the end of the month tween all probes in S1 towards all probes in S2 (and vice-
with respect to the static baseline amount. We see that versa), measuring the forwarding paths P1 between Tor
churn significantly increases the probability of compro- clients and guard relays, and the paths P2 between guard
mise. Indeed, the amount of compromised circuits in- relays and Tor clients. Similarly, we measured the for-
crease for 60% of the (src,dst). The increase reaches warding paths P3 between exit relays and Tor destina-
50% (ratio of 1.5) in 20% of the cases. tions, and the paths P4 between Tor destinations and exit
In addition to increasing the number of compro- relays. Overall, we measured 10 × 25 × 25 × 10 = 62500
mised Tor circuits, churn also increases the number of possible Tor circuits.
compromisable (src,dst) pairs. Indeed, while 5593 Churn nearly tripled the amount of vulnerable Tor
(src,dst) pairs could be compromised without up- circuits. If we use conventional methodology and only
dates, that number increased to 5754 pairs when consid- look for common ASes between P1 and P3 , we found
ering updates (an augmentation of nearly 3%). 12.8% of Tor circuits to be vulnerable on the first day
Few powerful ASes see some traffic for a large ma- of the experiment (red line in Fig. 9). In comparison,

7
USENIX Association 24th USENIX Security Symposium 277
 % relays % bw # pfx Name ASN
10.5 23 11.80 OVH 16276
% of Tor Circuits Vulnerable 6.30 13 6.68 Hetzner 24940
0.30
4.78 7 10.52 Online.net 12876
3.04 4 2.58 Wedos 197019
0.20

2.04 14 4.27 Leaseweb 16265

1.69 9 3.86 PlusServer 8972
0.10

Forward paths (day 1)

Bidirectional paths (day 1)
Bidirectional paths (day 21)
Total 28.35 70 39.71
0.00

5 10 15 20
Time (Day)
Table 5: 6 ASes and 70 prefixes host ∼30% of all Tor
guard and exit relays as well as ∼40% of the entire Tor
network bandwidth. As such, these constitute extremely
Figure 9: Percentage of Tor circuits vulnerable to an AS attractive targets for hijacks and interceptions attacks.
level adversary

5.2 Known Prefix Hijacking Attacks

if we also consider asymmetric paths (i.e., also look for While there have been numerous well-documented BGP
common ASes between P1 and P4 , P2 and P3 , and P2 and prefix hijacks and interceptions, it was unknown whether
P4 ), the percentage of vulnerable Tor circuits nearly dou- Tor traffic was intercepted or not. To this extent, we stud-
bled to 21.3% on the first day (blue line in Fig. 9), and ied occurrences of well-known prefix hijacks and looked
nearly tripled to 31.8% at the end of the three week pe- for leaked prefixes covering at least a Tor relay. To do so,
riod (green line in Fig. 9). we gathered BGP updates from Routeviews [7] around
the time of each attack and filtered out the ones unre-
lated to Tor prefixes. Overall, we found that three well-
5 BGP Attacks: Hijack and Interception known hijacks affected Tor relays: two separate incidents
involving one of Indonesia’s largest telecommunication
networks, Indosat, as well as one malicious hijack attack
In this section, we study and evaluate the feasibility whose goal was to steal Bitcoins.
of BGP hijack and interception attacks on the Tor net-
work. First, we show that Tor relays tend to be concen-
trated within few ASes and IP prefixes—making those # hijacked # hijacked # hijacked
Event
highly attractive targets for hijack and interception at- relays guards exits
tacks (§5.1). Second, we show that, in several real- Indosat 2011 5 (0.24%) 1 (0.15%) 4 (0.44%)
world BGP hijack attacks, Tor relays were among the Indosat 2014 44 (0.80%) 38 (1.80%) 17 (1.65%)
target prefixes (§5.2). Third, we perform a real-world
BGP interception attack against a live Tor guard relay, Table 6: Summary statistics for known Indosat prefix hi-
with success, to demonstrate the ability to accurately jacking events.
deanonymize Tor clients (§5.3).
Indosat 2011. On January 14th, 2011, Indosat (AS4761)
originated 2,800 new prefixes, which covered 824 differ-
5.1 Tor relays concentration ent ASes [2]. 7 of these prefixes affected the Tor net-
work by covering 5 of the Tor relays. As discussed in
The amount of Tor traffic attracted by a hijack or an in- Section 2, Indosat could potentially have learned infor-
terception attack depends on the number of relays that mation about the client IP addresses associated with each
lie within the corresponding prefix. As such, prefixes of the guard relays (reduced anonymity set).
and ASes that host many relays of high bandwidth are an Indosat 2014. On April 3, 2014, Indosat originated
interesting targets for attackers. To evaluate how vulner- 417,038 new prefixes; it usually originates 300 pre-
able the Tor network was to hijack and interceptions at- fixes [3]. This compromised 44 Tor relays, 38 of which
tacks, we computed the number of relays present in each were guard relays and 17 of which were exit relays (11
AS and in each BGP prefix. Surprisingly, close to 30% hijacked relays were both guards and exits). Table 6
of all relays are hosted in only 6 ASes and 70 prefixes. shows the summary statistics of both Indosat hijacking
Together, these relays represent almost 40% of the band- incidents.
width in the entire Tor network (see Table 5). As such, Canadian Bitcoin 2014. From February 2014 to
these few prefixes constitute extremely attractive targets. May 2014, an attacker compromised 51 networks at

8
278 24th USENIX Security Symposium USENIX Association
 traic traic
Internet Internet

announce client announce client

184.164.244.0/23 184.164.244.0/23

Transit Transit
GATECH Portal GATECH Portal
(AS 2637) VPN (AS 2637) VPN
Public AS Tunneling Public AS Tunneling
47065 47065

announce
VPN VPN
guard relay 184.164.244.0/24 guard relay
Tunneling Tunneling

ISI Transit ISI Transit

(AS 226) Portal (AS 226) Portal

Public AS Public AS
47065 47065

Figure 10: Transit Portal setup Figure 11: ISI performing interception attack

19 different ISPs, and resulted in the theft of ap- 184.164.244.0/23 (run by us in its entirety for the dura-
proximately $83,000 in Bitcoin [1]. We found that tion of our research) via the GATECH TP, so that traffic
198.245.63.0/24 and 162.243.142.0/24 were hijacked, destined for IP addresses within that range will be routed,
and contained a Tor relay, 198.245.63.228. AS16276 first to the GATECH TP, and then sent to our machine
(OVH) owns 198.245.63.0/24, but this prefix was hi- via the corresponding tunnel. We illustrate our setup in
jacked by AS21548 (MTO Telecom). The Tor relay that Fig. 10.
consequently was hijacked, 198.245.63.228, was a guard Next, We advertise BGP prefix 184.164.244.0/24
relay located in Montreal, Quebec. via the ISI TP, which constitutes a more-specific prefix
While we do not make any claims about the intent of attack against the original announcement announced by
the above hijacking ASes, our analysis shows the exis- the GATECH TP. Thus, after the new BGP prefix an-
tential threat of real-world routing attacks on the Tor net- nouncement gets propagated through the internet, Tor
work. Furthermore, the fact that the Tor and the research client traffic that is destined for our guard will be sent
community missed noticing the presence of Tor relays to ISI instead. Since we configured the ISI TP to forward
among the hijacked prefixes is surprising. traffic to our guard machine, the Tor relay can still re-
ceive the traffic and keep the Tor connection alive after
5.3 BGP Prefix Interception Attack Exper- the attack. We illustrate the interception attack model in
Fig. 11.
iment
Our setup constitutes a BGP interception attack. Ini-
Methodology and setup. We now demonstrate the feasi- tially, traffic is routed via GATECH and arrives at our Tor
bility of the interception attack by performing one, with relay machine via GATECH tunnel. After the attack hap-
success, on the live Tor network. For that, we set up a pens, traffic drains from GATECH tunnel and gets routed
machine to run as a Tor guard relay and made it reachable via ISI, and thus comes to our Tor relay machine via ISI
to the Internet by announcing a /23 prefix in BGP using tunnel instead. Since the traffic still arrives at the relay
Transit Portal (TP) [43]. TP enables virtual ASes to es- machine, it is an interception attack and the connection
tablish full BGP connectivity with the rest of the Internet does not get interrupted. We use tcpdump on our relay
by proxying their announcements via dozens of world- machine, listening to ISI tunnel, to capture client TCP ac-
wide deployments. Next, we configure the 50 Tor clients knowledgment traffic coming from that tunnel, which is
in PlanetLab to use our Tor guard relay as the entry relay exactly the data that an adversary would get from launch-
to reach 50 web servers, also hosted in PlanetLab. ing such an interception attack.
In order to perform the BGP prefix interception at- In the experiment, we first launch simultaneous HTTP
tack, we used two TP deployments (GATECH and ISI), requests using wget at the 50 Tor clients for the 100MB
located in different ASes. GATECH TP served the pur- file at the 50 web servers. Then, 20 seconds after launch-
pose of the “good” AS through which Tor traffic is nor- ing the wget requests, we start announcing the more-
mally routed, while ISI TP served as the “malicious” specific prefix via ISI. We use tcpdump listening to ISI
AS which performed the interception attack. We con- tunnel to capture TCP acknowledgment traffic sent from
nected the two TPs to our Tor relay machine via VPN the Tor clients during the interception attack. We also use
tunnels. First, in order for our Tor guard relay (run- tcpdump to capture traffic at the web servers during the
ning on 184.164.244.1) to be reachable, we advertised whole process. Finally, 300 seconds after launching the

9
USENIX Association 24th USENIX Security Symposium 279
 2.0

2.0
15

15
client client
server server

1.5

1.5
10

10
Data (MB)

Data (MB)

Data (MB)

Data (MB)
1.0

1.0
5

0.5

0.5
0.0

0.0
0

0
0 100 200 300 400 0 100 200 300 400 0 50 100 150 200 250 0 50 100 150 200 250
Time (s) Time (s) Time (s) Time (s)

(a) Traffic Flow via GATECH (b) Traffic Flow via ISI (a) Client & Correlated Server (b) Client & Uncorrelated Server

Figure 12: Traffic Flow During the Experiment Figure 13: Client ACK versus Server ACK analysis

attack, we send a withdrawal message via the ISI TP, so 20

the traffic will be routed via GATECH again as normal.
Our interception attack successfully deanonymized

frequency (%)
15
Tor sources with a 90% accuracy rate. In Fig. 12, we
plot the Tor traffic flow captured on our relay machine 10
from both GATECH tunnel and ISI tunnel. We can see
that all traffic is routed via GATECH at the beginning. 5
At t = 20s, ISI starts advertising a more specific /24 pre-
0
fix, which takes approximately 35 seconds for it to be 8 10 13 16 19 22 25
propagated through the internet and drain the traffic from prefix length
GATECH. At t = 55s, traffic starts showing up via ISI,
and GATECH does not receive traffic any more. Then, Figure 14: >90% of BGP prefixes hosting relays are
at t = 300s, ISI withdraws the IP prefix announcement, shorter than /24, making them vulnerable to our attack.
which takes approximately 22 seconds for the traffic to
appear back on GATECH again. During this interception files from the web servers at the same time, so the band-
process, the connection stays alive. width they could achieve will be limited by the guard and
The captured data from ISI tunnel is client TCP ac- the exit relay, which leads to similar bandwidths due to
knowledgment traffic. Thus, we will employ our Asym- the guard/exit bottleneck. However, this scenario is an
metric Traffic Analysis approach, described in Section 3, extreme and very unlikely case in real Tor connections.
with sample size of 50 client machines and 50 server With fewer clients connecting to the same Tor guard re-
machines to do the correlation analysis to deanonymize lay at the same time, the accuracy of the asymmetric traf-
users’ identity. We achieve 90% accuracy rate (see Ta- fic analysis should be higher.
ble 7). The vast majority of Tor relays are vulnerable to our
attacks. Technically, only prefixes shorter than /24 can
Accuracy False False
Rate Negative Positive be hijacked globally with a more-specific prefix attack
as longer prefixes tend to be filtered by default by many
Client ACK/Server ACK 90% 8% 2%
ISPs. To make sure of the feasibility of our attack, we
Table 7: Asymmetric Traffic Analysis accuracy rate computed the prefix length distribution of Tor prefixes
(see Fig.14). We can see that more than 90% of BGP pre-
fixes hosting relays have prefix length shorter than /24,
Fig. 13 shows an example of a client with its correlated
making them directly vulnerable to a more-specific pre-
server and an uncorrelated server, respectively. Note that
fix attack such as ours.
the time shown on the graph has been adjusted according
to the time that traffic starts showing via ISI.
The detection accuracy rate in the interception attack 6 Countermeasures Sketch
case decreases from the average 95% in static asymmet-
ric traffic analysis to 90%. One main reason is that we In this section, we first describe a taxonomy of counter-
configure all 50 Tor clients to connect to the same Tor measures against Raptor attacks. Second, we describe
guard relay, which leads to significantly higher probabil- a general approach for AS-aware anonymous communi-
ity that many of them will share the same Tor exit relay cation in which Tor clients are aware of the dynamics
(especially those clients which are in the same AS) as of Internet routing. Finally, we describe exploratory ap-
well, and as a result, their bandwidths are highly likely proaches for detecting and preventing BGP hijack and
to be similar. And also, all the clients start requesting interception attacks against Tor.

10
280 24th USENIX Security Symposium USENIX Association
6.1 Countermeasure Taxonomy 6.3 Mitigating Routing Attacks in Tor
There are two main categories of countermeasures: (a) Next, we consider two approaches for mitigating Rap-
approaches that reduce the chance of an AS-level adver- tor’s routing attacks: detection and prevention.
sary observing both ends of the anonymous communica-
tion, and (b) approaches that aim to mitigate correlation 6.3.1 Monitoring Framework for Detection Routing
attacks even when an adversary observes both ends of Attacks
the anonymous communication. Figure 15 illustrates the
We propose that the Tor network monitor the routing
design space of potential countermeasures against Rap-
control-plane and data-plane for robust detection of rout-
tor attacks. In this work, we advocate the former line of
ing attacks. Detecting routing attacks serves two pur-
defense – namely, to monitor both routing control-plane
poses: (1) First, this serves to raise awareness about the
and data-plane, and to strategically select Tor relays that
problem and hold attackers accountable. (2) Second, Tor
minimize the chance of compromise (§6.2). We also ad-
directory authorities can notify clients. Such notifica-
vocate defenses that aim to detect and prevent routing at-
tions allow the end-user to respond by either suspend-
tacks (§6.3). We do not focus on the class of approaches
ing its use of Tor (since most hijacks and interceptions
that aim to mitigate correlation analysis by obfuscating
are short lived), or choose another Tor relay . Next, we
packet sizes and timings, as they are generally consid-
discuss two proof-of-concept monitoring frameworks,
ered too costly to deploy (Appendix A).
based on BGP data and traceroute data respectively.
BGP Monitoring Framework. Our BGP monitor-
ing framework gathers BGP data from the Routeviews
Taxonomy  of  Countermeasures  
project. The framework filters BGP updates to consider
data about prefixes that involve a Tor relay. Building
1.  Mi4ga4ng  Traffic  Intercep4on   2.  Mi4ga4ng  Correla4on  A=acks   upon prior work in routing attack detection [16], we im-
plement the following heuristics. (1) Frequency heuris-
Sta4c    
Routes  
Rou4ng     Rou4ng    
Asymmetry   Churn  
Rou4ng    
A=acks  
Symmetric  
Correla4on  
Asymmetric    
Correla4on  
tic: routing attacks can be characterized by an AS an-
nouncing a path once (or extremely rarely) to a prefix that
*Monitor  AS-­‐Level     Obfuscate     it does not own. The frequency heuristic detects attacks
Paths   *Adver4se     Packet  Timing   Encrypt  TCP    
/24  prefixes   Header     that exhibit this behavior. It measures the frequency of
                 +  
*Select  closer    
Obfuscate    
Packet  Sizes  
Randomize    
TCP  Ack  protocol  
each AS that originates a given prefix; if the frequency
*AS-­‐Aware    
Path  Selec4on  
Guards  
Secure  BGP    
is lower than a specified threshold, then it could be a po-
Deployment   tential hijack attack. (2) Time Heuristic. Most known
attacks, including those discussed in § 5, last a relatively
Figure 15: Taxonomy of Countermeasures short amount of time. The time heuristic measures the
amount of time each path to a prefix is announced for;
if the amount of time is extremely small (below a speci-
fied threshold), then there is the possibility of it being a
6.2 AS-Aware Path Selection routing attack.
Detection Capability: We tested our BGP monitoring
To minimize opportunities for AS-level traffic analysis, framework based on BGP data during known prefix hi-
the Tor network can monitor the path dynamics between jack attacks, that were discussed in § 5. As a preliminary
the clients and the guard relays, and between the exit re- validation, the frequency and time heuristics were able
lays and the destinations. Information about path dynam- to detect all of the known attacks; the threshold used for
ics can be obtained using data-plane (e.g., traceroute) the frequency heuristic was .00001 (the fraction {# of an-
or control-plane (e.g., BGP feed) tools. For instance, nouncements for prefix p originated by AS A}/{total # of
each relay could publish the list of any ASes it used to announcements for prefix p}), and the threshold used for
reach each destination prefix in the last month. This in- the time heuristic was .01 (the fraction {length of time
formation can be distributed to all Tor clients as part of that prefix p is originated by AS A}/{total length of time
the Tor network consensus data. Tor clients can use this prefix p is announced by any AS}).
data in relay selection, perhaps in combination with their Traceroute Monitoring Framework. The BGP mon-
own traceroute measurements of the forward path to each itoring framework provides measurements of actual AS-
guard relay. For example, Tor clients should select relays level paths from BGP collector nodes. However, the in-
such that the same AS does not appear in both the first put data to the monitoring framework is limited to peers
and the last segments, after taking path dynamics into who chose to participate in frameworks such as Route-
account. views, and BGP data is only a noisy indicator of the rout-

11
USENIX Association 24th USENIX Security Symposium 281
ing control-plane. For robust detection of attacks, it is cate that Tor clients select their guard relays by favoring
also necessary to monitor the data-plane, which we do Tor relays with a shorter AS-level path between them.
via a Traceroute monitoring framework. Tor clients could either obtain AS-level path information
Traceroute is a network diagnostic tool that infers the via the Tor network consensus download mechanism, or
routers traversed by internet packets. To analyze both they can perform traceroutes themselves. This further
attacks and changes in AS-level paths to the Tor net- mitigates the risk to Tor clients due to an equally specific
work, we have built a traceroute monitoring framework prefix attack. We note that by selecting guard relays that
that runs traceroutes from 450 PlanetLab machines to all are closer to the client in the AS topology, the risk of
Tor entry and exit relays and stores the resulting tracer- asymmetric traffic analysis and BGP churn is also miti-
oute data. The set of all Tor entry and exit relays is gated. 2
updated daily to accommodate new relays that have re- Securing inter-domain routing: The research commu-
ceived the guard and exit flags. BGP hijack and inter- nity has proposed multiple protocols for securing inter-
ception attacks typically affect a variety of users from domain routing [41, 32, 19, 29, 17]. Real-world deploy-
different vantage points. Thus, traceroute measurements ment of these protocols would mitigate the BGP hijack
from 450 geographically diverse PlanetLab have the abil- and interception attacks on Tor. However, this approach
ity to detect data-plane anomalies arising out of routing requires buy-in from multiple stakeholders in the com-
attacks. The PlanetLab machines are distributed across plex ecosystem of the Internet, and progress on this front
140 ASes. Meanwhile, the Tor entry relays are dis- has been slow. We hope that the concerns we raise about
tributed across 982 ASes and the exit relays are dis- the compromise of user anonymity in Tor can help accel-
tributed across 882 ASes. We use Team-Cymru (http: erate the momentum for improving BGP security.
//www.team-cymru.org/) to compute the mapping be-
tween an IP address and its autonomous system. We will
make the data collected by our Traceroute monitoring 7 Discussion and Ethical Considerations
framework available to the research community.
Detection Capability: As a preliminary validation, our Colluding adversaries. In this paper, we quantified the
Traceroute monitoring framework was able to detect the threat of Raptor attacks from the perspective of indi-
the BGP interception attack discussed in § 5. From the vidual autonomous systems. In practice, autonomous
traceroute data, we observed AS-level path changes from systems can collude with each other to increase their
every PlanetLab node to our Tor guard relay, indicating capability of monitoring Tor traffic. For example, au-
an anomaly. tonomous systems within the same legal jurisdiction may
be forced to monitor Tor traffic and share it with a single
entity that may launch Raptor attacks.
6.3.2 Preventing Routing Attacks in Tor Applicability to other anonymity systems. It is impor-
In addition to monitoring the routing control-plane and tant to note that our attacks merely consider Tor as an
data-plane with respect to the Tor network, the following example of a low-latency anonymity system. Raptor at-
approaches can help prevent the threat of Raptor’s rout- tacks are broadly applicable to other deployed anonymity
ing attacks. systems such as I2P, Freenet and Tribler [47, 21, 50].
Advertising /24 Tor prefixes: Our experimental mea- Ethical considerations. We introduce and evaluate sev-
surements indicate that over 90% of Tor relays have a eral novel attacks against the Tor network. The Tor net-
prefix length shorter than /24. This allows an AS-level work has a userbase of several million users [9], and
adversary to launch a BGP hijack or interception attack these users are especially concerned about the privacy of
against these Tor relays by advertising a more specific their communications. Thus, it is of utmost importance
prefix for them (globally). We advocate that the Tor re- that our real-world experiments on the Tor network do
lay operators should be running Tor relays with a prefix not compromise the privacy and safety of Tor users. In
length of /24. Autonomous systems typically filter route this paper, we take multiple precautions to safeguard the
advertisements of prefix longer than /24, so AS-level ad- privacy of Tor users:
versaries will not be able to launch a more specific hijack
or interception attack. • Attack our own traffic. All of our attacks only exper-
Favoring closer guard relays: Even if a Tor relay adver- iment with traffic that we created ourselves, i.e., we
tises a /24 prefix, an AS-level adversary can launch an deanonymize our own traffic. In fact, we do not store
equally specific prefix hijack or interception attack (by or analyze traffic of any real Tor user.
advertising another /24). In this case, the impact of the 2 We note that if clients select closer guards, then knowledge of the
attack is localized around the attacker’s autonomous sys- guards reveals probabilistic information about the clients. We will in-
tem, since the route is not globally propagated. We advo- vestigate this trade-off in future work.

12
282 24th USENIX Security Symposium USENIX Association
• Attack our own relay. Similarly, to demonstrate the may not deanonymize the Tor clients. In contrast, Raptor
threat of prefix interception attacks on the live Tor net- attacks can completely deanonymize Tor clients.
work, we launch interception attacks against relays BGP insecurity: The networking research community
that we already control, i.e., we hijack/intercept our has extensively studied attacks on inter-domain routing
own prefix. protocols including BGP hijack [51, 52, 53, 44] and in-
• Firewall our Tor relay. We also used network-level terception attacks [16]. Similarly, there has been much
firewalls to ensure that real Tor users will never use re- work on proposing secure routing protocols that resist the
lays that we control: traffic from real users is dropped above attacks [41, 32, 17, 19, 29]. However, we are the
by the firewall. Only authorized traffic that we create first to study the implications of these attacks on privacy
ourselves can bypass the firewall and use our Tor relay. technologies such as the Tor network. Arnbak et al. [14]
discuss surveillance capabilities of autonomous systems
from a legal perspective, but do not discuss anonymity
8 Related Work systems.

AS-level adversaries: It is well known that an adversary

who can observe users’ communications at both ends 9 Conclusion
of the segment can deanonymize Tor clients [45, 54].
Feamster and Dingledine were the first to consider the at- Raptor attacks exploit the dynamics of Internet routing
tack from the perspective of an AS-level adversary [28]. (such as routing asymmetry, routing churn, and routing
Later, Edman and Syverson explored the impact of attacks) to enable an AS-level adversary to effectively
Tor path selection strategies on the security of the net- compromise user anonymity.
work [26]. Recently, Johnson et al. analyzed the secu- Our experimental results show that Raptor attacks
rity of the Tor network against AS-level adversaries in present a serious threat to the security of anonymity sys-
terms of user understandable metrics for anonymity [34], tems. Our key results include (1) demonstration of asym-
and Akhoondi et al. [13] considered path selection algo- metric traffic correlation on the live Tor network, which
rithms that minimize opportunities for AS-level end-to- achieves 95% accuracy with no observed false positives,
end traffic analysis. Finally, Murdoch et al. [40] consid- (2) quantifying the impact of routing asymmetry and
ered the analogous analysis with respect to Internet ex- routing churn on AS-level attacks – an increase of 50% to
change level adversaries, which are also in a position to 100% respectively compared to conventional attacks, (3)
observe a significant fraction of Internet traffic. uncovering historical BGP hijacks involving Tor relays,
We build upon these works and introduce Raptor at- and (4) successful demonstration of a traffic analysis at-
tacks, that leverage routing asymmetry, routing churn, tack via BGP interception on the live Tor network. We
and routing attacks to compromise user anonymity more also outlined a taxonomy of countermeasures against our
effectively than previously thought possible. attacks.
The attack observations in Raptor were briefly dis- Our work highlights the dangers of abstracting net-
cussed in a preliminary and short workshop paper [48]. work routing from the analysis of anonymity systems
In this paper, we go further by measuring the importance such as Tor, and motivates the design of next generation
of the attacks using real-world Internet control- and data- anonymity systems that resist Raptor.
plane data. We also demonstrate the attacks feasibility by
performing them on the live Tor network—with success. 10 Acknowledgments
Finally, we also describe efficient countermeasures to re-
store a good level of anonymity. Thanks to Ethan Katz-Bassett for support on setting up
Traffic analysis of Tor: An important thread of re- Transit Portal provided by the PEERING project. Thanks
search aims to perform traffic analysis of Tor commu- to ATLAS project for donating credits for our experimen-
nications via side-channel information about Tor relays. tal setup. Thanks to Matthew Wright, Nick Feamster,
Murdoch et al. [39], Evans et al. [27], and Jansen et Nikita Borisov and Roger Dingledine for helpful discus-
al. [33] have demonstrated attacks that use node con- sions. This work was supported by the NSF under the
gestion and protocol-level details as a side channel to grant CNS-1423139.
uncover Tor relays involved in anonymous paths. Fur-
thermore, Mittal et al. [37] and Hopper et al. [30, 31]
proposed the use of network throughput and network la- References
tency as a side channel to fingerprint Tor relays involved
in anonymous paths. We note that most of these attacks [1] BGP hijacking for cryptocurrency
provide probabilistic information about Tor relays, and profit. http://www.secureworks.com/

13
USENIX Association 24th USENIX Security Symposium 283
 cyber-threat-intelligence/threats/ [15] BALL , J. NSA stores metadata of millions of web
bgp-hijacking-for-cryptocurrency-profit/. users for up to a year, secret files show. http://
www.theguardian.com/world/2013/sep/30/
[2] Bgpmon: Hijack by AS4761 Indosat - a nsa-americans-metadata-year-documents,
quick report. http://www.bgpmon.net/ Sep. 2013.
hijack-by-as4761-indosat-a-quick-report/.
[16] BALLANI , H., F RANCIS , P., AND Z HANG , X. A
[3] BGPMon: Hijack Event Today by In- study of prefix hijacking and interception in the In-
dosat. http://www.bgpmon.net/ ternet. In Proceedings of the 2007 Conference on
hijack-event-today-by-indosat/. Applications, Technologies, Architectures, and Pro-
tocols for Computer Communications (New York,
[4] CollecTor: Your friendly data-collecting service NY, USA, 2007), SIGCOMM ’07, ACM, pp. 265–
in the Tor network. https://collector. 276.
torproject.org/.
[17] B OLDYREVA , A., AND LYCHEV, R. Provable se-
[5] RIPE Atlas. https://atlas.ripe.net/. curity of S-BGP and other path vector protocols:
Model, analysis and extensions. In Proceedings of
[6] RIPE RIS Raw Data. https://www.ripe.net/ the 2012 ACM Conference on Computer and Com-
data-tools/stats/ris/ris-raw-data. munications Security (New York, NY, USA, 2012),
CCS ’12, ACM, pp. 541–552.
[7] Routeviews. http://www.routeviews.org/.
[18] B RANDOM , R. FBI agents tracked
[8] Tor metrics portal. https://metrics.torproject.org. harvard bomb threats despite Tor.
Accessed, February 2015. http://www.theverge.com/2013/12/18/5224130/fbi-
agents-tracked-harvard-bomb-threats-across-tor.
[9] Who uses Tor? https://www.torproject.org/ Accessed, July 2014.
about/torusers.html.en. Accessed, February
2015. [19] C HAN , H., DASH , D., P ERRIG , A., AND Z HANG ,
H. Modeling adoptability of secure BGP proto-
[10] How the NSA attacks Tor/Firefox users col. In Proceedings of the 2006 Conference on
with QUANTUM and FOXACID. https: Applications, Technologies, Architectures, and Pro-
//www.schneier.com/blog/archives/2013/ tocols for Computer Communications (New York,
10/how_the_nsa_att.html, Oct. 2013. NY, USA, 2006), SIGCOMM ’06, ACM, pp. 279–
290.
[11] Peeling back the layers of Tor with Egotis-
ticalGiraffe. http://www.theguardian. [20] CHUN C HENG , P., Z HAO , X., Z HANG , B., AND
com/world/interactive/2013/oct/04/ Z HANG , L. Longitudinal Study of BGP Monitor
egotistical-giraffe-nsa-tor-document, Session Failures. ACM SIGCOMM Computer Com-
Oct. 2013. munication Review (CCR) (April 2010).
[12] Tor stinks. http://www.theguardian. [21] C LARKE , I., S ANDBERG , O., W ILEY, B., AND
com/world/interactive/2013/oct/04/ H ONG , T. W. Freenet: A distributed anonymous
tor-stinks-nsa-presentation-document, information storage and retrieval system. In In-
Oct. 2013. ternational Workshop on Designing Privacy En-
hancing Technologies: Design Issues in Anonymity
[13] A KHOONDI , M., Y U , C., AND M ADHYASTHA , and Unobservability (New York, NY, USA, 2001),
H. V. Lastor: A low-latency AS-aware Tor client. Springer-Verlag New York, Inc., pp. 46–66.
In Proceedings of the 2012 IEEE Symposium on Se-
curity and Privacy (Washington, DC, USA, 2012), [22] DANEZIS , G. Mix-networks with restricted routes.
SP ’12, IEEE Computer Society, pp. 476–490. In Privacy Enhancing Technologies, R. Dingledine,
Ed., vol. 2760 of Lecture Notes in Computer Sci-
[14] A RNBAK , A., AND G OLDBERG , S. Loopholes for ence. Springer Berlin Heidelberg, 2003, pp. 1–17.
circumventing the constitution: Warrantless bulk
surveillance on americans by collecting network [23] DANEZIS , G., D INGLEDINE , R., AND M ATHEW-
traffic abroad. In HotPETs (2014). Available at SON , N. Mixminion: Design of a type iii anony-
http://ssrn.com/abstract=2460462. mous remailer protocol. In Proceedings of the 2003

14
284 24th USENIX Security Symposium USENIX Association
 IEEE Symposium on Security and Privacy (Wash- for Computer Communications (New York, NY,
ington, DC, USA, 2003), SP ’03, IEEE Computer USA, 2004), SIGCOMM ’04, ACM, pp. 179–192.
Society, pp. 2–.
[33] JANSEN , R., T SCHORSCH , F., J OHNSON , A.,
[24] D INGLEDINE , R., H OPPER , N., K ADIANAKIS , AND S CHEUERMANN , B. The sniper attack:
G., AND M ATHEWSON , N. One fast guard for life Anonymously deanonymizing and disabling the
(or 9 months). In HotPETs (2014). Tor network. In Proceedings of the 21st Annual
Network and Distributed System Security Sympo-
[25] D INGLEDINE , R., M ATHEWSON , N., AND
sium (NDSS ’14) (2014), Internet Society.
S YVERSON , P. Tor: The second-generation onion
router. In Proceedings of the 13th Conference on
[34] J OHNSON , A., WACEK , C., JANSEN , R., S HERR ,
USENIX Security Symposium - Volume 13 (Berke-
M., AND S YVERSON , P. Users get routed: Traf-
ley, CA, USA, 2004), SSYM’04, USENIX Associ-
fic correlation on Tor by realistic adversaries. In
ation.
Proceedings of the 2013 ACM SIGSAC Conference
[26] E DMAN , M., AND S YVERSON , P. AS-awareness on Computer and Communications Security (New
in Tor path selection. In Proceedings of the 16th York, NY, USA, 2013), CCS ’13, ACM, pp. 337–
ACM Conference on Computer and Communica- 348.
tions Security (New York, NY, USA, 2009), CCS
’09, ACM, pp. 380–389. [35] J UEN , J. Protecting anonymity in the presence of
autonomous system and Internet exchange level ad-
[27] E VANS , N. S., D INGLEDINE , R., AND versaries, 2012. MS Thesis, University of Illinois
G ROTHOFF , C. A practical congestion attack at Urbana-Champaign.
on Tor using long paths. In Proceedings of the
18th Conference on USENIX Security Symposium [36] M AC A SKILL , E., B ORGER , J., H OP -
(Berkeley, CA, USA, 2009), SSYM’09, USENIX KINS , N., DAVIES , N., AND BALL , J.
Association, pp. 33–50. GCHQ taps fibre-optic cables for secret ac-
cess to world’s communications. http:
[28] F EAMSTER , N., AND D INGLEDINE , R. Location //www.theguardian.com/uk/2013/jun/21/
diversity in anonymity networks. In Proceedings of gchq-cables-secret-world-communications-nsa,
the 2004 ACM Workshop on Privacy in the Elec- June 2013.
tronic Society (New York, NY, USA, 2004), WPES
’04, ACM, pp. 66–76. [37] M ITTAL , P., K HURSHID , A., J UEN , J., C AESAR ,
M., AND B ORISOV, N. Stealthy traffic analysis
[29] G ILL , P., S CHAPIRA , M., AND G OLDBERG , S. of low-latency anonymous communication using
Let the market drive deployment: A strategy for throughput fingerprinting. In Proceedings of the
transitioning to BGP security. In Proceedings of 18th ACM Conference on Computer and Communi-
the ACM SIGCOMM 2011 Conference (New York, cations Security (New York, NY, USA, 2011), CCS
NY, USA, 2011), SIGCOMM ’11, ACM, pp. 14– ’11, ACM, pp. 215–226.
25.
[38] M ÖLLER , U., C OTTRELL , L., PALFRADER , P.,
[30] H OPPER , N., VASSERMAN , E. Y., AND C HAN -
AND S ASSAMAN , L. Mixmaster Protocol — Ver-
T IN , E. How much anonymity does network la-
sion 2. IETF Internet Draft, July 2003.
tency leak? In Proceedings of the 14th ACM Con-
ference on Computer and Communications Secu-
[39] M URDOCH , S. J., AND DANEZIS , G. Low-cost
rity (New York, NY, USA, 2007), CCS ’07, ACM,
traffic analysis of Tor. In Proceedings of the 2005
pp. 82–91.
IEEE Symposium on Security and Privacy (Wash-
[31] H OPPER , N., VASSERMAN , E. Y., AND C HAN - ington, DC, USA, 2005), SP ’05, IEEE Computer
TIN, E. How much anonymity does network la- Society, pp. 183–195.
tency leak? ACM Trans. Inf. Syst. Secur. 13, 2 (Mar.
2010), 13:1–13:28. [40] M URDOCH , S. J., AND Z IELI ŃSKI , P. Sam-
pled traffic analysis by Internet-exchange-level ad-
[32] H U , Y.-C., P ERRIG , A., AND S IRBU , M. Spv: versaries. In Proceedings of the 7th Interna-
Secure path vector routing for securing BGP. In tional Conference on Privacy Enhancing Technolo-
Proceedings of the 2004 Conference on Applica- gies (Berlin, Heidelberg, 2007), PET’07, Springer-
tions, Technologies, Architectures, and Protocols Verlag, pp. 167–183.

15
USENIX Association 24th USENIX Security Symposium 285
[41] O ORSCHOT, P. V., WAN , T., AND K RANAKIS , E. [50] Z EILEMAKER , N., AND P OUWELSE , J. Open
On interdomain routing security and pretty secure source column: Tribler: P2P search, share and
BGP (psBGP). ACM Trans. Inf. Syst. Secur. 10, 3 stream. SIGMultimedia Rec. 4, 1 (Mar. 2012), 20–
(July 2007). 24.

[42] OVERLIER , L., AND S YVERSON , P. Locating hid- [51] Z HANG , Z., Z HANG , Y., H U , Y. C., AND M AO ,
den servers. In Security and Privacy, 2006 IEEE Z. M. Practical defenses against BGP prefix hi-
Symposium on (May 2006), pp. 100–114. jacking. In Proceedings of the 2007 ACM CoNEXT
Conference (New York, NY, USA, 2007), CoNEXT
[43] S CHLINKER , B., Z ARIFIS , K., C UNHA , I., F EAM - ’07, ACM.
STER , N., AND K ATZ -BASSETT, E. PEERING:
An AS for us. In Proceedings of the 13th ACM [52] Z HANG , Z., Z HANG , Y., H U , Y. C., M AO , Z. M.,
Workshop on Hot Topics in Networks (New York, AND B USH , R. iSPY: Detecting IP prefix hijacking
NY, USA, 2014), HotNets-XIII, ACM, pp. 18:1– on my own. IEEE/ACM Trans. Netw. 18, 6 (Dec.
18:7. 2010), 1815–1828.

[44] S HI , X., X IANG , Y., WANG , Z., Y IN , X., AND [53] Z HENG , C., J I , L., P EI , D., WANG , J., AND
W U , J. Detecting prefix hijackings in the Internet F RANCIS , P. A light-weight distributed scheme
with Argus. In Proceedings of the 2012 ACM Con- for detecting IP prefix hijacks in real-time. In
ference on Internet Measurement Conference (New Proceedings of the 2007 Conference on Applica-
York, NY, USA, 2012), IMC ’12, ACM, pp. 15–28. tions, Technologies, Architectures, and Protocols
for Computer Communications (New York, NY,
[45] S HMATIKOV, V., AND WANG , M.-H. Timing anal- USA, 2007), SIGCOMM ’07, ACM, pp. 277–288.
ysis in low-latency mix networks: Attacks and de-
[54] Z HU , Y., F U , X., G RAHAM , B., B ETTATI , R.,
fenses. In Proceedings of the 11th European Con-
AND Z HAO , W. On flow correlation attacks and
ference on Research in Computer Security (Berlin,
countermeasures in mix networks. In Proceedings
Heidelberg, 2006), ESORICS’06, Springer-Verlag,
of the 4th International Conference on Privacy En-
pp. 18–33.
hancing Technologies (Berlin, Heidelberg, 2005),
[46] S YVERSON , P., T SUDIK , G., R EED , M., AND PET’04, Springer-Verlag, pp. 207–225.
L ANDWEHR , C. Towards an analysis of onion rout-
ing security. In International Workshop on Design- A Appendix: Rejected Countermeasures
ing Privacy Enhancing Technologies: Design Is-
sues in Anonymity and Unobservability (New York, Obfuscating packet timings and sizes: While the use
NY, USA, 2001), Springer-Verlag New York, Inc., of high latency mix networks [38, 23] and constant
pp. 96–114. rate cover traffic [22] can mitigate timing analysis even
against an adversary that observes all communications,
[47] T IMPANARO , J. P., C HRISMENT, I., AND F ES - these defenses are considered too costly to be deployed
TOR , O. A bird’s eye view on the I2P anonymous in the Tor network.
file-sharing environment. In Proceedings of the Mitigating asymmetric attacks: Recall that our asym-
6th International Conference on Network and Sys- metric correlation attack leverages information in the
tem Security (Berlin, Heidelberg, 2012), NSS’12, TCP header, namely the sequence number field that in-
Springer-Verlag, pp. 135–148. dicates the number of acknowledged bytes. One poten-
[48] VANBEVER , L., L I , O., R EXFORD , J., AND M IT- tial countermeasure would be to encrypt the TCP header,
TAL , P. Anonymity on quicksand: Using BGP to
by leveraging IP-layer encryption techniques such as IP-
compromise Tor. In Proceedings of the 13th ACM Sec. However, this approach introduces several chal-
Workshop on Hot Topics in Networks (New York, lenges. First, it would require a substantial engineer-
NY, USA, 2014), HotNets-XIII, ACM, pp. 14:1– ing effort to migrate Tor towards IPSEC. Second, since
14:7. IPSEC is not widely used, this would make Tor traffic
easy to distinguish from other encrypted traffic, thwart-
[49] W RIGHT, M., A DLER , M., L EVINE , B. N., AND ing its use for applications such as censorship resistance.
S HIELDS , C. Defending anonymous communica- Finally, encrypting the TCP header may not complete
tions against passive logging attacks. In Proceed- solve the attack. For example, an adversary could at-
ings of the 2003 IEEE Symposium on Security and tempt to correlate TCP data packets with simply the
Privacy (Washington, DC, USA, 2003), SP ’03, number of TCP ACK packets, disregarding the sequence
IEEE Computer Society. number field.

16
286 24th USENIX Security Symposium USENIX Association