Crowds (anonymity network)

Crowds is a proposed anonymity network for anonymous web browsing. The main idea behind Crowds anonymity protocol is to hide each user's communications by routing them randomly within a group of similar users. Neither the collaborating group members nor the end receiver can therefore be sure where in the group the packet originated. Crowds was designed by Michael K. Reiter and Aviel D. Rubin. It defends against internal attackers and a corrupt receiver, but provides no anonymity against a global attacker or a local eavesdropper (see "Crowds: Anonymity For Web Transactions"). Crowds is vulnerable to the predecessor attack; this was discussed in Reiter and Rubin's paper and further expanded in "The Predecessor Attack: An Analysis of a Threat to Anonymous Communications Systems" by Matthew K. Wright, Micah Adler, And Brian Neil Levine. Crowds introduced the concept of users blending into a crowd of computers.
Definitions.
Crowds uses and defines the following terms:
Basic Design.
Crowds works by making each node seem equally likely to be the initiator of the message. As we said each node joins the network by starting a "jondo" (from "John Doe"), which is a small process that will forward and receive requests from other users. When the jondo is started all nodes in the network are informed of the new node's entrance, and will begin to select him as a forwarder. To actually send a message a node chooses randomly (with uniform probability) from all nodes in the network and forwards the message to them. Upon receiving the message the node flips a biased coin (with probability formula_5) and if it lands heads forwards it to another random node, otherwise it forwards it to the final destination. Each node when forwarding to another node records the predecessor and in this way a tunnel is built, this is used for the communication between the sender and the receiver.
Security analysis.
We consider the question of what information an attacker can learn about the senders and receivers of web transactions, given the mechanisms of Crowds we described.
Local eavesdropper.
Recall that every message forwarded on a path, except for the final request to the end server, is encrypted. Thus, while the eavesdropper is able to view any message emanating from the user's computer, it only views a message submitted to the end server 
if the user's jondo ultimately submits the user's request itself.
Since the probability that the user's jondo ultimately submits the request is 1/n where n is the size of the crowd when the path was created. Thus we learn that the probability that the eavesdropper learns the identity of the receiver decreases as a function of crowd size. Moreover, when the user's jondo does not ultimately submit the request, the local eavesdropper sees only the encrypted address of the end server, which we suggest yields receiver anonymity that is (informally) beyond suspicion.
(beyond suspicion - no user is more suspicious than other).
Collaborating jondos.
Consider a set of collaborating corrupted jondos in the crowd. Because each jondo can observe plaintext traffic on a path routed through it, any such traffic, including the address of the end server is exposed to this attacker.
The question we consider here is if the attacker can determine who initiated the path. The goal of the collaborators is to determine the member that initiated the path.
We now analyze how confident the collaborators can be that their immediate predecessor is in fact the path initiator:
Note that H1 => I, but the converse I => H1 is not true, because the 
initiating jondo might appear on the path multiple times. There can be a case where path is composed as follow:
Note that the first collaborator on the path is in the third position.
P(I|H1+) - given that a collaborator is on the path, what is the probability that the path initiator is the first collaborator's immediate predecessor?
Definition: 
The path initiator has probable innocence if P(I|H1+)<=1\2.
In order to yield probable innocence for the path initiator, certain 
conditions must be met in our system.
In particular, let
pf > 1/2 (the probability of forwarding in the system.)
The theorem below gives a sufficient condition on pf, c, and n to ensure
probable innocence for the path initiator.
Theorem:
The path initiator has probable innocence against c collaborators in case
formula_7
Proof:
we want to show that pf > 1/2   if   formula_7
note that:
P(Hi) = formula_9
in order for the first collaborator to be in the ith position on the path, the path must first wander to i-1 noncollaborators each time with probability of 
formula_10, each of which chooses to forward the path with probability pf, and then to a collaborator with probability formula_11.
The next two facts follow immediately from this
P(H1+) = formula_12
P(H2+) = formula_13
P(H1) = formula_11
P(I|H1) = formula_15
P(I|H2) = formula_16
Now, P(I) can be captured as
P(I) = P(H1)P(I|H1) + P(H2+)P(IH2+) = formula_17
since I=>H1+
P(I|H1+)= formula_18 = formula_19 = formula_20
so, if formula_7
then P(I|H1+)<=1\2
E.g. if pf=3\4, then probable innocence is guaranteed as long as n >= 3(c + 1).
Static paths.
Dynamic paths tends to decrease the anonymity properties provided by the system against collaborating jondos. The reason is that the probable innocence vanishes if the collaborators are able to link many distinct paths as being initiated by the same jondo. Collaborating jondos might be able to link paths initiated by the same unknown jondo based on related path content or timing of
communication on paths. To prevent this, we made paths static, so the attacker simply does not have multiple paths to link to the same jondo.
Embedded images and timing attacks.
An HTML page can include a URL (e.g., the address of an image) that, when the page is retrieved, causes the user's browser to automatically issue another request. It is the immediate nature of these requests that poses the greatest opportunity for timing attacks by collaborating jondos.
The first collaborating jondo on a path, upon returning a web page on that path containing a URL that will be automatically retrieved, can time the duration until it receives the request for that URL. If the duration is sufficiently short, then this could reveal that the collaborator's immediate predecessor is the initiator of the request.
How to prevent?
When a jondo receives an HTML reply to a request that it either received directly from a user's browser or submitted directly to an end server, it parses the HTML page to identify all URLs that the user's browser will automatically request as a result of receiving this reply. The last jondo on the path requests these URLs and sends them back along the same path on which the original request was received.
The user's jondo, upon receiving requests for these URLs from the user's browser, does not forward these requests on the path, but rather simply waits for the URLs contents to arrive on the path and then feeds them to the browser. In this way, other jondos on the path never see the requests that are generated by the browser, and thus cannot glean timing information from them.
Scale.
The measure of scale that we evaluate is the expected total number of appearances that each jondo makes on all paths at any point in time. For example, if a jondo occupies two positions on one path and one position on another, then it makes a total of three appearances on these paths.
Theorem : In a crowd of size n, the expected total number of appearances that any jondo makes on all paths is
formula_22
Each jondo's expected number of appearances on paths is virtually constant as a function of the size of the crowd. This suggests that crowds should be able to grow quite large.
Attacks.
Crowds provides perfect anonymity against a corrupt receiver (i.e. formula_23 see Degree of anonymity) as all members appear equally likely to have been the initiator. As we showed against collaborating corrupt nodes Crowds provides probable innocence as long as formula_24 (see the paper for the derivation of this), and provides a degree of anonymity formula_25. Against the predecessor attack Crowds succumbs in formula_26; this attack works by a corrupt node retaining the previous hop in the path, as this will be the sender more than any other node over the rounds of rebuilding the network it will become apparent who the initiator is. Reiter and Rubin mention this and recommend "long" (and if possible infinite) time between path reformations (caused when a node in the path leaves the network). Crowds is unable to protect against a global eavesdropper as it cannot use encryption on the links, this is because each node in Crowds is able to communicate with every other node (a fully connected graph), because of this setting up symmetric keys requires formula_27 pairwise keys; this is too large of a number to be feasible. Against a local eavesdropper again Crowds provides no protection as the eavesdropper will see a message coming out of a node that did not enter, and this positively identifies the node as the sender.