Entropy with mixes in an onion routing network 

Team: Anthony Giardullo, Danish Lakhani

For our project we used the Anonymous Communication Model (as proposed by Serjantov, Danezis) to study the effects of varying parameters of different onion routing networks using mixes, on the anonymity of messages traversing such networks.

We used entropy as our measure of anonymity: a value denoting the number of additional bits of information that an attacker would need to completely identify that a message destined to a particular receiver came from a particular user 'u'. (S = -sum{p_u*log_2(p_u)} over all users). Maximum entropy is thus log_2(total number of users), and the minimum entropy is 0 (the attacker needs no bits of information to identify the sender of a message).

We considered two separate classes of models for our analysis:

In the first class, we considered only fully connected networks. In such networks, a bad mix was characterized as one which did no mixing at all (either because mixing is ineffective or the mix has been compromised by an attacker). In contrast, a good mix is one that could randomize messages such that an attacker's odds of guessing that the message destined for a particular receiver came from a sender is 1/n (where n is the total number of users -> uniform probability density). Note: a mix is bad with a probability equal to pBad and good with probability 1-pBad. This model was built using PRISM. (See entropy_basic.pm and entropy_basic.pctl.)

For our second class, we extended the first model to model randomized network traffic, and created randomized multi-graphs (to model different network topologies). To do this, we wrote code in Java that generated random 'snapshots' of network traffic in a random graph and outputted PRISM code. In addition, as this model was more complicated that our last model, we needed to write a tool in Java that helped us produce the tens of thousands of lines of PRISM code required to calculate the entropy. (See entropy.pm, preparse.java, and prismHelper.java).

To run our more advanced model, you need to pass the file entropy.pm as an argument to preparse.java to produce a .pm and .pctl file that can be run in PRISM. The file entropy.pm constains PRISM code that is annotated with our own syntax that is transformed into actual PRISM code after running preparse. See the comments in preparse.java for information on how to configure and run this model. In addition, see the comments in prismHelper.java if you are interested in using our annotated PRISM syntax.

In addition, we then tried to expand our model by having our attacker take into account a maximum and minimum route length for all messages. While this improved the attacker's power somewhat, we could not find a way to model this perfectly without requiring exponential space in PRISM. There were also other additions we wanted to make to our model, but could not because we were already pushing the limits of how much PRISM could handle. We spent some time rewriting our PRISM code to make it more efficient by reducing the number of reachable states. This made our model slightly faster but not significantly.

Results: For the simple model, we varied route length and the bad probability (the probability that a mix in the network is compromised) [We modeled for networks consisting for 3, 5, 10 and 20 users]. The results followed our intuition: increasing the route length increased the entropy (increasing the anonymity of the system). Even in cases where the majority of mix nodes have been compromised, increasing the route length can achieve extremely good entropy (this is obvious since the probability of getting at least one good mix grows significantly as the route length increases).

We also noticed that even for (small) fixed route lengths, increasing the bad probability has only a marginal effect of the entropy of mix systems at first, but causes a dramatic decrease in entropy when the pBad exceeds 75%. See the graphs in our PowerPoint Slides.

For our more complete model, we got similar results as our simpler model. The graphs show how resilient the anonymous network is against a large number of compromised nodes. However, it is worth noting that as shown in several of our graphs, the entropy can reduce extremely quickly as unfavorable conditions (such as low network traffic or an increased percentage of attackers) worsen. This shows that an implementation of an anonymous network needs to be prepared to adapt quickly under these circumstances. Once way we have shown to be effective at combating the loss of entropy is to increase the route lengths at the expense of network latency.

Last updated: March 12, 2004.