Anonymity on QuickSand: Using BGP to Compromise Tor

Authors: Laurent Vanbever, Oscar Li, Jennifer Rexford, Prateek Mittal (Princeton University)
Presenter: Laurent Vanbever

Laurent begins by reminding us of how We are Anonymous (punning on the hacker collective) ... but not really ... because of how routing works. Even if communication is encrypted, we can figure out who's talking to whom, infer location, and track behavior and interests. Tor is the best-known system to prevent the discovery of associations between the end-points of communications. Tor works by bouncing traffic over relays: an entry relay, middle, and exit relay. It forms a set of tunnels with the results being that no single entity can map the source to the destination: the entry relay knows the source, and the exit knows destination. But "because Tor is a low delay system", entry and exit traffic is highly correlated. By observing correlations at entry and exit points, its privacy can be broken. The question this work addresses is: can you increase an attacker's ability to make the necessary observations by (a) manipulating Tor itself (which is in the paper, but not part of the talk); and (b) manipulating the underlying routing?

The short answer to that question, this work shows, is yes. There are in fact, multiple BGP characteristics that increase the attack surface: (a) as BGP converges, more ASes see the traffic needed to make correlations; (b) an AS can also actively hijack routes to be able to see traffic; and (c) asymmetric routing in the Internet makes it worse because more ASes see the traffic (and it's enough to look at traffic in any direction).

To see how much impact these problems can have, the authors collected data on entry and exit Tor relays. It turns out, jut 3 ASes host 20% of Tor entry and exit relays, thus putting these ASes in a strong position as attackers. On path changes, how often do these happen in a way that impacts Tor? The authors use data from RIPE to answer this question, and find that Tor prefixes change more often than other BGP prefixes, and in 60% of these change more than 2 extra ASes receive traffic due to these changes, which is large, considering most routes don't involve many ASes (typically 4 or less).

So what suggestions do the authors have for mitigation?  To protect from BGP's natural dynamism, one could prefer stable relays; to protect from route manipulation, preferring close relays helps;  to protect against asymmetric analysis, one can encrypt the transport header. However, each of these solutions has its own difficulties, so ultimately, it's unclear how to solve the problem.

Q & A

Q: (Bruce Maggs) In Tor, don't they usually have more than one middle node?
A: Yes, it is just one node in the middle, at least logically. In any case, even if multiple middle nodes were being used (which I'm not sure about), not much would change in this analysis because we're primarily concerned about the entry and exit here.

Q: What about the correlations and timing? (Scribe note: I might have missed some part of the question.)
A: For attack mitigation, one can insert random delays, and people have worked on that. Effective approaches do impose additional latency, and can be used for mail etc., but not interactive application traffic.

Q: How transient are the BGP path changes? What time frame do you need for the attacks to work?
A: BGP convergence can often take minutes, so there's plenty of time to observe enough traffic for attacks.

Q A few ASes can capture lots of the Tor traffic (as your results show). Is that specific to Tor, or if you took any service, you could expect to find a similar skew just based on randomness?
A: This is probably specific to Tor, because lots of providers worry about hosting exit relays - shady things happen on Tor, and they don't want to be associated with them.