A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for P2P Routing Attacks <s> Recent peer-to-peer research has focused on providing efficient hash lookup systems that can be used to build more complex systems. These systems have good properties when their algorithms are executed correctly but have not generally considered how to handle misbehaving nodes. This paper looks at what sorts of security problems are inherent in large peer-to-peer systems based on distributed hash lookup systems. We examine the types of problems that such systems might face, drawing examples from existing systems, and propose some design principles for detecting and preventing these problems. <s> BIB001 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for P2P Routing Attacks <s> Structured peer-to-peer overlay networks provide a substrate for the construction of large-scale, decentralized applications, including distributed storage, group communication, and content distribution. These overlays are highly resilient; they can route messages correctly even when a large fraction of the nodes crash or the network partitions. But current overlays are not secure; even a small fraction of malicious nodes can prevent correct message delivery throughout the overlay. This problem is particularly serious in open peer-to-peer systems, where many diverse, autonomous parties without preexisting trust relationships wish to pool their resources. This paper studies attacks aimed at preventing correct message delivery in structured peer-to-peer overlays and presents defenses to these attacks. We describe and evaluate techniques that allow nodes to join the overlay, to maintain routing state, and to forward messages securely in the presence of malicious nodes. <s> BIB002 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for P2P Routing Attacks <s> In this paper, we show that two peer-to-peer systems, Pastry [13] and Tapestry [17] can be made tolerant to certain classes of failures and a limited class of attacks. These systems are said to operate properly if they can find the closest node matching a requested ID. The system must also be able to dynamically construct the necessary routing information when new nodes enter or the network changes. We show that with an additional factor of O(log2 n) storage overhead and O(log n) communication overhead, they can continue to achieve both of these goals in the presence of a constant fraction nodes that do not obey the protocol. Our techniques are similar in spirit to those of Saia et al. [14] and Naor and Wieder [10]. Some simple simulations show that these techniques are useful even with constant overhead. <s> BIB003 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for P2P Routing Attacks <s> A number of recent applications have been built on distributed hash tables (DHTs) based overlay networks. Almost all DHT-based schemes employ a tight deterministic data placement and ID mapping schemes. This feature on one hand provides assurance on location of data if it exists, within a bounded number of hops, and on the other hand, opens doors for malicious nodes to lodge attacks that can potentially thwart the functionality of the overlay network. This paper studies several serious security threats in DHT-based systems through two targeted attacks at the overlay network's protocol layer. The first attack explores the routing anomalies that can be caused by malicious nodes returning incorrect lookup routes. The second attack targets the ID mapping scheme. We disclose that the malicious nodes can target any specific data item in the system; and corrupt/modify the data item to its favor. For each of these attacks, we provide quantitative analysis to estimate the extent of damage that can be caused by the attack; followed by experimental validation and defenses to guard the overlay networks from such attacks. <s> BIB004 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for P2P Routing Attacks <s> To achieve higher efficiency over their unstructured counterparts, structured peer-to-peer systems hold each node responsible for serving a specified set of keys and correctly routing lookups. Unfortunately, malicious participants can abuse these responsibilities to deny access to a set of keys or misroute lookups. We look to address both of these problems through replica placement. Using Chord as an example, we present an equally-spaced replication scheme and prove that it can be tuned to produce any desired number of disjoint routes. To be specific, we prove that d disjoint routes can be produced by placing 2d-1 replicas around a fully populated Chord ring in an equally-spaced fashion. In this situation, we also prove that there exists a route to at least one replica, which contains only uncompromised nodes, even if an attacker controls more than a quarter of the contiguous identifier space in the system. Simulation experiments demonstrate that this scheme performs better than previously proposed replica placement schemes in rings that are sparsely populated, populated in clusters, or populated partially by compromised nodes <s> BIB005 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for P2P Routing Attacks <s> Much research has been devoted to the development of efficient distributed hash tables (DHTs). While many works have studied DHT systems, few have examined their security issues. For example, chord and other DHT implementations rely on the cooperation of individual peers to route requests. Consequently, any malicious node can drop and misroute messages at will, censoring the access of honest peers to content. In this paper, we introduce bypass, a novel DHT routing protocol designed to mitigate routing attacks. A key distinguishing feature of bypass from other implementations is a feedback-based filtering protocol that allows peers to avoid adversarial nodes when routing to the correct holders of a key. Our experimental results show that in principle bypass can achieve a lookup success rate close to theoretical bounds. <s> BIB006
As the Incorrect Lookup Routing affects the routing algorithms of DHTs strongly, several countermeasures were proposed. Most of those countermeasures increase the robustness of the routing algorithm by adding redundancy to the network. The recursive routing algorithms are susceptible to routing attacks as the source of the request can not detect malicious nodes due to the recursive behavior of the routing. To overcome this drawback, the Iterative Routing algorithm was proposed by Sit and Morris BIB001 as one of the first and most promising approaches. When an Iterative Routing is initiated, intermediate nodes have to send routing information about the next hop back to the source node. This way, the source node is able to interact with the intermediate nodes directly. Whenever an intermediate node proposes an incorrect next hop address or does not respond to a request at all, the source node is aware of this malicious behavior due to the missing reply or as the proposed next hop node does not match the expected one. After detecting a malicious node, the source node can reroute the request and bypass this node. On the downside, the lookup delay and the data overhead is increased as the source node has to resend lookup messages whenever a intermediate node does not respond and as intermediate nodes have to reply to the source node which adds one additional message per hop in the overlay. Another prominent approach to increase the routing robustness of DHTs was introduced by Castro et al. BIB002 . They proposed a redundant recursive routing algorithm. When multiple redundant requests are sent, the probability that all of them are dropped or redirected by malicious nodes is decreased. Due to this, the Redundant Routing algorithm improves the delivery rate of lookup requests. On the downside, redundant routing increases lookup overhead strongly. Srivatsa and Liu analyzed the importance of independent paths during redundant routing BIB004 . As long as the paths are not disjoint, a single malicious node may affect all sent requests. Sánchez-Artigas et al. BIB006 modified the Redundant Routing algorithm and combined it with a reputation system. The resulting Resistant Routing algorithm forwards lookup requests not only to the next hop, but also to n neighbors of the next hop. Those n + 1 nodes forward the request to the next set of n + 1 nodes around (and including) the next hop node. This way, the destination node and n of its neighbors receive the request after log(N ) hops. As Sánchez-Artigas et al. propose to store the replicas around the root of an object, the source node receives n + 1 keys at the end of the lookup procedure as each neighbor of the destination stores a valid replica. In order to reduce the resulting routing overhead, an additional reputation system is introduced. During the routing, each node has to rate the behavior of all of its neighbors. When a node is rated malicious (i.e., when it does not forward lookup requets / answers lookup requests incorrectly), routing requests are not forwarded to this node anymore. Further, as neighbors could forward the requests to different next hop nodes, the lookup process has to be coordinated (e.g., by iterative routing) as otherwise the number of forwarded requests may increase strongly. Due to the parallel lookup, probability of a successful lookup increases. According to Sánchez-Artigas et al., the reputation system works efficiently as long as the fraction of malicious nodes is below 50 %. Combining Redundant and Iterative approaches, Hildrum and Kubiatowicz BIB003 proposed a parallel and iterative routing algorithm. Whenever a request is initiated, the source node has to send n lookup request messages in parallel. Each intermediate node sends a reply message proposing a set of next hop nodes to the source of the request. Based on this information, the source node selects n next hop nodes and forwards n request to those nodes. These steps are repeated until the first request reaches the destination. Due to the combination of Redundant and Iterative routing, the packet delivery rate is increased strongly. Yet, this is paid for by a high overhead and delay as multiple request messages have to be sent iteratively. Besides increasing the redundancy of routing algorithms directly, distributing replicas can also increase the reliability of the lookup process. As every countermeasure discussed so far has to rely on the benign behavior of at least the destination node, the success probability of the lookup process can not be improved beyond the fraction of nodes behaving benign on average. Using replicas can overcome this drawback. While Castro et al. BIB002 proposed to spread the replicas in the neighborhood of the node that is responsible for the original object according to the DHT specification, Harvesf and Blough BIB005 proposed a replica set evenly distributed in the P2P overlay. As a result of equally distributed replicas, DHTs as Pastry can provide guaranteed disjunct multi-path routing. Due to the tree based structure of the primary routing table, storing a replica in each prefix domain of the highest level of the tree will ensure disjunct paths as different parts of the lookup table are used during the lookup for each replica. Replicas can further reduce the impact of Storage and Retrieval Attacks on the network, to deny access to a specific object, all nodes that are responsible for this service (i.e., all nodes holding replicas) would have to behave maliciously. As an intermediate node could pretend to be the destination of a request and respond with an incorrect result, the source has to validate each responding node that delivers an unexpected result. For this, Castro et al. proposed a Routing Failure Test. The source node has to check the virtual distance to the neighbor nodes and estimates an average node density. As most DHTs distribute the node-IDs equally in the ID space, the node density at the destination is equal to the node density at the source on average. Whenever object-ID and node-ID differ strongly regarding the node density estimated in the neighborhood of the source node, the responding node might not be the legitimate node that is responsible for the object. Table Manipulation The original specifications of most DHT-based P2P systems do not prevent corrupting routing tables of benign nodes by sending forged routing table updates. To address this issue, several countermeasures for a malicious routing table manipulation were proposed recently. Sit and Morris BIB001 suggested to send a probing message to links provided by other nodes to check the correctness of the routing information. This way, incorrect entries such as not existing nodes can be detected. Castro BIB002 proposed to generate a second, more secure routing table. The first routing table is the routing table as defined by the DHT, that is using the standard metrics to maintain the routing table. As most proposed metrics for routing table maintenance were developed to reduce traffic and, therefore, favor links to nodes that are in physical proximity, malicious nodes may misuse this metric and feign proximity to increase the probability of being added to the routing table. To prevent this, the second routing table uses a metric that ignores the physical proximity but adds nodes to the routing table that are virtually close to a specific node-ID. For example, whereas for the first routing table in Pastry the entries are chosen based on matching prefixes and a proximity metric, the second routing table as proposed by Castro et al. prefers entries that are next to the required prefix for the routing table entry combined with a predefined ending of the node-ID. As node-IDs are assigned randomly, malicious nodes can not misuse the metric of the second routing table. During routing, the first routing table is used until a lookup process fails. Whenever a routing failure occurs, rerouting is initiated based on the second routing table.