Crowds

From Wikipedia, the free encyclopedia

For other uses, see Crowd.
This article may require cleanup to meet Wikipedia's quality standards.
Please discuss this issue on the talk page or replace this tag with a more specific message.
This article has been tagged since February 2007.

Crowds is a proposed anonymity network that gives probable innocence in the face of a large number of attackers. Crowds was designed by Michael K. Reiter and Aviel D. Rubin and 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 is important as it introduced the concept of users blending into a crowd of computers, and many of the concepts used in newer systems (e.g. Tarzan).

Contents

[edit] 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 like to have initiated the message as to not have)
Local Eavesdropper 
An attacker that can observe all incoming and outgoing messages for any propersubset of the nodes
Corrupt Node 
A node is corrupt if it uses information obtained from forwarding the message to determine the sender
C 
The number of corrupt nodes
N 
The number of nodes (N − C is the number of good nodes)
pf 
The probability of forwarding

[edit] Basic design

Crowds works by making each node seem equally likely to be the initiator of the message. 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 p_f > \frac{1}{2}) 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.

[edit] The algorithm on each machine

OnReceive(Node P, Message M)

  1. Flip biased coin (\Pr(Heads) = p_f)
    1. If Heads Then Select a uniformly random node and forward to them
    2. Else Forward to destination
  2. Record P so that a tunnel can be built

[edit] Attacks

Crowds provides perfect anonymity against a corrupt receiver (i.e. d \gets 1 see Degree of anonymity) as all members appear equally likely to have been the initiator. Against collaborating corrupt nodes Crowds provides probable innocence as long as N \geq \frac{p_f}{p_f - \frac{1}{2}}\left( C + 1\right) (see the paper for the derivation of this), and provides a degree of anonymity d \gets \frac{\frac{N - p_f \cdot (N - C - 1)}{N} \cdot \lg\left[\frac{N}{N - p_f \cdot (N - C - 1)}\right] + p_f \cdot \frac{N - C - 1}{N} \cdot \lg\left[N/p_f\right]}{\lg (N - C)}. Against the predecessor attack Crowds succumbs in O\left(\frac{N}{C} \lg(N)\right); 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 O(N2) 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.

[edit] See also

[edit] External links

[edit] References

  1. ^  Claudia D\'{\i}az and Stefaan Seys and Joris Claessens and Bart Preneel (April 2002). "Towards measuring anonymity". Proceedings of Privacy Enhancing Technologies Workshop (PET 2002). Retrieved on 2005-11-10. 
  2. ^  Michael Reiter and Aviel Rubin (June 1998). "Crowds: Anonymity for Web Transactions". ACM Transactions on Information and System Security 1 (1). Retrieved on 2005-11-23. 
  3. ^  Matthew K. Wright and Micah Adler and Brian Neil Levine and Clay Shields (2004). "The predecessor attack: An analysis of a threat to anonymous communications systems". ACM Transactions on Information Systems Security 7 (4): 489-522. Retrieved on 2005-11-23. 
  4. ^  Matthew Wright and Micah Adler and Brian Neil Levine and Clay Shields (February 2002). "An Analysis of the Degradation of Anonymous Protocols". Proceedings of the Network and Distributed Security Symposium - NDSS '02. Retrieved on 2005-11-23. 
Retrieved from "http://en.wikipedia.org../../../c/r/o/Crowds.html"