Various Types Of The Sybil Attack Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Many security mechanisms are based on specific assumptions of identity and are vulnerable to attacks when these assumptions are violated. For example, impersonation is the well-known consequence when authenticating certificate are stolen by a third party. Another attack on identity occurs when one identity certificates are purposely shared by multiple individuals. For example, it is doable to arrange Internet polls by using multiple IP addresses to submit votes, to gain advantage in any results of a chain correspondence, and is a familiar and a major problem in actual elections.

General target for Sybil attacks are reputation systems including real-world systems like eBay. Most proposes against such malicious behaviour rely on the assumption that a certain division of the nodes in the system are honest. For example, virtually all protocols for tolerating Byzantine failures assume that at least 2/3 of the nodes are honest. This makes these protocols susceptible to sybil attacks , With sybil nodes consisting a large fraction (e.g., more than 1/3) of the nodes in the system, the malicious user is capable to "out vote" the candid users, effectively breaking previous defences against malicious behaviours. Thus, an effective defence against sybil attacks would remove a primary practical obstacle to collaborative tasks on peer-to-peer (p2p) and other decentralized systems. Such tasks include not only Byzantine failure defences, but also voting schemes in file sharing, DHT routing, and identifying worm signatures or spam. A trusted central authority that issues and verifies recommendation unique to an actual person can control sybil attacks easily. For example, it may be difficult to select/establish a single entity that every user worldwide is willing to trust. Furthermore, the central authority can easily be a single point of failure, a single target for denial-of-service attacks, and also a bottleneck for performance, unless its functionality is itself widely distributed. Finally, requiring sensitive information or payment in order to use a system may scare away many potential users.

Defending against sybil attacks without having a trusted central authority is very difficult. Many decentralized systems these days aim to fight sybil attacks by binding an identity to an IP address. However, malevolent users can instantly yield (take) IP addresses.


The Sybil attack was best described by Douceur in the context of peer-to-peer networks. He pointed out that it could defeat the redundancy mechanisms of distributed storage systems. In practical situations, Douceur has shown this cannot prevent the attack. A wide variety of applications have considered the effects of the attack. Karlof and Wagner distinguished that the Sybil attack poses a risk to routing systems in sensor networks.


It may be extremely difficult for an rival to initiate such an attack in a network where every pair of neighbouring nodes uses a unique key to initialize frequency hopping or extend spectrum communication. This type of attack is very much prominent in Link Layer. Sybil attacks thus pose a significant threat to geographic routing protocols.

Dimension 1: Physical Layer

The base of Sybil Attack is actually at the physical layer but it becomes more punctual in the higher layers like link layer and network layer. In this class of attack the rival introduces a malicious node into the network. This can be done by compromising any rightful sensor node or by fabricating a new node fictional Identities In some cases, the attacker can simply create arbitrary new Sybil identities. For instance, if each node is identified by a 32-bit integer, the attacker can simply assign each Sybil node a random 32-bit value. Stolen Identities given a mechanism to identify legitimate node identities, an attacker cannot fabricate new identities. For example, suppose the name space is intentionally limited to prevent attackers from inserting new identities.

In this case, the attacker needs to assign other legal identities to Sybil nodes. This identity stealing may go undetected if the attacker destroys or temporarily disables the impersonated nodes The malicious node behaves as if it were of different identities from different places in the network. It is a famous Classical Attack.

Tackle: Normally this class of Attacks is tackled efficiently in the higher layers of the protocol stack in a WSN, though they originate in the physical layer only. Some preventive measures like fixing of the number of nodes in a WSN (which may depend on the type of application, the WSN is intended for) can be taken which will prevent the adversary from fabricating new identities.

DIMENSION 2: Data Link Layer

Data Aggregation: Data aggregation is an important part in Wireless Sensor Networks as it reduces the power consumption as well as the bandwidth requirements for individual message transmission. In this situation a Sybil Attack can be used to induce negative reinforcements. A single malicious node is sufficient to act as different Sybil Nodes and then this may give many negative underpinnings to make the aggregate message a false one.

Voting : Voting may be a choice for number of tasks in a Wireless Sensor Network. Many MAC protocols may go for voting for finding the better link for transmission from a pool of available links. Here the Sybil Attack could be used to stuff the ballot box. An attacker may be able to determine the outcome of any voting and off course it depends on the number of identities the attacker owns.

