Re: Forward and reply messages

[Roger Dingledine <arma@mit.edu>]

On Mon, Apr 29, 2002 at 10:17:44AM -0400, George Danezis wrote:
> In general, while I find the proposal in itself ok, I am still not 
> convinced about dropping the requirement about un-distinguish-ability of 
> reply and forward messages. If the objective is to avoid the remaining 
> tagging attacks that the swap like approach leave I think it is a 
> disproportionate penalty.

I'll try to do one of my infamous summary mails here. But this time I'll
keep it short. ;)

Option one: Distinguishable forward and reply messages.
Flaw: adversary can divide messages into two sets. If one set is small
(ever), it's much easier to trace.
Not-very-good-solution: send dummy traffic to make the percentages equal.
But: This wastes a lot of bandwidth. (Other attacks?)

Option two: Indistinguishable forward and reply messages.
Flaw: forward payloads can't be integrity-checked -> introduces tagging
attacks.
Not-very-good-solution: use crossover point and decrypt-by-payload,
to ensure that either the first leg of the path hasn't been broken,
or the second leg is unknowable.
This-is-nice-because: we don't waste any bandwidth. (No other solution
claims this feature. (?))
But: Multiple-message tagging attacks. If Alice sends a bunch of messages,
you can tag some coming out of Alice, recognize the pattern (number of
tagged and untagged messages) at the crossover point, and observe where
the untagged ones go.

Ok. Now I get more verbose, I'm afraid.

We'd like to reduce this issue to an attack we're already willing to
accept: when Alice sends a bunch of messages, the adversary can count
them and look for the pattern later. He can also drop some of them and
look for resulting patterns.

Our flaw with option two comes from the risk that the adversary owns the
crossover point --- the mix Alice chooses as the last node in her leg of
the path. If the adversary owns Alice's outgoing link and happens to own
her crossover point, then it's easy to compare patterns. At the other
extreme, if Alice were only sending one message, we wouldn't have this
problem. So if Alice picks $k$ paths for sending her $n$ messages, then
to certainly match a signature the adversary would have to own all $k$
crossover points. (And even then, it seems harder because the subsets
of messages would overlap with subsets of messages from other senders.)

[Aside: We can prevent the adversary from using divide-and-conquer on
Alice's batches if Alice uses a hybrid path starting with a short cascade
--- so even if the adversary tags a subset of the messages he doesn't know
(unless he owns the whole cascade) where the tagged messages went.]

Key point: if the adversary doesn't own a given crossover point, the
tagging attack is equivalent to the dropping attack. The crossover point
in question simply doesn't deliver the message to the second leg.

So if the adversary doesn't own most of the crossover points, then the
tagging attack doesn't get him anything. And since Alice chooses the
crossover points, and if we assume the adversary doesn't own most of the
network (a good assumption, in my book, else lots of other stuff breaks
too), then it's really very hard to do succeed at a tagging attack.

Do you buy it?
--Roger