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

[Paul-Olivier Dehaye]

I use the word mixing 4 times, with two meanings:
"...enough mixing can happen..." : mathematical sense, on pairs of edges
around a node
"...yet highly mixing network..." : mathematical sense, on pairs of
entry/exit Tor nodes
"...between mixing chains and Tor, and can be seen as a lot of mixing
chains..." : traffic analysis sense, the first 'mixing chains' here should
have said 'mix networks' instead

Informally, in the mathematical sense, some topology is mixing if random
behaviour on it leads exponentially fast to the uniform distribution (which
amounts to no information in the security sense). See the part around [3].

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),
- The clique topology leads to a constant leak of information, because at
any time traffic analysis around a node X can be performed to recover a
non-uniform distribution on entry-exit pairs around that node.
Proposed solution:
- By simply lowering the number of allowed edges around a node, nodes can
adopt mixing chains-like behaviour combined with Tor-like behaviour, at
little cost. They have more or less the same amount of traffic to play
with, but they need to make it look constant (to resist against traffic
analysis) on less edges, so they need to fake a lot less traffic.
- Lowering the number of edges means that it increases danger of other
attacks, relying on global information on the topology (if the topology is
not a clique anymore, in 2 hops I might not be able to potentially be
everywhere). The point of my email is that for specific network topologies
(expanders) this is not really a problem (this was already observed in the
literature), and that some type of expanders can be created easily, with
the security guarantees needed (using Cayley graphs of matrix groups).

Paul

[3]
http://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/
Exercise
15 and remark below


On Fri, Aug 23, 2013 at 4:15 AM, Tom Ritter <tom at ritter.vg> wrote:

> So I don't work for Tor, nor am I a graph theorist, but I'll add a few
> preliminary thoughts.
>
> On 22 August 2013 21:08, Paul-Olivier Dehaye
> <paul-olivier.dehaye at math.uzh.ch> wrote:
> > As far as I can tell, the main threat by a global passive adversary comes
> > from traffic analysis (?).
>
> A Global Passive Adversary is technically outside of Tor's threat
> model (see
> https://trac.torproject.org/projects/tor/wiki/doc/TorFAQ#Whatattacksremainagainstonionrouting
> )
> - but if there are easy ways to make it more difficult for such an
> adversary, at a low engineering cost - then Tor tends to be up for
> them.
>
> > This attack should become easier as the number of
> > Tor nodes increases (?)
>
> I'm not sure I agree with that.  If the adversary is not global, but
> only partly global, then network diversity is crucial.  If the
> adversary is truely global, I don't think more nodes would help as
> much as more _traffic_.
>
> > A dual way to see this is that
> > not enough mixing can happen around a node for incoming/outgoing edge
> pairs,
> > bar injecting a huge amount of fake traffic.
>
> In what sense do you use the word 'mixing'?  In the traffic analysis
> literature, I think it tends to refer to mix networks, and collecting
> several messages into a pool before releasing some or all of them
> (http://crypto.is/blog/mix_and_onion_networks).
>
> -tom
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20130823/a8b1b1ba/attachment-0001.html>