  We perform a probabilistic analysis of onion routing. The analysis is
presented in a black-box model of anonymous communication in the Universally
Composable framework that abstracts the essential properties of onion routing
in the presence of an active adversary that controls a portion of the network
and knows all a priori distributions on user choices of destination. Our
results quantify how much the adversary can gain in identifying users by
exploiting knowledge of their probabilistic behavior. In particular, we show
that, in the limit as the network gets large, a user u's anonymity is worst
either when the other users always choose the destination u is least likely to
visit or when the other users always choose the destination u chooses. This
worst-case anonymity with an adversary that controls a fraction b of the
routers is shown to be comparable to the best-case anonymity against an
adversary that controls a fraction \surdb.
