Re: Forward and reply messages

[Roger Dingledine <arma@mit.edu>]

On Sat, Apr 20, 2002 at 03:00:23AM +0000, David Hopwood wrote:
> > We've been working on the problem of making forward and reply
> > messages indistinguishable at all points, [...]
> 
> The problem with that is:
> 
>  - Reply messages can't be made non-malleable over the full message.
>  - Therefore, if forward and reply messages are indistinguishable to nodes,
>    forward messages also can't be made non-malleable over the full message.
>  - If forward messages aren't fully non-malleable, then there is a traffic
>    confirmation tagging attack that works regardless of the number of hops
>    on the path:

Well, we're hoping the confirmation attack won't work. (I'm sold on the
swap option rather than strip, at this point, as described below and in
the last post.) Assume we're looking at a forward message. The message
goes from Alice over the first leg of her path, to the crossover point
where the headers get swapped, and then goes over the second leg of her
path to Bobby.

Because the swap operation involves decrypting the second header
with a hash of the second header and payload, then even a malicious
crossover point can't determine what the second leg is if anything has
been tampered.

So the idea is:

* If the first leg has been tagged, then you'll never learn what the
  second leg is.
* If the first leg hasn't been tagged, then Alice gets her
  sender-anonymity. The second leg can be tagged and we don't care.

A single leg (at most 8 hops here) must be sufficient to get anonymity.
I think that's ok.

> sufficient. The attack works for both forward-only and forward-then-reply
> messages, and it also works if a small number of the intermediate nodes
> check non-malleability of the full message (as George suggested), provided
> those nodes are controlled by Bobby (since in that case each tagged input
> message can be re-tagged when it is output).

It's not just that they check for tagging -- the protocol actively breaks
the next leg of the path if the message has been tagged.

> (I'm glossing over some details here. In particular, reply messages have
> to be encrypted and random-looking on the last hop in order for the reply
> path to be secure against parties other than the recipient, although that

Agreed

> doesn't prevent them from being encapsulated in an ordinary SMTP email.
> I.e. recipients of messages using reply blocks will need Mixminion software
> to decrypt, but do not necessarily need to run a node.)

Agreed

> Incidentally, there is another alternative to the 'swap' and 'strip'
> methods described in the archive, that makes forward and reply messages
> indistinguishable; it has a 'replace' operation that replaces part of
> (say, the last half of) the message header with pseudo-random junk. This
> would be more efficient in message size than 'swap', and slightly more
> flexible than 'strip', but since it still doesn't prevent the traffic
> confirmation tagging attack, it's not what I would recommend.

Actually, this was what the strip operation was all about. What I can't
solve is that if the second leg is built by the receiver and the first
leg is built by the sender, then the 'replace' operation needs to happen
at the end of the first leg but creating pseudo-random junk based on what
the second leg expects. So when you make a reply block you also need to
separately include a seed for generating the junk that the reply block
expects. So it seems klunkier than swap.

> In any case, having distinguishable forward and reply messages is not so
> bad. If we arrange that exactly half of the messages are of each type (e.g.
> by doubling the length of forward-only paths and making those messages look
> like reply messages on the second half of the path), then it only halves
> the size of the anonymity sets. The effect of that is pretty easy to analyse,
> and can be partly compensated by adding more cover traffic.
> 
> Another advantage of not trying to make forward and reply types
> indistinguishable is that in that case we can do without a variable-length
> block cipher (I think).

Fair enough. It's certainly worth comparing. Tell me more?

--Roger