From asr32@cornell.edu Thu Feb 16 09:26:09 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.7 required=5.0 tests=AWL,DATE_IN_PAST_06_12, MAILTO_TO_SPAM_ADDR autolearn=no 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 k1GEQ9t02528 for ; Thu, 16 Feb 2006 09:26:09 -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 k1GEQ8IQ006594 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Thu, 16 Feb 2006 09:26:09 -0500 (EST) Message-Id: <6.2.1.2.2.20060215132404.03417218@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Thu, 16 Feb 2006 02:11:37 -0500 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 8 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Range queries: GeoPeer: The central goal of Geopeer is to produce a location-aware peer to peer substrate. Instead of being labelled by a random hash, nodes are located in the system by their physical coordinates; messages can then be routed to points near nodes in Euclidean space. This may be useful for some sorts of location-aware systems, such as sensor networks. The authors accomplish this with a protocol that allows nodes to spontaneously form a Delauny triangularization (a planar triangle mesh with particular edge length properties) I'm very suspicious of their long-range contacts system. The analysis is unpersuasive: for below a few hundred nodes, it would probably be easier to just keep a complete node list; the system is only interesting for large networks. And their evaluation data doesn't explore large values of N. Also, if the system is deployed on a large scale, node density is likely to be extremely variable --Manhattan might have more nodes than all of the midwest. It is unclear how this will impact system performance, and in particular the choice of long distance links. Mercury: Mercury and P-Trees are both motivated by the same problem: the DHT operations of put and get are simply not adequate to the task of range queries. Mercury attempts to solve this in a peer-to-peerish way, by defining a distributing processing scheme. Mercury groups nodes into logical "attribute groups" for each field in the schema, and then does the range query within the attribute group. Mercury handles multi-attribute queries, but will choke as the schemas and queries grow larger--each query takes place over essentially one attribute hub, and a conjunction of large ranges will not be handled well. It's not clear how to extend mercury to handle reliable replication, nor how to handle failures in mid-query. P-Trees: While mercury is a systems-ish approach, P-trees are essentially a generalization of single-machine database data structures (in particular, they are a generalization of B-trees) to the peer-to-peer realm. The P-Trees is a relative of the B+ tree suitable for peer-to-peer systems. Each node stores a part of the overall tree. In this way, range queries can be sent to the nodes responsible for each part of the range, and the overall answers collected. Unfortunately, it is not clear how well P-trees scale to large numbers of nodes--if a node fails, the tree will be temporarily unstable. The authors have a stabilization procedure running to smooth out inconsistencies. As the network grows larger though, the number of node failures per second increases (for constant failure rate), and so the process has more and more work. There presumably is a point where the stabilization process is overloaded, and the system does not converge. If the system isn't stable, then queries will take significantly longer--raising the probability that a node dies in mid-query. Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From asg46@cornell.edu Thu Feb 16 11:56: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=0.0 required=5.0 tests=none 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 k1GGumt21554 for ; Thu, 16 Feb 2006 11:56:48 -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 k1GGukbk005405 for ; Thu, 16 Feb 2006 11:56:47 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Thu, 16 Feb 2006 11:56:47 -0500 (EST) Message-ID: <4721.128.84.98.90.1140109007.squirrel@webmail.cornell.edu> Date: Thu, 16 Feb 2006 11:56:47 -0500 (EST) Subject: paper 8 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 GEO-PEER it supports location-constrained queries and information dissemination. the previous systems that we have studied use random node identifiers which cannot represent a physical location. If node-ids are assigned on a geographical basis in previous systems, it would result in disrupting load balancing. BASIC STRUCTURE: the nodes are arranged to form a planar Delaunay triangulation network augmented with long range contacts(LRC). the characteristics of a Delaunay triangulation are the following : 1) expected O(1) node degree 2) good routing performance 3) distributed construction it has lower network diameter due to LRCs. a large number of messages are required for creating and maintaining the Delaunay triangulation. each node has a set of neighbors and maintains their alive status via beacon messages. each node P, based on its knowledge of its neighbors, computes the Delaunay triangle PMN and then sends a "TRIANGULATE" message about this information to both M and N. If the neighbors(M & N) agree with this assessment of P, a consistent set of "TRIANGULATE" messages are exchanged. in case of disagreement, a BREAKLINKS message is sent which causes the receiver to re-execute the local computation updating its local information ( BREAKLINKS contains the nodes whom the receiver should triangulate with as thought by the sender). node failure: when some neighbor of a failed node F detects the failure, it sends a FAILURE message to all its Delaynay neighbors. These neighbors,in turn if neighbors of F, correspondingly resend this message to their neighbors. This procedure ensures that all Delaunay neighbors of F become aware of its failure and the neighbors recompute the Delaunay triangle. Some other node P who was not the Delaunay neighbor of F can try to triangulate APF. This would result in storing the information about the failure of F forever. This problem is overcome by discarding info about F after the expiration of a timeout. when we have more than 3 co-circular nodes each node is the delaunay neighbor of the other. routing algorithm: the authors have suggested a greedy algorithm selecting that neighbor which is closest to the destination. they do point out that the algorithm is not "competitive". LRC: if routing was based on the greedy algorithm, lookups would be inefficient due to the large diameter of the network. the authors suggest mechanisms such as Hop level mechanism , hit count balancing methods, small world mechanism and e-CAN like mechanisms for LRC creation. hop-level mechanism represents a tree structure with base b and the level of a node is determined by its distance from the current node. to ensure that the hit-count counters do not diverge-they are halved periodically. P-TREES: efficiently evaluate range queries besides equality queries. cost for range queries: O(m+ lx N) lx represents log to base d m : number of peers in selected range N : number of peers d : order of P-tree space requirements at each node : O(d lx N) BASIC STRUCTURE: each node maintains parts of semi-independent B+ - trees. these parts represent the left-most root-to-leaf path of corresponding B+ -tree. P-trees differ from B+ trees as sub-trees have overlapping ranges allowing peers to independently grow or shrink their tree; thereby eliminating the need for excessive co-ordination and communication b/w peers (this is the TAKEAWAY FROM THIS PAPER) search : B+ -tree provides O(lx N) complexity. range queries are satisfied by reaching the lower bound first and then traversing along the ring. STATE MAINTENANCE : a ping process is used to check whether the node corresponding to the table entry has failed or not. the stabilize algorithm is used to stabilize each level at a time in increasing order of levels. the structure of the P-tree (i.e number of nodes at each level) is highly dependent on the number of nodes in the system currently for optimal performance. Thus, estimating the number of nodes in the system seems a consideration for optimal performance. MERCURY: performs multiple attribute based range queries as well as explicit load balancing. BASIC STRUCTURE: it handles multi-attribute queries by creating a routing hub for each attribute in the application schema assuming a small number of attributes. A hub is a logical collection of nodes in the system. each node in the hub is responsible for a certain range of the attribute which is represented by the hub. (a physical node can be part of multiple logical hubs but the authors do not discuss this idea) STORAGE REQUIREMENTS: 1) successor and predecessor links within the attribute hub 2) k long distance links for efficient intra-hub routing 3) one cross-link per hub for connecting to other hubs for better fault tolerance, the authors suggest more links for cross-hub and succ/pred nodes. a node randomly joins any hub initially. ROUTING: follows a greedy policy of selecting the closest link from its table. the protocol allows additional cached destinations to be added to the table. Random walks are used for propagating "keep-alive" messages ( no novelty here) LOAD BALANCING: in order to balance load, each node must estimate the load on other nodes in a distributed fashion. at each range in the value space, the load is estimated by a weighted average of its neighbor nodes preventing bias against low-density samples. However, their algorithm requires a lightly loaded node to gracefully leave its position and join a heavily loaded node thereby splitting the heavy load. in the real world, gracefully acceptance of heavy loads does not seem practical. (the heaviness of load on a node is determined by comparing it to the average load - but they mention no protocol for computing this average load) the authors also talk about query selectivity which essentially determines the order in which the conjunction of must be carried out. it talks about maintaining approximate histograms for each hub but a malicious cross-hub link could send wrong values during this estimation. in other words calculating this approximate value set seems difficult with malicious peers. From lackhand@gmail.com Mon Feb 20 19:05:34 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.5 required=5.0 tests=AWL,HTML_00_10,HTML_MESSAGE autolearn=no version=3.1.0 X-Spam-Level: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.201] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1L05Xt26217 for ; Mon, 20 Feb 2006 19:05:34 -0500 (EST) Received: by zproxy.gmail.com with SMTP id 13so1016702nzp for ; Mon, 20 Feb 2006 16:05:33 -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; b=g85U5/9FmqHscgAI/6za5IQXmbGtRnV4dyhTlxP+9d054TEuqTfR6tzGzvXr8YGvOi0qLVL2LtVoiJ3LSRtXBQ7Z/ksKBjhD5pIqY1BSKehdJgtTxSoChXjFjPi077iMY8iHImJDo5llSS3qr66yAhyO4MjqNJxG+yJc+ZNiIWY= Received: by 10.36.154.3 with SMTP id b3mr2747945nze; Mon, 20 Feb 2006 16:05:33 -0800 (PST) Received: by 10.36.146.8 with HTTP; Mon, 20 Feb 2006 16:05:33 -0800 (PST) Message-ID: <9aa7a97d0602201605t14b45cd4o1dd0bae712174254@mail.gmail.com> Date: Mon, 20 Feb 2006 19:05:33 -0500 From: "Andrew Cunningham" To: egs+summary@cs.cornell.edu Subject: PAPER 8 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_9644_21480057.1140480333295" ------=_Part_9644_21480057.1140480333295 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andrew Cunningham arc39 _The_Sybil_Attack_ John R Douceur The essential point of this paper is a taunting one: to reduce loss due to failure, redundancy can be employed; however, if the scenario involves a malicious entity, then if they can leverage sufficient resources, they can seize a considerable amount of control. The paper also proves that logicall= y centralized authorities can prevent Sybil attacks, but that otherwise, extreme and unrealistic assumptions about attacker capabilities must be mad= e (and thus vulnerabilities introduced). The difficulty here lies that it is not just redundancy which can be impacted by one attacker who can lay claim to multiple identities -- in cases of data being split among several entities, it can lead to data leakage; thus, the system must ensure that distinct identities refer to distinct entities. The assumption on relative resources (because, of course, with unbounded greater resources, an attacke= r can do nearly anything) is very weak: merely that there exists some n for which all entities can perform operations which are polynomial in n, but no entities can perform super-polynomial operations in n. The central concept was that the only way in-band to prove that two entities are separate is for the two to perform some computation in time that would tie up all of the resources of a single entity, and thus the identities must belong to separate entities. However, even this is not good enough, since it does not rule out collusion! Also, it assumes a certain degree of homogeneity; the assumption is easily broken by a motivated attacker, which is perhaps the threat model of every system. Once accepted, the paper goes on to indicate that identities may be able (depending on system) to vouch for other entities; thus the danger is that faulty entitie= s can (under the presented model) amplify their influence. The problem is wit= h the presented model of delegating identity verification: If we require not just individuals vouching, but paths vouching, then we can detect whether this attack is being used (or at least moderate the flow) based on the presented path contianing duplicates. _Defending_Against_Eclipse_Attacks_on_Overlay_Networks_ Atul Singh, Miguel Castro, Peter Druschel, Antony Rowstron In an overlay network, as the attacker compromises more and more nodes, their influence grows superlinearly; specifically, if the attacker can compromise a large fraction of the neighbors of a correct node, then they may 'eclipse' that node, preventing correct operation. It may be launched via a Sybil attack or via collusion, and is a higher order problem as attackers may manipulate the overlay maintenance algorithm to mount the Eclipse attack. The insight of the paper is that indegree of attacker nodes is going to be greater than that of "honest" nodes, and thus bounding this indegree mediates the attack, and to avoid the problem this creates by bounding outdegree as well. The defense hinges on a solution to distributing node identifier, which is not trivially solved, as the attacker cannot easily be prevented from gathering multiple identities, merely slowed. The auditing method uses source rewriting to have a set of nodes perform in- and out-degree queries on behalf of other nodes on the network. Since there are a set of indirect nodes, as long as we assume there are f failures and the set is of size 2*f+1, we can absolutely ensure correct behavior. This is polynomial in f, but capable of growing quite large. Moreover, it uses only shallow source re-writing, which means that a single compromised node can do significant damage; in fairness, however, in the peer to peer domain it is difficult enough to discover incorrect behavior, let alone absorb its damage flawlessly. _Secure_Routing_For_Structured_Peer_to_Peer_Overlay_Networks_ Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron, Dan S. Wallach This paper explores some of the capabilities of incorrectly functioning nodes in terms of message delivery through peer-to-peer overlays. They spli= t the weaknesses of peer to peer systems into three domains -- secure identification, routing table maintenance, and message routing -- and propose solutions for each vector of attack. Secure identification is in some senses a punted issue in this paper, a= s the solution is to require out-of-band verification of separate identities, or a weaker guarantee than separate identities. The only "resource" which w= e can assume is equally shared between users, and no replicable due to collusion, etc, is time; the paper proposes & rejects a cryptographic puzzl= e solution. Secure routing depends on good information which depends on secure identities; thus the solution to one aids the solution to the other. Their solution is to maintain, parallel to the optimized routing table, a second routing table with constrained choices, making the attacker's chance of having an entry in the table proportional to the number of nodes the attacker controls (rather than much greater). This segment does not, however, handle how to remove compromised nodes from the secure list, but merely uses it as a backup. Finally, secure message passing relies on replicating messages; this is a secure and inoffensive method of passing, though prevents information loss, not information leakage. ------=_Part_9644_21480057.1140480333295 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable    
Andrew Cunningham
arc39
    _The_Sybil_Attack_
    John R Douceur
    
    The essential point of this paper is a taunting one: to reduce loss due to failure, redundancy can be employed; however, if the scenario involves a malicious entity, then if they can leverage sufficient resources, they can seize a considerable amount of control. The paper also proves that logically centralized authorities can prevent Sybil attacks, but that otherwise, extreme and unrealistic assumptions about attacker capabilities must be made (and thus vulnerabilities introduced). The difficulty here lies that it is not just redundancy which can be impacted by one attacker who can lay claim to multiple identities -- in cases of data being split among several entities, it can lead to data leakage; thus, the system must ensure that distinct identities refer to distinct entities. The assumption on relative resources (because, of course, with unbounded greater resources, an attacker can do nearly anything) is very weak: merely that there exists some n for which all entities can perform operations which are polynomial in n, but no entities can perform super-polynomial operations in n.
    The central concept was that the only way in-band to prove that two entities are separate is for the two to perform some computation in time that would tie up all of the resources of a single entity, and thus the identities must belong to separate entities. However, even this is not good enough, since it does not rule out collusion! Also, it assumes a certain degree of homogeneity; the assumption is easily broken by a motivated attacker, which is perhaps the threat model of every system. Once accepted, the paper goes on to indicate that identities may be able (depending on system) to vouch for other entities; thus the danger is that faulty entities can (under the presented model) amplify their influence. The problem is with the presented model of delegating identity verification: If we require not just individuals vouching, but paths vouching, then we can detect whether this attack is being used (or at least moderate the flow) based on the presented path contianing duplicates.
    
    _Defending_Against_Eclipse_Attacks_on_Overlay_Networks_<= br>     Atul Singh, Miguel Castro, Peter Druschel, Antony Rowstr= on
    
    In an overlay network, as the attacker compromises more and more nodes, their influence grows superlinearly; specifically, if the attacker can compromise a large fraction of the neighbors of a correct node, then they may 'eclipse' that node, preventing correct operation. It may be launched via a Sybil attack or via collusion, and is a higher order problem as attackers may manipulate the overlay maintenance algorithm to mount the Eclipse attack. The insight of the paper is that indegree of attacker nodes is going to be greater than that of "honest" nodes, and thus bounding this indegree mediates = the attack, and to avoid the problem this creates by bounding outdegree as well.
    The defense hinges on a solution to distributing node identifier, which is not trivially solved, as the attacker cannot easily be prevented from gathering multiple identities, merely slowed. The auditing method uses source rewriting to have a set of nodes perform in- and out-degree queries on behalf of other nodes on the network. Since there are a set of indirect nodes, as long as we assume there are f failures and the set is of size 2*f+1, we can absolutely ensure correct behavior. This is polynomial in f, but capable of growing quite large. Moreover, it uses only shallow source re-writing, which means that a single compromised node can do significant damage; in fairness, however, in the peer to peer domain it is difficult enough to discover incorrect behavior, let alone absorb its damage flawlessly.
    
    _Secure_Routing_For_Structured_Peer_to_Peer_Overlay_Netw= orks_
    Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony R= owstron, Dan S. Wallach
    
    This paper explores some of the capabilities of incorrectly functioning nodes in terms of message delivery through peer-to-peer overlays. They split the weaknesses of peer to peer systems into three domains -- secure identification, routing table maintenance, and message routing -- and propose solutions for each vector of attack.
    Secure identification is in some senses a punted issue in this paper, as the solution is to require out-of-band verification of separate identities, or a weaker guarantee than separate identities. The only "resource" which we can assume is e= qually shared between users, and no replicable due to collusion, etc, is time; the paper proposes & rejects a cryptographic puzzle solution.
    Secure routing depends on good information which depends on secure identities; thus the solution to one aids the solution to the other. Their solution is to maintain, parallel to the optimized routing table, a second routing table with constrained choices, making the attacker's chance of having an entry in the table proportional to the number of nodes the attacker controls (rather than much greater). This segment does not, however, handle how to remove compromised nodes from the secure list, but merely uses it as a backup.
    Finally, secure message passing relies on replicating messages; this is a secure and inoffensive method of passing, though prevents information loss, not information leakage. ------=_Part_9644_21480057.1140480333295-- From sh366@cornell.edu Mon Feb 20 23:51:12 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=AWL 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 k1L4pCt03156 for ; Mon, 20 Feb 2006 23:51:12 -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 k1L4pBBj025770 for ; Mon, 20 Feb 2006 23:51:12 -0500 (EST) Message-ID: <1084056918.1140497470330.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Mon, 20 Feb 2006 23:51:10 -0500 (EST) From: Huang Shiang-Jia To: egs+summary@cs.cornell.edu Subject: PAPER 8 Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 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 k1L4pCt03156 * The three papers discuss security issues in peer-to-peer systems and present several defenses against the attacks. * The first paper presents Sybil attack: entities can counterfeit multiple identities to compromise the redundancy in peer-to-peer systems, and shows that this attack is always possible in the absence of trusted authority. * The second paper proposes a defense against Eclipse attack: attackers may control a large fraction of the neighbor of correct nodes even with only a small fraction of faulty nodes. * Secure routing in the third paper guarantees correct message delivery in the presence of malicious nodes by secure assignment of node identifier, secure routing table maintenance and secure message forwarding. [Comments] Other attacks include an attacker keeps inserting objects to bring down the system or an attacker inserts lots of different content of an object (the same name and key) to interfere with the correct one. * Large-scale peer-to-peer systems rely on redundancy to resist hostile remote entities. That a small number of remote entities forge multiple identities to break this resistance is called Sybil attack. * This paper presents a general distributed computing model whose environment is friendly, that is, each entity is placed minimal resource restriction and public-key cryptography is allowed, and show that faulty entities can counterfeit multiple identities unless correct entities validate all the identities simultaneously. * In the absence of trust authority, an entity may discriminate the identities by resource challenges by assuming resources of attackers are limited. In their model, three resources: communication, storage and computation are discussed. Concurrency is a very important requirement when performing resource challenges in either case of direct identity validation or indirect (via a group of identities that the entity has accepted) identity validation. * This paper proposes a defense against Eclipse attack by bounding the indegree and outdegree of nodes in choosing neighbors in structure peer-to-peer overlays. * Eclipse attack is launched either by populating the neighbor sets of correct nodes with a lot of fake identities (via Sybil attack) or by exploiting the routing table maintenance algorithm. * Unstructured peer-to-peer overlays are extremely vulnerable to Eclipse attacks since its selection of routing paths can easily been biased by attackers. Structured overlays are more resilient to these attacks because they assign uniform identifier to nodes, thus imposing more strict constraints on the neighbor sets. This property, on the other hand, limits the possibility to implement locality optimization. * The defense proposed in this paper, by auditing to enforce degree bounds, can be applied to both unstructured and structured overlays. It also permits performance optimization like proximity neighbor selection. In their approach, indegree is measured by entries of the back pointer list while the outdegree is measured by the size of neighbor set. Nodes choose neighbors who indegree and outdegree are below a threshold. They rely on certified node identifier to authenticate the replies of auditing challenges. Finally, an anonymous channel that challenges are relayed through a set of intermediate nodes (anonymizer nodes) is adopted in their approach. * [Issues] They perform experiments on Pastry and enforce bounds per routing table row because fitting malicious neighbors in the top rows is more severe. The results show that their defense is effective but increases delays in the absence of attacks. Besides, the measurements of indegree and outdegree need to be improved in a system with constant churn. * This paper proposes a secure routing scheme, which consists of secure assignment of node identifier, secure routing table maintenance and secure message forwarding, to guarantee correct message delivery in structured peer-to-peer overlays in the presence of malicious nodes. * In their model, an adversary has control over the network-level communication between malicious nodes, and these nodes may collude to cause damage to the system. Their secure routing primitive ensures that a query message sent by a correct node reaches all correct replica roots with high probability. * For secure assignment of node identifier, trusted certification authorities are used to sign certificates that bind a random node identifier to a principal’s public key and its IP address. The inclusion of IP address is important since an attacker now can’t freely move certificates across the nodes. To prevent attackers from getting a large number of certificates, users are required to pay money or present real-world identity. A less effective approach to generate certificates in a distributed fashion is using crypto puzzles. * For secure routing table maintenance, they use two routing tables: one that exploits network proximity for efficient routing and one that constrains table entries. The first table (as in Pastry and Tapestry) is used in normal operations to achieve good performance. Since attackers can fake proximity to introduce bad entries to this table, the second table (as in Chord), where strong constraints are imposed on choosing nodes identifiers, is used when previous routing fails. * For secure message routing, they apply a failure test to determine if a routing works and perform redundant routing if the failure test returns positive. Attackers may collect certificates of nodes that have left and include correct nodes in a prospective root neighbor sets to affect the failure test. So the sender needs to contact the neighbors to determine if they are alive and have valid certificates. Another nodeId suppression attack which may increase the false positives and false negatives in the test remain inevitable in decreasing the accuracy of the test. The idea of redundant routing is to route copies of the message over multiple paths toward each of the replica roots. As the cost is high, several parameters can be tuned to tradeoff security for performance. Rather, self-certifying data can be stored on replica roots; their integrity is checked by the client and only when it fails does the client resort to secure routing, thus minimizing the use (and overhead) of the secure routing scheme. From kash@cs.cornell.edu Tue Feb 21 00:16:28 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-0.8 required=5.0 tests=ALL_TRUSTED,AWL,HTML_10_20, HTML_MESSAGE autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe1.cs.cornell.edu (exchfenlb-1.cs.cornell.edu [128.84.97.33]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1L5GSt09323 for ; Tue, 21 Feb 2006 00:16:28 -0500 (EST) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 00:16:28 -0500 Content-class: urn:content-classes:message MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C636A5.F7696B07" X-MimeOLE: Produced By Microsoft Exchange V6.5 Subject: PAPER 8 Date: Tue, 21 Feb 2006 00:16:27 -0500 Message-ID: <2EE48095D8C21643B0B70EC95F9BFBAF0EE642@EXCHVS1.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: PAPER 8 Thread-Index: AcY2pfdPfW3Lha4gQAmzwKUZD14xLw== From: "Ian Kash" To: X-OriginalArrivalTime: 21 Feb 2006 05:16:28.0464 (UTC) FILETIME=[F7FC2B00:01C636A5] This is a multi-part message in MIME format. ------_=_NextPart_001_01C636A5.F7696B07 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The Sybil Attack presents a class of attacks on P2P systems based on an attacker obtaining multiple identities. The first attack is that a well provisioned entity can exploit the fact that he has a multiple of the resources of a minimally provisioned entity to appear as multiple = minimal entities. It identities are not verfied directly, and are instead = verified by having a certain number of established entities vote to accept them, = an attacker with sufficient resources to establish a voting block of the required size can create an unlimited number of identities. Finally, in = both cases, if identities are not all verified at the same time, even a = minimal entity can sequentially create an unlimited number of identities. One = factor that seems to be overlooked is that no additional work is required to = provide a cost for maintaining multiple identities. The costs of overlay maintainance and routing may, in many systems, provide enough of a cost = to keep the number of potential sybils small. Secure Routing for Structured Peer-to-Peer Overlay Networks presents a variety of techniques for securing overlays against malicious nodes. = The property that they seek to provide is: "when a non-faulty node sends a message to a key k, the message reaches all non-faulty members in the = set of replica roots R_k [i.e. those nodes storing a copy of the object with = key k]with very high probability." To provide this guarantee, they examine = ways to provide three lower level properties. The first is that the = assignment of nodeIDs is secure. They propose using real world certification of = nodeIDs to make difficult or prevent obtaining multiple or carefully chosed IDs. = They reject distributed solutions on the grounds that none they are aware of prevent obtaining a large collection of IDs over time. To ensure = attackers cannot hijack the routing table, they propose constraining the routing = table so that only a single node can fill any slot (as in chord). This = prevents an attacker from being able to fill a large number of slots with a small = number of nodes and also ensures that filling any chosen slot with a random = nodeID is unlikely. Finally, they examine ways to ensure that messages are delivered even if some nodes along the path are faulty. Their proposal = is to use redundant paths to ensure that a single node can not prevent any = pair from communicating. Eclipse attacks proposes a different solution to this same problem. By bounding the indegree of nodes, it prevents a small group of nodes from altering the routing tables so that a large fraction of messages must = pass through them. This presents a new problem because now a small group of = nodes can take up the entire indegree of a large group of nodes, cutting them = out. To prevent this, the outdegree must also be bounded. An auditing scheme = is used to enforce these bounds. Another possibility these papers could = have considered is an expander graph type structure. The fact that the neighborhood of a node grows exponentially fast may be sufficient to = provide the diversity of paths needed to prevent a small set of nodes from controlling routing. ------_=_NextPart_001_01C636A5.F7696B07 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable PAPER 8

The Sybil Attack presents a class of attacks on P2P = systems based on an attacker obtaining multiple identities.  The = first attack is that a well provisioned entity can exploit the fact that = he has a multiple of the resources of a minimally provisioned entity to = appear as multiple minimal entities.  It identities are not verfied = directly, and are instead verified by having a certain number of = established entities vote to accept them, an attacker with sufficient = resources to establish a voting block of the required size can create an = unlimited number of identities.  Finally, in both cases, if = identities are not all verified at the same time, even a minimal entity = can sequentially create an unlimited number of identities.  One = factor that seems to be overlooked is that no additional work is = required to provide a cost for maintaining multiple identities.  = The costs of overlay maintainance and routing may, in many systems, = provide enough of a cost to keep the number of potential sybils = small.

Secure Routing for Structured Peer-to-Peer Overlay Networks presents a = variety of techniques for securing overlays against malicious = nodes.  The property that they seek to provide is: "when a = non-faulty node sends a message to a key k, the message reaches all = non-faulty members in the set of replica roots R_k [i.e. those nodes = storing a copy of the object with key k]with very high = probability."  To provide this guarantee, they examine ways to = provide three lower level properties.  The first is that the = assignment of nodeIDs is secure.  They propose using real world = certification of nodeIDs to make difficult or prevent obtaining multiple = or carefully chosed IDs.  They reject distributed solutions on the = grounds that none they are aware of prevent obtaining a large collection = of IDs over time.  To ensure attackers cannot hijack the routing = table, they propose constraining the routing table so that only a single = node can fill any slot (as in chord).  This prevents an attacker = from being able to fill a large number of slots with a small number of = nodes and also ensures that filling any chosen slot with a random nodeID = is unlikely.  Finally, they examine ways to ensure that messages = are delivered even if some nodes along the path are faulty.  Their = proposal is to use redundant paths to ensure that a single node can not = prevent any pair from communicating.

Eclipse attacks proposes a different solution to this same = problem.  By bounding the indegree of nodes, it prevents a small = group of nodes from altering the routing tables so that a large fraction = of messages must pass through them.  This presents a new problem = because now a small group of nodes can take up the entire indegree of a = large group of nodes, cutting them out.  To prevent this, the = outdegree must also be bounded.  An auditing scheme is used to = enforce these bounds.  Another possibility these papers could have = considered is an expander graph type structure.  The fact that the = neighborhood of a node grows exponentially fast may be sufficient to = provide the diversity of paths needed to prevent a small set of nodes = from controlling routing.

------_=_NextPart_001_01C636A5.F7696B07-- From pjk25@cornell.edu Tue Feb 21 00:49:43 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 k1L5ngt18040 for ; Tue, 21 Feb 2006 00:49:42 -0500 (EST) Received: from [10.0.1.2] (cpe-69-207-41-159.twcny.res.rr.com [69.207.41.159]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1L5nfrI029687 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Tue, 21 Feb 2006 00:49:42 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: Philip Kuryloski Subject: PAPER 8 Date: Tue, 21 Feb 2006 00:52:27 -0500 X-Mailer: Apple Mail (2.746.2) THE SYBIL ATTACK In The Sybil Attack, Douceur suggests that in a distributed computing environment, it is impossible (barring unrealistic assumptions about network homogeneity) to keep newly entering nodes from presenting multiple network identities. These nodes can then defeat network security measures which rely upon node wise redundancy in the network, performing what is known as a Sybil Attack. The following general network model is formed: There are a set of entities, a broadcast communication cloud, and a pipe connecting each entity to the cloud. A subset of the entities are faulty or compromised nodes, and the rest are correct, or honest. Nodes may have different computation resources, except that no node posses the power do crack a public key session between two entities. Douceur suggests three methods of identifying an entity based on it's resources: latency, storage resources, and computational resources. He then gives four Lemmas regarding an entity's ability to claim multiple identities. The 1st two lemmas result from an overly capable node dividing it's resources to act as multiple nodes. If verification for each identity is not simultaneous, the faulty node can reuse it's resources to spoof an arbitrary number of identities. Lemmas 3 & 4 hold If in the system allows indirect verification. Lemma 3 states that if there exists enough faulty nodes to vouch for an identity, that collection of faulty nodes can vouch for an arbitrary number of false identities. Lemma 4 essentially combines Lemmas 2 & 3, allowing a single faulty node to vouch for an arbitrary number of identities. These lemmas in general do not bode well for peer-to-peer networks in general, however they are derived from a very simple network view, and so it should be possible to overcome some of these limitations. Primarily, it does not account for the use of any side channel information to verify node identities. For instance, in a sensor network, where node transmission ranges do not extend across the whole network, a single node cannot appear to exist at multiple points within the network. Thus, a node masquerading as many would have to appear to be a cluster of nodes, suggesting that redundancy could be spread across space rather than nodes, defeating the Sybil Attack. DEFENDING AGAINST ECLIPSE ATTACKS ON OVERLAY NETWORKS The eclipse attack is a more general attack than the Sybil attack, achieved by gaining control of the neighbor links of an overlay node and interfering with that correct nodes communication with the rest of the overlay network. Primarily, the authors suggest nodes which are attempting an eclipse attack will have high indegree as they try to isolate correct nodes. A simple solution is then to only connect to nodes with a sufficiently low indegree. This allows for another attack whereby attacker nodes attempt to raise the indegree of correct nodes. This can be avoided by limiting the outdegree of correct nodes. The authors note that this simple criteria can be applied to both structured and unstructured networks. Unstructured overlays are the mot vulnerable to eclipse attack, as the flooding or random walk searches used by these overlays allow messages to reach a large number of attacker nodes. In structured networks, many latency optimizations based on network heterogeneity increase the network's susceptibility to eclipse attacks (e.g. proximity neighbor selection, indegree proportional to node capacity). The authors propose the following method of validating a node's reported indegree and outdegree, provided that the overlay already can protect against Sybill attacks: Each node keeps a list of all known nodes linking to it, called a back pointer list. Periodically the node challenges its neighbors to produce their neighbor list. If a returned list is too large, or it does not contain the requesting node, the requesting node will remove that node from its neighbor list. To validate outdegree, each node periodically challenges each node on its back pointer list for its neighbor set. If the requesting node is not in the list, or the list is too large, the offending node is removed. In structured networks, it is required that backpointers are spread across different prefixes or routing table rows so that attackers cannot gain complete control of a routing hop. These requests are routed through anonymizer nodes to to conceal the identity of the requester, so appropriate backpointer lists cannot be forged. The system is simulated on top of a Pastry implementation, and reduces routing table infection by malicious nodes from ~%80 to %25 with perfectly accurate degree reports. A separate test is performed using the anonymizing scheme for backlist requests showing that it reduces routing table infection. Unfortunately these analyses do not consider the load placed on the network from the additional messages sent including anonymizations for node indegree and outdegree verification, and no nodes join or leave the network during simulations. SECURE ROUTING FOR STRUCTURED PEER-TO-PEER OVERLAY NETWORKS The authors propose a method of securing peer-to-peer networks such as Pastry, Tapestry, Chord, or others. They describe a method of providing a secure routing primitive, ensuring that a message will eventually reach at least one root node responsible for that key, thereby which overlay network security can be maintained. To achieve the secure routing primitive, three challenges must be addressed: Secure nodeId assignment, securely maintaining routing tables, and securely forwarding messages. To achieve sure nodeId assignment, the authors suggest the use of public key cryptography and CAs to hand out nodeId's, and possibly charge for nodeId's to make attacks costly. If this is not available, they suggest that nodes earn their id's through solving cryptographic puzzles, although they acknowledge the limitations of this solution. Secure nodeId assignment helps in the secure routing table problem but is not sufficient for systems which use proximity routing, and is not helpful in systems where it is difficult to detect malicious network updates masquerading as node join/leave messages. As a solution, the authors suggest that in networks using proximity routing, a backup routing table is maintained which does not use proximity information and works only in the nodeId space. When a message fails to be routed, the system reverts to the backup table. Secure routing is achieved by a detection method for failed routes and a rerouting scheme designed to overcome these failures. Failure detection is based upon the fact that most of the nodes in the system are not compromised, and thus colluding nodes will produce lower than expected set of replicas of a key. However, the authors admit that the detection scheme will fail, and so provide the rerouting mechanism, essentially a multicast. Finally, the authors give some performance evaluation of their system implemented on top of Pastry, and note the benefit of self-certifying data for reduction in cost of the secure routing primitive. Although this system succeeds to some extend in securing the overlay network, it does so building on secure assignment of nodeIds, suggesting that only a centralized scheme providing CA's can achieve this. This limits the P2P aspect of the system. Also, it solves later challenges essentially with additional redundancy and network overhead, rather than architectural changes to the underlying system. From ns253@cornell.edu Tue Feb 21 01:17:01 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 k1L6H1t26168 for ; Tue, 21 Feb 2006 01:17:01 -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 k1L6H0r7028767 for ; Tue, 21 Feb 2006 01:17:00 -0500 (EST) Received: from 69.207.49.126 by webmail.cornell.edu with HTTP; Tue, 21 Feb 2006 01:17:00 -0500 (EST) Message-ID: <55188.69.207.49.126.1140502620.squirrel@webmail.cornell.edu> Date: Tue, 21 Feb 2006 01:17:00 -0500 (EST) Subject: PAPER 8 From: "Niranjan Sivakumar" 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 Niranjan Sivakumar The Sybil Attack Defending Against Eclipse Attacks on Overlay Networks Secure Routing for Structured Peer-to-Peer Overlay Networks The Sybil Attack describes an attack on a p2p network overlay where single attackers can masquerade as numerous nodes on the network. The attack is on a network that does not have a central centralized trust verification system, but that allows public key cryptography. A simple generic model of a p2p network was proposed. The paper illustrates that even with techniques such as testing resource metrics, the realities of a heterogenous network and time coordination issues make it possible for a single attacker to deal with the challenges that they are faced with and to continue to masquerade. Having indirect identity validation also creates a problem as the attacker can basically vouch for itself through it's multiple identities. Eclipse attacks are somewhat similar to Sybil attacks, but more general. Essentially, the attacker uses either a Sybil attack or takes advantage of structural features of an overlay network to "eclipse" nodes by taking over their neighborhood and not allowing messages to pass to or from the target node. Unstructured overlays, such as Gnutella, are shown to be most vulnerable to such attacks because there are no constraints on a node's neighbor set. Though structured overlays can be somewhat more resilient to these attacks, they are not invulnerable. The paper proposes a method of degree bounding to combat eclipse attacks. In and out degrees bounds are audited anonymously in order to avoid falsified answers. The Secure Routing paper deals with a ensuring that messages are passed correctly in a structured p2p network even in the presence of malicious nodes. The paper first stipulates that the network must have secure nodeId assignment, and proposes that this is done with trusted certification authorities. The paper rejects the notion of distributed nodeId generation saying that there are fundamental security limitations in this scheme. The paper also mentions a need to maintain secure routing tables where invalid entries in tables are kept bounded. The paper proposes that two routing tables are maintained, one that constrains table entries and one that is based on efficient routing. Finally, the paper wants secure message forwarding. The solution is to be able to detect faults and to have redundant paths to forward messages. The general basis of the routing failure test that is provided compares nodeId densities around a sender and replica roots of the destination key (the example provided is for Pastry.) In the event of a detected error, messages are forwarded through redundant routes. The paper selects this method for seucure message forwarding over a technique of checked iterative routing. The Sybil Attack paper's general and somewhat simple network view may limit their ability to analyze solutions that, while perhaps not perfect, may alleviate this problem. Some techniques have been proposed for dealing with Sybil attacks in sensor and wireless networks where resource constraints and characteristics are more clearly defined (e.g. radio resource testing and random key predistribution). There are some unanswered issues in the Eclipse paper, particularly related to techniques that would work on an unstructured network, but this is mentioned by the authors as they have only presented a work in progress. There does seem to be a bit of strain put on the system from their defense method, and the audits could become a little more difficult to handle in a network with a lot of churn. The Secure Routing paper seems to be limited since one of the cornerstones of their approach is having secure nodeIds. They base this on having certification authorities, but it is not clear that this system is feasible for all kinds of p2p networks, as was illustrated in the Sybil Attack paper. From tc99@cornell.edu Tue Feb 21 02:09:10 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 k1L79At09364 for ; Tue, 21 Feb 2006 02:09:10 -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 k1L79Aim012964 for ; Tue, 21 Feb 2006 02:09:11 -0500 (EST) Received: from 24.59.114.243 by webmail.cornell.edu with HTTP; Tue, 21 Feb 2006 02:09:11 -0500 (EST) Message-ID: <1482.24.59.114.243.1140505751.squirrel@webmail.cornell.edu> Date: Tue, 21 Feb 2006 02:09:11 -0500 (EST) Subject: paper 8 From: "Theodore Ming Shiuan Chao" To: egs@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 The first two papers focus on two kinds of related attacks that can be launched on P2P networks. The first is Sybil, which is where an attacker tries to forge multiple identities in order to undermine the system. The paper outlines several requirements that can be put into place to restrict the number of identities a single entity could assume, which even though it cannot fully prevent a Sybil attack, can severely limit the amount of damage that can be done. The basic requirements are some sort of constrained resource test for validation that is conducted simultaneously across the network. In that case, if the test requires c resources to answer correctly and a fradulent entity has at most k times more resources, then that entity can assume at most k identities since the validation is done simultaneously. The second paper deals with Eclipse attacks, where an attacker tries to take control of the routing done in a network by inserting itself or other faulty nodes into numerous routing tables and links. The base assumption is that the network has some constraint of the type above on Sybil attacks; otherwise, an attacker could forge multiple identities and simply overwhelm the number of legitimate nodes with faulty ones. The authors limit the damage a node can do by limiting the out- and in-degree of nodes, so that no node is pointed to by too many nodes, and no node takes up the in-degrees of too many nodes. This prevents a small fraction of the nodes from dominating a large fraction of the routing table entries, and increase the probability that routing paths chosen do not pass through faulty nodes. The degree bounds are enforced using anonymous auditing to check the neighbor sets of its neighbors. Assuming that the anonymity works and the challenged node does not know who issued the challenge, the challenged node would have difficulty faking a neighbor set that contains the unknown node while hiding some of its out-degrees so that it appears as if it is under the limit. The last paper is far more general than either of the previous ones. It investigates three factors in P2P network security: nodeID generation, routing table maintenence, and message routing. For nodeID generation, their conclusion was that distributed generation is unable to prevent Sybil attacks, and that the best bet was to have a Certifying Authority with a requirement for attaining a certificate to make it expensive or impossible to obtain a large number of certificates (eg. monetary or unique identifications). For routing table updates, they constrain the routing table and use multiple bootstraps to prevent a corrupt bootstrap from unduly influencing a new node. The constraints could be such things as the out- in-degree constraints from the Eclipse paper, though the authors here do not offer any specific suggestions. The main content of the paper involves routing failure detection. The authors add deterministically chosen replicas for every root, and when a node initiates a query, it checks to ensure that the node it is sending the query to has a valid set of replicas. For Pastry, the replicas are the neighborhood leaf set, and the deterministic property of that is a probabilistic maximum width of the set and a balanced left-right property. If the replica set returned from the targetted key node is deemed to be invalid or doesn't even reach the sender, then redundant routing is initiated. The idea outlined in the Eclipse paper still seems quite vulnerable to attackers. Even though it would be difficult to control the entire routing table of the majority of the nodes in the network, a dedicated set of faulty nodes could still consume all of the in-degrees of certain selected sections of a network, possibly partitioning that segment of the ring. Furthermore, all of the ideas outlined in the three papers are only feasible for networks above a certain size. Smaller networks are naturally much more vulnerable since an attacker could easily muster the resources or entities to control the majority of the nodes in it. From ryanp@cs.cornell.edu Tue Feb 21 05:03:58 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe1.cs.cornell.edu (exchfenlb-1.cs.cornell.edu [128.84.97.33]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1LA3vt24542 for ; Tue, 21 Feb 2006 05:03:57 -0500 (EST) Received: from exchfe2.cs.cornell.edu ([128.84.97.34]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 05:03:57 -0500 Received: from [128.253.211.203] ([128.253.211.203]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 05:03:56 -0500 Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: "Ryan S. Peterson" Subject: PAPER 8 Date: Tue, 21 Feb 2006 05:03:56 -0500 X-Mailer: Apple Mail (2.746.2) X-OriginalArrivalTime: 21 Feb 2006 10:03:56.0662 (UTC) FILETIME=[20B65160:01C636CE] Douceur introduces the concept of a Sybil attack on a peer-to-peer system as an attempt by malicious users to thwart the normal operation of the network by creating multiple identities. In addition to describing the negative effects of Sybil attacks, the author proves that reasonable p2p systems have no hope of completely avoiding them. Most importantly, Douceur shows that large p2p systems are vulnerable to Sybil attacks for two reasons. First, as the number of total nodes increases, the number of malicious identities (multiple identities actually mapping to the same "real" entity) is also likely to increase. When the number of malicious nodes reaches a threshold, there are enough of them to launch an attack against some portion of the network. Second, if the correct ("honest") nodes in the system are required to accept new nodes into the system by verifying their trust, either directly or indirectly through other trusted nodes, they must synchronize their "accepting time intervals" to avoid accepting malicious nodes. Both problems demonstrate the vulnerability of p2p networks as they scale to large sizes, suggesting a difficult tradeoff in p2p system design: size versus security. Singh, et al. present a more general form of attacks on p2p networks called eclipse attacks and offer a method for preventing such attacks in some networks. Eclipse attacks are characterized by one or more malicious nodes hijacking connections to correct nodes, hiding the correct nodes from network view and possibly disrupting the network by acting on packets originally destined for the eclipsed nodes. The authors' main contribution is a defense against such attacks by capping the degree of each node in the system. Nodes involved in an eclipse attack necessarily have more incoming edges than correct nodes since they receive traffic destined for the hidden nodes. Therefore, by monitoring the degrees of neighboring nodes, correct nodes can decide which nodes are malicious and avoid them. The paper also presents an anonymous auditing protocol for periodically testing neighbor nodes to determine their degrees, removing them from their neighbor list if they exceed the degree limit. One limitation of this work is that it is designed for unstructured p2p networks, and does not easily transfer to structure networks such as Pastry and Chord. The final paper, Secure routing for structured peer-to-peer overlay networks, by Castro, et al. describes security in p2p systems, presenting and implementing a secure version of Pastry. The modified Pastry focuses on security in three aspects: node ids, node routing tables, and node forwarding. By creating a strict protocol over the the three domains, the resulting system guarantees that a message sent from a correct node will make it to its destination within the network with very high probability assuming a bounded number of malicious nodes, a claim much stronger than previous similar work. To ensure security in node routing tables, the protocol places strict constraints on what types of nodes each location of the routing table can point to. The intuition for secure forwarding is that a node sends a message normally and sets a timeout. If the timeout expires without receiving a response from the destination node, the sender assumes a malicious node intercepted the message, and so the sender resends the message via multiple, hopefully disjoint paths to the sender. With high probability, one path will contain only correct nodes, and the message will reach its destination. Experiments and analysis show that a network can withstand 25% malicious nodes without compromising the network. Ryan From ids3@cornell.edu Tue Feb 21 09:58:31 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 k1LEwUt16537 for ; Tue, 21 Feb 2006 09:58:30 -0500 (EST) Received: from [128.253.212.208] (r253212208.resnet.cornell.edu [128.253.212.208]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1LEwUXu001246 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 21 Feb 2006 09:58:30 -0500 (EST) Message-ID: <43FB2A9A.5010504@cornell.edu> Date: Tue, 21 Feb 2006 09:58:34 -0500 From: Ivan Stoyanov User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: egs+summary@cs.cornell.edu Subject: PAPER 8 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit The Sybil Attack The paper is claiming that a sufficiently recourseful attacker can grab a large part of a peep-to-peer network by simulating a sifficient number of identities, which reduces the resilience of the network due to redundancy. The problem posed is to ensure that distinct identities map to distinct identities. One way to do this is to issue challenges to each identity that will be difficult to respond to by a single entity at the same time. However, the challenges should be computationally feasible for the given time to the least resouceful correct node on the network, thus an attacker can claim as many identities and the floor of the ratio of its resourcefulness to this of the least capable correct node. The other interesting proposition is that identity checking can be "outsourced" to formerly accepted identities. An identity is accepted only if it has been accepted by a certain number of already accepted nodes. However, once a correct node accepts the threshold number of faulty nodes the group of fauly nodes can make the correct node accept anything else. Defending against Eclipse Atacks on Overlay Networks An attacker on a overlay network can "eclipse" a certain set of nodes by controlling all links in and out of the set of nodes. The eclipse attack is more general than the sybil attack. The main idea here is that the degree of correct nodes is going to be within certain bounds compared to that of faulty nodes. Bounding the degree will alleviate the strength of the attack. To do this nodes keep asymentric key paris to encrypt and sign messages. Nodes also keep a "back pointer" list, which is the set of nodes that have that node as a neightbor. The size of that list should be between the stipulated bounds. The list is verified by asking the its members directly. A node whose degree bounds are out of range is ignored. This approach makes rounting slower since messages need to be signed/encrypted at each hop. However, that may be a small price to pay since the eclipse attacks are very effective and the results show that the approach is reasonably effective. From km266@cornell.edu Tue Feb 21 11:07:07 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.7 required=5.0 tests=AWL,FORGED_OUTLOOK_TAGS, HTML_10_20,HTML_MESSAGE autolearn=no 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 k1LG77t10114 for ; Tue, 21 Feb 2006 11:07:07 -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 k1LG76ti003959 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Tue, 21 Feb 2006 11:07:06 -0500 (EST) Message-ID: <001001c63700$e5c309d0$4425cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 8 Date: Tue, 21 Feb 2006 11:07:21 -0500 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_000D_01C636D6.FC605230" 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 This is a multi-part message in MIME format. ------=_NextPart_000_000D_01C636D6.FC605230 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The Sybil attack paper points out that any attacker who has enough = resources (relative to the weakest person in the network) can dupe = himself many times. In other words, an attacker can fake multiple = identities. This would kill the security in any system which heavily = relies on redundancy for its security. To help show this, the paper = introduces 4 lemmas. The first one states that if you are x times more = privileged in terms of resources than another node, you can present = floor(x) identities to a local entity. The second lemma states that = unless all entities are validated simultaneously, any single entity can = present itself through distinct identities as many times as it wishes. = Lemma 3 says that even with trusted entities, if there are enough faulty = entities or they have enough processing power, they can still take over. = Lemma 4 builds upon others by saying that unless multiple nodes = coordinate time intervals, an attacker does not need too many resources = to hurt the network. An Eclipse attack is when an attacker tries to fill the neighbor sets of = nonfaulty nodes with faulty nodes. This would ensure that that node = would not be able to effectively communicate with the network. While = unstructured networks are most effected by this attack, it is a severe = problem in structured p2p systems as well. A key insight is that an = attacker node would then have a large in-degree and a large out-degree. = By limiting neighbor selection to those nodes who have low indegree and = low outdegree, a node could assume that its neighbor is legitimate. A = node could therefore ask any other node to give it their neighbor set = and back-pointer set. If the requesting node is not in it or the sets = are too large, then that node is removed from its neighbor set. This = will ensure that a malicious node cannot insert itself into the neighbor = set. The obvious counter to this is to put the requesting node into the = set before sending the set back. To counter against this, the = requesting node anonymously routes the request for the two sets through = nodes it trusts. In the end, it seems like there is a tradeoff between querying = neighbors and reliability. The more you query, the more reliable the = network, but this causes large bandwidth overhead. The less you query, = the less bandwidth, but your neighbors might not be reliable. The other = issue is that the paper seems to assume that the network is already = immune to a Sybil attack, which seems to be a chicken-and-egg problem. In the secure routing paper, the authors argue that three things are = necessary to ensure that a message will reach a correct node: assigning = node ids securely, maintaining routing tables securely, and forwarding = messages securely. To obtain a node id, a node would have to go through = a certification authority. The authority would then give the node a = cryptographic key based on its IP address. The problem is that a node = could request multiple certificates. To prevent this, you might have to = pay for a certificate, making it costly (literally) to get multiple = identities. The problem is the central authority: in general, it is = something you don't want in a p2p network. Since computational power is = limited, giving out cryptographic puzzles would limit the amount of time = between new IDs, but a powerful node would be able to overcome this = easily. The routing table turns into two routing tables. The first is = the same as any system which uses proximity information or which can be = duped into choosing neighbors. The backup routing table does not take = proximity into account and therefore, while it will not route as = efficiently, it is not as susceptible to attack. Secure routing tries = to detect routing failure and then re-routed the messages appropriately. = This seems like a failed part of the paper and in the end the authors = suggest using a flooding or gossip like system to get the message to its = destination: a complete failure in a structured network. ------=_NextPart_000_000D_01C636D6.FC605230 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
The Sybil attack paper points out that = any attacker=20 who has enough resources (relative to the weakest person in the network) = can=20 dupe himself many times.  In other words, an attacker can fake = multiple=20 identities.  This would kill the security in any system which = heavily=20 relies on redundancy for its security.  To help show this, the = paper=20 introduces 4 lemmas.  The first one states that if you are x times = more=20 privileged in terms of resources than another node, you can present = floor(x)=20 identities to a local entity.  The second lemma states that unless = all=20 entities are validated simultaneously, any single entity can present = itself=20 through distinct identities as many times as it wishes.  Lemma 3 = says that=20 even with trusted entities, if there are enough faulty entities or they = have=20 enough processing power, they can still take over.  Lemma 4 builds = upon=20 others by saying that unless multiple nodes coordinate time intervals, = an=20 attacker does not need too many resources to hurt the = network.
 
An Eclipse attack is when an attacker = tries to fill=20 the neighbor sets of nonfaulty nodes with faulty nodes.  This would = ensure=20 that that node would not be able to effectively communicate with the=20 network.  While unstructured networks are most effected by this = attack, it=20 is a severe problem in structured p2p systems as well.  A key = insight is=20 that an attacker node would then have a large in-degree and a large = out-degree.  By limiting neighbor selection to those nodes who have = low=20 indegree and low outdegree, a node could assume that its neighbor is=20 legitimate.  A node could therefore ask any other node to give it = their=20 neighbor set and back-pointer set.  If the requesting node is not = in it or=20 the sets are too large, then that node is removed from its neighbor = set. =20 This will ensure that a malicious node cannot insert itself into the = neighbor=20 set.  The obvious counter to this is to put the requesting node = into the=20 set before sending the set back.  To counter against this, the = requesting=20 node anonymously routes the request for the two sets through nodes it=20 trusts.
    In the end, it seems = like there=20 is a tradeoff between querying neighbors and reliability.  The more = you=20 query, the more reliable the network, but this causes large bandwidth=20 overhead.  The less you query, the less bandwidth, but your = neighbors might=20 not be reliable.  The other issue is that the paper seems to assume = that=20 the network is already immune to a Sybil attack, which seems to be a=20 chicken-and-egg problem.
 
In the secure routing paper, the = authors argue that=20 three things are necessary to ensure that a message will reach a correct = node:=20 assigning node ids securely, maintaining routing tables securely, and = forwarding=20 messages securely.  To obtain a node id, a node would have to go = through a=20 certification authority.  The authority would then give the node a=20 cryptographic key based on its IP address.  The problem is that a = node=20 could request multiple certificates.  To prevent this, you might = have to=20 pay for a certificate, making it costly (literally) to get multiple=20 identities.  The problem is the central authority: in general, it = is=20 something you don't want in a p2p network.  Since computational = power is=20 limited, giving out cryptographic puzzles would limit the amount of time = between=20 new IDs, but a powerful node would be able to overcome this = easily.  The=20 routing table turns into two routing tables.  The first is the same = as any=20 system which uses proximity information or which can be duped into = choosing=20 neighbors.  The backup routing table does not take proximity into = account=20 and therefore, while it will not route as efficiently, it is not as = susceptible to attack.  Secure routing tries to detect routing = failure and=20 then re-routed the messages appropriately.  This seems like a = failed part=20 of the paper and in the end the authors suggest using a flooding or = gossip like=20 system to get the message to its destination: a complete failure in a = structured=20 network.
------=_NextPart_000_000D_01C636D6.FC605230-- From nsg7@cornell.edu Tue Feb 21 11:18:46 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 k1LGIjt13453 for ; Tue, 21 Feb 2006 11:18:45 -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 k1LGIiO5000613 for ; Tue, 21 Feb 2006 11:18:44 -0500 (EST) Received: from 132.236.227.119 by webmail.cornell.edu with HTTP; Tue, 21 Feb 2006 11:18:45 -0500 (EST) Message-ID: <1685.132.236.227.119.1140538725.squirrel@webmail.cornell.edu> Date: Tue, 21 Feb 2006 11:18:45 -0500 (EST) Subject: PAPER 8 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 "The Sybil Attack" presents four lemmas regarding properties of nodeid assignment hijacking (called the Sybil attack) in structured p2p overlays. The Sybil attack is simply misrepresenting your identity, specifically one entity might present several overlay identities in order to launch some sort of attack (a weakness of the overlay systems we've studied so far). The four lemmas presented fall into two categories. The first two lemmas relate to direct identity verification. The first states that even in the presence of distinct identity verification methods (e.g. computational puzzles), a malicous entity can misrepresent g identities where g is the lowerbound on the resource disparity in a hetrogenous network. The second lemma states that if these verifications aren't done concurrently for every verified identity, attackers can misrepresent an unbounded number of identities. The next two lemmas relate to indirect or distributed identity verification (where one node depends on some group of other trusted nodes to verify the identity of a new node). The first of these state state that a group of malicious identities (e.g. falsely verified by exploiting the first two lemmas) can collude to misrepresent an arbitrarily large number of identities. The final lemma states that, again, these verification processes must be done concurrently (in this case concurrently across the trusted set of identities) or malicious entities can easily misrepresent an arbitrarily large number of identities. "Defending against Eclipse..." presents another type of attack where malicious nodes "eclipse" a correct node by joining the correct node's neighbor set. Here no analytic model is presented, but a possible solution is proposed where indegree and outdegree bounds are enforced. This enforcement is done by anonymous auditing where a node x is verified by its neighbor's or by nodes in the backpointer set of x (nodes who have x as a neighbor). this anonymous auditing technique involves the use of a set of intermediary nodes used by all auditing nodes to preserve the aynonymity of the auditors and guarantee that with high probability a malicious node x is detected. "Secure Routing..." (in addition to representing Pastry, Tapestry, CAN, and Chord) presents a scheme for secure routing consisting of three elements: (1) secure assignment of nodeids (preventing Sybil attacks), (2) secure routing table maintenance (preventing Eclipse attacks) and (3) secure message forwarding (guaranteeing that at least one copy of a message reaches its destination(s)). These three elements are presented first as an abstraction, and arguments are made throughout that these three elements are important for various security properties of p2p networks. Implementations for these elements are also presented (along with so-called rejected approaches). A presented approach to (1) is to use centralized certificate authorities to issue a nodeid to ip address binding to each node as it enters the overlay. An alternative (rejected approach) uses distributed assignment where nodes are required to solve some puzzel to get a nodeid which can be later easily verified by other nodes ("The Sybil Attack" already pointed out why this does not guarantee safety from Sybil attacks). A presented approach to (2) is to augment the existing routing information with a "constrained" routing table at each node such that this constrained table (along with a solution for (1)) with high probability provides successful routing. Finally, a solution to (3) is presented with uses (2) along with redundant routing and a "failure test" to guarantee that messages are delivered. The standard routing methods provided by the overlay are used and the failure test is applied. If a failure is detected, redundant, diverse routes are used to send message copies to their destinations. "The Sybil Attack" presents four simple, analytical results which reveal an inherrent problem facing p2p systems. However, no solution is proposed. And no mitigating techniques are suggested or analyzed and the concept of mitigating techniques (to increase the cost of an attack above the benefit received by the attacker) are dismissed. This type of technique may be possible and may be sufficient in many networks. The other two papers present solutions and some empirical results, but fail to build a strong (and simple) analytical framework in which to understand the problem and reason about solutions. "Secure Routing..." introduces many changes to existing systems without analyzing how the properties provided by the underlying systems are changed (except to note that performance will degrade, perhaps significantly). It seems that these papers strive to guarantee security properties at the significant cost of performance which the underlying systems sought to provide in the first place. A deeper study of existing, real-world systems might reveal the security requirements of those systems and solutions which meet those needs, without sacrificing performance requirements might be possible. In addition, a better analytical framework to model these systems and the salient properties might reveal a simpler solution which (while perhaps not guaranteeing the various properties) provides some probability to address system needs. From victoria@cs.hmc.edu Tue Feb 21 12:36:03 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from turing.cs.hmc.edu (turing.cs.hmc.edu [134.173.42.99]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1LHa3t06257 for ; Tue, 21 Feb 2006 12:36:03 -0500 (EST) Received: by turing.cs.hmc.edu (Postfix, from userid 34382) id 10F265322B; Tue, 21 Feb 2006 09:35:57 -0800 (PST) Date: Tue, 21 Feb 2006 09:35:56 -0800 From: Victoria Krafft To: egs+summary@cs.cornell.edu Subject: PAPER 8 Message-ID: <20060221173556.GA11127@cs.hmc.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.1i All of the papers for this class examine the problems inherent in securing a peer-to-peer network. Within a peer-to-peer network, we need some way of authenticating the nodes; otherwise, a sibyl attack, where a single physical machine can join the network many times. If a single machine can do this, it compromises the network's reliability, since that machine crashing will cause a large portion of the network to fail. Ideally, we would like each physical machine which will be present in the network to have a unique identifier, such as a public/private key pair signed by a trusted authority. However, we cannot use a single central authority, because then that authority could be compromised. In the Sybil paper, it is shown that without a logically centralized authority, Sybil attacks are always possible unless some rather implausible assumptions are made about coordination and resource parity among entities in the network. The next paper, on Eclipse attacks, paints an even grimmer picture. In many peer-to-peer networks, it is possible for a small number of nodes to eclipse nodes in the network, dropping or rerouting messages to those nodes. Some types of peer-to-peer networks are more vulnerable to this than others. The authors propose that Eclipse attacks can be defended against by setting limits on the in degree of nodes in the network, since attacking nodes will need many in going connections. Those limits will be enforced by anonymous auditing. This entire structure relies on nodes having certified keys, and only a small portion of the network being compromised. Ignoring that little detail, it seems that this scheme would cause increased network traffic, especially if the attacking nodes attempted to disrupt the network by running frequent audits on other nodes. There is no information about the impact of auditing on the network performance, especially in a large network, where a small fraction of the nodes auditing the same node at the same time might overwhelm its network connection. The third paper proposes a secure routing protocol which works efficiently for small numbers of compromised nodes, and continues to work until up to 25% of the nodes in the network have been compromised. They assume the existence of a trusted CA, which assigns appropriate and non-conflicting node ids. Once secure node ids are assigned, the next area of concern is the routing table. While only a fraction of the nodes in the network are bad, they could provide bad routing data, and fill the routing tables of valid nodes with more faulty nodes. The proposed solution is to maintain two routing tables, one using network proximity to provide improved service, and one constrained so that it cannot be filled with faulty nodes. The proximity table will be used unless problems with message delivery are detected, at which point a node will fall back on the constrained table. To ensure that a message is routed properly, the node sending it tries a failure test, and if the results of the message are not correct, then the node will have its neighbors send out the message as well. By only relying on redundant routing when there is a problem with the network, this scheme does not produce too much overhead for a small number of faulty nodes. The main problem I have with this scheme is that it prevents many of the optimizations normally used to improve peer-to-peer performance. Load balancing by changing node ids or using virtual nodes is not possible. This scheme also does not help unstructured networks such as Gnutella. -- Victoria Krafft From kelvinso@cs.cornell.edu Tue Feb 21 12:39:18 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-0.9 required=5.0 tests=ALL_TRUSTED,AWL autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe1.cs.cornell.edu (exchfenlb-1.cs.cornell.edu [128.84.97.33]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1LHdHt07564 for ; Tue, 21 Feb 2006 12:39:17 -0500 (EST) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 12:01:11 -0500 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" X-MimeOLE: Produced By Microsoft Exchange V6.5 Subject: Paper 8 Date: Tue, 21 Feb 2006 12:00:45 -0500 Message-ID: <2AA53C9C489B0049B43E56D28088677B52D475@EXCHVS2.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: Paper 8 Thread-Index: AcY3CFriXUaK6m0gS0KwUfkAioO90Q== From: "Kelvin So" To: X-OriginalArrivalTime: 21 Feb 2006 17:01:11.0971 (UTC) FILETIME=[6AEB4F30:01C63708] Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k1LHdHt07564 The first paper, "Sybil Attack," describes an attack where one faulty entity creates multiple entities in the overlay network. Using multiple identities in the network, one faulty entity can control a large portion of the overlay network and undermine its function. One way to solve such a problem is to use centralized trusted authorities to sign certificate for each entity. The paper claims that the system without a trusted authority is not practical to use resource-demanding challenges, such as computation, storage or communication challenges, to validate one's identity because node needs to send out challenges concurrently and it assumes the system has uniform resource constraints. Also, if we indirectly validate entities using vouchers, the number of vouchers has to be greater than the number of faulty nodes. As system scales to larger size, it is not feasible to use such a technique to verify node's identity to prevent Sybil Attack. The second paper, "Defending against Eclipse attacks on overlay networks," presents a more general attack which controls a large fraction of the neighbors' pointers of correct nodes. Defense for Sybil attack may not work for Eclipse Attack, because faulty nodes can manipulate the overlay maintenance algorithm instead of presenting multiple identities to launch Eclipse attack. In this paper, it presents a general technique by limiting the in-degree and out-degree of a node to minimize Eclipse Attack on any overlay network. Using such a technique, the overlay network does not require any special structure in the overlay maintenance algorithm. To audit the in-degree and out-degree of a node, each node needs to maintain a back pointer list. Periodically, node sends out challenges to verify the in-degree and out-degree of a node. Also, it also needs to implement an anonymous channel such that nodes do not know who challenges the node and the reply only comes from challenged node. Using such a defense, the construction of overlay network is more constrained and optimization, such as PNS, does not perform as well in such a constrained network (because it has fewer neighbors to pick from). The third paper, "Secure routing for structured peer-to-peer overlay networks," presents techniques to provide security in structured overlay network. It describes three major components in secure routing, which include a secure assignment of node identifiers, secure routing table maintenance, and secure message forwarding. In secure assignment of node id, it uses certified node id to against Sybil Attack. For secure routing table maintenance, it uses two routing tables, one normal pastry table and another constrained version of pastry table, which points to the closest node Id in id space instead of using proximity metric. For secure message forwarding, it uses routing failure test by comparing the densities of nodes to test if the root is likely to be correct for the key. If the test returns negative, it will uses redundant routing to route to the correct node. From tudorm@cs.cornell.edu Tue Feb 21 12:58:40 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1LHwet13333 for ; Tue, 21 Feb 2006 12:58:40 -0500 (EST) Received: from exchfe2.cs.cornell.edu ([128.84.97.28]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 12:58:40 -0500 Received: from [128.84.223.148] ([128.84.223.148]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 12:58:40 -0500 Message-ID: <43FB54CC.9090702@cs.cornell.edu> Date: Tue, 21 Feb 2006 12:58:36 -0500 From: Tudor Marian User-Agent: Thunderbird 1.5 (X11/20051201) MIME-Version: 1.0 To: egs+summary@cs.cornell.edu Subject: PAPER 8 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 21 Feb 2006 17:58:40.0162 (UTC) FILETIME=[72338020:01C63710] The paper presents a type of attack (Sybil) upon large p2p systems, and argues that in the absence of a centralized authority this type of attacks are always possible. A Sybil attack unfolds when some entity is capable of forging multiple identities, thus the rest of the peers are oblivious to the fact that a single entity is chosen instead of multiple distinct identities during the protocol. Such attacks are always possible since an entity can use all its available resources in projecting the image of several valid identities, and thus "convince" other entities. Moreover, if entities are not validated simultaneously, a large number of distinct identities can be presented, and thus the malicious node may grow its identity numbers indefinitely. Without a central identification authority, p2p systems are vulnerable to such attacks, therefore we see a tradeoff between scale and security on one side and heterogeneity and security on the other size - the latter is due to the fact that if all entities have virtually identical resources Sybil attacks are less disruptive. The paper discusses and proposes a solution to the Eclipse attacks on overlay networks. More general then the Sybil ones, the Eclipse attack is initiated by some attacker that controls a significant fraction of the nodes in the neighborhood of correct nodes, thus "eclipsing" the correct ones and preventing them to take part in the protocol. The defense against such an attack proposed by the authors consists of limiting the indegree and outdegree of the nodes. The reason behind this is that attacker nodes have a larger indegree since more nodes connect to the faulty ones as opposed to the eclipsed ones. Secondly, imposing just an indegree limit brings upon the possibility of a different attack, namely malicious nodes may consume all the incoming slots of correct nodes, therefore the limit must be imposed on the outdegree as well. The bounds are enforced by an auditing scheme, when the challenger is anonymous, thus forcing the challenged to respond correctly. The downfall is that in structured networks an attacker can "guess" with high accuracy where the challenge originated from, therefore the auditing might be unsuccessful. The paper considers the general problem of security and how one can address it in the context of p2p overlays. First they abstract out the overlay networks and their properties such that there is no particular system they have in mind, even though their implementation was done on Pastry. They describe a series of attacks that can be performed and identify secure routing as the main building blocks that secure overlays can take advantage of. Secure routing is split into three subproblems: secure node ID assignment, secure routing table maintenance, and secure message forwarding. Secure node ID assignment requires the existence of a centralized CA (as we have seen proved by the first paper). Secure routing table maintenance is achieved by imposing stringent constrains on the routing table entries, and the fact that nodeID's have been assigned securely. Secure forwarding is a 2-phase operation, first a fault is detected - by means of a timeout or a failure test upon the replica roots, and second, if there was a failure then the message is resent but on multiple paths, hoping they are disjoint and thus at least one reaching the destination with high probability. The experimental evaluation did not include the resource cost of the secure methods. Tudor From okennedy@cs.cornell.edu Tue Feb 21 13:19:19 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe1.cs.cornell.edu (exchfenlb-1.cs.cornell.edu [128.84.97.33]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1LIJJt20583 for ; Tue, 21 Feb 2006 13:19:19 -0500 (EST) Received: from exchfe2.cs.cornell.edu ([128.84.97.34]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 13:16:24 -0500 Received: from [128.84.98.36] ([128.84.98.36]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Tue, 21 Feb 2006 13:16:24 -0500 Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <336FE6BD-7FF1-452C-92C3-7CC3DA488AF5@cs.cornell.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: Oliver Kennedy Subject: PAPER 8 Date: Tue, 21 Feb 2006 13:16:30 -0500 X-Mailer: Apple Mail (2.746.2) X-OriginalArrivalTime: 21 Feb 2006 18:16:24.0469 (UTC) FILETIME=[EC93DC50:01C63712] This weeks papers present two general classes of attacks on P2P networks, and provide a set of potential counters to those attacks. The first paper attempts to show that without a centralized authority to map entities to identities, it is not possible to assert that two identities belong to distinct entities. This leads to what they call a Sybil attack, where one entity enters the P2P network under multiple identities in an attempt to disrupt the network's operations. By overwhelming the number of fair nodes with its own identities, an attacker can partition the network, bypass security based on separation of effort, and with high probability disrupt access to certain objects. The paper goes on to demonstrate the necessity of such a centralized authority, as any other attempt to securely determine the distinctness of two different entities would be infeasible. The second paper presents a more general attack called an eclipse attack. This class of attacks takes advantage of the fact that the only way a node can learn about other nodes is to ask other nodes. If several attackers (or a single attacker with multiple identities) are able to collude, the attacker nodes can refer node requests to other attacker nodes. By doing this, a single attacker can eventually gain near total control over all routing in the network. This can result in dropped queries, faulty responses, or any number of other network disruptions. The paper suggests several responses. Firstly, nodes may be restricted to a certain number of connections. Assuming it is possible to audit an attacker for the number of nodes he is connected to, the attacker will not be able to compromise more traffic than a normal node would be able to. They propose an auditing scheme where a node keeps track of all of its connections. Periodically it asks all the nodes that it is connected to to send it a list of their connections. If any of the results is too big or does not contain the original node, the offending node is removed. In order to prevent the attacker from falsifying this list on the spot, the request is routed through an "anonymizer" chosen from the set of nodes closest to the potential attacker. Of course, if an attacker is able to establish a subnet or a range of addresses of compromised nodes with itself at the center, the anonymizer approach fails with high probability. Finally the last paper points out three aspects of P2P networks where security issues are most likely to occur in structured P2P networks. Firstly, attacks on the nodeID. Allowing clients to choose their own nodeID (or allowing them to choose from a large set of potential nodeIDs) results in an attacker being able perform several disruptive attacks. By using the certificate authority suggested by the Sybil paper to give each node a static nodeID, this problem may be avoided. They concur that distributed algorithms are insufficient for this task. The second potential vulnerability is in the routing algorithm. A faulty node could intercept messages not meant for it and attempt to populate a valid node's routing table with other faulty nodes. The paper suggests solving this by eliminating the fuzziness included in the node selection. While a node would typically pick the node in a range with the best ping, now a particular node is deterministically selected. This leads to the last of the problems, in particular the routing algorithm. A node is capable of intercepting all messages that pass through it and even with encryption techniques, it could still drop the packets. In order to ensure that the message arrives intact at the destination with high probability, the paper suggests sending multiple copies at once. - Oliver Kennedy There cannot be a crisis next week. My schedule is already full. -- Henry Kissinger From ymir.vigfusson@gmail.com Tue Feb 21 13:24:34 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from nproxy.gmail.com (nproxy.gmail.com [64.233.182.202] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1LIOXt22340 for ; Tue, 21 Feb 2006 13:24:33 -0500 (EST) Received: by nproxy.gmail.com with SMTP id o25so843632nfa for ; Tue, 21 Feb 2006 10:24:32 -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=W5QpCWDK4Bbm8PeC/6kABeLhFWfSJTCvYyY1Lq4CVU5ybo2xz+FnKl7uAZ9w+WJtbZm9/WvEaUwDqgb5pJ2Tj5Elzs/EmZjMYWAUkKtCgf9ctSkYew7c0d/Ef8h2TTP3rJ2xUhd1vqskm8nohHEGZ7FSKbRIDSUt2hgRS0Et5Xw= Received: by 10.49.68.13 with SMTP id v13mr1566227nfk; Tue, 21 Feb 2006 10:24:32 -0800 (PST) Received: by 10.48.217.10 with HTTP; Tue, 21 Feb 2006 10:24:32 -0800 (PST) Message-ID: <9302f1e20602211024s2d139ec5nf60961848e8c2449@mail.gmail.com> Date: Tue, 21 Feb 2006 13:24:32 -0500 From: "Ymir Vigfusson" To: egs+summary@cs.cornell.edu Subject: PAPER 8 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 k1LIOXt22340 Paper 1: Secure routing for structured peer-to-peer overlay networks Paper 2: The Sybil attack? Paper 3: Defending Against Eclipse Attacks on Overlay Networks. In Paper 1 the authors address security issues in overlay networks, especially large-scale attacks when a fraction f (0 <= f < 1) of the nodes on the network may be faulty/malicious in coalitions of size of up c*f (where 1/N <= c <= f). The first issue they address is thwarting attacks directed at replica roots by a 'secure routing primitive' which ensures that when a legitimate node asks for content, all non-faulty replica roots are reached w.h.p. The paper then elaborates on how this primitive is to be accomplished, and discusses three problems that need to be solved. 1) Securely assign nodeIDs to nodes: If an attacker could choose his nodeID, or forge enough clones to control a large enough fraction of the nodeID space (Sybil attack), she could take on the overlay network (e.g. route traffic to her, partition the ring, etc.) The authors mention the use of central certification of nodeIDs, but this solution is awkward for a number of reasons - it relies on central figures which counters the p2p paradigm, and their assumption that malicious users usually only control a few IP addresses is based only on faith. They then move on to the terrible idea of charging users $20 for a nodeID, or binding actual identities to nodeIDs (confiscating anonymity) and argue that this should prevent Sybil attacks. Fortunately, the authors realize that these ideas are not a solution, and conclude by listing other ideas, such as solving crypto puzzles or computing particular SHA1 hashes, all of these are based on the assumption that the attacker has very limited resources to mount an attack. 2) Securely maintain the routing tables: The authors argue that securely assigning nodeIDs is necessary but not sufficient to thwart attacks on the routing table maintenance protocol. Tapestry and Pastry use overlay locality when constructing their rings, and are suspectible to attacks where malicious users lie about their proximity. Also, they are example of systems without strong contraints on the nodeIDs in the routing tables, and are thus suspectible to attack. The authors propose that a viable solution is to impose constraints on the routing table, or by having an additional routing table with heavy contraints (ala Chord). 3) Securely forward messages: When 1) and 2) are in effect, an attacker may still choose not to forward messages, and even when f is small, this attack is effective. This is prevented by applying a failure test to see if the messages was routed, and if not, use some redundant route. The paper then spends some pages on describing how a statistical failure test can be done efficiently, and conclude with a model where that the probability of a false positive is about 12% (when ignoring node suppression attacks). This section needs some more subsequent work. Next, the paper describes how redundant routing can be done as they address the problem of ensuring the routes are diverse. The describe a technique called neighbour set anycast where "copies of a message are sent towards the destination key until you reach a node that has the key's root in its neighbour set. It then uses detailed knowledge that such a node has about the portion of the identifier space around the destination key to ensure that correct replica roots receive a copy of the message." Redundant routing is then compared with iterative routing where you iteratively look up the next hop in the routing table, keeping track of where you went, until you find the root of the destinatio key. It turns out that this is expensive. This section then concludes with performance analysis of redundant routing. The article concludes with a description of self-certifying data (data whose integrity can be verified by the client) to minimize the overhead incurred by implementing the ideas above. Paper 2 discusses the Sybil attack in which a potentially malicious user forges multiple identities. The paper shows that for practical purposes, it is impossible to determine if identities are distinct in a distributed environment with no prior information available. The paper formalizes this by modelling a generic distributed environment. It then proceeds to show that for direct identity validation, a malicious user can counterfeit a constant number of multiple identities even when severely resource constrained, and that these identities must be verified simultaneously, otherwise the number is unbounded. Larger scale networks exacerbate this problem. For indirect validation (you accept entities that are accepted by already accepted entities), a sufficiently large set of malicious users can counterfeit an unbounded number of identities, and that all entities in the system need to perform identity validations concurrently, otherwise the each faulty entity can counterfeit a constant number of multiple entities. Again, this problem grows as the system size increases. The paper is brief, and does not go into full depth of the obstructive power that malicious entities can have. Paper 3 presents a so-called Eclipse attack which is a generalized version of the Sybil attack. Here, malicious users can also attack the routing table maintenance mechanism so that the number of nodes that the attacker has full control over grows with time as maintenance messages are infiltrated (this is what Paper 1 presented as one of the main security problems in p2p networks). The authors propose a mechanism called anonymous auditing (you don't know who is challenging you) that attempts to bound the degrees of the nodes. They conclude by showing that this line of defense is effective by providing some experimental results. The authors identify some weaknesses of their approach, namely that the ideal hacker mechanism need be identified, and that anonymous auditing needs to be evolved. From asr32@cornell.edu Tue Feb 21 20:57:39 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,MAILTO_TO_SPAM_ADDR autolearn=no 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 k1M1vdt29859 for ; Tue, 21 Feb 2006 20:57:39 -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 k1M1vcX5017333 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 21 Feb 2006 20:57:38 -0500 (EST) Message-Id: <6.2.1.2.2.20060221205731.031c4af8@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Tue, 21 Feb 2006 20:57:45 -0500 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 8 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sybil: A Sybil attack is when a given principal acquires many different IDs, in order to take control of a disproportionate fraction of the network, to do damage. A Sybil attack, properly defined, is a building block of some other attack. In order to prove strong security properties, it would be very nice to be able to show that distinct machines in a P2P network are owned by different principals. Alas, the central result of this paper is that there are no good strategies for limiting Sybil attacks. In particular, techniques for directly proving that two hosts are distinct via network have an error margin proportional to the difference in resources between a "powerful" host and a "weak" one. Different hosts must be tested simultaneously, rendering distributed challenges difficult. Vouching schemes are also problematic. The Sybil paper unfortunately does a fairly shallow analysis. It implicitly assumes that all authentication must be done across the network, through messages. It assumes that every malicious node has a valid identity. It implicitly assumes that identities are either accepted or not, with no middle ground. Eclipse: In an eclipse attack, the attacker attempts to inject faulty nodes into every entry in the target host's routing table, with an eye to preventing proper overlay operations. In the end, the target host may have all its network operations mediated through hostile nodes. To make this attack harder, the authors propose to limit the degree of nodes in the overlay network. They propose a protocol for this, in which nodes can anonymously query their neighbors to verify that their neighbor's table includes them, and has a legal degree. If not, then that neighbor is dropped. This defense is only partial. The anonymous query protocol proposed has a number of weaknesses. If an attacker controls a node and its entire anonymity set, the protocol fails. An attacker can also cause innocent nodes to be marked as suspicious by falsifying their responses. And even if the protocol works properly, an attacker's fraction of routing table entries can still be substantially higher than their fraction of overall nodes. Secure routing on structured overlays: This paper proposes a general scheme for reliable delivery of messages on peer-to-peer networks, in the presence of malicious nodes. Messages are sent redundantly, to each of several root nodes for a given object. The authors propose to use two routing tables, one optimized for speed, the other constrained deterministically to limit an attacker's flexibility. This does allow something otherwise impossible--very reliable behavior, with a substantial fraction of the network compromised. The protocol fails when more than around 25% of nodes are compromised. When it does work, the proposed protocol is quite expensive, with substantial time and message cost; an attacker can easily force it every time, which would significantly degrade the network. Another weakness is that the paper does not offer suggestions for cheaper protocols when the threat level is less severe. Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From gp72@cornell.edu Fri May 12 01:30:19 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=BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from iago.cs.cornell.edu (iago.cs.cornell.edu [128.84.96.10]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k4C5UJ216505 for ; Fri, 12 May 2006 01:30:19 -0400 (EDT) Received: from postoffice10.mail.cornell.edu ([132.236.56.14]) by iago.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Fri, 12 May 2006 01:29:44 -0400 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 k4C5TgWV003831; Fri, 12 May 2006 01:29:43 -0400 (EDT) Received: from 128.84.98.245 by webmail.cornell.edu with HTTP; Fri, 12 May 2006 01:29:43 -0400 (EDT) Message-ID: <3469.128.84.98.245.1147411783.squirrel@webmail.cornell.edu> In-Reply-To: <2537.128.84.98.245.1147406914.squirrel@webmail.cornell.edu> References: <2537.128.84.98.245.1147406914.squirrel@webmail.cornell.edu> Date: Fri, 12 May 2006 01:29:43 -0400 (EDT) Subject: PAPER 8 From: "Gopal Parameswaran" To: egs+summary@cs.cornell.edu Cc: gp72@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 X-OriginalArrivalTime: 12 May 2006 05:29:44.0239 (UTC) FILETIME=[1359CBF0:01C67585] Sybil Attack In this paper the author discusses the effects of faulty or hostile remote computing elements, which could present more than one identity and can control a portion of the network and undermine the redundancy in the system and cause failures. Systems usually utilize replication of tasks across multiple remote sites for failure prevention or fragment the tasks across multiple nodes for privacy. The author argues that a distributed environment needs a centralized authority to prevent such attacks. However the presence of a centralized authority would destroy the anonymity of the nodes in the network that undermines the peer-to-peer network. Sybil attack or forging multiple identities in a distributed certifying environment as opposed to a centralized certifying authority could be compromised at startup by malignant nodes that join the network initially and provide certification for other bad nodes. The author states that based on a PKI based solution with a centralized certifying authority is the solution. However the author has not taken into effect the group effect of good certifying nodes and bad certifying nodes and hasn’t done enough study before denouncing a distributed certifying system. A distributed certifying system is both practical and reliable with slight modifications where a centralized server only monitors and certifies a certain set of certifying nodes. AS the trust in the network spreads any certifying node or set of nodes that is malignant reports to the a set of its neighbor certifying nodes of malignant nodes and such certifying nodes can lose its rights to provide certification and can be revoked by a central certifying authority. Thus the central certifying node only takes action when it receives reports of malignant nodes that have been certified as otherwise and in which case it goes for the node that certified it. Thus in course of time a set of certified nodes would emerge which are not malignant. Thus a co-operative certifying authority would work where the distributed would fail. Eclipse Attacks & Secure Routing for Structured peer to peer networks Eclipse attacks are more general than Sybil attacks are usually launched after a Sybil attack where a portion of the network is controlled and the efforts are made to disrupt the routing in the overlay network. The main purpose is to prevent correct overlay operation. In Eclipse attacks the attacker even if controlling only a small fraction of the nodes can still launch an attack by manipulating the overlay algorithm. In an eclipse attack eventually the attacker gets control over the whole network. The authors suggests an approach based on choosing neighbors based on a threshold value for the number of in connections and out connections for each neighbor to be added as a neighbor. This limits the attack since the degree of the attacking nodes must be higher than the average degree of number of neighbors and number of neighbors refereeing to each attacking node. So when a value is chosen that is below that of the average for the network then the attack can be thwarted. Implementation of the protocol is done by enforcing degree bounds by auditing the neighbor nodes for its in degree and based on if it exceeds the threshold it removes the node from the list or maintains it in its list besides adding a random nonce to ensure the authenticity of the replies from the neighbor nodes. In the paper Secure Routing the authors follow up on the earlier paper where Eclipse attacks were discussed and dwells into the impact on Pastry CAN, Chord and Tapestry and proposes a secure routing protocol that is based on sending multiple messages and in triggering failures in the routes where the messages timed out without a response and is based on the assumption that the average density of the good nodes is more than that of faulty nodes.