<div dir="ltr">I use the word mixing 4 times, with two meanings:<div>"...<span style="font-family:arial,sans-serif;font-size:13px">enough mixing can happen..." : mathematical sense, on pairs of edges around a node</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">"...</span><span style="font-family:arial,sans-serif;font-size:13px">yet highly mixing network..." : mathematical sense, on pairs of entry/exit Tor nodes</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">"...</span><span style="font-family:arial,sans-serif;font-size:13px">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</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">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]. </span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">The short summary of the weakness of Tor here: </span></div><div><span style="font-family:arial,sans-serif;font-size:13px">- 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), </span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">- 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. </span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">Proposed solution: </span></div><div><span style="font-family:arial,sans-serif;font-size:13px">- 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. </span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">- 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).</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">Paul</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div><div><span style="font-size:13px;font-family:arial,sans-serif">[3] </span><a href="http://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/" target="_blank" style="font-size:13px;font-family:arial,sans-serif">http://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/</a><span style="font-size:13px;font-family:arial,sans-serif"> Exercise 15 and remark below</span></div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Aug 23, 2013 at 4:15 AM, Tom Ritter <span dir="ltr"><<a href="mailto:tom@ritter.vg" target="_blank">tom@ritter.vg</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
So I don't work for Tor, nor am I a graph theorist, but I'll add a few<br>
preliminary thoughts.<br>
<br>
On 22 August 2013 21:08, Paul-Olivier Dehaye<br>
<div class="im"><<a href="mailto:paul-olivier.dehaye@math.uzh.ch">paul-olivier.dehaye@math.uzh.ch</a>> wrote:<br>
> As far as I can tell, the main threat by a global passive adversary comes<br>
> from traffic analysis (?).<br>
<br>
</div>A Global Passive Adversary is technically outside of Tor's threat<br>
model (see <a href="https://trac.torproject.org/projects/tor/wiki/doc/TorFAQ#Whatattacksremainagainstonionrouting" target="_blank">https://trac.torproject.org/projects/tor/wiki/doc/TorFAQ#Whatattacksremainagainstonionrouting</a>)<br>
- but if there are easy ways to make it more difficult for such an<br>
adversary, at a low engineering cost - then Tor tends to be up for<br>
them.<br>
<div class="im"><br>
> This attack should become easier as the number of<br>
> Tor nodes increases (?)<br>
<br>
</div>I'm not sure I agree with that. If the adversary is not global, but<br>
only partly global, then network diversity is crucial. If the<br>
adversary is truely global, I don't think more nodes would help as<br>
much as more _traffic_.<br>
<div class="im"><br>
> A dual way to see this is that<br>
> not enough mixing can happen around a node for incoming/outgoing edge pairs,<br>
> bar injecting a huge amount of fake traffic.<br>
<br>
</div>In what sense do you use the word 'mixing'? In the traffic analysis<br>
literature, I think it tends to refer to mix networks, and collecting<br>
several messages into a pool before releasing some or all of them<br>
(<a href="http://crypto.is/blog/mix_and_onion_networks" target="_blank">http://crypto.is/blog/mix_and_onion_networks</a>).<br>
<br>
-tom<br>
_______________________________________________<br>
tor-dev mailing list<br>
<a href="mailto:tor-dev@lists.torproject.org">tor-dev@lists.torproject.org</a><br>
<a href="https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev" target="_blank">https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev</a><br>
</blockquote></div><br></div>