How crowds works
# Each user joins a crowd of other users by registering himself at the blender which is a single server responsible for membership management. When a user registers, all the other members in the crowd are notified. The blender is also responsible for key distribution, as it distributes symmetric keys to individual pairs of jondos, used for encryption and decryption, respectively of packets routed along the virtual paths. # Each user is represented by a jondo on her machine which is an application that runs on a user's computer. # Each jondo either submits a request to the end server or forwards it to a randomly chosen jondo (possibly itself). Other jondo tasks are to strip out any personal information such as cookies, identifying header fields. # A jondo cannot tell if a request is initiated by the previous jondo or one before it. # Request and reply follow the same virtual paths which are constructed using an algorithm involving probabilities. The virtual paths are torn down and reconstructed on a regular basis to allow anonymity for newly added members.Definitions
Crowds uses and defines the following terms: ; Sender : The initiator of a message ; Receiver : The final recipient of a message ; Probable Innocence : The attacker is unable to have greater than 50% confidence that any node initiated the message (a node appears equally likely to have initiated the message as to not have - each user is more likely innocent than not.) ; Local Eavesdropper : An attacker that can observe all incoming and outgoing messages for any proper subset of the nodes ; Corrupt Node : A node is corrupt if it uses information obtained from forwarding the message to determine the sender ; : The number of corrupt nodes ; : The number of nodes ( is the number of good nodes) ; : The probability of forwardingBasic 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 ) 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.The algorithm on each machine
# Flip biased coin () ## ''If'' Heads ''Then'' Select a uniformly random node and forward to them ## ''Else'' Forward to destination # Record P so that a tunnel can be builtSecurity 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: #Let Hk, k >= 1, denote the event that the first collaborator on the path occupies the kth position on the path, where the initiator itself occupies the 0th position (and possibly others). #Let define Hk+ = Hk or Hk+1 or Hk+2 or . . . . #Let I denote the event that the first collaborator on the path is immediately preceded on the path by 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: :initiator jondo(0 - position) ----> jondo(1 - position) ----> :initiator jondo(2 - position) ----> Collaborating jondo(3 - position) Note that the first collaborator on the path is in the third position. :4.Given this notation, the collaborators now hope to determine: 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: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.Prevention
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 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. seeSee also
*References
Further reading
# # # #External links