From shafat@CS.Cornell.EDU Thu Nov 14 03:51:45 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAE8pj916659 for ; Thu, 14 Nov 2002 03:51:45 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 64 Date: Thu, 14 Nov 2002 03:51:44 -0500 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134FE0@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 64 Thread-Index: AcKLrM29lCJN2Em0Rh+ZVKtGq1CGlg== From: "Syed Shafat Zaman" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id gAE8pj916659 CROWDS -------- Crowds is a system that aims to provide an increased level of anonymity to web users by "blending them into a crowd". The paper defines the notion of degrees of anonymity and Crowds' effectiveness varies depending on the type of attacker. It fails to provide any type of sender anonoymity to a local eavesdropper, while receiver anonymity is beyond suspicion and the probability is a function of crowd size. It also provides some degree of anonymity for both sender and receiver against collaborating members. As for the end server, absolute sender anonymity is guaranteed as long as the web content doesn't reveal any such information. Crowds does not present any single point of failure that could lead to a total breakdown of the system if compromised. No single failure also discontinues all web transactions. However, since a centralized mechanism is used to control Crowds membership, this could lead to total vulnerability of the system. This also makes Crowds somewhat inefficient. Firewalls also present a problem in the current implementation, as it requires all Crowds members to be inside the firewall. There can, however, be an outgoing path from within the firewall to a jondo outside - but that reveals the domain of the path initiator. In terms of scalability, the paper does not present any concrete result to show the effect on performance in terms of crowd size. Theroetical proofs suggest that the expected number of appearances of a jondo on a path is approximately constant regardless of crowd size. THE DINING CRYPTOGRAPHERS' PROBLEM ------------------------------------ The Dining Cryptographers' Problem presents a solution to sender and recipient untraceability. Anonymity is provided by a procedure by which a group of nodes jointly create a message in such a way that no other subgroup can identify the originator of the message. Even in the case when only one member in a group has something to say, any other member outside the group would fail to trace back the sender. In case of partial "collusion" or collaborating members, the members of the collusion still fail to derive any significant information from the messages they receive. Secrecy in this protocol is maintained using public/private keys. The sender can sign the message with the intended recipient's public key. Authentication is implemented with digital signatures. An untraceable owner will always have the same digital signature on all its sent messages. The protocol also has a mechanism to exclude disrupters from future participations if enough disrupted rounds are contested. And finally, although the paper does not explicitly talk about scalability, it seems that scaling might be a problem since only one user can send at a time. If the groups are made larger, this will result in large latency and also wasted bandwidth. P5 ---- Peer-to-Peer Personal Privacy Protocol or P5 uses a broadcast hierarchy based solution that provides sender, receiver and sender-receiver anonymity of different degrees in the network. It presents a trade-off between anonymity and cost of communication. At any time during the process, a user can lower its level of anonymity by choosing a more efficient bandwidth setting in the hierarchy. The reverse is however not possible, which makes the system slighly less efficient. The protocol itself is based on public-key cryptography. P5 can withstand a number of different types of attacks, such as, correlation, intersection, difference, DoS and Mob attacks. However, it is somewhat helpless against active attackers who can gain control over a large part of the network. In terms of scalability, the paper presents simulation results 8192 users, and shows that P5 can still perform at a reasonably satisfactory level without compromising reliability or bandwidth usage. From mp98@cornell.edu Thu Nov 14 03:56:22 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAE8uM917580 for ; Thu, 14 Nov 2002 03:56:22 -0500 (EST) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id DAA28891 for ; Thu, 14 Nov 2002 03:56:21 -0500 (EST) Date: Thu, 14 Nov 2002 03:56:21 -0500 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 64 From: Warren Lapine To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: X-Mailer: Apple Mail (2.546) Crowds: Crowds are a simple system providing sender anonymity (though not receiver anonymity) for web transactions. Crowds are easily to describe: Each participant maintains a web proxy or jondo. Requests through the proxy are forwarded at least one hop, and may be forwarded another hop probabilistically or sent directly to the end web server. These paths are set randomly the first time a node joins the crowd, but then remain constant. The jondos use hop-by-hop encryption for their links. The anonymity of this system is mediocre at best, because an eavesdropper on the local link level can tell when a user is sending, although they cannot necessarily read the message due to encryption (they can read the message when it is submitted. This means that one should never have a path of the form self->self->submit because this would allow a local eavesdropper to read all one's messages). A local eavesdropper can only determine the receiver if they eavesdrop on the last node in the path. A single malicious node has a probability of being a part of any jondo's path and can thus read the message. They can easily determine the identity of the receiver. The identity of the sender is a bit harder because the message may have been forwarded from another node. A nice feature of crowds is that they scale well: As more nodes are added, the average path length does not increase and the amount of state and traffic each node must maintain increases only slightly (by smaller amounts as each node joins the network in fact since they are less likely to be involved in a path). Their centralized solution for crowd membership, could use some work, however. Their efficiency measurements in terms of latency are complete bullshit: Latency does not arise from encryption. If every message had to use public key encryption, then perhaps. But there is no real reason that hop-by-hop encryption cannot be achieved through fast symmetrical key encryption (if one is concerned about a known plaintext attack, one can avoid this simply by using a block cipher in CBC mode with a random IV). The ability of malicious nodes to read messages has already been mentioned above. However, it should be noted as well that malicious nodes can drop all their packets if they desire, or forward them incorrectly or do any number of destructive actions. In addition, their use of a master key server and organizer (the blender) is a single point of failure for the network. Their system contains little discussion of what to do in the event of a node failure (obviously a new path must be constructed, but whether this should be an entirely new path from the source or just from the point of failure is unclear). DC-Nets: Dining Cryptographer nets are a nifty system designed by David Chaum whose anonymity is based upon the XOR of secret keys. Unlike Crowds, DC-nets resist local eavesdropping attacks to anonymity. However, they do so by forcing all nodes to constantly participate in expensive communication. Anonymity of DC-Nets is a function of the key topology. Messages are viewable by everyone in the DC-Net. But only if all nodes with whom v shares a key collaborate can these nodes determine which messages are v. In a complete graph, this is difficult. Scalability is somewhat a function of the network (rather than the key) topology. If the network topology is a complete graph, the system will not scale in terms of overall bandwidth (see poor performance in Cliquenet paper by Polte, Robson and Sirer.) There is no backoff scheme mentioned in the paper, and if trapping is implemented the amoung of traffic grows at least linearly with the number of hosts (star topology) or as badly as exponentially (fully connected graph). Efficiency is ultimately limited: If anyone wants to send a single bit of information, the total number of bits sent is proportional to the number of participants in the network. There is some natural tamper-suscibility to dc-nets since they keep the identities of senders anonymous within the system. However, Chaum does suggest solutions using traps (which increase the amount of traffic greatly) and cutting people out of the network. P5: P5 is another protocol which like DC-Nets limits anonymity to a small group of nodes, though P5 lets the user choose their trade-off between efficiency and anonymity. P5 can scale pretty well, since communication is once again accomplished in small groups. However, its efficiency is terrible since nodes must constantly send traffic to each other in order to mask their communication pattern. From tmroeder@CS.Cornell.EDU Thu Nov 14 08:58:12 2002 Received: from dhcp99-96.cs.cornell.edu (dhcp99-96.cs.cornell.edu [128.84.99.96]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEDwB929159 for ; Thu, 14 Nov 2002 08:58:12 -0500 (EST) Received: (from tmroeder@localhost) by dhcp99-96.cs.cornell.edu (8.11.6/8.11.6) id gAEDwCE04248; Thu, 14 Nov 2002 08:58:12 -0500 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15827.44020.277385.636797@dhcp99-96.cs.cornell.edu> Date: Thu, 14 Nov 2002 08:58:12 -0500 To: Emin Gun Sirer Subject: 615 PAPER #64 X-Mailer: VM 7.07 under Emacs 21.2.1 The first paper for today was Crowds, which seeks to provide sender and recipient untraceability by passing the message along a random path within a group of participants. They try to protect the sender from the recipient and from collaborating members of the crowd. They also protect the recipient from a local eavesdropper on the sender's machine. One significant concern I have with this scheme is that taking over the blender and still causing it appear to function correctly will allow an attacker collaborating with other nodes to have significant control over the key distribution mechanism and also would allow them to mount the kind of timing and path change attacks which are described in the paper but which the blender is designed to prevent. The single point of failure really can cause a problem, despite their best efforts. It does not scale particularly well with the size of the crowd, since paths can become very long with non-zero probability. The Dining Cryptographers paper describes dc-nets, in which pairs of nodes share key bits and announce results about the similarity or difference of the pairs of bits, inverting the result to send information. The idea itself is intuitively clear, but it leads to great scalability and efficiency problems, since to send the information anonymously, much bandwidth must be wasted in noise, and traps become necessary to make the system more tamper-resistant. The level of anonymity that any participant can get is entirely dependent on the structure of the graph, the number of colluding nodes, and the level of collusion. It is thus difficult to exactly state the level of tamper-resistance, since it depends on the particular network. It is clear, however, that in any such network, DoS attacks are feasible at least for short periods of time (even if they cause potential exposure of the attacker). The system is quite inefficient, as noted above, since many bits need to be sent to communicate one bit anonymously. P5 tries to be a protocol which allows users to trade off between communication latency, bandwidth usage, and anonymity/untraceability at runtime. It uses different groups, ordered by prefix into logical trees, and broadcasts which are sent to groups in the specified prefix and higher up the tree. The nodes must, as in dc-nets, send noise, this time to preserve sender-receiver anonymity, and so some efficiency is lost there. There is also the problem of scaling the broadcasts to so many nodes as the tree grows. In general this is a choice of the node itself, for it chooses which prefix to use when sending the message. There are several attacks which can be successfully mounted by a sufficiently powerful attacker, but in general the anonymity properties of the system are high for small attackers. From bd39@cornell.edu Thu Nov 14 10:31:49 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEFVn926325 for ; Thu, 14 Nov 2002 10:31:49 -0500 (EST) Received: from boweilaptop.cornell.edu (dhcp-128-84-93-87-wifi.ece.cornell.edu [128.84.93.87]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA09458 for ; Thu, 14 Nov 2002 10:31:39 -0500 (EST) Message-Id: <5.1.0.14.2.20021114102814.00b79778@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 14 Nov 2002 10:28:57 -0500 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed PAPER 64 Dining Cryptographers The dining cryptographers paper introduces an interesting way of transmitting messages in which the identity of the source of the transmitter is unknown from a group of participants to this protocol. At each round in the algorithm, a participant shares a bit in a key with another participant, and each participant announces the XOR of the two bits, inverting it if a transmission is desired. Because each bit in every key contributes twice to the XOR, the parity of all uninverted bits is 0. Given a transmission, the parity will be changed to 1, however, the originator of the flipped bit is unknown. Unless some kind of hierarchy is used, it seems that the DC net needs to be formed from a nearly full connected graph in order to prevent colluders from partitioning the graph and divining the identity of the sender of the message. This scales as O(n^2), which is not good for large numbers. Also, there has to be communication among all participants to all of the nodes they are connected to, which also incurs a great deal of bandwidth. A DC Net connected component essentially forms a single broadcast channel which all participating nodes share. Crowds The Crowds paper describes a system in which multiple participants can blend together and generate network traffic that is indistingusishable from one another, that is, the originator of a message is unknown from within the participants of the Crowd. Message in the crowds are probabilitically forwards between to other participants in the crowd and the outside network. Thus, any the origin of any request cannot be positively discerned. Static paths are use because the context of multiple random paths could be correlated to an originating node. Efficiency wise, it seems that the join algorithm used by Crowds is highly inefficient. Upon every join, all current paths used in communication are wiped out and reformed. Also, Crowds does not give anonymity to the originator when there is a passive attacker listening to many of the nodes participating, unless bandwidth is constantly being used to deliver false message between hosts. It seems unlikely that a crowd would be deployed in across corporate domains because of the lack of protection from denial of service attacks. Crowds scales well because the length of the path taken to anonimize the originator is independent of number of nodes, except to maintain the level of probability of where the originator was. P5 In P5, anonymity is obtained by using a scalable broadcast algorithm. All participants in P5 attach themselves to a position in the broadcast network. Communication is broadcast from a node down to its descendents. (The parent/child relation is determined by how much of a address's prefix is matched. The root is */0, which matches all addresses in the tree.) Because a node can be reached by a broadcast from a higher node, the only knowledge that an attacker has of the node is particular subtree the node had reponsded. One problem with P5 is the fact that once a node has demoted its anonymous status, it cannot recover it. The use of constant "noise" packets consumes large amounts of bandwidth, which could limit the scalability of the system. Also, the presence of asymetrical connections (different connection have difference delays and bandwidth) can limit the usefulness of having random noise messages in the system. From kwalsh@CS.Cornell.EDU Thu Nov 14 11:03:06 2002 Received: from kwalsh4158.cs.cornell.edu (dhcp99-7.cs.cornell.edu [128.84.99.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEG35906081 for ; Thu, 14 Nov 2002 11:03:05 -0500 (EST) Message-Id: <5.1.1.6.0.20021114110245.00a9b240@popsrv.cs.cornell.edu> X-Sender: kwalsh@popsrv.cs.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Thu, 14 Nov 2002 11:03:07 -0500 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Crowds: Anonymity for Web Transactions. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. P5: A Protocol for Scalable Anonymous Communication. The three systems presented here provide varying levels of anonymity. All aim to provide some level of receiver and sender anonymity, as well as unlinkability of senders and receivers. The systems vary in the attackers they can protect against. Crowds can not protect against a global eavesdropper, nor can it protect a sender from a local eavesdropper. Collaborating participants are tolerated depending on the what fraction of the total number of nodes are collaborating. DC-nets, from the dining cryptographer paper, provide stronger anonymity for senders, and can withstand a varying number of collaborating participants depending on the key-sharing graph. P5 attempts to provide strong anonymity against global passive or local eavesdroppers. None of the systems seems particularly scalable, in that they all require increasing global coordination with increasing anonymity requirements. Crowds has difficulty when a node wishes to join the network, and relies on a centralized group membership protocol with infrequent changes. Each node must maintain global group membership information in the form of shared-keys. DC-nets would be similar with a complete graph, but allows the possibility of gaining some scalability with a less-strong graph structure, such as a k-connected graph, or a simple ring or lattice. Still, DC-nets requires a constant stream of data, somewhat like a global broadcast medium. P5 is similar, but perhaps more scalable due to its use of hierarchies. P5 also seems to require some form of global key distribution, though. Crowds seems particular prone to tamper resistance, mostly due to the problem domain. Since it aims to provide anonymous web transactions, it has to deal with all of the vagaries of HTML, SSL, Javascript, ActiveX, etc. These all present loopholes which seem fragile in the face of tampering by malicious participants, servers, or attackers. In terms of efficiency, again none seem particularly efficient as compared with the status quo (but perhaps this is an unfair comparison, since currently very little to no anonymity is provided). Crowds has the problem of multiplying the bandwidth requirements of each node by the average number of hops in the system, and worse-than-linear increases in latency with increasing path length. DC-nets and P5, as stated earlier, require constant bit streams, although P5 has the advantage of hierarchical dissemination rather than global broadcast. DC-nets introduces some delay as well, as all participating nodes must coordinate before a message can be received. From jsy6@postoffice2.mail.cornell.edu Thu Nov 14 11:08:20 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEG8K907610 for ; Thu, 14 Nov 2002 11:08:20 -0500 (EST) Received: from Janet.cornell.edu (syr-24-58-33-193.twcny.rr.com [24.58.33.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA14856 for ; Thu, 14 Nov 2002 11:08:13 -0500 (EST) Message-Id: <5.1.0.14.2.20021114110340.00b4c690@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 14 Nov 2002 11:07:16 -0500 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 64 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id gAEG8K907610 The main goal of Crowds is to achieve anonymity based on the idea of “blending in a crowd”. A user first joins a crowd of users and is represented as a jondo. Any request coming from the browser is sent directly to the jondo. Messages are forwarded along a random path within the crowd before being sent to the server. This random path is static and not dynamic in order to ensure that an attacker does not have multiple paths to link to the same jondo and thus compromise user anonymity against collaborating jondos. The paths are rerouted ony when a failure occurs (the path remains the same up until the failed jondo) or new jondos join the crowd. No sender anonymity, but intended receiver anonymity against a local eavesdropper is provided. Collaborating members anonymity is achieved assuming that there is an upper bound on the number of corrupt members based on the size of the crowd. Also, Crowds offer no anonymity for pages that contain executable scripts. Based on analytic arguments, it is shown that Crowds scales well. The total number of appearances each jondo makes on all paths at any point of time is close to constant. In performance, one would think Crowds was not very scalable since monitoring the crowd depends on broadcasted messages. The average hop-count of Crowds is dependent on the value of p, the probability a message if forwarded to another member, and not on the size of a crowd (thus there exists a tradeoff between the degree of anonymity and efficiency). As the crowd-size increases, the availability of the bandwidth decreases. Thus Crowds overall is not very scalable. The solution to the dining cryptographers problem (DCP) provides unconditional sender and recipient untraceability. Each user has a secret bit in common with every other participant. During each round, each participant outputs the sum mod 2 of all the key bits he shares. If the user wishes to transmit, he inverts his output. If no one transmits, then the sum of all the outputs is zero. A transmit with no collision results in the sum of all the outputs as one. An observer only knows the overall parity of the inversions and is naïve in distinguishing who requested the transmit. This system is not very scalable, the number of keys needed in such a system is O(n^2). Some optimizations might be to have an hierarchical arrangement of key sharing instead of each user sharing a private bit with every other participant. DCP is also costly since only one participant can send at a time and additional bandwidth is needed to handle collisions and contentions. Peer-to-Peer Personal Privacy Protocol (P5) is a protocol for anonymous communication on the Internet. P5 allows participants to trade-off degree of sender, receiver and sender-receiver anonymity for communication efficiency. The underlying system is a broadcast system which in its nature is not very efficient. P5 offers a range of how efficient communication within a broadcast system is by creating a hierarchy of broadcast channels. A user can achieve only two of the three following properties in P5: communication latency, bandwidth usage, and anonymity, Unicast communication achieves low latency, high bandwidth usage, but no anonymity. Multicast communication offers low latency and a tradeoff between bandwidth and anonymity. P5 allows the user to decide what property to trade-off. From smw17@cornell.edu Thu Nov 14 11:19:38 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGJc910411 for ; Thu, 14 Nov 2002 11:19:38 -0500 (EST) Received: from cornell.edu ([128.84.84.84]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA10892 for ; Thu, 14 Nov 2002 11:19:38 -0500 (EST) Message-ID: <3DD3CCF4.8010106@cornell.edu> Date: Thu, 14 Nov 2002 11:19:00 -0500 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.1) Gecko/20020823 Netscape/7.0 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 64 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Crowds Crowds is a protocol for providing anonimity over conventional Internet communications protocols through the introduction of an anonimity proxy server called a jondo. The core concept here is to forward the request through some chain of other participating nodes that forward the request to other such nodes with high probability (>0.5). The last node of this link connects directly to the end server, and the transmissions are transmitted in encrypted form between jondos. Crowds provides a degree of anonimity. Assuming that we have a transmission chain established, a local eavesdropper can determine the sender of a packet (packet transmitted without a correlated incoming packet), but not the contents of the packet itself. The reciever is capable of determining only that the message originated somewhere within the crowd, and that the final sending node is somewhat more likely than the rest of the crowd to have been the originator. Nodes eavesdropping the reciever's link should be able to identify the reciever, as the standard Internet protocols are used over the final hop. Collusions of multiple jondos can work together to provide a better estimate of a node's likeliness of originating a message by providing multiple opportunities to insert themselves into a chain. Colluding nodes in a chain can deduce that the sending node before them is more likely than an average node in the crowd to have originated the message, but cannot totally expose a node unless it is also local to that node - an output without a correlated input sent to your jondo strongly exposes the sender. Crowds is reasonably scalable, as the expected path length is a function of the forwarding probability rather than the size of the crowd, so that the deterioration of performance should be insensitive to path size. Tamper resistance is a different story, as the final jondo is responsible for the actual connection to the server and forwarding the data back. Thus, a malicious jondo could easily 'decide' not to forward to another and return almost any data they see fit to the originator. P^5 P^5 attempts to provide strong anonimity in the presence of strong passive attacks, as well as including a mechanism by which users may trade off between anonimity offered and performance achieved. The base configuration for P^5 is a tree representing a series of broadcast groups, with each sub-tree of the root graph comprising a more specific broadcast group. Nodes achieve anonimity by becoming members of a subgroup within the graph. Once the node is a member of a given subgroup, a message can be sent to them either to their true subgroup, or to any higher-level ancestor group on the tree. This configuration gives nodes a choice of anonimity. At the highest level, all transmissions can traverse the root tree, thus establishing nothing about the location of the destination node, but also incurring a high bandwith penalty. Alternately, nodes may advertise a more specific mask identifying a smaller subgraph. This provides a more bandwidth efficient communication (fewer collisions), but also localizes the node to a smaller set of nodes, thus reducing the level of anonimity. Reciever anonimity is achieved by having a fixed rate of data communications between nodes irrespective of actual data transmission. Assuming that random data is indistinguishable from encrypted data, even an omniscient passive observer gains no information from a transmission, as the end result is the same for either data or random noise. In the worst case of a compromised channel router, the sender may be exposed to within the broadcast group that the router serves. Thus, the sender may choose to make use of the channel router for more efficient communications, but risks a greater worst case exposure that narrows the field to the broadcast group served by the channel router. This system provides good anonimity, permitting a tradeoff with efficiency. The heirarchal structure should provide a reasonable degree of scalability provided that users are reasonable in their requests and are cabable of accepting lower anonimity in exchange for better performance. Since communications are node to node via a partial broadcast, a standard public-key encryption mechanism should provide good tamper resistance in the system. Dining Cryptographers The Dining Cryptographers solution provides anonimity by encoding the revealed data in such a way that it is observable as the parity sum of an entire group of communicating nodes. In a completely connected system, this provides resilience against anything short of a full collusion of all non-transmitting nodes, although obviously each colluding node reduces the possible sender set. In systems where nodes may bisect the graph, well-chosen colluding nodes are capable of localizing a sender to the portion of the network that the sending was observed on, essentially reducing the potential senders to the set of senders in that network partition. This solution suffers in the area of efficiency, as only one sender should attempt to send at any one time, reducing the effective bandwidth as more nodes become available. It folloes that it is not particularly scaleable; a heirarchy may me imposed to improve performance, but there is still a limit on the bandwidth imposed by the desire to avoid colliding transmissions. It is also subject to disruptive nodes, as even though it is possible over time to detect, identify, and remove disruptive nodes from the system, such nodes can still cause significant problems before they are removed, and the limited network bandwidth combined with no limitations on transmission rates leave this mechanism vulnerable to denial of service attacks. From nbs24@cornell.edu Thu Nov 14 11:41:48 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGfl917437 for ; Thu, 14 Nov 2002 11:41:48 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA03916; Thu, 14 Nov 2002 11:41:44 -0500 (EST) Date: Thu, 14 Nov 2002 11:41:44 -0500 (EST) From: nbs24@cornell.edu Message-Id: <200211141641.LAA03916@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 64.185.145.94 Subject: 615 PAPER 64 Crowds: Anonymity for Web Transactions Crowds provides privacy for web transactions using an approach that hides one’s actions within the actions of many others, by submitting requests from a user to a web server through random members, with each member maintaining its own list of crowd membership. The receiver cannot resolve the sender of a message since messages take potentially randomly chosen routes through the network. To the aspects of anonymous communication, the paper introduces the ‘degree of anonymity’ which ranges from ‘absolute privacy’ to ‘provably exposed’. It seeks to protect a user against attacks from a local eavesdropper, collaborating crowd members or the end server, unless the user provides identity details like a name. To a local eavesdropper, the sender’s anonymity is exposed but the receiver’s anonymity approaches beyond suspicion with increasing size of the crowd. To collaborating members, a sender’s anonymity is guaranteed probable innocence but the receiver’s anonymity approaches absolute privacy with increasing crowd size. To the end server, the sender’s anonymity is guaranteed beyond suspicion. Crowds does not protect against DoS attacks and it doesn’t ensure that crowd members will not maliciously modify the request to be forwarded. Even though a user may initiate a path outside its firewall, members outside the firewall are offered less anonymity exposing the initiator. The authors do not provide any measurements about how scalable Crowds is. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability To provide sender-receiver anonymity, a public key infrastructure is assumed and 2 participant nodes share secret key bits and report to the world whether their keys are the same or different, making traceability hard. A sender always digitally signs its messages to provide authentication. The downside is that the communication overhead to maintain anonymity is huge and only one ‘conversation’ can be sustained at any one time. This also makes handling contention and collisions more bandwidth-intensive. It also does not prevent malicious disruption of the system. Collusion also becomes nontrivial in a non- complete graph if it leads to the partitioning of the graph because information about the origin of the messages outside the collusion can be inferred. There is no mention of scalability by the author but things could get really complicated in a large complete graph. P5: A protocol for Scalable Anonymous Communication P5 seeks to provide sender, receiver and sender- receiver anonymity. It is based on public-key cryptography but does not require a global public-key infrastructure, and uses a logical broadcast hierarchy. A secure public hash function is used to map users to a node of L (consisting of a bitsring and a specified length). It provides a trade-off between communication latency, bandwidth usage and anonymity. A user is allowed to lower its level of anonymity but not vice versa. Why would I want that anyway? The authors show how P5 can thwart correlation, intersection, difference, DoS and mob attacks but their protocol is still susceptible to adversaries who can generate multiple addresses and by which can actively manipulate large portions of the network. The protocol provides decent scalability as communication is among small pockets of users. Nana From vrg3@cornell.edu Thu Nov 14 11:41:59 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGfw917475 for ; Thu, 14 Nov 2002 11:41:58 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA04106 for ; Thu, 14 Nov 2002 11:41:56 -0500 (EST) Date: Thu, 14 Nov 2002 11:41:56 -0500 (EST) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 64 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The Crowds paper presents a system for providing anonymity for web transactions. Crowds provides anonymity for clients by having each client send its request to other clients probabilistically, and forward requests it receives either to other clients or to the server. This way, the actual node which sends a request to a server does not correspond directly to the node which issued the request. Crowds does involve a centralized server, called the blender, which controls admission into the network and could be a scalability and efficiency bottleneck. The lengths of paths go up with the size of the network, but sub-linearly, and increases in path length do improve anonymity. Since each client depends on other clients' proxies, Crowds is subject to tampering. A malicious node could corrupt or drop packets. The Dining Cryptographers paper presents a generalization of the problem of allowing for messages to be publicly broadcast without revealing the source. This is accomplished by having all members of the network participate in forming the message; each node shares a secret key bit with other nodes, and publicly announces the modulo two sum of all the key bits it sees, inverting it if it wishes to transmit. After each node has transmitted, the the sum of the outputs is even if there was no transmission, and odd if there was. This provides strong anonymity but can scale very badly, because of the overlaid network of key-bit sharing. If this network is kept relatively sparse, efficiency will rise but the risk of collusion and tampering increases. If it is kept relatively dense, it scales quadratically with the number of nodes. Efficiency is relatively low since a single message requires all nodes to participate. The P5 paper presents a system to provide anonymity for both senders and receivers. Both of the above papers provided anonymity at the cost of efficiency; P5 allows nodes to choose how much they are willing to trade off. Nodes can switch to more efficient routes by giving up some anonymity, but cannot switch back. P5 networks function much like DC-net networks, and so share the inefficiency incurred by DC-nets because of the fact that all nodes have to transmit when any node needs to. From ag75@cornell.edu Thu Nov 14 11:55:29 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGtT922039 for ; Thu, 14 Nov 2002 11:55:29 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA14179 for ; Thu, 14 Nov 2002 11:55:26 -0500 (EST) Date: Thu, 14 Nov 2002 11:55:26 -0500 (EST) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 64 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This week we are presented with three models for protecting user privacy. Crowds protects user's privacy while retrieving information from the internet. The system works by grouping web users into geographically diverse collection, called a crowd, which retrieves information on its users' behalf by way of a simple randomized routing protocol. Crowds gives varying degrees of anonimity to senders and receivers based on the kinds of attackers that exist. No sender anonimity is guaranteed when a local eavesdropper is present, while receiver anonimity increases as a function of crowd size. There is sender anonimity against attack by the end server. And there is a performance tradeoff that users can make depending on their needs between length of path and ability to tolerate collaborators. In general the authors claim that Crowds is efficient. They also claim that it should scale well, but there is only an analytical argument, there are no performance measurements. Finally, crowds does not defend against DoS attacks such as user not passing information sent to them or passing wrong information. Dc-net uses unconditional secrecy channels to construct an unconditional sender-untraceability channel. Dc-net offers sender anonimity unless there are 2 colluders around you or there are too many colluders in the network. It scales linearly with the number of people in the network, so it probably would not be suitable to very large networks. Dc-net protects against DoS attacks by excluding people who disrupt the network using trap messages, so it offers some degree of protection against DoS attacks. The model presented in the paper was not implemented or tested. Thus, it's hard to say anything else about its performance. P5 is meant to provide scalable anonymous communication over the Internet. P5 provides sender, receiver and sender-receiver anonimity and allows users to trade-off anonimity for communication efficiency. P5 works by creating a hierarchy of broadcast channels to which participants send fixed length packets, encrypted so that only the receiver can decrypt them, at a fixed rate. Since this is a broadcast protocol, it is not very efficient in its use of bandwidth. However, it is scalable to a very large number of users and it protects against a number of attacks, including DoS attacks. From adam@graphics.cornell.edu Thu Nov 14 11:56:03 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGu3922124 for ; Thu, 14 Nov 2002 11:56:03 -0500 (EST) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id gAEGtv0k088156 for ; Thu, 14 Nov 2002 11:55:58 -0500 (EST) Date: Thu, 14 Nov 2002 11:55:24 -0500 (EST) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 Paper 64 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Crowds: Take the idea that you can pass a message around in a crowd and then submit it. It will be hard (or impossible hopefully) to probabilistically determine if the request came from the user submitting it. The goal of this is to have sender anonymity and unlikability of sender and receiver. Doing this however is harder problem then it seems. Crowds address the problems of local eavesdroppers (although doesnt' address the situation when the local user gets back its own message that it sent out (then the local eavesdropper could determine which requests were his and which weren't)), collaborating crowd members and end server. It doesn't however address tamper-resistence and DOS. DOS is easy for collaborating crowd members, they can always forward to each other for logging or packet dropping purposes and further can share information w/ each other about which packets it receives and going where. There is a potential for partial DOS in a crowd w/ collaborating users. Crowds adds linear overhead to RTT (each jondo which touches it adds a certain time), so long paths will be slow and therefore not necessarily advantageous in the scheme of fast communication. W/out long paths (knowing that path length is only 5) would make it easier to determine the sender. Further a possible DDOS could be established by collaborators, rapidly joining and unjoining the crowd (possibly faking other IP's or something like that) to halt path establishment. This protocol doesn't scale well... it should be for "small crowds". Further blender takeover is just as bad as proxy server takeover. Dining Cryptographers: There is high overhead (not efficient) w/ the constant XOR metric, but it accomplishes the goal of having local anonymity (defeats a local eavesdropper). The problem that all DC's need to be in constant transmission is a problem when you think about connectivity, wireless devices or any scheme in which the network might change state (link status, node status or traffic). So despite DC being a good way to support anonymity it has other drawbacks. I am not sure that this system will scale very well, especially in very large, highly-connected networks. DC has some weird properties WRT to collusion, it seems that even in the face of tampering or collusion the colluders themselves can remain anonymous, which could provide for many collusion groups including the same people. P5: It seems terribly inefficient since it requires traffic hiding, but does scale (or at least can scale). This broadcasting far outweighs (or at least is my belief that it does) the benefits of the trade-offs w/ sender, receiver and sender-receiver anonymity degree. P5 lacks the "wiping clean" that Crowds has so once a user identifies itself w/ less anonymity, more anonymity can never be regained. From hs247@cornell.edu Thu Nov 14 11:56:10 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGuA922141 for ; Thu, 14 Nov 2002 11:56:10 -0500 (EST) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id gAEGu9k19052 for ; Thu, 14 Nov 2002 11:56:09 -0500 (EST) Message-Id: <5.1.0.14.2.20021114115554.00b22530@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 14 Nov 2002 11:56:13 -0500 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Crowd is designed for anonymous web transactions. Crowd is a group of nodes, and any node in this group who wants to initiates a web request forwards the request to another node in the "Crowd". The receiving node then decides to either forward the request to the actual server, or forward the request to another node in the crowd. By the time the request reaches the web-server, the web-server will have no idea who the initiator of the request was. P5 (peer-to-peer personal privacy protocol) is based on broadcast communication of encrypted messages. All nodes in a group know the public keys of all other nodes in the group. If he wants to communicate a message to a specific node X, he encrypts the message with X's public key. Next he broadcasts this message to all nodes in the group. This retains anonymity because the sender has no idea which node is X. It only know the message is getting to the receiver because of the public key binding and trusts that only X can decrypt the message. On the other hand, X has no idea who the message is from because of the broadcast nature, anyone of the nodes could have sent the message. This broadcast nature is obviously inefficient and unscalable. P5 uses the idea of broadcast group hierarchies. Each level in the hierarchy provides more anonymity, but the broadcast becomes larger. A node can choose how much anonymity it uses with each message. Dining Crytographers, but the basic idea is that nodes are again in a group. This protocol allows groups to announce messages however, subgroups can not figure out who actually sent the message. This node who wants to send a message basically inverts a shared key with a neighbouring node if he wants to send a message. Because all nodes must participate in order to preserve anonymity, only one node can transmit at a time. Dining philosopher preserver sender and receiver anonymity as the channel are secure and therefore no one can figure out who the message was sent to. Crowd provides sender anonymity, but not receiver anonymity as each message is directed t a webserver. P5 seems to be the most power providing sender & receiver anonymity as well as sender-receiver anonymity. As far as scalability, the broadcast nature of Dining Cryptographers doesn't seem to be that scalable. Similarly, P5 would have scalability issues but their claim is that their hierarchy architecture allows the system to scale (but at the cost of anonymity). Crowd is probably most scalable as it doesn't require broadcasts. However all 3 schemes have the problem of key distribution and gaining knowledge of all public keys in the system. In the same way the broadcast nature of DC, and P5 make it less efficient. It trades broadcasts for anonymity. Crowd gains anonymity by trading path length. For tampering, Crowds potentially could have malicious nodes improperly routing routes, however this can be somewhat avoided since paths are generated at random. With DC, and P5 can be susceptible to collusion. From mtp22@cornell.edu Thu Nov 14 11:58:47 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEGwl923070 for ; Thu, 14 Nov 2002 11:58:47 -0500 (EST) Received: from mtp22.cornell.edu (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA20835 for ; Thu, 14 Nov 2002 11:58:46 -0500 (EST) Message-Id: <4.3.2.7.2.20021114115812.0362e530@postoffice2.mail.cornell.edu> X-Sender: mtp22@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 4.3.2 Date: Thu, 14 Nov 2002 11:58:59 -0500 To: egs@CS.Cornell.EDU From: Matt Piotrowski Subject: 615 Paper 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The three protocols Dining Cryptographers (DC), Crowd, and P5 achieve different levels of anonymity, as is noted in the P5 paper. DC achieves sender anonymity and receiver anonymity but not sender-receiver anonymity; this is a result of DC's failure to mask when a message is sent. P5 provides all three types of anonymity, achieving sender-receiver anonymity by requiring nodes to produce noise. Crowd only provides sender anonymity (and even this is not safe against statistical analyses). DC has trouble scaling because only one transmission at a time is allowed. Also, once the anonymity vs. bandwidth tradeoff is set, it cannot be adjusted. P5, on the other hand, was designed to be scalable. It allows simultaneous transmissions, dynamic adjustment of anonymity vs. bandwidth, and is organized in a hierarchical tree structure. In this tree structure, efficiency is possible through the use of masks, which are the cornerstone of the anonymity vs. bandwidth tradeoff. P5's use of noise greatly decreases its efficiency. In order to produce noise, nodes must constantly generate packets, even when they have nothing to send. This consumes extra bandwidth and node processing power. Crowd can be inefficient because it uses round-about paths to deliver packets to their destination. This round-aboutness results in packets consuming the processing power of more nodes and the bandwidth of more links. From ashieh@CS.Cornell.EDU Thu Nov 14 12:15:48 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEHFm926966 for ; Thu, 14 Nov 2002 12:15:48 -0500 (EST) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id gAEHFlM09573 for ; Thu, 14 Nov 2002 12:15:47 -0500 (EST) Date: Thu, 14 Nov 2002 12:15:47 -0500 (EST) From: Alan Shieh To: Subject: 615 PAPER 64 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ** Anonymity - Crowds Assumes that attackers can only subvert nodes and not the global network. An eavesdropper on a particular node can perform traffic analysis to defeat sender anonymity, but cannot determine the receiver due to the encryption of requests along a path. Given bounds on the number of nodes and subverted nodes, multiple subverted nodes in the network can only determine that their immediate successor along any path is probably innocent; all other possible initiators are less likely to have sent the message. However, any subverted node along a path can obviously determine the intended receiver. Either of global traffic analysis or subversion of the centralized crowd controller allows anonymity to break down completely. - DC-net In even the strong attack model of global traffic analysis, provides sender anonymity beyond suspicion. Node subversion reduces the number of possible senders. Depending on the transmission model, there are varying levels of receiver anonymity. If broadcast, then provides receiver anonymity beyond suspicion. If unicast, then no receiver anonymity. - P5 Provides absolute privacy to the sender against global traffic analysis. Sender anonymity is the size of its broadcast group, assuming subverted nodes can decrypt all routing traffic in this group. Receiver anonymity depends on the size of the group to which a particular packet is destined. ** Scalability - Crowds Keys only need to be exchanged between members along a particular path. Path length is constant, hence linear scaling. - DC-net Depends on the topology of the DC-net. A clique topology would require O(n^2) keys and messages to be exchanged. A ring topology would require O(n) keys and messages. - P5 Keys must be exchanged between a node and all nodes within broadcast groups for which it is a member. This O(N^2), since each node can broadcast to all other nodes. To re-escalate anonymity, a node must select a new private key and insert itself into a new location in the network, and then broadcast this key to all other nodes. ** Tamper-resistence - Crowds Intermediate nodes restricted to DOS if MAC is appended to each message. Admission control on new nodes prevent malicious nodes from inducing path changes within the system. - DC-net If malicious nodes succeed in partitioning the graph, then they may reduce anonymity by determining which of the disconnected components a message is being sent from. Malicious nodes may also interfere with the reservation scheduling system, but this is merely a DOS attack, and such behavior is detectable. - P5 Malicious nodes can cause DOS attacks by masquerading as routers or inducing packetloss in the system. If all routers into and out of a channel/group are subverted, then traffic analysis can determine that a particular packet originated from within that group. Out of band mechanisms can potentially trick a client into dropping its anonymity level. ** Efficiency - Crowds Constant bandwidth overhead (pathlength). - DC-net Bandwidth overhead depends on the topology of the DC-net. - P5 Depends on the desired level of anonymity. Bandwidth in the underlying network is consumed at a constant rate due to use of constant traffic pattern to defeat traffic analysis. Hence, a higher desired peak datarate requires a higher constant datarate. Bandwidth consumption is also a function of the negotiated broadcast depth between the two nodes; the lower the depth, the larger the broadcast groups that need to be crossed. Hence, each actual message consumes broadcast overhead (which translates to queuing pressure and constraints on *useful*, but not absolute, bandwidth consumption), which is multiplied by a constant factor: the expected small number of routing hops between broadcast groups. The general architecture results in extremely high loss rates. ** Summary of system design - Crowds Crowds is a distributed HTTP anonymizing proxy. Each node selects a random static overlay routing path upon joining a crowd; dynamic paths strictly weaken Crowds. HTTP requests are sent along this routing path and encrypted at each hop. Upon reaching the end of the path, the request is sent to the server, and the requested object forwarded back along the reverse path. Care must be taken to decouple discrete actions that may yield timing attacks; possible sources include correlated sequences of object fetches, and correlated user activity. To prevent the former, the expected sequence of requests is aggregated, and the objects required to render the first requested object are returned en masse. Hence, only one request is necessary to recursively yield all necessary objects related to a page. - DC-net In DC-net, each object listens to the transmissions from other objects in a network, and then emits the XOR of these bits to send a 0 (or no message), and the inverse of the XOR to send a 1. Hence, data is transmitted via even and odd parity of all XORs broadcast by the nodes within a net. An anonymous reservation-based scheme is used to reduce the probability of multiple simultaneous transmissions, and normal collision detection encoding is used to catch the remaining transmission errors. - P5 P5 is a hierarchical broadcast-based scheme that allows nodes to tradeoff communications overhead for anonymity. Nodes broadcast packets at regular intervals; if no useful data is available at a particular time, then noise is sent. Each group is marked with a bit pattern and a tree depth. A transmission is directed at a particular group; such a transmission is broadcast to every group that shares a minimum common prefix (determined by tree depth) with the destination group. The position of a node in a tree is determined by hashing the public key of the node. To facilitate routing between smaller, deeper levels and avoid broadcasting to larger levels to reach more distant nodes, nodes may also generate a set of routing keys, which are hashed to determine alternate routing groups for a particular node. This topology is advertised in each group. From ks238@cornell.edu Thu Nov 14 12:29:11 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEHTA900862 for ; Thu, 14 Nov 2002 12:29:10 -0500 (EST) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA28332 for ; Thu, 14 Nov 2002 12:29:06 -0500 (EST) Message-Id: <5.1.0.14.2.20021114122836.025ca600@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 14 Nov 2002 12:29:04 -0500 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The fist paper introduces a new system called "Crowd" which is an implementation that enforces anonymous communication between nodes. Put very simply the design of the system is to create crowds, or clusters in the system, whereby when a node communicates from the crowd, the network perceives a message from the general crowd rather from a specific node. In other words, should a node (i.e. denoted a jondo in the paper) send a message to another node, it will be unclear if that nodes is forwarding the message on behalf of another node or is the originating point of the message. This type of implementation is useful when preventing against eavesdroppers who may potentially decipher the contents of the message. The paper focuses on implementing three types of anonymity: sender, receiver and unlinkability of sender and receiver. Crowd does not address attacks by local eavesdroppers which is a downfall. Another one of the weaknesses which is identified in the paper is not preventing against denial of service attacks. The Dining Cryptographer's problem paper proposes the use of dc nets which when implemented ensures sender untraceability in a given network. The key contribution of this paper is the use of these dc nets in which pairing nodes share a common key and each node decides on an inversion of the result which then facilitates the sending of a message. The paper discusses the level of anonymity that can be achieved by a certain node, which is contingent in part on the number of nodes that are colluding against a sending node in the network. Unfortunately, due to the level of keys needed to implement such dc nets (i.e. m(m-1)/2 keys) this brings up major issues in regards to excessive resource exhaustion which is needed to maintain the system (i.e. bandwidth, memory). This can clearly be the noted as the primary weakness of this implementation. The final paper presents P5, a secure and scalable protocol which ensures sender and receiver anonymity as well as sender-receiver anonymity. The paper primarily focuses on passive attacks rather than active attacks such as eavesdropping within the network. P5 is based on a public key cryptography system by which N nodes may form a logical broadcast hierarchy based on these public keys. The goal of the implementation is that packet origination can not be identified from the broadcast messages. The paper continues to discuss a host of different attacks that P5 can adequately protect against. For instance, correlation attacks (locating packet origination), intersection attacks (using the intersection of two sets to determine origination), difference attack (in one set and not in another set), denial of service attacks and mob attacks. From sc329@cornell.edu Thu Nov 14 12:42:10 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEHgA903981 for ; Thu, 14 Nov 2002 12:42:10 -0500 (EST) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA22522 for ; Thu, 14 Nov 2002 12:42:02 -0500 (EST) Message-Id: <5.1.0.14.2.20021114123814.02ab35c8@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 14 Nov 2002 12:42:06 -0500 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Crowds is a system for protecting users' anonymity on the world wide web. The basic idea of their approach is to hide one's action behind the actions of many others. The user's request is first passed to a crowd. That member can either submit the request to the end server or choose another random member and forward to it. So when the request is finally submitted, the initiator is indistinguishable from a member that simply forwards a request from another. This paper mainly looks at three types of anonymity - sender anonymity, receiver anonymity and sender-reciever unlinkability. The paper also descirbes the six degrees of anonymity. Three distinct types of attackres are described here - a local eavesdroper, collaborating crowd and the end server.Crowd guarantees probable innocence sender anonymity against collaborating members and beyond suspision sender anonimity against end server.The probability of beyond suspision receiver anonymity against local eavesdroper and absolute privacy against collaborating members approaches 1 as the number of the members in the crowd approaches infinity. But these inference do not hold true if a local eavesdroper collaborates with the end server in an attack. Crowd does into make an attempt to defend against denial-of-service atacks. The crowd approach is shown to have better performance than the use of just a proxy or by using mixers. The member in the crowd is called a 'jondo' and the server which admits a node into the crowd is the 'blender'. The message forwarded on a path except for the final request is encrypted. It has been shown that by making the probability of forwarding high, the fraction of collaborators that can be tolerated approaches half the crowd. Timing attacks by collaborators are prevented by not propagating the request for embedded urls by the user's browser and instead being fed into it by a first jondo in the reply path. They give an analysis of the scalability of the system. They claim that each jondo's expected number of appearances on the paths is virtually constant as a function of the size of the crowd, which suggests that crowds should be able to grow quite large. The membership to crowd is granted based on some policies to avoid malicious nodes from joining. Dining cryptographers protocol provides sender anonymity under an adversary model. DC-net assumes a public key infrastructure and users send encrypted broadcasts to the entire group, thus achieving receiving anonymity. But since all the members are made aware of when a message is sent, DC do not provide much sender-receiver anonymity. Also in DC, only one user can send at a time, so it takes additional bandwidth, which makes the systems not that scalable. P5 is another anonymous communication protocol over the internet. A novel feature is that it allows participants to trade-off degree of anonymity for communication efficiency. P5 uses a broadcast heirarchy, with level providing different levels of anonymity. Users of the systems localy select a level of anonymity and communication channel depending on their tradeoffs. Each group corresponds to a broadcast channel and the communication efficiency increases as the group's mask size increases. However an increase in efficiency comes at an expense of reduced anonymity. A nice property of the system is that the anonymity of any node is dependant only upon the length of the mask that A is willing to respond to. The design given shows that P5 is scalable and compatible with current internet protocols. But the constant noise generated by the sysem should be reduced if good scalability is to be achieved. From pj39@CS.Cornell.EDU Thu Nov 14 13:04:21 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEI4L909830 for ; Thu, 14 Nov 2002 13:04:21 -0500 (EST) Received: from pj39.cornell.edu (syr-24-59-67-50.twcny.rr.com [24.59.67.50]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA21833 for ; Thu, 14 Nov 2002 13:04:19 -0500 (EST) Message-Id: <5.1.0.14.2.20021114130054.02275738@postoffice2.mail.cornell.edu> X-Sender: pj39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 14 Nov 2002 13:04:22 -0500 To: egs@CS.Cornell.EDU From: Piyoosh Jalan Subject: 615 PAPER 64 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Crowds: Anonymity for Web Transactions. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. P5: A Protocol for Scalable Anonymous Crowds is an approach to provide anonymity for users in web transactions and is based on the idea of "blending into the crowd". A user first joins a "crowd" of other users. The initiator of the web request passes the request to a random member of the crowd, this random member either sends the request to the webserver or again passes it to a random user and so on until the request is passed on to the webserver. The user who gets a request from the initiator has no way of telling if that user is forwarding a request of initiating it, hence it maintains sender anonymity. Thus in crowds a local eavesdropper residing on a local computer can only eavesdrop messages sent or received by the user's computer. In case the eavesdropper is at the end server the senders identity is beyond suspicion as the sender is no more likely to be the originator of the message than any other potential sender in the system. Crowds provides anonymity for either the sender or the receiver and does not provide anonymity for the linkage between sender and receiver. If the eavesdroppers at a local system and at the end server collaborate than crowds provide neither sender nor receiver anonymity. Crowds also provide sender anonymity against collaborating crowd members. Crowds is not tamper-resistant as it makes no attempt to defend against a rogue crowd member, which can either fail to pass on the message or modify the message. As far as efficiency is concerned Crowds is efficient as for providing anonymity it does not use any cryptography which are costly operations. Crowds can theoretically scale to limitless no of nodes as the load on each user computer is expected to remain roughly constant as new users join the crowd. The dining cryptographers problem paper presents a solution to the senders anonymity problem using unconditional secrecy channel so that the sender could be rendered untraceable. Secrecy of an anonymous message could be maintained if a cryptographer encrypts the message with the intended recipients public key. The identity of the recipient could be maintained secret by leaving it to each recipient to try to decrypt the message. Tamper resistance is achieved by nondisrupters stopping disruption by - agreeing on the key sharing graph - agreeing on each participants output for a round on the basis of outputs of other users in that round and - having some rounds contain inversions in a way that does not compromise the untraceability of any nondisrupter. The approach is not as efficient as in Crowds due it is use of cryptography which consumes lot of processing power and hence energy. The paper does not talk about scalability. The Peer to Peer Personal Privacy Protocol (P5) paper presents broadcast based channel based using public key cryptography which provides sender, receiver and sender-receiver anonymity. In P5 all participants in the anonymous communication channel sends fixed fixed length packet at a fixed rate by encrypting these packets with the recipients public key. Receiver anonymity is provided since the sender does not know the whereabouts or address or name of the receiver, it just knows that it is part of the broadcast group. It provides sender anonymity since all the messages to a given receiver comes from a single upstream node. Moreover the sender could not be linked to a receiver as an eavesdropper always sees a fixed rate of packets of fixed length at a node. The system is inefficient due to its broadcast nature and more over it is not scalable as more and more nodes join the performance of the system would degrade. The paper presents a solution to this by the use of hierarchical broadcast channel. It also provides simulation results for 8192 node P5 network where users can where users can successfully communicate anonymously at the speed of hundreds of kilobits per second. Due to the use of public key cryptography P5 is also tamper resistant and is invulnerable to correlation attack, intersection attack, DOS attack and Mob attack. From vivi@CS.Cornell.EDU Thu Nov 14 14:19:42 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEJJg929883 for ; Thu, 14 Nov 2002 14:19:42 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615paper64 Date: Thu, 14 Nov 2002 14:19:42 -0500 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AFA7@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper64 Thread-Index: AcKMEshFw7YJk/UPTTesJz+ShjLs4w== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id gAEJJg929883 Crowds is a system designed to maintain anonymity during transactions on the web. Here each user runs a process called a jondo that handles all web traffic. The jondo, on receiving a request from a browser, decides to either forward the request to any of the currently running jondos or send the request to the web-server directly. This process repeats at every hop of the path, thereby ensuring that a node cannot be immediately sure if the previous node in the path was indeed the node that originated the request. Crowds does not attempt to hide the correlation between inputs to a node and its outputs. Thus simple traffic analysis starting from the web-server (the endpoint) enables an adversary to trace the path used, thus exposing the source. Similarly the adversary can track the intended recipient of some traffic, even if he/she cannot decrypt the packets themselves. Crowds also is helpless against rogue nodes that either refuse to forward packets or modify the contents of packets. Crowds' policy of making new joiners wait until the next join commit (one day) could mean that nodes will have to wait for inordinately long amounts of time before they can use the system (especially when nodes keep going down and coming up again, and have to keep joining the network afresh). Crowds does appear to be scalable as the number of hops a message takes is independent of the number of nodes in the network, but key management could be a problem. P5 aims to enable anonymous communication over the internet by making use of a hierarchy of broadcast channels, where communication in each channel is anonymous. P5 is built as a tree of groups, each with member nodes. Any message sent to a group is sent to all nodes that belong to the group, all the groups that belong to the sub-tree of the group, and all groups along the path from the group to the root of the tree. During the transmission of any packet, who originated the packet, and who the packet is addressed to is kept confidential. P5 cannot provide both strong anonymity and efficiency at the same time. Another factor that contributes to the inefficiency of P5 is the constant number of fixed-length packets each user has to generate, irrespective of whether the user has anything to transmit or not. Also, while the paper claims P5 is scalable, results contradict this claim. As the size of the network grows, the data sending rate has to be restricted to (1/Size), which clearly indicates that P5 is not scalable. P5 is resistant to data-tampering, since packets are encrypted, and only the user can decrypt them. Replay attacks also are ruled out, since no node in the path knows to whom the packet is addressed. From linga@CS.Cornell.EDU Thu Nov 14 14:56:44 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAEJui910356 for ; Thu, 14 Nov 2002 14:56:44 -0500 (EST) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id gAEJuil20590 for ; Thu, 14 Nov 2002 14:56:44 -0500 (EST) Date: Thu, 14 Nov 2002 14:56:44 -0500 (EST) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 64 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII CROWDS A new scheme for providing sender anonymity, receiver anonymity and sender-receiver anonymity on www has been proposed in this paper. They introduce a new tool named degrees of anonymity for describing and proving anonymity properties. This a simple scheme. The idea is for a user to join a crowd and forward requests (both generated by this user and the ones forwarded to it by other users) to another random user in the crowd with some probability p. With probability (1-p) the user contacts the target web-server. This clearly prevents the end-server or an eavesdropper from knowing the true initiator of the request. The authors propose a new aspect of anonymity called the degree of anonymity. This is a spectrum from absolute privacy (where the attacker cannot perceive communication) to provably exposed (where identity of the sender and receiver is provable revealed). Crowd guarantees anonymity (provable innocence for sender anonymity and absolute privacy for receiver anonymity) from c-collarborating members for the number of members in the crowd (n) is reasonably large compared to c. Denial-of-service attacks by rogue crowd members cannot be handled by crowd. There is a single server called blender that handles join requests to a crowd. Each user has a jondo process which contacts the blender when the user wants to join the crowd. The blender sends the membership information about the crowd to the new user on receiving a request from its jondo. Authors prefer this simple centralized approach to tackling the membership problem (instead of using the standard group membership protocols) because the requirements here are less stringent. Also the blender is responsible for key-generation for the users and also hands in the public-keys of other users in the crowd when a new user joins the crowd. Communication between any two crowd members is encrypted. To prevent the attacker from having access to multiple pathers that link to the same jondo (which decreases anonymity if we have collaborating jondos) authors propose using small number of static paths to each jondo. Evaluation is very minimal. Pros and Cons: A simple protocol for use in www which provides decent user anonymity has been proposed in this paper. This scheme does not provide protection against denial of service attacks. This scheme does not appear to scale well (given that they use a single blender which responsible for all key-generation and membership maintenance). This scheme is also not very efficient in terms of b/w usage as the request is forwarded randomly. DINING CRYPTOGRAPHERS PROBLEM Interesting problem and a simple solution. We have n (>2) crytographers (Cs) having dinner. The bill is to be paid anonymously and is bill is either paid by one of the cryptographers or NSA (bill is paid only once). How do we do this? A simple protocol for n=3 is given and it has been generalized to any n. I will summarize the n=3 protocol here. Each C flips an unbaised coin the outcome of which is know to him and his right neighbor. Then each C spells out loud whether if the outcome of his coin matched that of his left neighbor. If one of the C pays he spells out the opposite of what he sees. Now if there are odd number of difference uttered, then one of the Cs is paying. Otherwise NSA is paying. Using this protocol if a C is paying none of the other Cs know for sure who has paid. For the generalization the model considered is: Each C is assumed to have two kinds of secrets: keys shared with other Cs for each round; inversion used in each round (1 if C inverts in that round and 0 otherwise). Collusion of some of the participants can atmost reveal the parity sum of the inversions of Cs. Disruption can be avoided by non-disruters by meeting the following requirements: key-sharing graph is publicly agreed on; each participant's outputs are publicly agreed upon (they cannot change their output based on the other participant's outputs for that round); some rounds contain inversions that would not compromise that untraceability of any nondisrupter (this could be realized using a slot-reservation technique described in the paper). Pros and Cons: This paper presents a way to construct unconditional sender-untraceability channel using unconditional secrecy channels. They show that this method satisfies a wide range of pratical concers (collusion, disruption etc). They have not presented any evaluation of the protocol presented in this paper. This protocol appears to scale linearly with n (number of participants). P5 P2P Personal Privacy Protocol is a scalable anonymity preserving protocol for communication over the Internet. Interesting feature of P5 is that it allows participants to trade-off degree of anonymity for communication efficiency. P5 provides sender anonymity, receiver anonymity and sender-receiver anonymity. A naive solution involves each node broadcasting fixed length encrypted packets. Each node should maintain a fixed communication rate even though it is not actively communicating at a given point of time. So it generates noise packets when it does not have anything to communicate. P5 is based on this inefficient broadcast solution. It uses a heirarchy of broadcast channels to enable scalability of the system. Different levels of the heirarchy provide different levels of anonymity with associated communication costs. Greater anonymity requires greater communication cost. At any point of time anonymity level can be decreased by choosing a more communication efficient channel. Basic idea is to use to bitstring (b) and number of valid bits (m) to build a logical broadcast hierarchy. P5 is invulnerable to the following attacks: Correlation attack, intersection attack, difference attack, DoS attack and Mob attack. Pros and Cons: Presents a protocol to provide anonymity for communication over the Internet. Simulation not exhaustive. System not very scalable. B/w requirements are very high.