Re: Fwd: Proposal: Incorporate Unreachable ORs into the Tor Network

[Nick Mathewson <nickm@xxxxxxxxxxxxx>]

On Mon, Mar 24, 2008 at 10:10:44PM +0000, Robert Hogan wrote:
> On Saturday 22 March 2008 15:13:10 Nick Mathewson wrote:
> > On Sat, Mar 22, 2008 at 11:11:12AM +0000, Robert Hogan wrote:
> > > I'm not sure how much merit this proposal has, or how serious it's
> > > problems are.  Does anyone have any thoughts on it? Are the problems
> > > I've outlined fatal, or is there a problem with it I've missed? I
> > > suspect one or the other.
> >
> > Hi, Robert!  I think this is definitely a step in the right direction,
> > with some tricky issues associated with it.  In particular, it
> > represents a big deviation from Tor's current clique topology.  We
> > should definitely drop the clique assumption (for scaling reasons if
> > nothing else) at some point, though, and there's no reason it can't be
> > soon.
> >
> > Send it to or-dev and let's talk about it there?

Added as proposal 133.

> >
> 
> Hi Nick,
>
>  Had to scratch my head on what clique topology means but I think I
> get it: where every node has to be able to connect to every other in
> the network. I guess that does mean a few anonymity properties
> previously taken for granted on Tor may get flushed out by this -
> pretty sure I haven't captured them all.

Right.  There are some papers that have tried to figure out the
implications of limited topologies like this, but I don't know what
they have to say about this case in particular.

What's bigger in scope is that our current requirement that (mostly)
every router be able to talk (mostly) to every other router can't
possibly scale.  Assuming that the number of users stays large enough
to saturate most routers, as the number of routers grows, so does the
number of sockets and buffers that every router needs to maintain.
Thus, for the network to continue to grow, we'll need a design where
the number of links does not grow as the square of the number of
routers.

George Danezis's "Mix-networks with Restricted Routes" paper in PET
2003 tried to analyze the anonymity implications of one design like
this in a mix-network situation.  Roger, Vitaly, and Paul talked about
some restricted-route designs in their "Synchronous Batching" apper.
The MorphMix design is also worth looking at, though new attacks
against it appear pretty frequently.

The main challenges in designs of this kind are:

  - Attacks where an attacker who sees only one part of the path can
    deduce too much information about the rest of the path from the
    network topology.

  - Attacks where a set of attacker-controlled nodes manipulate the
    topology assignment process to arrange to move into a strategic
    position relative to one another on the network.

There are probably other attacks, too.

>  Are there any better ways of finding out how many servers out there
> fail to publish because they can't pass the orport reachability
> test? The proposal assumes there are a lot, but maybe there are
> surprisingly few.

I don't know a better way than what you suggest (having such servers
upload "I'd like to be a server, but I'm unreachable" statements to
the authorities).  I'm not sure how much we can learn from this,
though: it will only tell us how many people have set up computers to
be servers, found that their firewalls have blocked them, and then
given up but left the Tors configured as servers.  This isn't the same
as learning how many people would *like* to set up Tor servers, but
know that they can't do so with their firewalls, and have decided not
to try.

yrs,
-- 
Nick