Security Issues - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 163

7.4 Sybil Attacks
It is conceivable that a malicious user in the P2P network controls a large
number of peers. Specifically, for instance, such a user runs a large number
of P2P client programs on the network so that different peers are actually
representing the same physical user behind the scene. Such dominance in
participation could possibly lead to controlling the operations of the P2P
system. For example, the malicious user can easily out-vote other honest peers
in the system. This is commonly known as the Sybil attack [Douceur, 2002,
Dinger and Hartenstein, 2006]. The root of this problem is the mapping of
peer identifiers to physical users.
Dinger and Hartenstein [Dinger and Hartenstein, 2006] formalized the
Sybil attack as follows. The set of participants in the P2P network is denoted
by: N ={p 1 , . . . , p n }. The set of physical users in the network is denoted
by: U ={u 1 , . . . , u m }. We have n≥m. The set of peers controlled by (or
representing) a physical user u i is denoted by N i . It follows that N i N j for

all i = j, and N 1 N m = N . Now we can characterize a Sybil attack

launched by user u i as|N i |> c, for a certain constant threshold c.
To prevent Sybil attack, obviously we need a mechanism to avoid assign-
ing multiple peer identifiers to the same physical user. However, under the
assumption that a powerful malicious user can modify the P2P client pro-
gram that is being used, such identifier assignment function cannot be incor-
porated in the P2P client program. In other words, the assignment process
has to be “external” to the client. Now, we have two choices. First, we can
use a centralized entity such as a server (e.g., a particular bootstrap server or
a tracker) for securely assigning identifiers based on each P2P client's phys-
ical attributes (e.g., IP address, MAC address, etc.). However, doing this is
somewhat contradictory to the original intent of a P2P network because a cen-
tralized authority is involved. Furthermore, this centralized authority would
become a single-point-of-failure or single-point-of-attack.
To use a distributed approach in identifier assignment, multiple currently
participating peers have to be involved. For example, in the DHT-based algo-
rithm suggested by Dinger and Hartenstein [Dinger and Hartenstein, 2006],
multiple peers on a Chord ring have to verify and approve the identifier as-
signed to a new peer. The identifier is generated based on the IP address of
the new peer. A possible loop-hole in this approach is that a malicious user
can still get multiple identifiers by using spoofed IP addresses.
Rowaihy et al. [Rowaihy et al., 2007] described another fully distributed
approach for identifier assignment in a P2P network. Specifically, their ap-
proach is designed for a tree-structured network. In order to be admitted into
the network (i.e., obtaining a legal ID), a new peer has to contact a tree-leave
peer in the tree. The new peer then needs to solve a cryptographic puzzle
which is designed to be resource (e.g., time or memory) constrained. Solv-

. . .