Re: hostile node anonymity attack scenario

[Roger Dingledine <arma@xxxxxxx>]

On Tue, Feb 01, 2005 at 01:08:52AM -0500, Geoffrey Goodell wrote:
> On Mon, Jan 31, 2005 at 09:34:10PM -0800, Paul Forgey wrote:
> > That answers my question. So any attack approaching my scenario would 
> > thus require that enough of these nodes have fooled whomever we trust to 
> > publish the master list of permanent nodes. Or, in simpler terms, not 
> > likely!

Right. When your Tor client (call it Alice) asks the first hop to extend
to the second hop, part of this extend process requires the second hop
to prove to Alice that it knows the appropriate private key:
http://tor.eff.org/doc/design-paper/tor-design.html#subsubsec:constructing-a-circuit
plus the diagram above that.

So the only way the first hop could "fake" the extend is by knowing the
appropriate private key, e.g. by colluding with the second hop. Since
Alice chooses which nodes to use for each hop, then the chance that
they'll be colluding is low as long as many nodes in the network don't
all collude with each other.

But you're right to point out the weakness of trusting us to keep the
master list. But if we just let anybody sign up, we could have real
problems:
http://freehaven.net/anonbib/#sybil
This is a tricky problem already, and it's going to get even trickier
as we try to scale up the network and take the humans out of the loop.
One approach we're considering is just to do it anyway and hope that
no large attacker cares to try attacking the network (and as we grow,
the bar for successfully attacking the network becomes higher and higher).

> A more interesting question to ask might be, "what happens if a client
> creates N independent connections through the network, over a long
> period of time so that circuits are not reused?"  If a malicious
> operator possesses only three nodes, and N is sufficiently large (i.e.
> greater than n*(n-1)*(n-2), where n is the number of Tor nodes), then
> chances are, the attacker would be able to break the anonymity of at
> least one connection...

Actually, this attack is overkill. The attacker only needs to have Alice
happen to pick bad nodes for both her first and last hops. Even if nodes
in the middle are good, we suspect end-to-end traffic confirmation attacks
(based on packet timing and volume) can be used with great success:
http://freehaven.net/anonbib/#danezis:pet2004
http://freehaven.net/anonbib/#timing-fc2004
http://freehaven.net/anonbib/#SS03

This is why Tor's security is mainly based on the diversity of the
network:
http://freehaven.net/anonbib/#feamster:wpes2004
We hope to grow large enough that most real-world adversaries are unlikely
to be in the right places to attack users.

As for the specific attack of waiting until Alice happens to pick bad
first and last hops, this is why we need to investigate using helper
nodes, that is, fixed first hops:
http://freehaven.net/anonbib/#wright03
http://freehaven.net/anonbib/#wright02
People running hidden services are particularly vulnerable to this issue,
since other users (such as the adversary) control the rate at which they
build connections.

Hope that helps,
--Roger