The following are some comments on the Univ. Colorado at Boulder tech report "Low-Resource Routing Attacks Against Anonymous Systems" that has been getting lots of press and other web attention lately and been somewhat discussed on this list. It is only today that I have managed to find time to sit down and read the paper. The nutshell for people that don't want to read the details below: A good paper. It does _not_ show Tor to be broken. (Nor did it ever claim to. I only state that because of some of what has appeared in the blagnpress, which to their credit, the authors tried to curtail.) It is a nice contribution, especially in showing the limitations of the current approach to entry guard selection. Overstates its novelty over prior work, which is really unnecessary because it makes valuable contributions of its own (and which is more or less my fault not theirs, cf. below). More details: This is a nice piece of work. Its greatest contribution is in directing attacks on entry guards. In the theory and simulation work in which such ideas were introduced by Wright et al. they were introduced (as "helper nodes") to reduce vulnerability. As a recent addition to Tor, the nature of defense they provide but also the possible risks from how they are used in actual implementation and deployment needed to be explored. It was understood from the start that there is something of a tradeoff in introducing them. It was realized that profiling without entry guards was in practice trivial enough that the additional risk of adding entry guards and thus simplifying and enhancing profiling for anyone who unfortunately had an adversary guard node was clearly worth it. I don't think this paper changes that. However, by attacking the guard selection process itself, the research forces us to examine it more closely. What they did was apply techniques that Lasse and I developed in "Locating Hidden Services" to ordinary client circuits. Though we had said this would be straightforward to do, we didn't actually do it. Because we were focused on the deployed Tor network we could not pursue this sort of attack there. We were also focused primarily on what could be accomplished with a single hostile node. This limits to cases of either a hostile website (as in Murdoch and Danezis and as mentioned on p. 10 of this tech report) or a hostile client and a hidden service, which is what we reported on. Deploying a Tor network on PlanetLab and using synthetically generated data removes some of the "in the wild" reality from the results. But, by accepting this limitation, it allowed them to obtain data at all about Tor circuits for ordinary use (not hidden services). Much in the practicality spirit of onion routing. The experimental networks were more than an order of magnituded smaller than the current deployed Tor network. One cannot be sure something will scale until actually trying it, but in this case there is no reason to doubt it does scale. Still if we take the 9 percent figure given by the authors as an arbitrary line at which attacks become significant, that is still almost a hundred nodes in the current network. At about twice the entire size of the experimental networks that were set up this starts to be a bit more than low-resource. Still one could do quite a bit with less than 9 percent. Also, as a counter to my own point, see "On the countermeasures" below. On prior work: Before I start noting all the things that the authors didn't properly cite, I should observer that they first contacted me about their work way back in last October and have cc'd me on correspondence with Roger, who did read their work and respond to them. If these are indeed omissions and oversights in their paper, then it is my fault because they gave me plenty of opportunity to comment before it hit the interblag. I just didn't squeeze in the time before now. I already mentioned that the basic techniques are similar to what was in my paper with Lasse Xverlier, "Locating Hidden Servers". The authors say that they think theirs is "the first approach capable of [compromising anonymity] before the client starts to transmit any payload data". I believe that the code we ran would be entirely able to do this. We mentioned it only briefly in passing in our paper, and we didn't actually do it. The authors of this report did. They also say they have introduced the idea of nodes falsely reporting bandwidth and uptime. As they note this is central to the way their basic attack works. As they do not note, this was explicitly used by Lasse and me in our attacks. I quote from our paper, "Alice's server node will report a false higher uptime and the maximum network bandwidth to the directory server in order for other nodes to trust it for their circuits. This is still possible as there is (yet) no method for keeping reliable track of uptime at the different servers." They also introduce the idea of selective path disruption to speed up attacks by dropping circuits, because that will cause more circuits to be built. This was also part of our attacks albeit since we controlled the client connecting to the hidden service, it could be done there. The statement that the algorithm for choosing entry guards was "implemented to protect the first hop of a circuit by using what are believed to be more reliable and trustworthy nodes" is false. Using more reliable nodes was seen as sensible because it should minimize the number of entry guards a client uses, which is the whole point. Nobody thought that this made them more trustworthy. In fact the general threat of adversaries running reliable nodes (in both onion routing and mixnets) to attract more traffic is well recognized. On the threat model. While the design document does use the c^2/n^2 basic result from "Towards an Analysis of Onion Routing Security" as a starting point. This was not thought to be accurate once we had substantial deployment and was acknowledged as such. Cf., "Challenges in deploying low-latency anonymity" http://www.onion-router.net/Publications.html#challenges On the countermeasures: Rather than discuss all of them in detail in an already overly long post, I'll just note that I think they may help against an adversary that has only several hundred to a few thousand dollars in resources. The authors note that they are considering just that case, and it is certainly worthwhile to see what it takes to mount an attack and what works against a low resource adversary. That was also part of our motivation to show what could be done with a single bad node. But, an adversary that has a few tens of thousands of dollars can simply run many reliable high bandwidth nodes and thus mount the attack invulnerable to any countermeasure against lying. Michael Gersten noted the threat of this attack in a separate context in a post to this list yesterday (March 6). And it has long been recognized as a potential threat to Tor in general. I have begun to look at countermeasures that should work unless the adversary owns major hunks of the network, e.g., social network based, but will not get into that further here. More than you wanted to read. Hope it was useful anyway. aloha, Paul ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE [demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc]