From tmroeder@CS.Cornell.EDU Wed Nov 20 19:43:33 2002 Received: from dhcp99-96.cs.cornell.edu (dhcp99-96.cs.cornell.edu [128.84.99.96]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAL0hX914957 for ; Wed, 20 Nov 2002 19:43:33 -0500 (EST) Received: (from tmroeder@localhost) by dhcp99-96.cs.cornell.edu (8.11.6/8.11.6) id gAL0hXV24323; Wed, 20 Nov 2002 19:43:33 -0500 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15836.11317.119317.700559@dhcp99-96.cs.cornell.edu> Date: Wed, 20 Nov 2002 19:43:33 -0500 To: Emin Gun Sirer Subject: 615 PAPER #70 X-Mailer: VM 7.07 under Emacs 21.2.1 Today's paper examines methods to repulse the attacks to which the various structured P2P systems that we have examined are vulnerable. Each of Pastry, Tapestry, Chord, and CAN have similar vulnerabilities, which the paper tries to overcome via various changes to the protocols to make the routing secure. As usual, this is in the language of defending against Byzantine failures of nodes in the system. The first attacks described are Sybil attacks and nodeId choice attacks. Their solution is to have a centralized certification authority, which to me is not an acceptable alternative. In what sense is a system P2P if it is regulated by a central authority? I would prefer a web of trust model or some sort of similar method where you choose who to trust (either based on outside knowledge, past and current experience, or transitive trust relationships). The idea behind their central authority is sensible: to keep large number of attacker nodes off the network, they must commit some amount of resources. I don't believe that money will do the job, given the resources of some entities that I would consider hostile. They then try to counter attacks on the routing infrastructure, and in particular those that prevent nodes from getting a real, current copy of a particular object which has already been inserted into the network. They do this by having a separate method of routing which is activated if they believe that they cannot go through the regular route that the protocol would suggest. They devise a heuristic by which they can determine if the information they have does not represent the real state of the system. They run simulations of Pastry to show that as the percentage of compromised nodes rises, it becomes very difficult to route correctly. In general, the paper addresses many of the concerns that have been raised in class, and does so in a fairly reasonable way for most of the cases. From ag75@cornell.edu Thu Nov 21 03:05:43 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAL85g916500 for ; Thu, 21 Nov 2002 03:05:43 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id DAA18855 for ; Thu, 21 Nov 2002 03:05:40 -0500 (EST) Date: Thu, 21 Nov 2002 03:05:40 -0500 (EST) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 70 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The paper we read for today describes attacks, against structured P2P overlay networks, aimed at preventing correct message delivery and presents defenses to these attacks. The authors identify secure routing as a key building block needed to defend against these attacks. Secure routing ensures that the message is eventually delivered, despite nodes that may corrupt, drop or misroute the message and that the message is delivered to all legitimate replica roots for the key, despite nodes that may attempt to impersonate a replica root. Secure routing requires a secure assignment of node identifiers, secure routing table maintenance, and secure message forwarding. The authors' solution to securing the assignment of nodeIds is to delegate the problem to a central, trusted authority - a CA, which means there is now a single point of failure in the P2P network. In order to secure routing table maintenance, the authors use two routing tables: one that exploits network proximity information for efficient routing, and one that constrains routing table entries. The first routing table is used to forward messages to achieve good performance, while the second one is used only when using the efficient routing technique fails. This is a good solution because it allows for efficient operation when there are no attacks. Finally, the authors achieve secure message forwarding by running a failure test to determine if efficient routing failed and using the more expensive redundant routing if it did. Once again this is a good technique because message forwarding is efficient without attacks. The authors try to make the system more efficient by explaining how using self-certifying data can minimize the use of secure routing. The authors claim that using secure routing allows the system to tolerate up to 25% malicious nodes while providing good performance when the fraction of compromised nodes is small. It would be interesting to see some real simulation results to see just how good the performance is using secure routing when there are no attacks and when there are attacks, but unfortunately the authors do not provide us with them. From shafat@CS.Cornell.EDU Thu Nov 21 03:25:58 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAL8Pv920194 for ; Thu, 21 Nov 2002 03:25:58 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 70 Date: Thu, 21 Nov 2002 03:25:56 -0500 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134FF0@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 70 Thread-Index: AcKRF2MaeY7iROdkR2+R7F37/mTg7g== From: "S. Shafat Zaman" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id gAL8Pv920194 This paper addresses security issues currently faced in p2p overlay protocols, such as Pastry, Chord, CAN and Tapestry. In particular, they aim to employ a Byzantine fault-tolerant model to minimize the degree of damage, malicious or faulty nodes can do over the entire system. The model is independent of the underlying protocol, and the paper uses Pastry as an example, and for performance evaluations. Some of the persiting security problems in p2p networks involve malicious nodes, that can drop or corrupt messages, deliver to another faulty node etc. This calls for an implementation of "secure routing" that can be broked down into three sub-problems: secure nodeID assignment, secure routing table maintenance, and secure message forwarding. The secure nodeID assignment does not give a node to choose any arbitrary nodeID that would seriously compromise the integrity of the network. Their solution to such types of "Sybil attacks" is to assign nodeID certificates by a set of trusted certificate authorities (CA). Using money to control issuing of such certificates is not entirely foolproof either. Binding nodeIDs to real world identities or static IP addresses may be a better solution, but could lead to scalibility issues. Secure routing table maintenance is also a necessity to avoid attackers inserting more than a fraction of corrupt nodeIDs into another node's routing table. They present a solution to this problem that uses two routing tables - the first one is used for efficient routing, and in the case when it fails, the second constrained routing table is used. Finally, secure message forwarding ensures that at least one copy of the message reaches at least one of the replicas of the destination. We don't want the malicious nodes to drop all copies of the messages. The simulation results show that most of the proposed solutions have a good performance with regards to Pastry, and can tolerate upto 25% of the nodes in the system being faulty. From mvp9@cornell.edu Thu Nov 21 03:40:33 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAL8eW923009 for ; Thu, 21 Nov 2002 03:40:32 -0500 (EST) Received: from zoopark.cornell.edu (syr-24-59-74-132.twcny.rr.com [24.59.74.132]) by cornell.edu (8.9.3/8.9.3) with ESMTP id DAA15298 for ; Thu, 21 Nov 2002 03:40:30 -0500 (EST) Message-Id: <5.1.0.14.2.20021121033830.00aec920@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 21 Nov 2002 03:40:18 -0500 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 70 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The focus of this paper is describing and rebutting attacks aimed at distributed hash tables, such as Pastry or Chord. The authors classify the attacks into 3 types according to their targets: assignment of node Id's, routing information maintenance and finally message forwarding. The contribution is listing a moderately detailed set of attacks against each phase of operation and describing some not too complicated schemes that counteract them. The security guarantee that they aim to maintain is that a message sent will be eventually delivered to all legitimate replica roots for its key. Most of the solutions provided are not particularly satisfactory. For example, for securing node id's we are to use certification authorities. While quite powerful, this, as any centralization brings in a host of new problems. Their offers of using money of crypto puzzles are not practical, as they admit. To secure the actual transmission of messages in the face of faulty nodes, they suggest to just send many copies (with some heuristic optimization); far from satisfactory. Although they have considerable correspondence between analytical models and simulation, the details of the latter are not revealed and in either case would not be unequivocal. The self-certifying data seems to be the most attractive of their schemes as it does not in itself require additional load on the network. Although the main concerns are addressed, the solutions are just not impressive, even if their simulations say that the system functions well with 1/3 of the nodes faulting. Something like a voting or data encapsulation or an overlay protocol would be more interesting, but naturally, it's not that simple. This area is ripe for research and if this paper stimulates it, the job is done. From nbs24@cornell.edu Thu Nov 21 10:26:08 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALFQ8923993 for ; Thu, 21 Nov 2002 10:26:08 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id KAA24041; Thu, 21 Nov 2002 10:26:05 -0500 (EST) Date: Thu, 21 Nov 2002 10:26:05 -0500 (EST) From: nbs24@cornell.edu Message-Id: <200211211526.KAA24041@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 64.185.145.94 Subject: 615 PAPER 70 Secure routing for structured peer-to-peer overlay networks In spite of the scalability, fault-tolerance and effective load-balancing provided by structured p2p overlays such as Chord, Pastry, Tapestry and CAN in the construction of various decentralized services like content distribution and network storage, the question of trust is an issue. These overlays are susceptible to various malicious attackers. This paper raises the following concerns and proposes some solutions. Secure assignment of nodes: As in a Sybil attack, an attack has the opportunity to either to select nodeIds that are not random or select an IP address that hashes to a desired interval in the nodeId space. The authors propose the use of a central authority to sign nodeId certificates which are bought with money by an attacker, making the cost of an attack grow with the network size. What if an attacker has no money constraints? I can envisage a rich person’s account being compromised to pay for such an attack. Another solution they propose is to bind nodeIds to real-world identities. However, they admit that these solutions won’t work for small networks. I particularly don’t like the return to a central authority since they represent points of failure. Another ineffective solution they propose is to have nodes solve crypto puzzles. Secure routing table maintenance: An attacker can supply bad routing updates to nodes, thus reducing the probability of a successful route. They propose a locality-aware routing table. For Pastry, this presents several routes and a node picks the entry with minimal network delay from the set of candidates it receives for each routing table slot. For Chord, a node picks the nodeId that is closest to the desired point for the entry, from the set of candidates it receives for each entry. Secure message forwarding: The probability of routing successfully between two correct nodes diminishes quickly with increased network nodes or compromised nodes. The authors propose the use of more expensive redundant routing when a failure test (to determine if a routing worked) returns positive. But yet again, their failure test is not a very accurate one. In my opinion, this paper raises the security concerns in p2p overlays but does not necessarily provide robust solutions. Nana From smw17@cornell.edu Thu Nov 21 10:27:05 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALFR4924081 for ; Thu, 21 Nov 2002 10:27:04 -0500 (EST) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id KAA01303 for ; Thu, 21 Nov 2002 10:27:04 -0500 (EST) Message-ID: <3DDCFA00.8080004@cornell.edu> Date: Thu, 21 Nov 2002 10:21:36 -0500 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.1) Gecko/20020823 Netscape/7.0 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 70 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Secure Routing for Structured P2P Networks The authors of this paper look to achieve two major goals. First, to provide an analysis of the relative (in)security of current P2P networks by demonstrating their vulnerability to a number of different attacks, and second, to modify these networks to permit secure routing. Basic structured P2P networks demonstrate resilience in the face of random node failures, but are quite vulnerable to effects caused by malicious nodes in the system. One of the most basic (and hard to defend against) attacks is a Sybil attack, in which the attacker acquires a large number of nodes in the network. Once an attacker has complete control over a significant number of network nodes, it becomes easier to use these nodes to leverage any of the other attacks mentioned here. The second major point of attack is the routing table. On systems with constrained routing table updates (such as CAN), there is a single node suitable to fill an entry in the routing table. But on systems such as Pastry and Tapestry where routing table entries are intentionally less strict in their definition so as to allow better performance, malicious nodes may take advantage of this freedom to use false routing updates to attempt to fill the routing tables with routes to other compromised nodes. Thus, it is possible for a relatively small number of nodes to collaborate to have a disproportionate effect on the overall network. Finally, nodes may selectively drop, corrupt, or otherwise disrupt normal message traffic. Such an attack can be very effective even for small fractions of compromised nodes, as a multi-hop route need only lose one of its links to function incorrectly. Although normal failures are handled by detecting broken links, these mechanisms do not account for links that are not broken, but are intentionally disruptive. There are a few propsed solutions presented. The Sybil attack is one of the harder attacks to deal with, and the only real solutions provided involve making it expensive in some sense to join the network. While this may reduce the threat in some ways from malicious parties, it does little to protect against intervention by governments or corporations with the resources to force cooperation of a certificate authority in order to monitor content. The general solution to the two remaining attacks is a two-tier approach. The standard algorithm is maintained for normal use, where the primary goal is efficiency. When, however, we detect a routing failure (a query returns a set of replica roots that we consider to be sufficiently unlikely to be the actual set), a second constrained/redundant routing scheme is employed. That is, we make use of a routing table that is formed by a strict set of guidelines, so that malicious nodes cannot significantly influence the contents, and we can send over multiple redundant links, in the hopes that at least one route will not pass through a malicious node. The failure detection is achieved either through a lack of response (timeout), or through the application of the test, which checks that all nodes have a valid certificate, the middle node is the node closest to the key, the nodeID's satisfy the neighbor set definition, and the average distance between nodes is within a fixed multiplicative factor gamma of the local average. Based on their simulations, these additions permit correct routing in networks where up to 25% of the total nodes are faulty and potentially collaborating. It does, however, depend on the random distribution of faulty nodes. Any entity capable of selecting nodeID's at will could easily arrange to occupy two entire leaf sets, which is sufficient to partition the network and require that all non-local traffic passes through a given node. Similarly, nodes may crowd in on a node with objectionable content and effectively excise it from the network. In essence, any node that can either compromise the ID selection, or has a sufficiently large pool of ID's to choose from can employ targeted attacks that greatly reduce the effectiveness of the security features described in this paper. From bd39@cornell.edu Thu Nov 21 10:54:20 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALFsJ900809 for ; Thu, 21 Nov 2002 10:54:19 -0500 (EST) Received: from boweilaptop.cornell.edu (dhcp-128-84-93-87-wifi.ece.cornell.edu [128.84.93.87]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA16154 for ; Thu, 21 Nov 2002 10:54:18 -0500 (EST) Message-Id: <5.1.0.14.2.20021121105049.00b6bd40@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 21 Nov 2002 10:51:33 -0500 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 70 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed PAPER 70 Secure Routing for structured-p2p overlay networks This paper seeks to address the issue of security the routing of peer to peer networks. The authors note that current overlay networks are prone to failure even when a small fraction of nodes become compromised. Also, because of the open structure of a p2p network, malicious nodes can easily participate, making trust and security a large issue. The goal is to provide a way for a non-faulty node to be able to reach all non-faulty members of a set of replicas in the network with high probability in the face of malicious attackers. Secure Assignment of Node IDs: Most of the overlay networks assume a random distribution of node IDs for construction of routes. Attackers can manipulate their IDs to partition the network, or cause a network packets to be routed to nodes under their control. One solution to this is the introduction of a Certificate Authority which signs all assignments of IPs to node ids. In order to prevent an attacker from joining large numbers of nodes, the CA must make joining expensive (literally) or bind them to other secure identifiers. (This seems to be a cop-out since then there is the problem of maintain the security of those identifiers.) Also, node can be made to solve a computationally difficult task before being allowed to join. This doesn't seem to solve the problem either, because a malicious attacker could join en-masse in parallel and finish solving the puzzle very quickly. This does prevent a single machine from joining the network repeatedly. Periodic invalidation of node ids would prevent an attacker from slowly acruing a set of keys, but would also cause all routing in the network to grind to a halt as the nodes recompute their keys. The introduction of a centralized CA seems to not mesh well with the distributed nature of the network. Secure Routing table maintenance: Routing tables updates can be attacked by manipulating proximity information, causing routes to converge towards using a compromised node, or by broadcasting many update messages. The paper proposes keeping two different routing tables, one that is constructed normally using routing latencies and another table in which routing entires are highly constrained for backup routing purposes. The entries in the backup table are acquired by querying many different nodes and taking the closest node found among those, rather than using just one node for the neighborhood set, reducing the probability that a malicious node will be corrupting the entries. This is still susceptible to the sybil attack from above, in which the attacker can always get a group of closest ids. Secure Message forwarding: DoS attacks can be launched by refusing to forward routing packets. Because each path in the routing network is approximately O(log N) long, this gives attacking nodes O(log N) opportunities to drop the routing message. In their experiment, when only 0.5 percent of the nodes in the system were compromised, virtually all routing ceased to be successful. The paper introduces a routing failure test which uses the uniformity of node ID distributions to determine whether or not a replica root set was valid. It seems that this tests is only a rough heuristic at best. Attackers can still manipulate the replica set by suppressing node IDs from the response, which would change the distribution of nodes in the root set, which would cause the inefficient routing to be use more than is necessary. Once a route has been determined to fail, a redundant routing scheme is used. Redundant routing attempts to route through as many different paths as possible by anycasting to its neighborhood set. At each level all of the nodes respond with their neighborhood set that is close to the key, which is then used by the requesting node as the next neighborhood set to route to. Could this scheme be attacked by faking node ids closer and closer to the desired node, arbitrarily delaying the request. Also, how diverse are the routes obtained by anycasting to a neighborhood set, since routes are supposed to quickly converge. From ashieh@CS.Cornell.EDU Thu Nov 21 11:06:44 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALG6h904305 for ; Thu, 21 Nov 2002 11:06:43 -0500 (EST) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id gALG6hw25551 for ; Thu, 21 Nov 2002 11:06:43 -0500 (EST) Date: Thu, 21 Nov 2002 11:06:43 -0500 (EST) From: Alan Shieh To: Subject: 615 PAPER 70 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ** Secure routing for structured peer-to-peer overlay networks This paper contributes identifies some security weaknesses of P2P overlays, and proposes some solutions. P2P security is viewed as a hierarchy of vulnerabilities. At the most basic level, if attackers can choose their own nodeIDs, then they can disrupt the distribution of nodes, as well as focussing limited resources on a subset of the overlay. The solution proposed in this paper is to use a central authority to bind nodeIDs to IP addresses. This way, an attacker cannot manipulate a generation function that is dependent on IP addresses or other such variables. Given this assurance of uniform distribution of attackers in the overlay, nodes can form a globally consistent routing table consisting of nodes close to predetermined points in the ID space without worrying about attackers taking over these points. This prevents a large class of attacks wherein attackers might poison routing tables to create cycles or other strange effects. As this canonical routing table may have poor performance (especially since it will be used for multipath routing), a metric-based routing table (optimized using the standard techniques) is also maintained. This optimized table is used for routing when attackers are not suspected. Possible attacks are detected by comparing the density of nodes in the neighborhood of the originating node, and the replica set returned by routing. The density is expected to be similar in both parts of the network. If the variance in density exceeds a threshold, then the node falls back on safe multipath routing to the destination. However, this test is not precise; in some situations it may be necessary to tolerate a high degree of false positives in order to keep false negatives to a minimum. The authors note that there are a number of ways to avoid the penalty of multipath routing. If the data is self-certifying, that is, freshness is easy to check, or the requestor has access to a signature chain from which replica placements can be authenticated, then malicious activity may be detected with a more precise test. For instance, a datablock has a unique content-dependent hash in CFS, hence any pointers to that datablock from inodes will point only to the correct version. If a node knows which other nodes were in the replica set in the past, and nominating new replicas required the signatures of the previous replica nodes, then the node can simply follow a certificate chain. The replicating nodes need not use multipath routing; rather, they can simply use their neighbor tables to find close alternate routes, move the object, and sign as necessary. * Shortcomings All the mechanisms proposed in this paper are predicated upon the very strong assumption that a centralized authority can be trusted to maintain the appropriate node density in the network, and prevent malicious nodes from procuring large ammounts of keyspace. This seems a terribly bad single point of failure, since a compromise means that bad nodes can park in the canonical points used for constructing the failsafe routing table, and bad nodes can dominate the neighbor set of any arbitrary node. It seems like a certificate chain approach may accumulate errors. For instance, as time progresses it becomes more and more likely for replicas to have been captured by bad nodes at some point in the past, after which point the certificate chain is compromised. * Future work - Investigate more elegant solutions for preventing routing table poisoning. For instance, add tracking information to routing entries. If some routing entries are propagated more widely than usual, then perhaps an attacker is manipulating routing table entries. Unfortunately, any consensus algorithm would be built on top of a suspect routing table to begin with. - Perhaps there is some way to construct a certificate chain on the trace used to construct a routing table. A possible secure basis for such a chain would be the leaf set; a node checking the chain would make sure that the leaf set has the expected density, and then follow the chain of signatures and timestamps from there before trusting any routing table entry. From mp98@cornell.edu Thu Nov 21 11:07:44 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALG7i904449 for ; Thu, 21 Nov 2002 11:07:44 -0500 (EST) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA10612 for ; Thu, 21 Nov 2002 11:07:42 -0500 (EST) Date: Thu, 21 Nov 2002 11:07:39 -0500 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 70 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <5B868F0A-FD6B-11D6-8540-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) This paper sets out to complement those which we've seen before; previous papers have designed systems which are scalable and efficient, but have not set down security as a primary objective. This paper examines possible attacks and solutions to protect against them; in general the system focuses around the secure routing problem and delineates it into three seperate problems: Secure node assignment, secure routing table maintenance, and secure forwarding of messages. Secure node assignment relies on nodeId certification, with the caveat that it must be expensive (computationally or otherwise) to get a certificate or Sybil attacks would be feasible. The CA represents a single centralized point of failure, unfortunately. It is possible--perhaps--to overcome this by making nodeId's solutions to cryptographic puzzles. Secure routing table maintenance is obtained by splitting the routing table into one wherein locality information is used (for efficiency) and one which places tight constraints on the nodeIds (for security). The idea being that if node assignment is secure, it will be hard for an attacker to attack the tightly constrained table. Chord already has a constrained configuration, and the authors provide instructions on how to add it to Pastry/Tapestry. Note however that this really only protects against nodes which cause packets to fail and not against more subtle attacks. The author's suggest self-verifying data to remedy their expensive route failure tests, but it could also be used to help detect certain malicious attacks (i.e. data corruption). Ultimately, this paper presents only two problems and solutions. They somewhat underestimate the creativity of a malicious node (constraining it to routing failures) without taking into account more subtle attacks like traffici analysis. Nonetheless, it is the first paper with an eye to security in p2p networks we've read outside of Freenet. From sc329@cornell.edu Thu Nov 21 11:43:35 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALGhZ913641 for ; Thu, 21 Nov 2002 11:43:35 -0500 (EST) Received: from sangeeth.cornell.edu (syr-24-58-5-174.twcny.rr.com [24.58.5.174]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA10905 for ; Thu, 21 Nov 2002 11:43:34 -0500 (EST) Message-Id: <5.1.0.14.2.20021121114132.028241e0@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 21 Nov 2002 11:43:37 -0500 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 70 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper describes and evaluates techniques that allow nodes to join an overlay network , to maintain routing state, and to forward messages securely in the presence of malicious nodes. Secure routing is a major issue in peer to peer systems modelled on overlays like CAN, Chord, Pastry or Tapestry in that a small fraction of malicious nodes can prevent correct message delivery through out the overlay. The three main components for secure routing as mentioned in the paper are 1) a secure assignment of node identifiers 2) secure routing table maintenance and 3) secure message forwarding. The current overlay network sonly provide a best-effort service to deliver a message to a replica root associated with a given key. The secure routing primitive ensures that when a non-faulty node sends a message to a key k, the message reaches all non-faulty members in the set of the replica roots with very high probability. Secure routing table maintenance ensures that the fraction of faulty nodes that appear in the routing tables of correct nodes does not exceed , the fraction of faulty nodes in the entire overlay. The system uses a set of certification authorities to assign NodeIds to principals and to sign nideId certificates, which bind a random nodeId to the public key and an IP address. By binding nodeId to an IP address, it becomes harder for an attacker to move nodeIds across nodes.Sybil attacks could be thwarted by either charging fees for obtaining certificates or by tying real-world identities to nodeIds. The solution for securing routing table information is to use to routing tables: one that exploits network proximity information for efficient routing and one that constraints routing table entries. The entries in the constrained routing table could be initialized by using secure forwarding to obtain lice nodeId closest to the desired point p in the id space. For secure routing, a failure test is done after every routing. Only if it fails the test, would the alternate method of sending data be used. If the routing tests fail, redundant routing could be deployed where copies of messages are routed through multiple routs towards the destination key's replica roots. The techniques suggested in the paper seems to show promising results, allowing the network to tolerate upto 25 % malicious nodes while providing good performance when the fraction of compromised nodes is small. From jsy6@postoffice2.mail.cornell.edu Thu Nov 21 11:50:00 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALGnx915125 for ; Thu, 21 Nov 2002 11:50:00 -0500 (EST) Received: from Janet.cornell.edu (syr-24-59-78-146.twcny.rr.com [24.59.78.146]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA08493 for ; Thu, 21 Nov 2002 11:49:59 -0500 (EST) Message-Id: <5.1.0.14.2.20021121102354.00b53e00@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 21 Nov 2002 11:47:49 -0500 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 70 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper's contribution is outline possible attacks in peer-to-peer systems and to provide secure routing primitives that can be coupled with existing structured peer-to-peer overlays. Secure routing is composed of the following three properties: secure assignment of node identifiers, secure routing table maintenance, and secure message forwarding. The peer-to-peer overlay networks we have seen up until now are highly resilient but are not secure. It is important to guarantee secure routing in an environment where no pre-existing trust relationships established between any two parties. Secure Node ID assignment: An attacker only needs to control a small portion of nodes in a p2p system if it can choose node IDs. Node IDs can be chosen such that the network can become partitioned. Control over node IDs also allows control over access to target objects since all replications of the object are stored in a particular subspace of key space. Even if random node ID assignment is guaranteed but one must also guarantee an attacker can not obtain a large number of node ID certificates. Solution: require each new node to generate a key pair where the SHA-1 hash of the public key has zero as its first p bits. This hash is their node ID. Also, the node ID should be bound to the node's IP address to avoid attacks that exploit network locality. To prevent the accumulation of many node IDs, node IDs should be periodically invalidated. This requires a trusted entity to broadcast a different initialization vector foe hash computations. Secure routing table maintenance: To be secure, routing tables must have an average fraction of at most f random entries that point to malicious nodes. Bad routing updates can increase the fraction of bad entries. Attackers can fake proximity for systems that utilize proximity to improve routing efficiency. An attacker can also supply faulty routing table entries when new nodes joining the system. The effect of such an attack cascades with each subsequent update. Solution: Use two routing tables. One table exploits network proximity information and is used to forward messages to achieve good performance. The other table constrains routing table entries and should be used if the first one fails. Secure message forwarding: A node can simply not forward messages in order to create insecure message forwarding. Minimizing the number of hops needed to route a message increases the probability of routing correctly. Thus there exists tradeoff between the cost of route table maintenance and the probability of routing success. Solution: redundant routing. A message is routing to the root of the destination key using the locality-ware routing table. A set of replica routes is collected and applied the failure test. A positive test results in the message being sent over diverse routes to the various replica routes. The failure test decides whether or not a set of roots is likely to be correct for a key by comparing the density of node IDs in the neighbor set of the sender with the density of node IDs close to the replica roots of the destination key. The average density of node IDs is greater than the average density of faulty nodes. These secure routing primitives add significant overhead. Good performance is only guaranteed for only a small fraction of malicious nodes. From vrg3@cornell.edu Thu Nov 21 11:53:04 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALGr3916141 for ; Thu, 21 Nov 2002 11:53:03 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA22424 for ; Thu, 21 Nov 2002 11:53:00 -0500 (EST) Date: Thu, 21 Nov 2002 11:52:59 -0500 (EST) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 70 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents an analysis of what is required for a peer-to-peer overlay network to be robust and secure against attackers. The goal is for the overhead to be proportional to the fraction of malicious nodes in the network. The authors define a secure routing primitive, and identify three problems which it relies on: secure node ID assignment, secure route table maintenance, and secure message forwarding. Secure node ID assignment is necessary to ensure that an attacker cannot select his position in the network so as to force a partition or to target a particular node as a victim. Somewhat disheartening is the decision that this can only be achieved by using universally trusted centralized certificate authorities. These CAs would issue signed node IDs. To make sure nobody acquires multiple IDs, they issue them either in exchange for money (which means the only way to get many IDs is to spend a lot of money, making an attacker's likelihood of success rise with his wealth) or based on some other unique identification (which means that not only do you have to get permission from an external entity before you can join the peer-to-peer network, but you also have to give up a bit of personal information). Secure route maintenance is needed to make sure nobody's routing table is full of routes that go through malicious nodes. The proposed solution is that each node maintain two routing tables, one for normal routing whose goal is efficiency, and one for fail-safe routing. The latter is formed by securely querying for multiple nodes in a certain address space. Secure forwarding is a difficult problem because there are so many chances during the routing of a message for a malicious or broken node to drop, redirect, or otherwise mangle a packet. The solution proposed is basically to try routing normally (using your efficient routing table), and if that doesn't work, route using your failsafe table using many redundant routes. The routing failure test is an interesting contribution of this paper. The test validates a set of replica roots for a given key. The set of replica roots is deemed to be likely correct if the density of existing node IDs in the neighbors of the sender is less than the density of existing node IDs in the vicinity of the potential replica roots. The main contribution of this paper is an analysis and identification of the problems of securely routing in peer-to-peer overlay networks. The proposed solutions have some flaws but they did demonstrate, in simulation, successful secure operation even with a full quarter of the nodes in the network being corrupt. From mr228@cornell.edu Thu Nov 21 11:53:56 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALGru916205 for ; Thu, 21 Nov 2002 11:53:56 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA23049; Thu, 21 Nov 2002 11:53:53 -0500 (EST) Date: Thu, 21 Nov 2002 11:53:53 -0500 (EST) From: mr228@cornell.edu Message-Id: <200211211653.LAA23049@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: mr228@cornell.edu Reply-To: mr228@cornell.edu Cc: mr228@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: mr228@cornell.edu X-Originating-IP: 128.84.223.176 Subject: 615 PAPER 70 This paper identifies a problem that is common to all of the P2P overlay networks we've studied: a small number of malicious nodes can disrupt the proper functioning of the network by misreporting routes, simply dropping packets, etc. This paper discusses the problems and attempts to solve them through a variety of means. The central goal is to create networks that are resistant to large percentages of malicious or badly behaving nodes. The issue is one of trust: How to trust the information received from other nodes. The resulting approach gives bounds on how many nodes must be trusted to ensure, with high probability, correct functioning of the network. There are 3 operations they seek to make secure: Assignment of Node IDs, Route Table Maintenance, and Message Forwarding. Secure assignment of node ids can be done through a central authority. This authority can enforce whatever joining policy you want and then sign a certificate indicating a right to join. To keep conspiring nodes from joining repeatedly, a challenge from this authority can be introduced. This challenge can be something taking a decent amount of compute time thereby throttling the rate at which one can join. Invalidation of keys on some regular basis may be necessary. This central server solution introduces a single point of failure and may not scale. Routing tables can be manipulated by malicious nodes. Nodes could misreport routes and route characteristics in order to force good nodes to route through other conspiring nodes. This paper proposes creating an additional routing table where the metric are based on the underlying network's characteristics, not those reported by the overlay network. With a very small number of nodes refusing to forward packets, all network traffic can be stopped. They propose countering this by redudancy and replicas throughout the network. From adam@graphics.cornell.edu Thu Nov 21 12:00:05 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALH04917691 for ; Thu, 21 Nov 2002 12:00:04 -0500 (EST) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id gALGxx0k067339 for ; Thu, 21 Nov 2002 11:59:59 -0500 (EST) Date: Thu, 21 Nov 2002 11:59:21 -0500 (EST) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 paper 70 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Have secure applications on top of structured P2P networks requires that there is secure routing at a lower level. This paper concentrates on security issues of overlay networks like CHORD, CAN, Tapestry and PASTRY. Secure routing requires that three things are accomplished: securely assigning nodeIDs to nodes, securely maintaining routing tables, and securely forwarding messages. Secure node Ids: Make sure an attacker can't pick a "good" nodeID for it (one which they could control namespace they want or mediate traffic). This is solved using a trusted authority (potentially doesn't scale?). They suggest avoiding sybil attacks by using a payment system which I find to not a good solution. There is no evenness in this system (a weak attacker is one w/ no money) but a system where you have exponentially increasing cost (say solve a problem that takes a week to solve and you get the key, or read a book for some reference or something like that) could deter people just as easily. Secure Routing Tables: Bad routing updates could pollute routing tables so an attacker should be limited in it's ability to do this. Faking proximity (worm holes, etc) is a good way for an attacker to exploit routing. There solution to this is to use constrained routing tables which means that we allow only routing information for to distributed from the closest nodeId about a point in Id space. This assumes that Secure nodeIds have been established and the that bootstrap computer is not faulty (or an attackers computer). Secure Routing Maintenance: once again attackers could poison a table by adding many bad entries by supplying bad routes. This must be controlled and simply using Secure nodeIds is not enough. Attackers could fake proximity to increase bad routing entries. Once again the solution is constrained routing like the previous solution. Secure Message forwarding: routing and constrained routing aren't sufficient if an attacker can reduce the successful delivery of messages. Solution to this is to user diverse routes and detect faults. Basically send a message that is pre-agreed upon and check for failure, use redundant routing if it fails. I think an extension could be a voting system to give preference to routes that are good or bad (based on past metrics) this however could make systems highly susceptible if a highly trusted system is compromised. I am not sure that there are very many good solutions when you have unknown attackers in a p2p system. From vivi@CS.Cornell.EDU Thu Nov 21 12:30:05 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALHU5924140 for ; Thu, 21 Nov 2002 12:30:05 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615paper70 Date: Thu, 21 Nov 2002 12:30:04 -0500 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AFB2@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper70 Thread-Index: AcKRg5xIjz1NGx5LQVuA0f8sEfdKEA== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id gALHU5924140 Today's paper presents ways to implement secure routing in p2p systems. The authors attempt to achieve this goal by ensuring that nodeIds of all nodes are legitimate, by limiting the erroneous routing table entries at every non- malicious node, and by securely forwarding messages from a non- malicious node. NodeId assignment is handled by a Certification Authority(CA) that ensures that all nodeIds are randomly chosen. The CA signs nodeId certificates, enabling verification of the authenticity of any nodeId. Each node maintains two routing tables: the (locality- aware) routing table used for normal (more efficient) routing, and the constrained routing table that is used when routing through the normal tables "fails". When a routing failure is detected, "redundant" routing is employed, which sends out the messages to different nodes, increasing the probability that the legitimate replica holders receive the message. Weaknesses -In the redundant routing phase, a node(say A) that has the destination in its neighbor set has to do a lot of work to assist the sender in secure message delivery. A might not choose to do so, unless provided with an appropriate incentive. (A's decision to assist in this phase is totally independent of the success of A's secure message delivery, when A itself has some messages to send.) - The CA is centralized and is a single point of failure. Possible improvements Incentives to make sure nodes contribute to the routing mechanism. From pj39@cornell.edu Thu Nov 21 13:33:42 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALIXg909646 for ; Thu, 21 Nov 2002 13:33:42 -0500 (EST) Received: from photon (pit096.cs.cornell.edu [128.84.223.196]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id NAA11586; Thu, 21 Nov 2002 13:33:37 -0500 (EST) From: "Piyoosh Jalan" To: Cc: Subject: 615 PAPER 70 Date: Thu, 21 Nov 2002 13:31:12 -0500 Message-ID: <000401c2918c$2c0a0ba0$c4df5480@ising.cs.cornell.edu> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook CWS, Build 9.0.2416 (9.0.2911.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Secure routing for structured peer-to-peer overlay networks This paper discusses security issues associated with P2P overlay networks. An overlay network of nodes running a P2P protocols like CAN, chord, Pastry and Tapestry are highly resilient, that they can route messages correctly when even when the network is dynamic and when a large fraction of the nodes crash or when the network partiotions. However these overlay networks lack security in the event of a fraction of nodes behaving maliciously and may or may not colluding. The malicious nodes can mis-route, corrupt or drop messages and routing information or assume the identity of other nodes. The author states that secure routing is the key building block to construct a secure P2P ON. Secure routing requires secure asssignment of node ids, secure routing table maintenace and secure message forwarding. Secure node Id assignment ensures that an attacker cannot chosse eht valie of nodeIds assigned to the nodes that the attacker controls. Secure routing table maintenance ensures that the fration of faulty nodes in the routing table does not exceed the fraction of malicious nodes in the ON. Secure forwarding of message ensures that atleast once copy of a message sent to a key reaches correct replica root for the key. The paper presents multiple solutions to the secure node Id assignment problem. The first being use of a certification authority (CA) to assign node ids. The CA's would assign node Ids in such a way to bind the ip address of the nodes to its node Id, in this way the attacker cannot move node Ids around across nodes. However there are many problems associated with this approach, one being the attacker may obtain a number of legitimate node Ids from the CA. The solution to this problem is to make it harder for the attacker to obtain node Ids. This can be achieved in many ways. The first one being to associate some money to acquire a node Id thus for an attacker to acquire a lot of node Ids would require him to pay a substantial amount of money which may prove to be a big deterrent. Another approach being to bind the node Ids to real world entities like person name, this is feaible in an organization but not in an open community. However the whole notion of using the CA approach for node Id distribution in a P2P ON is not adivisable as again the CA become a single point of failure and attack. The alternative to CA being to require prospective nodes to solve crypto puzzles to gain the right to use a node Id. The idea beind is to have each node spend some time to acquire the node Id and this could be a deterrant for an attacker with many node Ids. Secure routing table maintenance is also necessary to subvert fake attackers that fake proximity and because of the inability of the routing protocols(chord, pastry) to differentiate between a fake and legitimate routing update. To enable secure routing table maintence a strong constraint should be imposed on the the set of nodeIds that fill up the routing table. The paper proposes to maintain two routing tables one based on network proximity information and ont that constrains routing table entries. The second table being used only when the first (efficient routing) one fails. The reliance on secure routing can be reduces ( as they add significant overhead) by the use of self certifying data so that the clients so that the integrity of data can be verified by the client. Secure message forwarding is necessary because the attacker can reduce the probability of successful delivery by simply not forwarding messages. As if one node in the route is malicious and and simply drops the messge the routing may fail. The solution proposed is to use diverse redundant routing when the failure test return positive. The failure test takes a key and a set of prospective replicas for the key and returns negative if the set of roots is likely to be correct otherwise it return positive. In the event of failure test returning positive the paper suggests use of redundant routing where copies of message is send over multiple fourtes towards each of destination kesy replica roots. The solutions presented in the paper are elegant the paper states that with simulation results for pastry that these techniques allow to tolerate up to 25% malicious nodes. I beleive there is a lot of overhead involved in using the techniques presented but as always security cannot be achieved without an overhead. From liuhz@CS.Cornell.EDU Thu Nov 21 14:07:14 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALJ7E919500 for ; Thu, 21 Nov 2002 14:07:14 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 70 Date: Thu, 21 Nov 2002 14:07:14 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE726@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 70 Thread-Index: AcKRkTOkAZYWyKxeRqOFnBNjAmZUMg== From: "Hongzhou Liu" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id gALJ7E919500 This paper introduces a secure routing primitive for structured P2P overlay networks. While many structured P2P systems have previously assumed a fail-stop model for nodes, this work is based on a model where malicious nodes can act in any way and conspire with each. The secure routing protocol present in this paper contains mainly three parts: secure node joining, secure routing table maintenance, and secure messages forwarding. The secure nodeID assignmenet scheme guarantees attackers can not choose nodeID for the nodes under their control freely by adding some certification authorities(CAs) to the systems. The set of CAs is used to assign nodeID to principals and to sign nodeID certificates, which bind a random nodeID to the public key that speaks for its principal and an IP addresss. While the CAs represent points of failure, The paper also suggests some totally distributed method that can moderate the rate at which an attacker can acquire nodeIDs. The basic idea is to request the attackers to spend some time to find nodeIDs that meet some special requirements. The goal of secure routing table maintenance is to keep the fraction of faulty entries in a routing table approximately the same as that of faulty nodes in the system. If no care is taken, attackers can increase the fraction of bad entries by supplying bad routing updates. This problem is especially serious in Pastry and Tapestry. The solution in the paper is to use a constrained routing table as well as the efficient routing table (used in Tapesty and Pastry) that take advantages of proximity. Unlike the efficient routing table, the constrained one poses a strict limit on entries in it. A typical requirement for such entry is that it must be the node whose ID is closest to a point. The efficient routing table is used to forward messages to achieve good performance, while the constrained one is for security and used only when the efficient routing fails. The basic idea of secure message forwarding is to route a message efficiently first and to apply a failure test to determin if routing worked. If it failed, some more expensive redundant routing would be used. The routing failure test is based on the observation that the average density of nodeIDs per unit of "volume" in the id space is greater than the average density of faulty nodeIDs. The test works by comparing the density of nodeIDs in the neighbour set of the sender with the density of nodeIDs close to the replica roots of the destination key. If this test indicates failure, redudant routes are applied. Multiple copies of messages are sent over multiple routes toward each of the destination key's replica roots. This method is clearly very expensive. To reduce the overhead induced by secure routing, the paper supposes to store some self -certifying data on the nodes, therefore clients are able to check retrieved data's integrity by themselves and resort to secrure routing only when the integrity check fails. This paper is well-organized. The secure routing techniques applies to most P2P systems. It can be combined with existing, application-specific security technques to construct secure, decentralized applications upon structured overlays. From hs247@cornell.edu Thu Nov 21 18:27:50 2002 Received: from mailout5-0.nyroc.rr.com (mailout5-0.nyroc.rr.com [24.92.226.122]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gALNRo916610 for ; Thu, 21 Nov 2002 18:27:50 -0500 (EST) Received: from hubby.cornell.edu (syr-24-59-74-55.twcny.rr.com [24.59.74.55]) by mailout5-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id gALNRlF19248 for ; Thu, 21 Nov 2002 18:27:47 -0500 (EST) Message-Id: <5.1.0.14.2.20021121182633.00b48d28@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 21 Nov 2002 18:27:51 -0500 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 70 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed So far we have seen many p2p overlay networks: Chord, Pastry, Tapestry...etc. Though some address security with regards to information integrity (using asymmetric cryptography), none of them have addressed the issues of malicious attackers. This paper identifies 2 attacks that p2p networks can be susceptible as well as offer possible solutions. The first of these attacks is the nodeID assignment attack. In each network we want nodeID's to be randomly assigned. Therefore a malicious node should not be able to pick its own ID in the system and therefore take control of a particular key space of interest. One step above this attack is the Sybil attack. If an organisation is able to insert many malicious nodes in to the network, then they can certainly have a high probably of controlling the network in anyway they want. To prevent this attack, the authors suggest having a central authority assign nodeIDs. Therefore they can limit the number of nodes an organisation can insert into the network as a well make sure the distribution is random. The obvious problem is that it makes a distributed system rely on a centralized resource. The second of these attacks is routing attacks. A malicious node in the network can potentially not follow the routing protocol and do things such as drop packets, route packets in infinite loops etc. Their solution relies on the fact that the nodeID assignment has been addressed and that nodes are randomly assigned. The solution is to have a secondary routing table that is used when malicious routes are suspected. This secondary routing table is comprised of less efficient routing, but is formed in a way where it is very unlikely for a malicious node to be in it. And finally, to guarantee message forwarding they propose a scheme of diverse routes. First if they detect a route to be faulty using the most efficient route, they propose falling back on less efficient routes. Overall, this paper offers good insights on the vulnerabilities of overlay networks. However the solutions they offer are not satisfactory. More research has to be done on finding better solutions. From linga@CS.Cornell.EDU Thu Dec 5 16:48:06 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gB5Lm6909741 for ; Thu, 5 Dec 2002 16:48:06 -0500 (EST) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id gB5Lm6S10986 for ; Thu, 5 Dec 2002 16:48:06 -0500 (EST) Date: Thu, 5 Dec 2002 16:48:06 -0500 (EST) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 70 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Secure routing in structured P2P overlay networks Current P2P systems like Chord, Pastry, Tapestry etc are not secure. This paper attempts to introduce security into these systems. This paper describes attacks that can be mounted and also proposes secure routing as the key building block that can be used to build secure P2P applications on top of the above mentioned P2P systems. Secure routing requires: secure assignment of node ids; secure routing table maintenance; secure message forwarding. Secure assignment of node ids: Attackers who can choose node ids can easily compromise the integrity of a P2P system. Solution proposed is have certified nodeIds with certificates issues by central certification authorities (CAs). This is still not good if an attacker can get a lot of nodeIds. To discourage from acquiring a lot of nodeIds the attacker will be asked to pay for each nodeId acquired. Authors argue that distributed nodeid generation is not secure enough. Secure routing table maintenance: Routing table maintenance involves creating routing tables and neighbor sets and maintaining them. Attacks involve making a lot of the routing entries to point to bad nodes (nodes controlled by attackers). First attack is applicable when n/w proximity info is used to improve routing efficiency. The attacker can fake proximity to increase the number of bad entries. Second attack involves manipulating routing updates so that a lot of the bad entries are introduced. The proposed solution to these two attacks is to use two routing tables: one based on proximity (like in Pastry) and one that constrains routing table entries (as in Chord). Constrained routing table is used only when the efficient routing technique fails. Secure message forwarding: Attackers can reduce probability of successful delivery by not forwarding messages according to the algorithm. Given a message and a destination key: What we need is an efficient way to send atleast one copy of the message to every correct replica for the key with high probability. Solution proposed to route a message efficiently, apply the failure test to see if routing worked and use the redundant routing only if the failure test was positive. The failure test is based on the observation that: average density of nodeIds per unit in the id space is greater than the average density of faulty nodeIds. So basic approach in the test is to compare the density of nodeIds in the neighbor set of the sender with the density of the nodeIds close to the replica roots of the destination key. Several attacks are possible to invalidate the analysis and weaken the failure test. Some simple fixes are also suggested. Authors show that use of secure routing can be reduced by using self-certifying application data. Experiments show that the techniques proposed can tolerate upto 25% malicious nodes and degradation in performance is proportional to the number of malicious nodes.