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

[dmolnar <dmolnar@hcs.harvard.edu>]

On Tue, 1 May 2001, Roger Dingledine wrote:

> Anyway, I think I've just convinced myself in both directions of the
> "are witnesses anonymity-breaking" argument. DavidM/Mike, want to chime
> in here?

I think Danezis' attack certainly applies in the case that the
MIX fails for only one message. Then the witness sees a message from N_i
headed to N_{i+1} and bridges the MIX. Such a situation could be brought
about by an active adversary which mounts a "trickle attack" - let only
one message through, then cut the wire between N_i and N_{i+1}. The MIX
sends that message to the witnesses.

In this case, however, the attack is very similar to the original
"trickle attack" - let only one message through to the MIX, then wait
until it comes out. A potential difference; without deadlines we can delay
messages randomly and indefinitely so that an adversary is not actually
sure whether the outcoming message is the same one which was trickled in. 
With deadlines, we can't do this.

Now there's the issue of what happens when several messages come into a
MIX with the same destination and a wire is cut. The messages had better
be re-ordered. In which case it seems that the witness's view is exactly
the same as that of a passive adversary watching the input of N_i and the
*input* of N_{i+1}...it knows that these messages are headed for N_{i+1}
and came from N_i but can't match them up with any of the incoming
messages headed for N_i.

I think that this is less information than a passive adversary which sees
all of the incoming N_i and all the outgoing messages of N_{i+1}, because
such an adversary has the view of "all messages going to N_{i+1}" as a
subset of its view. We know that MIXes are secure against such an
adversary...

So on this reading, the attack isn't a big deal, if I understand
correctly. Part of the issue here seems to be that it wasn't clear 
(even to us - except David, of course!) whether the messages output to the
witnesses would be batched and reordered - and we seemed to implicitly
assume that only one message would be sent to a MIX at a time.
Note that creating extra traffic to "pad" a batch doesn't give the witness
the same view as a passive adversary, and so it's not clear whether that
hurts or helps. 


-david