Re: [Remops] Why are reply blocks single use?

[Roger Dingledine <arma@mit.edu>]

On Sat, Aug 09, 2003 at 01:04:47PM -0700, mindfuq@comcast.net wrote:
> I'm reading the design docs for MixMinion.  The authors are saying
> that reply blocks must be single use because traffic analysis can be
> done via flooding replay attacks, and that the replay block can be
> derived from this.  I can see how this is the case with simple reply
> blocks, but what about the reply blocks that have branching and
> varying probabilities?  Couldn't one create a reusable reply block
> complex enough to foil this type of analysis?

It's conceivable you could win in an arms race (complexity of mix-net vs
analysis capabilities of adversary). But there are a number of factors
that make that hard:

a) In general, complexity is bad in security systems. It's hard to
get the design right, and hard to even *know* what's right in this
case. The traditional assumption is that the adversary is smarter and more
determined than you are. The adversary also has an easier time of it: you
have to defend against all attacks, and he just has to find a single flaw.

b) Encoding branches in a reply block is tricky from a design
perspective. Because you're doing layered encryption, with the naive
approach the size of the onion grows exponentially with the number of
choices, not linearly as we'd like. (But see the paper by Pfitzmann
and Waidner from 1985 (http://freehaven.net/anonbib/#1985), where they
describe a mix-net in which messages can 'jump over' dead nodes in the
path, yet the onion still grows linearly with path size.)

c) If somebody replays a message and it happens to follow the same path,
then it *looks the same*. Exactly the same, bit for bit. So over time,
an observer will learn all possible next hops from a given point on the
path, and then the game is over.

(Actually, link encryption may obscure that, as long as the next hops
are popular nodes so enough other traffic goes to them also, and as long
as the adversary doesn't happen to own the next hop.)

Babel (http://freehaven.net/anonbib/#1996) uses multi-use reply
blocks. They introduce the concept of "inter-MIX detours" during the
reply path, where nodes can rewrap a reply message and send it through
a few randomly chosen new hops --- so even the sender cannot be sure of
recognizing his message as it leaves the MIX. Along with link encryption,
this seems to make recognizing outgoing messages quite hard for a local
adversary.

d) All the messages in a flooding attack ultimately arrive at the same
user --- no matter how complex you make the network in the middle. So
for a strong adversary such as a global observer, end-to-end traffic
analysis (where you treat the mix-net as a black box and just observe
'stuff going in' vs 'stuff going out') will work great.

e) Allowing MURBs in the current Mixminion design requires either that we
add the same branching logic to *forward* messages (all of them), or that
we allow forward messages and reply messages to be distinguishable to the
mixes. This might be ok, but would mean additional complexity all-around.

In general, MURBs don't seem so bad for a weak adversary. But if your
adversary controls an exit remailer, and can get ahold of your reply
blocks, and you regenerate new reply blocks from time to time, and you
don't run your own remailer, then eventually you lose.

--Roger