Addressing the tagging attacks

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

Dear all,

Under the light of the tagging attacks that Nick and Roger have found
I propose that we modify the design in the following way.  

- We have a fixed size (say 2kb) "routing block" (for all messages)
  that contains a certain number (say 16) of headers (each 128 bytes
  long), as defined before in the MixMinion Specs. 
  Q: How long should the "routing block" be?
- Additionally each header contains a hash (8 bytes since it does not
  need to be collision resistant) of what the mix decoding the header
  expects to see as the rest of the "routing block".  
- Instead of having a type (2 bytes) field in the header we only have
  1 bit that lets the node know if it is the last one or not (and will
  include the Type in the payload to minimize the value of the tagging
  attacks that are still possible). 
- The payload of the message can be encoded with a secure keyed
  all-or-nothing transform (AONT), to be stripped at each stage of the
  processing. It has the property that Ek1(Dk1(M)) = M and Dk1(Ek1(M))
  = M (So Ek1 = Dk1), but Dk1( x XOR Ek1(M)) = UNPREDICTABLE_JUNK.    
- Modifications to the standard processing:
  * Now the node needs to check the integrity of the "routing block".
  * It also needs to insert 128 bytes of junk between the end of the
    "routing block" and the beginning of the message.
  * The node applies the AONT to the payload.

How do we combine forward paths(sender anonymity) and SURBS(receiver
anonymity) to provide bidirectional anonymity? 

We can have a standard module (like DROP) that gets the SURB from the
payload, creates a new message using it and sends it out. It is
possible therefore for only 1 node to tell that a message is sent
using one mechanism or the other (which is also true if you send a 
message directly only using a SURB).

Security?

The header tagging attacks are completely defeated since any mix can
detect someone fiddling with these.

As discussed before on the list only the last mix can tell if a
message payload is tagged, and it can only distinguish between messages
with different timestamps(*), since all of the body is going to be
completely random. It cannot tell what type the message (since the
type information is in the body).
Note that the original sender has no way of decrypting the communication 
under compulsion either, so knocking down his door at 5am will not help 
finding out what this message was about or for.

The maximum route length is fixed and smaller than before BUT even the
last node cannot know the number of hops a message traveled through (that 
is new). 

(*) Timestamps

As it has been described in the previous email timestamps 
are becoming a nightmare. Now I found out they they allow an attacker to 
separate the messages per day. Should be consider having a "deadline" 
instead of a timestamp? So that packets are not valid after that deadline 
that could be quite large (although intermediate nodes need to keep some 
state per packet until that deadline).

Yours,

George