A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil Attacks <s> Large-scale peer-to-peer systems face security threats from faulty or hostile remote computing elements. To resist these threats, many such systems employ redundancy. However, if a single faulty entity can present multiple identities, it can control a substantial fraction of the system, thereby undermining this redundancy. One approach to preventing these "Sybil attacks" is to have a trusted agency certify identities. This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities. <s> BIB001 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil 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 Sybil Attacks <s> Security is important for many sensor network applications. A particularly harmful attack against sensor and ad hoc networks is known as the Sybil attack based on J.R. Douceur (2002), where a node illegitimately claims multiple identities. This paper systematically analyzes the threat posed by the Sybil attack to wireless sensor networks. We demonstrate that the attack can be exceedingly detrimental to many important functions of the sensor network such as routing, resource allocation, misbehavior detection, etc. We establish a classification of different types of the Sybil attack, which enables us to better understand the threats posed by each type, and better design countermeasures against each type. We then propose several novel techniques to defend against the Sybil attack, and analyze their effectiveness quantitatively. <s> BIB003 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil Attacks <s> Distributed Hash Tables (DHTs) are very efficient distributed systems for routing, but at the same time vulnerable to disruptive nodes. Designers of such systems want them used in open networks, where an adversary can perform a sybil attack by introducing a large number of corrupt nodes in the network, considerably degrading its performance. We introduce a routing strategy that alleviates some of the effects of such an attack by making sure that lookups are performed using a diverse set of nodes. This ensures that at least some of the nodes queried are good, and hence the search makes forward progress. This strategy makes use of latent social information present in the introduction graph of the network. © Springer-Verlag Berlin Heidelberg 2005. <s> BIB004 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil Attacks <s> Due to the open, anonymous nature of many P2P networks, new identities - or sybils - may be created cheaply and in large numbers. Given a reputation system, a peer may attempt to falsely raise its reputation by creating fake links between its sybils. Many existing reputation mechanisms are not resistant to these types of strategies.Using a static graph formulation of reputation, we attempt to formalize the notion of sybilproofness. We show that there is no symmetric sybilproof reputation function. For nonsymmetric reputations, following the notion of reputation propagation along paths, we give a general asymmetric reputation function based on flow and give conditions for sybilproofness. <s> BIB005 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil Attacks <s> We consider the problem of defending against Sybil attacks using computational puzzles. A fundamental difficulty in such defenses is enforcing that puzzle solutions not be reused by attackers over time. We propose a fully decentralized scheme to enforce this by continually distributing locally generated challenges that are then incorporated into the puzzle solutions. Our approach consists of an all-to-all broadcast of challenges, with a combining function to ensure this can be done efficiently. The combining function generates certificates that can be used to prove that each node's challenge was delivered to and used by each other node, therefore proving the freshness of each puzzle. We show how our distribution and verification mechanisms can be implemented on top of the the Chord in Stoica et al., (2001) overlay <s> BIB006 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil Attacks <s> Mobility is often a problem for providing security services in ad hoc networks. In this paper, we show that mobility can be used to enhance security. Specifically, we show that nodes that passively monitor traffic in the network can detect a Sybil attacker that uses a number of network identities simultaneously. We show through simulation that this detection can be done by a single node, or that multiple trusted nodes can join to improve the accuracy of detection. We then show that although the detection mechanism will falsely identify groups of nodes traveling together as a Sybil attacker, we can extend the protocol to monitor collisions at the MAC level to differentiate between a single attacker spoofing many addresses and a group of nodes traveling in close proximity. <s> BIB007 </s> A Survey on Security in Mobile Peer-to-Peer Architectures—Overlay-Based vs. Underlay-Based Approaches <s> Countermeasures for Sybil Attacks <s> Though reputation-based trust mechanism is optimal for stimulating peers to cooperate in P2P networks, it cannot avoid facing some malicious attacks. In this paper we investigate the characteristic of P2P reputation networks and propose a group-based trust metric to alleviate the effects of Sybil attack and collusion. The CNM algorithm is used to divide the whole network into some trust groups and show the relationship between them. Our trust metric contains factors of the relationship between trust groups, the degree of the peer, and the similarity between the neighbors of the peer. We evaluate the metric and show that the effects of the Sybil attack and collusion can be alleviated effectively. <s> BIB008
Douceur BIB001 proposed three types of authentication schemes to prevent Sybil attacks. Using a trusted entity (CA) to authenticate each node that wants to join the network is a centralized approach. Besides authenticating nodes centrally, each node may authenticate new nodes on its own. However, this approach does not scale to the network size. The last authentication scheme proposed by Douceur is based on trust relationships between authenticated nodes. This way, each node has to be authenticated only once by a single node when it joins the network. Other nodes accept this new node without further authentication. This approach is decentralized and scales to the network size. Yet, malicious nodes that do not show misbehavior until they are authenticated may misuse this scheme and allow other malicious nodes to join the network. Further, an open question is how to distinguish between benign nodes with a single identity and malicious nodes with multiple identities. To prove that one node does not have multiple identities, Douceur proposed that computationally expensive tasks have to be preformed by each node. By doing so, a Sybil node with n identities has to provide n times as much resources as a node with one identity, and the number of identities per node can be limited. Yet, as the resources available at a node can only be estimated, and due to the heterogeneity of devices in a P2P network, the tasks are designed for the weakest device assumed such that each node has to perform the same tasks to join the network. Due to this, malicious nodes may generate multiple virtual identities as long as they are able to perform the required tasks. Still, at least the number of identities is limited by this countermeasure for which Douceur proposes three tasks that demand (1) communication, (2) storage, or (3) computation resources from all identities simultaneously. An example for limiting the number of identities by computationally expensive tasks was proposed by Borisov BIB006 . Each node in the network has to solve computational puzzles at regular intervals. This way, even nodes with high resources are limited in generating multiple identities. The puzzles require a large amount of computation to be solved but the solutions are simple to verify. Due to this, the neighbors of the challenged node can verify the solution without a high computational cost. Castro et al. BIB002 proposed to bind the virtual node to a real world identity. This way, users have to authenticate themselves instead of their node. Also paying real world resources (e.g. money) to enter the network would limit the number of identities. Yet, these approaches require a CA for reliable user authentication. Analyzing the relationship of nodes can also be used to avoid or at least to reduce the impact of Sybil attacks. SybilGuard  is a prominent approach that analyzes graphs generated by using social networks in order to separate malicious nodes from honest ones. Besides social relationships, relationships between nodes during booting can also provide insights that can be harnessed to reduce the impact of Sybil attacks. As an example, Danezis et al. BIB004 proposed a modified routing metric to reduce the impact of malicious nodes in a DHT. Danezis et al. assume that Sybil nodes join the network at a single point of the bootstrapping graph. Due to this, malicious nodes are mostly connected to other malicious nodes only and, therefore, can not affect the rest of the network. Thus, the routing algorithm can benefit when related nodes are preferred during routing. Further, several approaches were proposed to improve the robustness of trust-based metrics to Sybil attacks BIB005 BIB008 . While those trust-metrics were developed to limit the impact of free riders, the proposed solutions also prevent that Sybil nodes improve their own reputation. As MANETs are decentralized and, therefore, a central trusted entity is (most probably) not available, detecting Sybil attacks is very challenging. The countermeasures for Sybil attacks proposed by Douceur BIB001 can also be used in the context of MANETs. Yet, as resources in a MANET are strongly limited and as network nodes differ strongly in the availability of resources (from mobile phones to high-performance computers), those countermeasure may not be efficient. Newsome et al. analyzed Sybil attacks in sensor networks. They proposed multiple countermeasures BIB003 to prevent or, at least, limit Sybil attacks. Newsome et al. assumed that each node in a network has a single network card and, therefore, is only capable of transmitting and receiving data at a single channel simultaneously. The Radio Resource Testing was proposed as a countermeasure that is based on this assumption. Each node detects Sybil nodes in transmission range by assigning each neighbor to a specific channel. Each neighbor has to transmit a message at a specific time on this channel. Whenever a neighbor does not transmit the message on the assigned channel at the expected time, a potential Sybil node is detected. This test has to be repeated multiple times to detect as many Sybil nodes as possible in the neighborhood. The approach is simple to implement but requires bandwidth for the active probing for malicious nodes. Further, Radio Resource Testing has to be repeated by each node in the network as no collaboration is performed. Newsome et al. additionally introduced the Code Attestation and the Registration countermeasures. As the code deployed on malicious and benign nodes differs, verifying the memory of a node provides information on whether this node behaves benignly. Also, registering and authenticating each node in the network at a central entity and using a list of known benign nodes may prevent Sybil nodes. Another promising approach uses the mobility of nodes in MANETs to detect Sybil attacks. For this, Piro et al. introduced the Passive Ad hoc Sybil Identity Detection (PASID) BIB007 . Each node of the network has to keep track of all nodes in transmission range by overhearing sent messages. This way, the sender of a transmitted message can be identified and, thus, neighbors can be detected. As Sybil nodes share the same physical location, nodes which always appear together are suspicious to be a single malicious node. Nodes in transmission range have to be monitored for a sufficiently long time until a node can be accused to be malicious. The specific amount of required time differs due to the mobility of nodes and the scenario size. In order to optimize the efficiency of the detection system, Piro et al. proposed a collaboration of nodes during monitoring. By exchanging collected data, malicious nodes can be detected more efficiently and faster. Yet, Piro et al. lack to provide a mechanism to identify trustworthy nodes that can be used for a collaborative monitoring. As PASID may falsely suspect benign nodes that travel in a group, Piro et al. introduced an extension to their algorithm. The PASID with Group Detection (PASID-GD) algorithm is capable of distinguishing between malicious and benign nodes that travel together in close proximity by monitoring collisions on the Medium Access (MAC) Layer. Whenever multiple benign nodes are in transmission range, collisions occur since nodes eventually start transmitting at the same time. In contrast, as Sybil nodes share the same network card, data has to be sent in a serial way and, thus, no collisions occur. This results in a strongly reduced probability of false positives during Sybil detection. Tangpong et al.  followed a similar approach to identify neighbors by overheard messages. In contrast to Piro et al, Tangpong et al. suggested an approach on how to prevent a misuse of the collaboration scheme for the detection of Sybil attacks. They proposed a PKI-based approach to enable a reliable collaboration and to validate exchanged observations between nodes to increase the effectiveness of the countermeasures. The observations are signed before they are transmitted in order to avoid benign nodes getting accused falsely by modified or forged observation messages. Due to the combined effort of multiple nodes, efficiency can be increased. Yet, this happens at the cost of a required PKI and the resource requirements of asymmetric encryption.