This post deals with the verification of the correctness of the Theorem 5.2 for anonymity from the work of Rubin et al on Crowds: “Anonymity for Web Transactions“. I did this to complete my Bachelors degree.
The main statement to verify is that “The initiator of the message has proven probable innocence against the collaborative members.”
Here, n is the total number of nodes and c is the number of collaborating members.
To verify the correctness a tool was needed. The work resulted in this software that can be used to simulate anonymity network protocols. The overall goal was to provide a tool to empirically analyze anonymization protocols. The simulator was designed with respect to extend it easily by further protocols. One can easily run simulations on the pre defined network and perform attack scenarios on the protocols in order to find possible (unknown) security issues. Crowds is implemented with the Dijkstra algorithm to find the path through the network.
In order to be able to empirically verify the correct functionality of the Crowds protocol, collaborating attackers are used in the simulator. For the verification of the probable innocence under condition 100 runs were simulated twice.
At first the assumption of the theorem was observed and then the theorem was violated. If the theorem was violated, it should be possible to the attacker to determine the sender of the message.
To verify this 100 simulations with 200 nodes each were performed. The test was exectued with a probablitiy of p_f = 0.7. From this it follows, at 200 nodes that (c + 1) is less than 57.14 in order not to violate the requirement of the condition above. The number of collaborating nodes was set to 50, 55, 56, 57 and 58 nodes for five simulation runs. A safe variant deals with 50 nodes. As a result, the correct sender was not detected a single time. Within these simulations, it was not possible for the attacker to reveal the sender with a probability greater than 1/2. At 58 nodes, on the other hand, half of the 200 simulations the sender was detected.
As a result, the Theorem (Theorem 5.2. of Rubin et el.) is correct and when the condition is violated the sender can be detected with a probability of 1/2.