[freehaven-dev] mix-acc: witnesses provide linkability in rare case

[Roger Dingledine <arma@mit.edu>]

Mix path P consists of mixes M_i.

A --X-- M1 --X-- M2 --X-- M3 --X-- M4 ...
 \     /  \     /  \     /  \     /  .
  \   /    \   /    \   /    \   /    .
   \w/      \w/      \w/      \w/      .

If

* Each edge in the path P is broken, as X above
* Every node M_i in P does reach some specific w

Then that w can determine P. This contradicts our statement in the paper
that adding the witnesses does not impact anonymity.

We could:

1) Mix at M_i to w. Thus w couldn't track which message was going
where. Yet because of the deadline M_i cannot delay indefinitely; if
the volume to w is low, this won't protect much.

Speaking of which, does our deadline notion itself increase linkability?
I believe it does.

2) Use some subset of w's at each hop, such that at least one
*consecutive* set of witnesses is disjoint. Yet for a fixed global
set {w_i}, two consecutive disjoint subsets of {w_i} will not *both*
contain more than half the elements of {w_i}; in the current scheme less
than half the witnesses *cannot* provide a quorum of failure statements,
and so this approach cannot help.

3) Reduce the size of a quorum. Some of these approaches are easier if
quorum is not majority. Yet this increases the amount of trust we must
place in each witness. I want to avoid this.

4) Use some subset of w's at each hop, such that no w appears in
*every* subset. Thus multiple w's can collude, but no single w can
break anonymity.

Consider 10 witnesses a-j and 5 hops 1-5: hop 1 uses witnesses a-h,
2 uses c-j, 3 uses e-b, 4 uses g-d, 5 uses i-f. Thus no witness is in
every bucket, and we stlil have most of the witnesses in use at each
hop. Note that if the adversary owns 4 witnesses can he prevent a quorum
at some hop. *But* 10 witnesses, 2 hops? Reduce to case 2.

5) Leave protocol alone, and weaken our claim: we are vulnerable to the
situation where the adversary can selectively kill packets out of each
node M_i \in P (widespread active edge adversary).

6) Since we can't rely on being able to batch well to w under time
constraints, we add dummy traffic to the transmission to w. You have to
make the dummy traffic go at least one hop past w, introducing potential
failure (and thus loop back to witnesses). If all edges in P are broken,
then w might notice that some of the traffic generates later witness
requests and some doesn't. This might get complex, but might work.

7) Allow senders to set a bit for each M_i \in P: "witness me" or "don't
witness me". Thus he could specify "don't witness" for some {M_i} \subset
P. Yet those mixes might undetectably drop? So this is a bad idea.


How's my logic? I favor option 5 (though option 4 is neat to think about).
--Roger

(Thanks to George Danezis for pointing out the problem.)