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

[Roger Dingledine <arma@mit.edu>]

On Tue, May 01, 2001 at 07:33:46PM +0100, David Hopwood wrote:
> Roger Dingledine wrote:
> > 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.
> 
> I don't think that's correct. Remember that each mix is batching and
> reordering the messages, so w will not be able to link incoming and
> outgoing messages from each uncorrupted mix, any more than a passive
> adversary would in a standard mix-net.
> 
> (Of course a standard mix-net is not completely proof against active
> attacks - for example an adversary can force all but a small number of
> messages in a batch to be dropped, and make up the batch size with
> dummy messages - but adding witnesses doesn't make that problem
> any worse, AFAICS.)
 
At this point I'm inclined to agree with David on this -- the attack
George describes is valid if only one message out of each MIX is rerouted
to the witness, *and* if it's the same message at each hop. That is, for
each hop, there's a polynomial chance that our particular message will
be the one that failed; but over n hops, it becomes exponentially small.
Specifically, the chance is exponentially small that the path the witness
reconstructs is actually the path taken by any message, rather than a
set of segments each from a different message path.

So I think this attack is not one that we have to worry about. The
witness in this situation can be thought of a "a passive adversary
which is observing every link in the path" -- and the mixing done by
each honest mix is done precisely to foil that attack.

Do you have a response to this, George?

Thanks,
--Roger