Compromised entry guards rejecting safe circuits (was Re: OSI 1-3 attack on Tor? in it.wikipedia)

[Paul Syverson]

On Sat, Feb 16, 2008 at 01:43:02AM -0500, Roger Dingledine wrote:
> 
> Imagine an adversary who can observe any connection attempt from Alice
> and fail any of them that he wants. Imagine this adversary also runs, say,
> 10% of the Tor network, including some guard nodes and some exit nodes.
> 
> Alice starts up, learns about the Tor network, picks her entry guards, and
> tries to connect to some. Our adversary keeps tricking her into thinking
> she picked bad nodes, until she picks an adversary-controlled entry guard.
> Then he lets all connections to that entry guard succeed, but when Alice
> picks a second hop that isn't adversary-controlled, he claims that next
> hop is down. Until eventually he picks an adversary-controlled second
> hop. Repeat for the exit node.
> 
> Ignoring bandwidth weightings, exit policies, etc, Alice would need to
> try (.1*.1)^-1 = an estimated 100 circuits before she makes three bad
> hops (assuming she's already happened across the bad entry guard). For
> a more reasonable 1% of the network being bad, that changes to 10000
> circuit rebuilds.
> 
> See http://freehaven.net/anonbib/#ccs07-doa for a related paper here.
> 

http://freehaven.net/doc/sync-batching/sync-batching.pdf
might also give some insight into theses same points, although applied
to different network structures, especially in its "Robustness of
Anonymity" section, although

-Paul