New attack on mixminion (& fix)

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

Ok, I have an new attacks that can be fixed very easily.

It concerns the classic tagging attack problem. If a mix touches the 
second header of the message on the first leg of its journey then the 
second header will come out as junk at the cross over point, BUT the 
payload will still be in clear. The attack therefore proceeds as follows:

- The attacker tags the second header of a mix minion message coming out 
of the victim. 
- Then it notices that at a crossover point it controls a 
message has its second header come out as junk. 
- It then records the payload of the message, and discards the 
minion message (it does not have enough information to forward it anywhere 
anyway).
- Since the message has never arrived we can assume that the sender will 
send the message again. 
- The attacker then does not tag the first leg of the message, but waits 
until one of the crossover points sees the same payload as the old 
discarded message. 
- When the attacker sees a message with the same payload it tags the 
second leg of the message, or it tries to follow it in another way 
(recursive operator torture).

It is trivial to fix the above by making sure that the payload comes out 
as junk if the second header is touched. We just use the hash of the 
second header to transform the payload using an All or nothing transform 
(like BEAR). This in fact makes a three round cipher at the cross over 
point that looks itself like BEAR. The circle is therefore complete.

Yours,

George