Tackle: Radio Resource Testing is a popular defence against Sybil Attack. If one node is interested in verifying whether its neighbours are valid or Sybil identities then this node can assign each of it's 'n' neighbours a different channel to broadcast some test messages. After this the node can listen to any channel and find out whether the neighbour that was assigned that channel is legitimate or not. Apart from this some secret information may be shared by a node with its neighbours and Sybil identities may be detected. But this may put some extra communication overhead.

DIMENSION 3: Network Layer

All multi-path routing protocols are vulnerable to Sybil attacks. The malicious node present in the network may advertise different identities. Then all paths in the multipath protocol may pass through the malicious node. And the protocol may have a picture of existence of different paths. But actually it is the same path through the malicious node. Sybil attack actually can fool the protocol giving a picture of existence of different routing paths to the destination but it is the same path through the Sybil node. On top of that even Geographic Routing Protocols are also vulnerable to Sybil attack. It is because of the fact that the same Sybil Identity or different Sybil Nodes may give an illusion of their presence at different Geographic Locations.

Tackle: There is no effective defensive mechanism available against sybil attack in Network Layer. But it is important to note that this attack can not survive only in routing layer. First of all, the attacker interested in sybil attack must attack the link layer and also she needs to get sybil identities. And very good defensive mechanisms for sybil attack in link layer are available through which this type of attack can be defended in the link layer itself.



Douceur proposes resource testing as a method of direct validation. In resource testing, it is assumed that each physical entity is limited in some resource. The verifier tests whether identities correspond to different physical entities by verifying that each identity has as much of the tested resource as a physical device. The resources proposed by Douceur to use for this purpose are computation, storage, and communication. Computation and storage are unsuitable for wireless sensor networks, because the attacker may be using a physical device with several orders of magnitude more computation and storage ability than a resource starved sensor node. The proposed method of testing communication is to broadcast a request for identities and then only accept replies that occur within a given time interval. This method is also unsuitable for wireless sensor networks because all the replies converging at the verifier will result in that part of the network becoming congested.


Radio Resource Testing: In random key pre-distribution, we assign a random set of keys or key-related information to each sensor node, so that in the key set-up phase, each node can discover or compute the common keys it shares with its neighbours; the common keys will be used as a shared secret session key to ensure node-to-node secrecy.

Our key ideas are:

1. Associating the node identity with the keys assigned to the node.

2. Key validation, i.e., the network being able to verify part or all of the keys that an identity claims to have.

Consequently given a limited set of captured keys, there is little probability that an arbitrarily generated identity is going to work, for the keys associated with a random identity are not likely to have a significant intersection with the compromised key set, making it hard for the fabricated identity to pass the key validation.

Again, for key validation, we have indirect and direct validation. In the case of direct validation, each node challenges an identity using the limited knowledge it possesses and makes a decision independent of other nodes. Thus nodes may not reach a globally consistent decision. With indirect validation, nodes could collaborate in validating a node, thus it is possible to reach a globally consistent decision. Of course we may also delegate the validation task to a central trusted party such as a base station. Generally speaking, indirect key validation is much more costly in terms of communication overhead than the direct case, because in the former case, if node IDi tries to validate IDj , messages only need to be exchanged between IDi and IDj ; while in the latter, it will also involve exchanging messages between other parties. Also indirect validation, if done improperly, could become the victim of blackmail attacks. However, indirect validation usually provides stronger defence against the Sybil attack, for, due to the memory constraint of sensor nodes, each individual node has limited knowledge that it could use to pose a challenge to an identity.

Different variants of existing random key pre-distribution techniques include the basic key pool approach [2, 4], the single-space pair wise key distribution approaches [1, 2], and the multi-space pair wise key distribution approaches [3].

So far, researchers have studied these techniques in the context of establishing secret keys between neighbouring nodes.

However, we shall study them for the purpose of defending against the Sybil attack. We propose an extension to the basic key pool approach to allow it to defend against the Sybil attack. We analyze and compare the effectiveness of several key predistribution schemes in defending against the Sybil attack.

