Re: Anonymity easily thwarted by flooding network with relays?

[Roger Dingledine <arma@xxxxxxx>]

On Thu, Nov 18, 2010 at 06:19:03PM -0800, Theodore Bagwell wrote:
> Some of you may be aware of the paper,"Cyber Crime Scene Investigations
> (C2SI) through Cloud Computing"
> (http://www.cs.uml.edu/~xinwenfu/paper/SPCC10_Fu.pdf) which illustrates
> a feasible method of invalidating the anonymity afforded by Tor.

I just took a brief look through it. I wish they'd included analysis of
guard nodes in their equations -- because relays take several days or
more to get the Guard flag, and clients only rotate their guards monthly,
the equations in this paper are misleading and their conclusions like
"99% if the user connects three times" and "the network forensics section
may last for a few hours [and still be effective]" are also misleading.

That isn't to say that the general point is wrong -- I think with the
current size of the Tor network, a well-funded adversary could run enough
relays that he will have a high probability of deanonymizing users. We
sure do need to get a larger network if we want to raise the cost of
these attacks. But at some point somebody should run the numbers to
find out how much it would cost in practice. (These numbers might also
convince us to change the parameters like "3 guards" and "30 days".)

We should also take the next step in our bandwidth measurement authorities
at some point -- right now the directory authorities put in a better
estimate for your bandwidth _once we have a better estimate_, and use the
self-advertised bandwidth until that point. I think that's a security
flaw. We could cap the believed self-advertised bandwidth at something
like 100KB. It would mean that newly volunteering relays would take even
longer before they're usefully contributing. The step after that would
be to accelerate the initial measurements on new relays, to narrow the
window where we don't have an opinion on bandwidth weight.

There's also an open research question on how to combine Mike Perry's
measurements (which are more accurate at high bandwidths) with Robin
Snyder's measurements (which are more accurate at low bandwidths). I
know Mike would love to have some help there.

> I nominate this paper as a founding reason why Tor should permit users
> to increase the number of relay nodes used in each circuit above the
> current value of 3...

No, that won't work. The key vulnerability is the first-last correlation
attack, which doesn't care how many hops your path has (as long
as it's at least two). You can read more about it from the various
freehaven.net/anonbib/ links in this blog post about a related topic:
https://blog.torproject.org/blog/one-cell-enough

--Roger

***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxxxxxxxx with
unsubscribe or-talk    in the body. http://archives.seul.org/or/talk/