[tor-dev] Global semi-passive adversary: suggestion of using expanders

[Paul Syverson]

On Fri, Aug 23, 2013 at 03:45:31AM -0400, Roger Dingledine wrote:
> On Fri, Aug 23, 2013 at 09:19:32AM +0200, Paul-Olivier Dehaye wrote:
> > The short summary of the weakness of Tor here:
> > - We would like the whole protocol to be mixing (to an observer, the
> > probability of exiting at any node C given entrance at node A is close to
> > 1/N),
> 
> Right, you're using terminology and threat models from the mixnet
> literature. Tor doesn't aim to (and doesn't) defend against that.
> 
> You might find the explanation in
> https://blog.torproject.org/blog/one-cell-enough
> to be useful. The first trouble with mixing in the Tor environment is
> that "messages" from each user aren't the same size, and it's really
> expensive to make them the same size ("round up to the largest expected
> web browsing session").
> 
> Another key point: it's not about the paths inside the network -- it's
> about the connections from the users to the network, and from the network
> to the destinations.
> 
> That said, for the beginning of your related work, see
> http://freehaven.net/anonbib/#danezis:pet2003
> 
> And for a much later follow-up, see
> http://freehaven.net/anonbib/#topology-pet2010
> 

You might also want to look at the following for a design that tries
to address your issues.
http://freehaven.net/anonbib/#active-pet2010
See also citations therein for partial solutions.

High-order bit: I think this is about state-of-the-art for this area,
and it's my paper, but we still need a lot of basic research progress
in this space before we would have anything worth putting into Tor.
And, except for adding small amounts of noise (besides uniform cell
sizes, but that should be a gauge of tolerable overhead for anything
we do) to complicate trawling, I'm not very sanguine about the
prospects of this ever making practical sense. You might also consult
my "Why I'm not an Entropist"
http://www.syverson.org/entropist-final.pdf

aloha,
Paul