Random Key Pre-distribution: For the basic key pool approach, by mapping a node's identity to the indices of its keys using a one-way function, and through means of indirect validation, a randomly generated identity has only probability p of being usable. An adversary has to try 1 p times on average to obtain a usable Sybil identity, thus for the sensor network to be immune to the Sybil attack, p has to be very small. Single-space pair wise key distribution, such as Blom's approach and the polynomial-based approach, is intrinsically resistant to the Sybil attack as long as the attacker does not capture more than n nodes. Here, direct validation ensures a globally consistent validation outcome. However, once the attacker succeeds in capturing more than n nodes, the entire space is compromised and he can fabricate an arbitrary number of identities.

Multi-space pair wise key distribution is superior to the single-space case in that the attacker has to compromise far more than n nodes to compromise one space, for each node is randomly assigned k out of m spaces, and he has to capture more than n instances of each space to compromise it. Besides, he has to compromise at least k spaces to pass full validation, which is even more difficult. To compare it with the key pool approach, we assume the nodes have equal memory constraint.400 nodes; he has a high probability of successfully forging usable Sybil identities in the key pool scheme; whereas in the multi-space pair wise scheme, the attacker will succeed only with a probability of around 0.05 even in the case without validation. We therefore believe the multi-space pair wise approach to be the best among these approaches.

Registration: One obvious way to prevent the Sybil attack is to perform identity registration. A difference between peer-to-peer networks and wireless sensor networks is that in wireless sensor networks, there may be a trusted central authority managing the network, and thus knowing deployed nodes. The central authority may also be able to disseminate that information securely to the network. To detect Sybil attacks, an entity could poll the network and compare the results to the known deployment. To prevent the Sybil attack, any node could check the list of known good identities to validate another node as legitimate. Registration is likely to be a good initial defence in many scenarios, with the following drawbacks. The list of known identities must be protected from being maliciously modified. If the attacker is able to add identities to this list, he will be able to add Sybil nodes to the network. Additionally, the deployment information that is checked against must be accurately and securely maintained by the entity that owns and/or manages the sensor network.

Position Verification: Another promising approach to defending against the Sybil attack is position verification. Here we assume that the sensor network is immobile once deployed. In this approach, the network verifies the physical position of each node. Sybil nodes can be detected using this approach because they will appear to be at exactly the same position as the malicious node that generates them. While there has been research on automatic location determination [5, 6], it remains an open research question how to securely verify a node's exact position. Such a method may

be difficult to find, but researchers have proposed methods to securely verify that a node is within a region [7]. By placing a limit on the density of the network, in-region verification can be used to tightly bind the number of Sybil identities that a malicious node can create. Note that a mobile attacker may be able to present several identities by being verified as one identity at one location, and then moving to a different location and being verified as a different identity. To defeat this type of attack, all nodes' positions could be verified simultaneously. Alternatively, given an upper bound on the attacker's mobility, it would only be necessary to test the nodes within a certain range simultaneously.

Code Attestation: Remote code verification or attestation is another promising new technique that could be employed to defend against many types of attacks, including the Sybil attack. The basic idea is to exploit the fact that the code running on a malicious node must be different from that on a legitimate node. Therefore, we could validate a node by verifying its memory content. Researchers have already started investigating this idea. Recently, Seshadri et al. proposed SWATT, a new technique to securely verify the code running on a remote embedded device. Though this technique is not readily applicable to a wireless network environment, hopefully in the near future code verification will become possible in wireless sensor networks, helping solve many problems including the Sybil attack. Future computing devices may be equipped with trusted hardware that provides strong security guarantees, such as a component developed by the Trusted Computing Group

(TCG) [8] (Formerly known as TCPA), or the Next-Generation Secure Computing Base (NGSCB) [9] (formerly known as Palladium) developed by Microsoft. Both TCG and NGSCB provide an attestation mechanism, which enables an external device to get integrity guarantees about the application state. Through a challenge-response protocol, another device can achieve assurance of the code running on a device. However, the high cost and energy consumption of trusted hardware devices precludes using them in current sensor devices. Dropping costs and increasing efficiency, however, make trusted hardware a promising technique to secure future sensor networks.


The taxonomy and classification are very essential in elaborating and analyzing the threat posed by the Sybil attack and their corresponding justification mechanism. Radio resource verification can be disrupted with custom radio hardware and validation proves pricey in terms of energy.

Position verification can only put a bound on the number of sybil nodes and an attacker can generate unless it is able to verify node position precisely. Random key pre-distribution is most promising which is already desirable in many applications for secure communication. Here we presented several novel methods by which a node can authenticate whether other identities are sybil identities and including radio resource testing, random key distribution position verification and registration etc.