From asr32@cornell.edu Wed Mar 15 23:57:06 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2G4v5t23453 for ; Wed, 15 Mar 2006 23:57:06 -0500 (EST) Received: from dreadnought.cornell.edu (r253240123.resnet.cornell.edu [128.253.240.123]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2G4v5TK001741 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Wed, 15 Mar 2006 23:57:05 -0500 (EST) Message-Id: <6.2.1.2.2.20060314234207.02ea8648@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Wed, 15 Mar 2006 23:09:07 -0500 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 15 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Crowds is a particularly simple and clean source-rewriting system, without any cryptography at all. Crowds is designed to allow anonymous web browsing, and to provide anonymity with respect to web servers, and colluding Crowds nodes. In Crowds, there are no mixes. Nodes (called jondos) simply forward requests through other nodes through persistent routes (reminiscent of onion routes). The routes are chosen on a hop-by-hop basis by the preceding node. Everything is sent in plaintext, so there is no need for public key infrastructure, and no need for lengthy setup. There is, however, no anonymity from a global passive observer, or a passive observer able to monitor all traffic into or out of a given node. The success of crowds seems largely due to the fairly accommodating threat model. P5: It is possible to build a system that gains anonymity from broadcast primitives. In a source-rewriting system, attackers can always try to trace streams back to endpoints. In a broadcast-based system, there are many different and indistinguishable endpoints, foiling this attack. In this way, broadcast systems promise greater anonymity. The best example of this sort of system is P5, which has been simulated but never implemented. A P5 system consists of a logical tree, each of whose nodes is mapped to some number of nodes. Nodes continually output encrypted traffic, which can only be understood by a node with the appropriate private key. This traffic is then broadcast to each relevant node; specifically, the root of the tree, and the path through the hierarchy to the exact match node, and all the children of the exact match mode. Note that this broadcasting is presumably done by the P5 system, at the application layer. P5, alas, seems to use inordinate bandwidth, and as a result seems not to be usable in practice. DC-nets: A radically different solution for anonymity is the "Dining Cryptographer's" protocol, proposed by Chaum in 1988. In this protocol, each node borders on some other nodes, with which it shares some stream of random or pseudorandom key material. It then broadcasts the mod-2 sum of its key material and the bit to transmit. Since each key is shared by exactly two participants, the mod-2 sum of all bits transmitted in the network is just the mod-2 sum of the data bits. In the absence of collision, this allows a node to transmit data with unconditional anonymity. Collisions are dealt with by treating the DC-net as a common media, and using straightforward techniques such as ethernet's CSMA/CD. By laying "trap" messages, protocol disrupters can be probabilistically identified and removed from the network. The DC system provides very strong anonymity guarantees, but with a price. The system provides k-anonymity, but the system moves at the pace of the slowest member of the set, and the total throughput therefore falls as k grows. If k-anonymity is desired for large k and fairly high performance, DC nets are not truly suitable. Herbivore: It turns out that it is possible to make DC-nets scale., to an extent. The only implemented system that actually uses DC-nets in a scalable way is Herbivore, an anonymous filesharing system. Herbivore clusters nodes into cliques, each of which has a location on a Pastry ring. Each Herbivore clique runs the dining-cryptographer protocol separately. As a result, anybody in the clique could have sent a given message. Messages can also be sent from clique to clique, using individual nodes in each clique as proxies. (This means, however, that the proxy in each clique, or a global passive observer, knows which clique the message came from.) Latency is masked by running the protocol many times in parallel. Herbivore masks latency, it does not eliminate it. This means that it is only suitable for bulk transfer of data. Herbivore is also vulnerable to denial-of-service attacks. While an attacker cannot "take over" a clique, even one hostile member can paralyze it by joining, and then transmitting slowly, or by talking out of turn. If an attacker has a suitably sized pool of solved cryptopuzzles, they may be able to keep up a steady stream of joins, and use each joined node to block the clique for a time. In this way, an attacker is able to permanently block the system (assuming that a struck node can reenter at some point in the future). Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From sh366@cornell.edu Thu Mar 16 02:43:17 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2G7hHt02372 for ; Thu, 16 Mar 2006 02:43:17 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2G7hHUd018562 for ; Thu, 16 Mar 2006 02:43:17 -0500 (EST) Message-ID: <1452781051.1142494995483.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Thu, 16 Mar 2006 02:43:15 -0500 (EST) From: Huang Shiang-Jia To: egs+summary@cs.cornell.edu Subject: PAPER 15 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: uPortal WEB email client 3.0 The papers to be discussed today present schemes to communicate anonymously over the Internet. Crowd achieves this by routing messages through different, potentially random paths. P5 scales the broadcast protocols by allowing anonymous connections through a logical broadcast hierarchy. DC-Net provides a framework for unconditional anonymous communications, which forms the basis of Herbivore, a peer-to-peer file sharing system with anonymity. Crowd can't resist statistic correlation attacks. The noise packets of P5 imply heavy load over the Internet all the time. DC-Net and Herbivore are vulnerable to disruption attacks. * In Crowd, a sender delivers by passing his/her messages to a randomly chosen member. That member either delivers the messages to the receiver or forwards them to a randomly chosen member, so on and forth. Any member on the path, as a successor to route the messages, can't tell whether his/her predecessor initiates or simply forwards the messages. However, if the attacker can trace the whole traffic over the Internet, he/she can identify the originator. * P5 provides scalability for anonymous broadcast protocols as follows: Each node in P5's binary tree corresponds to a broadcast channel. It is represented by (bit-string/bit-mask) pairs. A user participates as a member of some node whose bit-string can act as a prefix of his/her key's hash value. The bit-mask i.e., hierarchical level, is decided independently based on the user's security policy: the lower levels increase communication efficiency at the expense of decreased anonymity and vice versa. Users communicate via a common channel. * P5 is subject to two attacks: (Difference Attack) If A has communicated with someone via a channel of level v, he/she should avoid responding to a message delivered to the channel of level < v, since in this way attackers can map A to a smaller set of users. (Intersection Attack) Because participants may exist in a set of groups as they need to communicate with each other via a common channel, their anonymity might be reduced by the intersecting sets they appear. It is therefore important for users to communicate through only one anonymous group. * DC-Net transmits messages in the following way: Suppose there are three participants A, B and C. (We say that A, B and C form an anonymous set.) Each pair of them tosses a coin in secret, namely AB, BC and CA. Basically, everyone reports the XOR of his/her coin tosses for every transmission. If one of them (A) wants to transmit a one-bit message m, he/she reports the XOR of his/her coin tosses with the message. In this case, the overall parity of their reports turns out to be m. Neither B nor C knows the bit is delivered by A because B has no idea about CA and C has no idea about AB. * (1) Scalability is a problem of DC-Net since it requires N^2 secrets shared by all participants. (2) Randomness of the secrets shared by participants is essential to this scheme. In the cryptographic system, this is generally achieved by having two participants share a secret key and use that as the seed to generate a pseudo-random sequence. (3) Underlying communication techniques is another concern. Star topology is more efficient than ring topology communication systems in delivery of messages. (4) An anonymous protocol for participants to reserve transmission slots is required. * Herbivore adapts the scheme of DC-Net and scales through a divide-and-conquer approach that partitions the system into several anonymizing cliques. It allows participants to anonymously sign up for slots before transmission so as to avoid collisions. File queries and transfers are conducted within each anonymizing clique. Inter-clique communications are carried out by proxies. * One issue of Herbivore is that one malicious participant is sufficient to anonymously disrupt the whole transmission. Another issue on the anonymizing cliques is its locality. Since they are formed according to the participants' identifiers strictly, nodes located at different areas may exist in an anonymizing clique, thereby causing long propagation latency. The protocol might be loosened in such a way that forms several anonymizing cliques across a range of identifier space, each accommodates participants geographically nearby. From gp72@cornell.edu Thu Mar 16 10:32:47 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2GFWkt05568 for ; Thu, 16 Mar 2006 10:32:46 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2GFWiNA016978; Thu, 16 Mar 2006 10:32:44 -0500 (EST) Message-ID: <2125310959.1142523163742.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Thu, 16 Mar 2006 10:32:43 -0500 (EST) From: Gopal Parameswaran To: egs+summary@cs.cornell.edu Subject: PAPER 15 Cc: Gopal Parameswaran Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: uPortal WEB email client 3.0 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k2GFWkt05568 Dining Cryptographers Problem: This paper discusses a new elegant way of anonymous communication based on using more than one person's key for encrypting the message by XOR and thus when the message is being decoded the sender of the message cannot be determined. Thus each participant in the process has two kinds of secrets viz. A key that is shared with other users and the inversion that is used to change the message. This schema can be subject to disruptions but the author shows that if three requirements are met then the system would be stable to disruptions and the disrupting node would get excluded from the network. The first requirement is that the information need not be secret and should be made known to all participants and that the participants agree on it. The second requirement being in part that disrupter be unable to change their output after hearing other participants' outputs. And the third requirement is that at least some rounds can be contested without compromising the traceability of non-disrupting senders. This solution to the dining cryptographers problem demonstrates that unconditional secrecy channels can be used to construct an unconditional sender-untraceability channel. It also shows that a public-key distribution system can be used to construct a computationally secure sender-untraceability channel. The approach appears able to satisfy a wide range of practical concerns. P5: P5 is a protocol for anonymous communication over the Internet for peer to peer systems. It handles all the three common subtypes of sender security, receiver security and sender-receiver security. However P5 scales the simple solution of a global broadcast channel to all users by creating a broadcast hierarchy where different levels of the hierarchy provide different levels of anonymity, at the cost of communication bandwidth and reliability. Users of the system locally select a level of anonymity and communication efficiency and can locally map themselves to a level which provides requisite performance. At any time, it is possible for individual users in to decrease anonymity by choosing a more communication efficient channel. It is possible to choose a set of parameters that use mutually incompatible levels of bandwidth utilization and anonymity that is not supported by the system. This system also allows a trade off between bandwidth and communication efficiency, in this system only one sender-receiver pair may simultaneously communicate in this system. Thus, these systems cannot be used to implement large anonymous communication groups. Crowds: Crowd provides anonymous peer to peer communication by selecting a node a t random while sending a message and then changing the message so that it seems that the message had originated from that node. This process of random selection of nodes for senders are done multiple times and this hides the original sender of the message. Thus even the crowd member nodes cannot identify the source since the source can be the random sender or the original sender. However Crowd does not make any effort to defend against denial of service attacks but those attacks are detectable when crowd members refuse to pass on messages which they have accepted. Unlike P5 the length of a message routed through the network does not grow proportionally to the number of nodes it has passed through. IN Crowd a user when he joins the network is allocated a proxy server and on the first request allocates a random path of random nodes that carry on the message for the user. At every point the server selects randomly whether to send the message to its destination or pass it to another random server. However once a path has been selected subsequent request follow the same path. HerbivoreFS: This paper outlines the design of HerbivoreFS an anonymous peer to peer network for file sharing that provides strong anonymity and provides computational guarantees that even adversaries able to monitor all network traffic cannot deduce the identity of a sender or receiver beyond an anonymous clique of k peers. Scalability is achieved by partitioning the global network into smaller anonymous cliques. The lower layer herbivore protocol is based on the dining cryptographers networks and guarantees that an adversary with unrestricted wire tapping capabilities cannot deduce the provider or requester of a file without breaking the RSA code or reversing a one way hash function. It performs anonymous file lookup and spreads culpability across a wide set of nodes that makes it intractable to mount blind legal attacks against groups. From ns253@cornell.edu Thu Mar 16 10:58:59 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2GFwxt16805 for ; Thu, 16 Mar 2006 10:58:59 -0500 (EST) Received: from localhost (cpe-69-207-49-126.twcny.res.rr.com [69.207.49.126]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2GFwwKv000375 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Thu, 16 Mar 2006 10:58:58 -0500 (EST) Date: Thu, 16 Mar 2006 10:58:58 -0500 From: Niranjan Sivakumar To: egs+summary@cs.cornell.edu Subject: PAPER 15 Message-Id: <20060316105858.92746a9b.ns253@cornell.edu> Organization: Cornell Law School X-Mailer: Sylpheed version 2.2.2 (GTK+ 2.8.13; i686-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Niranjan Sivakumar Crowds: Anonymity for Web Transactions The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability P5: A Protocol for Scalable Anonymous Communication Crowds are based on forwarding queries through a number of nodes in a network such that it is difficult to tell whether the node from which a request is received is the source of the query. The authors define different levels of anonymity in a system aiming for a minimum of "probably innocence". The system is resilient at some level to eavesdropping on the local, end server, and collaborative level. However, someone with a global view of the network would be able to trace queries. The nodes, known as jondos, encrypt packets on the path to the ultimate destination, but the system does not rely on a public key infrastructure. The system does not use constantly changing paths due to vulnerabilities in this approach. There is some possibility of timing attacks against the crowd system. P5 bases its approach on the idea that it is difficult to tell who the intended recipient of a message is when it is broadcast. The system takes this basic principle, which would be quite inefficient to implement on the Internet, and attempts to scale it by providing a hierarchical system to provide different levels of anonymity. Lower levels in the tree-based hierarchy provide lower levels of anonymity in exchange for better efficiency. Traffic is encrypted, and as in Crowds, a public key infrastructure is not assumed. There are some vulnerabilities in the system to a very powerful attacker. The dining cryptographers protocol is based on the idea that nodes in a ring can share a "coin-flip" secret with adjacent nodes and broadcast the XOR of the two secrets that they know to the group. One participant can also embed a message into their announcement. The message can be retrieved, but the participants in the network cannot determine who the sender is because of they can never know both of the secrets that the sender knew. This general approach is expanded to use secret keys instead of a literal "coin flip" to implement the protocol. Herbivore is based on DC-Nets and works to improve inefficiencies. Herbivore makes small DC-Net groups that are inserted into a Pastry network. This approach means that the source group, or clique, of a request can be known, but it is not possible to determine who in the clique actually sent the message. A system of crypto-puzzles is used to protect against Sybil attacks to some extent. Some of the approaches that we have seen to do not seem to scale well to different kinds of Internet media. There seems to be a problem of incentive to get nodes to forward large amounts of data to preserve anonymity, such as for redirecting a streaming video or audio broadcast. The ethics section of P5 seems to be quite underdeveloped, in particular, it is not clear if they are claiming that the weakness of their protocol to a strong attacker is a "feature" or "benefit" or some kind, but they do raise the important issue of abuse of anonymity. At another level, it seems that it may be important in some instances to mask that you are even a participant in an anonymity system. This is particularly a problem in crowds, where participants are very clearly indicated. Since there is certainly some performance loss when participating in these anonymity systems versus directly seeking data, it could be a problem if people only use such systems for activity that they want to hi! de rather than for all of their usage. If an anonymity system is used only for conduct that may be "questionable" in some sense, then all participants in a network may be held liable for facilitating such conduct by knowingly participating in the system. From nsg7@cornell.edu Thu Mar 16 11:36:49 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.9 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2GGant29760 for ; Thu, 16 Mar 2006 11:36:49 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2GGalCE028690 for ; Thu, 16 Mar 2006 11:36:48 -0500 (EST) Received: from 132.236.227.119 by webmail.cornell.edu with HTTP; Thu, 16 Mar 2006 11:36:48 -0500 (EST) Message-ID: <1689.132.236.227.119.1142527008.squirrel@webmail.cornell.edu> Date: Thu, 16 Mar 2006 11:36:48 -0500 (EST) Subject: PAPER 15 From: "Nicholas S Gerner" To: egs+summary@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal "Crowds..." presents a system meant to provide anonymity for HTTP (and a few other related protocols) transactions. The way this is provided is to route requests (and their responses) along a path through a "crowd" of "jondo" nodes. Each jondo knows the previous and next nodes on the path relative to its position and two successive jondos on a path transmit the request between them such that the previous and next nodes on the path are not directly revealed. Paths are constructed probabilistically such that each node will forward the message to another jondo rather than the end server with some probability, otherwise the message is delivered to the end server. Two anonymity properties are argued to be provided to varying degrees: sender anonymity (such that the sender is not known to the attacker) and receiver anonymity (such that the receiver is not known to the attacker). Three types of attackers are considered: local eavesdropper, collaborating jondos, end server. A high degree of receiver anonymity is shown to be provided against these attackers as the size of the crowd grows and a similar degree of sender anonymity is shown against collaborating jondos as long as non of these jondos participate in the path (which happens with high probability as the crowd grows). Jondos join a crowd by contacting a centralized membership server called a "blender". Messages are encrypted between Jondos and the contents of requests and responses are encrypted along the entire routing path within the crowd. Performance of such a system seems to degrade very quickly (as shown empirically) as the strength of the anonymity properties increases. It seems that the RTT between initiator and server scales linearly with path length. Recall that the probability of providing the anonymity properties scales with the crowd size. Sybil attacks also seem to pose a difficult challenge to such a system couting on small crowd size (for performance reasons). Such a small crowd also does not provide much cover to a particular node (even crowds of size four empirically impose high latency without much cover) because joining a crowd reveals all members of the crowd. P5 provides a tree extenion to a naive global broadcast channel providing sender and receiver anonymity. Here a tree is formed where each node is a broadcast channel in which many peers participate. Higher tree-nodes provide a higher degree of anonymity while trading off worse performance. A peer can always move down the tree to achieve better performance at worse anonymity, but not vice versa. If a peer wishes to send a message it encrypts the contents with the destination peer's public key (globally known) and adds the destination address (which identifies a tree node to route the message to along which lies the tree node containing the destination peer). The message is then forwarded up and down the tree accordingly. When the message arrives in the specified tree-node each peer must decrypt a chunk of the message to see if the message is destined for that peer. Peers also send noise messages to random addresses periodically to prevent an adversary from correlating messages. This system provides a tradeoff of performance vs. anonymity (a peer can select in which part of the tree to reside), however even lower tree-nodes require substantial network cost even if the peer sends no useful communication. Also tree-nodes must have a certain number of peers in order to provide proper anonymity and so the heirarchy must be rebuilt if the membership of a tree-node falls below this treshold. Herbivore extends DC-net whereby a sender can broadcast a message without revealing its source. Each pair of peers shares a coinflip and these coinflips are xor'd and broadcasted by each peer. The sender does this, but additionally xors its message and broadcasts this. All these broadcasts can be xor'd to retrieve the original message. Herbivore builds several of these cliques and places them on a global DHT ring to overcome the inherent scalability problems of such a clique. Queries are first broadcasted in the local clique and every clique member checks their filestore and a cache of other files. When files are found they are broadcasted to the entire clique which caches a copy. When not found locally queries are sent to the proper clique via proxies selected from the local and remote clique. Herbivore overcomes the constant broadcast required in P5 and is decentralized and structured unlike Crowds. There is clearly a tradeoff between bandwidth (performance) and cliquesize (strength of anonymity) in Herbivore which is argued to be inherent in this type of anonymity system. From kelvinso@gmail.com Thu Mar 16 11:38:23 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.202] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2GGcMt00294 for ; Thu, 16 Mar 2006 11:38:22 -0500 (EST) Received: by wproxy.gmail.com with SMTP id 68so482763wra for ; Thu, 16 Mar 2006 08:38:22 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=Ui+E5O5nx6HIW+7AY8DMI0VpsSO51jywvTvkzj/ZOr9RnWpcHNz2Ge1AXIYPSJW/vTB8/fSD/2GDpacXKBfgRndaqUMnMtWgbtvhS/zCAh7EIpgifjHUE2NRHs7JbYOD20V+51cJWlpYa38ZA7pVNaHTVFEwhLKBj82VBcVuYb8= Received: by 10.54.65.15 with SMTP id n15mr1796962wra; Thu, 16 Mar 2006 08:38:22 -0800 (PST) Received: by 10.54.80.9 with HTTP; Thu, 16 Mar 2006 08:38:22 -0800 (PST) Message-ID: <6e1ca4560603160838w73883003i9008c859940c2c7a@mail.gmail.com> Date: Thu, 16 Mar 2006 11:38:22 -0500 From: "Chiu Wah Kelvin So" To: egs+summary@cs.cornell.edu Subject: Paper 15 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k2GGcMt00294 The first paper, "Crowds: Anonymity for Web Transactions," present an architecture to increase anonymity in the Internet. Crowds increase the anonymity of the sender by sending the packet to a random member in the crowds. Then, the member will decide to forward the packet to random member or send it to the server. Therefore, the server has no way to find out who is the sender of the messages (sender anonymity) since the packet came from the sender or a random member in crowds. The advantage of crowd is that it has low aggregate on the network. However, an adversary can perform statistical correlation attack in crowds, where a passive adversary listen for number of packets can make some correlation with the packets and its original sender. The second paper, "P5: A Protocol for Scalable Anonymous Communication," presents an anonymous communication over the internet. The primary idea is to broadcast the message at a fixed rate to all the members in the group and encrypt the receiver public key. Therefore, everyone in the group will receive the message and only the receiver with the private key understands the message. P5 built a logical tree and disseminated the message from the sink to all the other members. Each node in the tree can contain multiple users. To send a message to a user, it first needs to send the message to the sink, and then sink disseminates the message using the tree. To avoid adversary to perform statistical correlation attack from sender to the sink, P5 periodically sends out noise packet when user has no packet to send. It also provides tradeoff between anonymity and number of users to send to. One of the drawbacks of P5 is that it uses up too much aggregate bandwidth since it sends every message to all the users and dummy messages when user is idle. The third paper, "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability," presents another way for anonymous communication. The primary idea is to use XOR. If there are A, B, and C users and one of the user needs to communicate with the rest of the group without other user knows about the sender, each user first roll a number. Let's say A rolls X, B rolls Y, and C rolls Z. Each person will XOR with the person on the left, which results A XOR B, B XOR C, and C XOR A, and tells everyone the XOR result. With A wants to send out message m, it will do A XOR B XOR m. Therefore, the combining all the XOR result, we will have A XOR B XOR B XOR C XOR C XOR A XOR m = m. The paper generalizes this idea to use in DC-nets. However, the proposed algorithm is not scalable. The forth paper, "Eluding Carnivores: File Sharing with Strong Anonymity," generalize DC-net and make it scalable. Herbivore scales by partitioning the all the users into smaller anonymous cliques. Each clique operates on its own for efficiency. Herbivore is built on top of Pastry. Therefore, when a node joins, it can efficiently find the closest preexisting clique in the logical identification space. Instead of using a random number it generates each time, each user exchanges the random generator SEED instead. To reduce network load, each round of information exchange is designated to a mediator in the clique. The mediator will collect all the packets from clique members and disseminate them. Therefore, multiple rounds can run at the same time with different mediators. From km266@cornell.edu Thu Mar 16 11:55:17 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.5 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2GGtHt05712 for ; Thu, 16 Mar 2006 11:55:17 -0500 (EST) Received: from KEVSTOY (cpe-69-207-37-68.twcny.res.rr.com [69.207.37.68]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2GGtGvm022316 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Thu, 16 Mar 2006 11:55:17 -0500 (EST) Message-ID: <000901c6491a$670b77e0$4425cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 15 Date: Thu, 16 Mar 2006 11:55:16 -0500 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2527 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2527 Crowds is a simple system that has a Blender (a pre-known server) that sets up communication between a p2p like system and a client. The client requests, from the Blender, all the peers in the system (although not all are necessary) and then when it sends out a request, it forwards it on to one of them (possibly itself). To prevent an attacker from using the newly incoming node as information, joins are done in batches. Crowds is not concerned with an all-knowing observer: the communication is not symetric. Therefore, an observer can see that a request was made from a node that never had an incoming packets. The observer could therefore know exactly which node originated the request. Mix that in with no gauranteed receiver anonymity and you have a problem. Crowds works by having clients run a program called a 'jondo' that works as an application-layer program that forwards and processes requests. The jondo, when a user requests a page, forwards that request on to another server. If the request came from another node then it, with probability p_f, forwards the message on to another node and with probability p_f-1 sends the request to the destination. Communication between peers is encrypted so anyone outside the crowd cannot see what is being transmitted. Anyone along the path, however, can see the packet in plaintext. This is necessary since they might be the node that has to forward the request on to the server. Also note that paths are persistent. For security measures, each time you send a request you send it along the same path. Even if a peer drops out then you keep forwarding it along the same path until the dropped peer and then randomly pick a new peer. Crowds has several problems. A lot of Crowds depends on the end user. When a join commit occurs, the jondo alerts the user to stop browsing the same website or they might be discovored: this seems like a downfall. All of the interesting things are also put into the Blender: node joins, commits, usernames and identifying information. While security might not be comprimised if the Blender goes down, a legal attack on the server will make Crowds non-functional since no-one new can join and once you drop out you are out for good. The Blender also gets rid of Sybil attacks and user-duplication problems. Lastly, performance on this system is pretty terrible: a 25k packet takes nearly 20 seconds to be routed through 5 people! P5 is another protocol that uses a heirarchical system of mixes. A mix is a group of peers that constantly send information back and forth to each other (making communication synchronous). If a message is 'real' then it is encrypted and looks just as random as the 'junk' messages that normally get sent between peers. The obvious down side to this is the high overhead of encryption and the massive amount of bandwidth overhead that is needed for synchronous communication...especially since most of the packets are likely to be garbage. P5 scales this system up by making it heirarhical. The mix that you join depends on how much communication you are willing to bear. The more you are willing to take on, the more anonymitty you are gauranteed. The nice thing about this system is that an all-knowing passive observer (that can't hack encryption) cannot get to the contents of the message, cannot know where the receiver or the senders are. At any point, if a node wants to decrease its communication throughput and decrease its security alongside it, they can do that (while climbing up is impossible). It seems that the massive amount of communication would still be a downside to this system. Both encryption and the synchronous communication make the system too hefty. HerbivoreFS is a file-sharing protocol that preservers user anonymity. It acheives this by inserting Dining Crypto Nets into a P2P system. In this way, an attackers that has infinite wire-tapping abilities can only find out which net the packet came from, not the exact peer. Therefore, if your net is large enough, legal attacks cannot be mounted on a specific person (and anonymity is preserved). The Dining Cryptographers paper introduces a concept of XORing public keys together. In this way, when a receiver gets the packet that is destined for her, she cannot determine exactly which sender actually sent it (since it is encrypted with all the keys along the path to her). The author goes on to show that using several methods, it is possible to deter a malicious or misbehaving node. The problem is that you need a concensus protocol or some sort of hefty higher level communication between nodes to get them to agree to some of the conditions the author outlines, making this system unrealistic. The second problem is the massive amount of encryption going on, slowing down the packet while it is being dragged along the path. From asg46@cornell.edu Thu Mar 16 12:11:13 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2GHBDt10534 for ; Thu, 16 Mar 2006 12:11:13 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2GHBBoo020524 for ; Thu, 16 Mar 2006 12:11:12 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Thu, 16 Mar 2006 12:11:12 -0500 (EST) Message-ID: <1054.128.84.98.90.1142529072.squirrel@webmail.cornell.edu> Date: Thu, 16 Mar 2006 12:11:12 -0500 (EST) Subject: paper 15 - anonymity From: "Abhishek Santosh Gupta" To: egs+summary@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal CROWDS crowd members are termed as jondos. when a jondo receives a request, it flips a biased coin to determine whether or not to forward this request to another jondo. each packet has a path identifier to enable jondos to take independent actions since it might occupy multiple positions on the path. a member of the crowd may submit requests initiated by others users. SECURITY ANALYSIS sender anonymity is not offered against a local eavesdropper. receiver anonymity is offered beyond suspicion. increasing the probability of forwarding a request increases the number of collaborating jondos that can be tolerated (since forwarding paths will be longer)however system performance decreases. even crowd members cannot identify the initiator of the request. crowd based systems can fail in case of malicious members which may drop packets or forward incorrect ones. HTML TIMING ATTACKS : when a jondo receives a HTML page as response, it might request for additional URLs from that page. The immediate nature of these requests opens opportunities for timing attacks by collaborating jondos. Timing attacks have been eliminated by the last jondo on the path requesting these URLs and sending them on the same path as the original request. Thus, the initiator waits for these URLs instead of explicitly issuing requests. P5 P5 allows users to trade-off the degree of anonymity for communication efficiency ( you can decrease the amount of anonymity but not increase it) packets are encrypted using the receiver's public key. every message is hop-by-hop encrypted (each node acts as a mix). a broadcast hierarchy is created to make the broadcast mechanism scalable. the hierarchy consists of a binary tree which is constructed using the public key of the users. each node of the tree contains a bitstring and a bitmask (b/m). the bitmask specifies as to how many of the msb of the bitstring are valid. a message sent on (b/m) is forwarded to: 1) all members in (b/m) group 2) all members of the group at nodes higher up ( which match some prefix of the bitstring b) 3) all members of the subtree below this node (nodes whose bitstring has prefix b) each user in the system can join a set of broadcast groups dependent upon the hash of the user's public key. the user can also select the bitmask value thus determining the specific group that he wants to join. noise: each user generates a fixed amount of traffic at all times to prevent local eavesdropping. message dropping algorithms must be used to control queue sizes (which increase easily due to broadcast mechanism) ANONYMITY ANALYSIS : sender and receiver anonymity depend upon group sizes. ATTACKS : Correlation attacks will be avoided due to noise packets. Difference and Intersection attacks map the user to a smaller subset of the group based upon the knowledge of his presence in more than 1 group. HERBIVORE FS: based on DC-nets DC nets have the following properties 1) only 1 sender can send at a time 2) requires a mediator 3) even if 1 member in the clique is malicious the scheme fails beyond repair herbivore FS takes care of 1) and 2) 1) to prevent multiple messages from being garbled - a concept of transmission slots and reservation protocols exist 2) the mediator is replaced by a broadcast ( or another center node which acts a mediator for each round) 3) the paper talks about a strike table mechanism to remove malicious node. However, a malicious node could still target a smaller set of users without being striked out. each node is forced to choose a random ID to prevent targeting a particular user. multiple instances of the protocol with different mediators help in achieving higher throughputs. INSERTION ATTACKS : each node reserves space for two sets of files A and B - A for the files that it introduced and B for the files introduced by the clique. files placed on the A-list are transferred to the B-list after response to the first query. the B-list is managed as a LRU cache. This caching mechanism hides the identity of the node as the node does not insert a file into the network more than once(each member of the clique then has a copy of it in the B-list) dropping of files seems to be a valid tradeoff of availability against security.