[freehaven-dev] Project "Anonymity and Unobservability in the Internet"

[Roger R Dingledine <arma@mit.edu>]

http://www.inf.tu-dresden.de/~hf2/publ/2000/BeFK2000cfp2000/index.html

Abstract. It is a hard problem to achieve anonymity for real-time
services in the Internet (e.g. Web access). All existing concepts fail
when we assume a very strong attacker model (i.e. an attacker is able
to observe all communication links). We also show that these attacks
are real-world attacks. This paper outlines alternative models which
mostly render these attacks useless. Our present work tries to increase
the efficiency of these measures.



They address chaum mixes, onion routing, the freedom network, the web
anonymizer, etc. I didn't see any quantification (but hey, we don't have
any either), but it looks like they get at least a bit specific about what
they mean.
I especially like this part:




Prevention of intersection attack. A perfect system has to prevent
intersection attacks: Because of the on-line/off-line periods of the
users or a special distinguishable behavior an attacker may trace users
by observation over a long period. Ordinary Internet users have a limited
number of communication relations and show a very balanced behavior. That
means, they have got at most a few hundred e-mail addresses they use, and
the number of periodically visited Web sites changes very rarely. More
technically spoken, if a client configures his browser to request a
certain Web page each time he opens a new browser window, he puts his
unobservability at risk. The observer has only to remember the identities
of all active users at the time of the request. Later on, when the page
is requested again (and again), the observer intersects the previous set
of active users with the currently active users. This kind of attack does
not definitely uncover a client. However, it dramatically reduces the
potential size of the anonymity group. Whenever the user sends individual
information (i.e.  Cookies, ID numbers, pseudonyms or data of any kind
used more than once) that no one else uses, the opponent will be able
to uncover all belonging communication relations with a high certainty.




They leave it as an open question whether the intersection attack can
be solved: specifically, they address the web anonymizer, crowds,
onion routing, freedom network, chaumian mixes, and their own "web mixes"
work, and conclude that none of these systems offer any protection
against the intersection attack.

I guess other people think it's tough too. :)

--Roger