Analyzing anonymity attacks through noisy channels

Anonymity protocols focus on protecting the identities of senders and/or receivers in a network communication. Most of these protocols rely on randomness to achieve their goal and therefore can very well be represented as noisy channels in the information theoretic sense. In this paper we examine the problem of measuring the anonymity degree of anonymity protocols. We investigate a new idea of measuring anonymity based on how much the rows of the channel probabilities matrix are different from each other. We propose a new and generic approximation algorithm for the open problem of finding where anonymity of a given protocol is minimized. We illustrate how the probabilities matrix is constructed for some known anonymity protocols and we use the information leakage measures to study known attacks on those protocols. The analysis shows counter intuitive results in particular for Timed dynamic pool (Cottrell) mixes. Finally, we discuss the applicability of the proposed measures on Tor Network.