Paper about static mix-networks

[Roger Dingledine]

On Fri, Jan 31, 2003 at 05:23:26PM +0100, Marc Rennhard wrote:
> Folks,
> 
> I've been writing up some stuff about 'why static mix-networks are
> not suited to bring anonymity for the masses'. It's not finished yet,
> but it should be readable and I need some feedback from experts.
> 
> http://www.tik.ee.ethz.ch/~rennhard/publications/anomasses.ps
> http://www.tik.ee.ethz.ch/~rennhard/publications/anomasses.pdf

Comments as I read through:

Section 1, First paragraph: Actually, I tend to use a different taxonomy:

1) Synchronous mix systems: cascades, web mixes, the stuff from Chaum's
papers, and what the voting people talk about when they say mix
2) Asynchronous mix systems: onion routing, mixmaster, and other
bastard children of cypherpunks trying to adapt Chaum's ideas to the
Internet. The difference here is that you're trying to hide the *path*
used, rather than directly trying to hide the user within other users.
3) Plausible deniability systems: Crowds, Freenet, GAP, and in a sense
Tarzan and other p2p systems. This is where you pass traffic for others
and gain some protection for yourself from that.

I think categories 2 and 3 overlap. I'd like to see/do some further
investigation on that notion sometime.

When you mention static vs dynamic, I am reminded of Dogan Kesdogan's
paper on open/closed mix networks, at Info Hiding this past October. But
your notion of static vs dynamic is for the mixes, whereas his open vs
closed was for users; so I guess they're not so related.

The top of page 2 is an ideal place to cite Adam Back et al's paper from
IH4, and also Acquisti et al's paper from FC03.

Botton of page 2: I might rephrase this as designs for non-interactive
anonymity systems can resist attacks at least as well as those for
interactive systems. The key here is that you're comparing the designs,
rather than the actual systems you would produce. To quote Acquisti
et al, "Weak security parameters (e.g. smaller batches) may produce
\emph{stronger} anonymity by bringing more users."

2.2: an active attacker is not necessarily also a passive
attacker. Imagine somebody who can flood a remailer, but can't read any
of the other stuff going into the remailer.

I like your discussion in 2.2.1.

Top of page 5: I think you focus a bit much on the DoS possibilities for
a pipe-net like system, though, towards the end of 2.2.1. But it gets
me thinking about incentives -- if you intentionally disconnect from
the system, then you're hurting yourself a lot, but you're only hurting
other people a little bit, right? If that were the only attack, then
you're still doing pretty well, because you can think of the anonymity
set as the group of people trying to play by the rules.

End of 2.2.2 and 2.2.3: there's another attack to consider here. An
adversary who owns a node in the path can induce timing signatures on the
packets going through, and attempt to recognize these signatures later
(either by passively observing the link coming out of the mix-net, or
by owning a hop later on the path). Basically this is taking advantage
of a covert channel (timings) to communicate. We might be able to weaken
this attack by enforcing normalization at each hop (say, batch 10 cells
together and only send them with certain timing, to try to remove any
signal that the adversary put into the channel. I haven't investigated
this fully, but I imagine it's very hard to completely remove such
signal. So it would seem that even end-to-end dummy traffic is not
sufficient against this adversary. Indeed, this attack may be quite
possible simply by an active attacker on the first *link*, together with
a passive observer on the last link. So no nodes need to be owned at all?

End of 3.2: Actually, that's quite encouraging. It means that we can
handle 500 users per onion router. If only users limit themselves to
5MB per day. :)

Top of page 13: why do you say 10% here? Perhaps if they can only see 10%
of the nodes when there are many nodes, then they should only be able
to observe 10% of the nodes when there are a few nodes too?  This 10%
figure seems critical to your argument, and comes out of nowhere. I worry
that the 40 ISPs are not equally used. In particular, I worry that our
ideas that traffic "bounces around the internet" are incorrect, and in
reality traffic bounces back and forth over a single backbone that can
be tapped. But then, that's exactly what this paper is about. :)

Section 4.2, second paragraph: increasing the chain length does help
reduce the chance that the adversary owns the entire chain; but the
attack we worry about here is timing correlation between a node early
in the chain and a node late in the chain. It would seem that having
more nodes in the middle would soften the signal, but I'm not sure by
how much. In short, for low-latency systems increasing the length of
the chain doesn't seem to be a good way to improve anonymity.

End of 4.2: what about Advogato and other trust metrics that bound the
number of bad guys that can get certified? I bet they could scale up to
1000+. But of course, more research remains on that front. :)

Page 15: you mention that universities might be threatened to not run a
mix. But consider the case of MIT -- we run a reasonably high profile
mix and nym server, and (some) people respect MIT more for it. So there
are examples either way I guess.

Section 5.3: you're leaving lots of issues out of the p2p discussion. One
of the biggest is exit abuse -- do users really want people sending
web requests from them? What if your IP was the one that filled out the
hotmail form to send mail to the President? It seems maybe the static
nodes are in a better situation here, a) because they have lots of
traffic and quite plausibly didn't send it themselves, b) because they
decided to put up the node and think it's a good idea to keep it, etc.
I worry that a few well-placed arrests/lawsuits for individual citizens
will completely destroy such a p2p anonymizing network. Other issues
include getting a topology that offers comparable anonymity to the clique
topology assumed earlier in the paper (and also addressing the fact that
the adversary could control just a few mixes in the right place to attack
a certain victim), dealing with users on modems, dealing with users that
leave as soon as their web browse is done (making them useless for large
downloads or ssh connections), etc.

So the conclusion in 5.4 that the p2p networks are the best choice seems
unmotivated. Rather than looking like the best choice, they instead look
like the least explored choice.

--Roger