Re: Addressing the tagging attacks

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

On 3 Apr 2002, Nick Mathewson wrote:

> On Wed, 2002-04-03 at 11:32, George Danezis wrote:
>  [...]
> > - 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). 
> 
> I don't get the implications of this.  How does delivery work?  How does
> the last node know whether to deliver to Bob or not?  Do all recipients
> need to run nodes?
> 

The situation is exactly as before but the information about the type of 
packet is in the payload instead of the header. If the "bit" is zero 
everything happens as before. If the "bit" is 1 then the decoding routine 
kicks in (if it is a SURB based packet), and the packet is given to the 
module layer that looks inside it (where the type information now should 
be) and decides to give it to some particular module for processing.

Final recipients of sender anonymous messages do not need to run nodes or 
specialized software since you can have gateways from MixMinion-SMTP etc. 
Recipients that benefit from anonymity properties will need to run an 
application that understands MixMinion but do not have to be relays 
themselves (they simply do not advertise keys, and the software only 
supports packets with the "bit" set to 1 and drops the others).

[...]
> >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).
> 
> How do you create a routing block from a SURB?  Or are all SURBs
> block-length?

A SURB is a full "routing block" (around 2kb). That has the advantage that 
they are fixed length, and one can infer how many hops they contain.

> 
> > Security?
> [...]
> > 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).
> 
> Whoa, I don't think this is right.  The node that extracts a SURB from
> the body will be able to tell scrambled from non-scrambled messages,
> right?
> 
> And if the typecode is in the body, that last node will be able to tell
> messages with scrambled bodies from messages without.
> 

Indeed this node is the only untrusted node that would be able to say that 
the message was tagged. And what does that mean for security?

The scenario is the following: Sender S wants to send a message to 
receiver R using his SURB (that contains a path through A+B+C). In order 
to protect his privacy S decides to first relay the message through X+Y+Z 
and ask (Bad node) to change it into a SURB based message and pass it on.

As you have guessed (Bad node) and X are evil nodes and collaborate in 
order to perform the tagging attack. (Bad node) is tho only one that might 
confirm messages tagged by X (C is not and the Receiver want to protect 
his anonymity).

Sender -X-Y-Z-> (Bad node that    -A-B-C-> Receiver
                 translates SURBS)

So X changes the body of the message and when the message arrives at (Bad 
node) it notices that it is scrambled. Since they have only done this to 
this particular message today, and they also know all the other bad guys 
that have promised not to run tagging attacks today they believe that S 
is the originator of the message.

So what? (Bad node) is still not able to link S to any communication, 
since the content of the body that contained the SURB to be used is 
permanently destroyed. The only information that (Bad node) gets is that 
the message arrived from S which in this case in particular (conversion 
between normal and SURB transport) only tell him that S has sent a message 
and nothing else.

Note that this is not important in this particular case because some 
transport information is always encoded inside the payload (the SURB) and 
destroyed is the payload is tagged. If (Bad node) was the final recipient 
then indeed the Sender S would have his anonymity compromised.

What about the following fix:

We cut the size of the "routing block" to half and always include two of 
them in the same way as we do in order to convert from "normal" to SURB 
transport. We use one to route the packet until a particular node that 
then takes the second block from inside the payload and sends it in the 
network again. In that way the model presented above 9and its security) 
holds for the forward path as well.So in that case any tagging attack can 
only compromise half the route and the other half will be secure?

The above fix also presents the advantage that since all nodes are using 
this method (even for forward "normal" routing) it is not any more 
possible to tell if the conversion is done from "normal" to SURB or from 
"normal" to "normal" routing.

> And doesn't this imply that it's no longer possible to receive messages
> without client software?

The situation is the same as before. The clients that do not need 
anonymity can access the network through gateways and only those those who 
get security have to understand the MixMinion protocols (but they do not 
have to be nodes)

> > (*) 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).
> 
> No, that's still vulnerable. If Alice sends a message on April 1 that's
> valid till April 30, Mallory can delay it till April 30, when there
> won't be many messages at all with an April 30 deadline.
> 

That is a tough one, and seems to be quite orthogonal to the tagging stuff 
(although it contributes to it). Anyone has any ideas?

Yours,

George