Boulder Tech report on low-resource routing attacks on Tor

[Paul Syverson <syverson@xxxxxxxxxxxxxxxx>]

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 Øverlier, "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