by Alex Biryukov, Ivan Pustogarov and Ralf-Philipp Weinmann
Tor is one of the most widely used tools for providing anonymity on the Internet. We have devised novel attacks against the Tor network that can compromise the anonymity of users accessing services that exhibit frequent and predictable communication patterns and users establishing long-lived connections.
Anonymity on the Internet is a double-edged sword. On the one hand, anonymity allows people to express their thoughts and ideas without fear of repression; on the other hand it can be used to commit crimes in the digital domain with impunity. The Tor network is one of the most popular and widely used tools for enabling anonymous Internet communications. By routing connections through a variable chain of three “relays”, volunteer-operated Tor servers, the origin of the user establishing the “circuit” is cloaked.
As a consequence, services that the user connects to do not see the real IP address of the user but rather the IP address of the last computer in the chain of relays. To make this mechanism more secure, the series of servers used for new connections is changed every ten minutes and connections between Tor relays multiplex sessions of multiple users. Moreover, the first relay in the chain, the so-called “guard”, is picked from a small set of relays – usually consisting of only three elements – that is randomly chosen by the user’s Tor client on its first start. The concept of guard nodes was introduced to give users a chance to avoid falling prey to attackers controlling a fraction of the Tor network. Guard relays remain in this set for approximately one month.
Figure 1: User contacts server through the Tor network.
We have found techniques to scan the connectivity of Tor relays. These can provide us with a topological map of the Tor network (see Figure 2 for an example).
With a speed of approximately 20 seconds per scanned router or under three minutes for scanning the whole network in a parallelized manner we are also able to observe dynamics in the topology.
Figure 2: Connectivity of the 105 fastest Tor relays on March 14th, 2012, 13:59 GMT.
Based on these data we have devised attacks that compromise the anonymity of users exhibiting one of the following two communication patterns over the Tor network:
- Long-lived connections:
Large downloads, a number of instant messaging protocols and BitTorrent over Tor will create circuits that are kept alive for many hours. Looking at differences in the topology to identify connections between relays that remain stable enables us to trace the communication back to the guard node.
- Frequent, identifiable reconnections:
Some Internet services, for example webmail services such as GMail, will frequently re-establish connections to a server. In case these connections can be identified to belong to the same user, an attacker that can observe a good chunk of the exit traffic of the Tor network is also able to trace the user back to a set of guard nodes. In particular, we will be able to identify guard nodes with low bandwidth.
As the Tor network steadily grows in size, we have created a model to estimate the effectiveness of our attacks for arbitrary parameters. The main parameter affecting the connectivity of a relay is the bandwidth it provides to the Tor network. The probability of any given relay being chosen for a route mainly hinges on the bandwidth contributed. Even though there are other parameters influencing this probability, it only takes a very simple model to predict the observed connectivity well.
Experimental verification of our attacks against connections made by ourselves over the real Tor network show that they work in practice and our model predicts their effectiveness correctly.
All prior research on Tor assumed the topology of the Tor network to be opaque. Since our attack methodology is orthogonal to other attacks described in the literature, inference of the Tor network topology can also be used to enhance these attacks.
The work described in this article has been accepted to the European Symposium on Research in Computer Security (ESORICS 2012) and the Tor Project has been made aware of our findings. In the paper  we also describe countermeasures that can be used to mitigate our attacks.
 R. Dingledine, N. Mathewson, P. Syverson: Tor: The Second-Generation Onion Router in Proceedings of the 13th USENIX Security Symposium, August 2004, p. 303-320
 A. Biryukov, I. Pustogarov, R.-P. Weinmann: TorScan: Tracing Long-lived Connections and Differential Scanning Attacks, Proceedings of ESORICS 2012, to appear
University of Luxembourg, Luxembourg