Re: Anonymity risks of 2 vs 3 hops

[Paul Syverson <syverson@xxxxxxxxxxxxxxxx>]

On Fri, Jan 08, 2010 at 09:08:30PM +0100, Lexi Pimenidis wrote:
> On Fri, Jan 08, 2010 at 08:56:37PM CET, Sam Peterson wrote:
> 
> Hej,
> 
> > Clearly the experts think it makes things considerably easier here, so
> > maybe there's something I'm missing.  I appreciate all tutelage.
> 
> Just one trivial example is: given that you only have two hop circuits
> and an attacker who owns, e.g., four nodes. If your circuit enters the
> Tor network he can kill any circuit using any other node than one of
> his three as an exit sooner or later, possibly in a way which makes you
> believe that it was "just the typical tor way of killing circuits".
> This way an attacker can trick you into building a more than
> proportional part of crcuits over his nodes.  The same attack would not
> be possible, or as easily, with an unrelated middle node.
> 

While I think that the cost/benefit tradeoff comes down strongly in
favor of three hops, I'm sorry to say that I don't think this argument
is correct.

End-to-end correlation attacks are trivial. Examples of how to do them
were given in the first onion routing paper in 1996, and this has been
shown in experimentation and simulation numerous times in numerous
ways.  The nutshell way we have always said this is that onion routing
prevents traffic analysis not traffic confirmation.  People seem to
keep missing this point and think coming up with yet another way that an
adversary at distinct points in a Tor circuit can recognize that
circuit when encountered in both places is worth publishing. It
isn't. The last worthwhile contribution to this general area was in
2007 when Bauer et al. showed that correlation could be done with very
high confidence and virtually no false positives using just circuit
initialization, i.e., before any application traffic is even sent.

The point is that an adversary who can watch your circuits enter the
network and kill them when he does not see them exiting the network
does not need to have entry and exit directly connected to do it.
(Cf. also "Synchronous Batching: From Cascades to Free Routes" and
"Denial of Service or Denial of Security? How Attacks on Reliability
can Compromise Anonymity" for related points and analyses of how
effective such attacks are on various anonymity networks---not just
Tor. Both are available at the FreeHaven Anonymity Bibliography.)  The
extra effort to recognize a circuit (or recognize that ones nodes have
failed to do so and kill it) is real but not significant enough to
matter in practice. Also, for a tiny toy example such DoS to
DoAnonymity is significant. Even with the 800 node Tor network that
Borisov et al looked at in 2007 in the above paper, this attack only
started to matter when more than twenty percent of the nodes were
compromised.

To answer the original question:
There are many arguments for and against a three-hop minimum.
I think the most compelling arguments in its favor are
(1) If an exit node sees a circuit of interest it now knows one
of the entry guards for that client. It thus is worth trying to attack
or eavesdrop on that entry guard now to try to see who its clients
are either to see the list or if, e.g., the adversary is a destination
to catch and identify the IP addresses of clients that use that
entry guard and visit that destination again.
(2) Because of (1) and also just because he does know the entry
nodes of circuits, an exit's claim to know nothing useful about the
origin of circuits exiting through it goes away. Thus even if an
attack based on (1) does not succeed it could still be an attack/problem
for the exit node. As exit nodes are more scarce, this amounts to
an attack on the Tor network itself. (I made this second point,
but not the first in a post to this list on Nov. 23. Cf. the discussion
under the thread titled
"The Case for Banning Reduced Hop Count Implementations"

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