Local View Attack on Anonymous Communication
Marcin Gogolewski, Marek Klonowski, Miroslaw Kutylowski
We consider anonymous communication protocols based on onions: each
message is sent in an encrypted form through a path chosen at random by
its sender, and the message is re-coded by each server on the path.
Recently, it has been shown that if the anonymous paths are long enough,
then the protocols provide provable security for some adversary models.
However, it was assumed that all users choose intermediate servers
uniformly at random from the same set of servers.
We show that if a single user chooses only from a constrained subset of
possible intermediate servers, anonymity level may dramatically
decrease. A thumb rule is that if Alice is aware of much less than 50%
of possible intermediate servers, then the anonymity set for her message
becomes surprisingly small with high probability. Moreover, for each
location in the anonymity set an adversary may compute probability that
it gets a message of Alice. Since there are big differences in these
probabilities, in most cases the true destination of the message from
Alice is in a small group of locations with the highest probabilities.
Our results contradict a quite common belief that the protocols
mentioned guarantee anonymity provided that the set of possible
intermediate servers for each user is large.