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

[Roger Dingledine <arma@xxxxxxx>]

(I changed the thread's Subject, since "Anon Mus"'s attack is not the
same as the attack described on it.wikipedia.)

On Fri, Feb 15, 2008 at 12:42:59PM -0800, Anon Mus wrote:
> F. Fox wrote:
> > Anon Mus wrote:
> >> 3. Attacker has a list of known public/private key pairs. These are
> >> generated over the years by government security service supercomputers
> >> and their own secure network computers (around the world). Such lists
> >> are
> >> regularly swapped between 'friendly' countries and are fro sale on the
> >> black market. Given any tor nodes public key, the attacker looks up
> >> that
> >> key in the list and it returns the tor nodes genuine private key, where
> >> it
> >> has it in its list. (Interesting note: here you have to imagine that
> >> there is software of out there, like the tor network itself, which
> >> could
> >> be used for generating and acquiring billions of key pairs a year over
> >> millions of networked computers world wide. You only need to store the
> >> key pairs such networked software generates after they have finished
> >> with them.)
> >
> > Umm... unless you're talking about lists of *compromised* keys (i.e.,
> > stolen, like via malware), then this is pure FUD. Trying to figure out
> > the private key by other means, is pretty infeasible.

I agree with others here that this particular item from Anon Mus is
bogus. The math simply doesn't work this way: 1024 bits is really big,
and enumerating and storing products of 512ish-bit primes is going to
fill up your disk way before you have a non-trivial fraction of them.

> I must say, I feel that 3 very deliberate and clumbsy attempts have
> been 
> to shoot down such a VERY obvious and sound scenario.
> 
> Why so?

Probably the reason they all misinterpreted your attack is the thread
you posted it in (which describes a similar-sounding attack that *is*
bogus), plus the above "A.3" which sounds like it's straight out of some
conspiracy theory.

Now that we've cleared that up (if we have), let me rephrase your attack
and we can see if it makes sense to more people here.

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.

Mike Perry also brought up an attack like this when he was working on
SoaT. Alas (or perhaps fortunately), he's been working on Torbutton-dev
lately instead. The number of competent anonymity programmers and
designers in the world is still woefully small.

Note that to make this attack work, you really do need to be able to
reject any connection from Alice that you want. Otherwise, if she picks
some bad guards and some good guards, she'll switch to using her good
guards as soon as the bad guards demonstrate themselves to be flaky. And
if you're in that powerful a position for Alice, I'm not too worried
about this attack; or to say it differently, I worry a lot about other
attacks too, and I'm not sure I can help Alice much.

--Roger