Re: On reply blocks and tagging attacks (was Re: Problems withbit-twiddlers)

[George Danezis <gd@theory.lcs.mit.edu>]

On Tue, 2 Apr 2002, Roger Dingledine wrote:

> On Tue, Apr 02, 2002 at 02:09:09PM -0500, Nick Mathewson wrote:
> > Second, your claim "that an adversary can extract very little
> > information" seems superficially false:  If I control nodes 1 and 4 in a
> > cascade, and I tag an incoming mail at node 1, won't I discover the
> > recipient when it comes out as bit salad at node 4?  In this
> > configuration, you only need one per message to link senders and
> > recipients.
> 
> Hm.
> 
> Unless, of course, people intentionally send trash periodically. That way
> you can't be sure which was the one you stomped on, or even if the one
> you stomped on made it through at all.
> 
> This isn't a very good answer, though.
> 

Indeed I am not too happy to give the standard "dummy traffic" answer to 
any of our problems. But I have to say that at the end of the day this is 
a traffic confirmation attack (it only allows to test for a particular 
hypothesis) and not a traffic analysis attack (it does not allow to trace 
the message though the network) so it might be that we can only resolve 
it by using dummies. 

Now why is it that (IMHO) 1bit of global information is not enough to mount 
attacks: The traffic confirmation attack, by which the body is modified 
into a "bit salad" can only be mounted when one expects some "structure" 
in the payload. All intermediate nodes see random payloads and therefore 
it is impossible to tell if it has been tagged or not. Therefore all the 
attack can do is confirm that it ends up at a particular node. Even then 
the final node will not ba able to tell apart between different messages 
that have been tagged, so it is only possible to tag one message in the 
system. (Not even possible to divide by recipient/time ...)

Therefore:
- You (along with all the other attackers) can only tag one message in the 
system, until you are confident it has been flushed out. (if each mix has 
a latency of 1h and there are 16 max mixes then that would be one attack 
every 16 hours). 
- You need to make sure that you control the final recipient.
- You do not know at all what the content of the message was (but we do 
not really care about that), and therefore cannot use it or find out the 
final recipient or extract ANY information about what the recipient was 
sending (offers plausible deniability as in our specs).

Are we still unhappy with this situation?

George