10-12-2012, 12:08 PM
SybilGuard: Defending Against Sybil Attacks via Social Networks
Defending Against.pdf (Size: 562.91 KB / Downloads: 14)
ABSTRACT
Peer-to-peer and other decentralized, distributed systems are known
to be particularly vulnerable to sybil attacks. In a sybil attack, a
malicious user obtains multiple fake identities and pretends to be
multiple, distinct nodes in the system. By controlling a large fraction
of the nodes in the system, the malicious user is able to “out vote”
the honest users in collaborative tasks such as Byzantine failure
defenses. This paper presents SybilGuard, a novel protocol for
limiting the corruptive influences of sybil attacks. Our protocol
is based on the “social network” among user identities, where an
edge between two identities indicates a human-established trust
relationship. Malicious users can create many identities but few
trust relationships. Thus, there is a disproportionately-small “cut” in
the graph between the sybil nodes and the honest nodes. SybilGuard
exploits this property to bound the number of identities a malicious
user can create. We show the effectiveness of SybilGuard both
analytically and experimentally.
INTRODUCTION
As the scale of a decentralized distributed system increases, the presence
of malicious behavior (e.g., Byzantine failures) becomes the
norm rather than the exception. Most designs against such malicious
behavior rely on the assumption that a certain fraction 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 vulnerable to sybil attacks [9],
in which a malicious user takes on multiple identities and pretends
to be multiple, distinct nodes (called sybil nodes or sybil identities)
in the system. With sybil nodes comprising a large fraction (e.g.,
more than 1/3) of the nodes in the system, the malicious user is
able to “out vote” the honest users, effectively breaking previous
defenses against malicious behaviors.
MODEL & PROBLEM FORMULATION
This section formalizes the desirable properties and functions of
a defense system against sybil attacks. We begin by defining our
system model. The system has n honest human beings as honest
users, and one or more malicious human beings as malicious users.
By definition, a user is distinct. Each honest user has a single (honest)
identity, while each malicious user has one or more (malicious)
identities. To unify terminology, we simply refer to all the identities
created by the malicious users as sybil identities. Identities are also
called nodes, and we will from now on use “identity” and “node”
interchangeably. All malicious users may collude, and we say that
they are all under the control of an adversary.
Nodes participate in the system to receive and provide service
(e.g., file backup service) as peers. Because the nodes in the system
may be honest or sybil, a defense system against sybil attacks aims
to provide a mechanism for a node V to decide whether or not
to accept or reject another node S. Accepting S means that V is
willing to receive service from and provide service to S. Ideally, the
defense system should guarantee that V accepts only honest nodes.
Because such an idealized guarantee is challenging to achieve, we
aim at providing the following guarantees that, while weaker, are
still sufficiently strong to be useful.
SYBILGUARD DESIGN
With the preceding high-level sketch in mind, this section provides
the detailed design of SybilGuard, explains the insights, and also
formally argues about its properties.
Social Network
Consider the social network defined in the previous section. Each
pair of friends shares a unique symmetric secret key (e.g., a shared
password) called the edge key. The edge key is used to authenticate
messages between the two friends (e.g., with a Message Authentication
Code). Because only the two friends need to know the edge
key, key distribution is easily done out-of-band (e.g., via phone
calls). A node can also revoke an edge key unilaterally simply by
discontinuing use of the key and discarding it.
Because of the nature of the social network and the strong trust
associated with the notion of friends in SybilGuard, we expect
node degrees to be relatively small and will tend not to increase
significantly as n grows. As a result, a user only needs to invoke
out-of-band communication a small number of times. In order to
prevent the adversary from increasing the number of attack edges
(g) dramatically by compromising high-degree honest nodes, each
honest node (before compromised) voluntarily constrains its degree
within some constant (e.g., 30). Doing so will not affect the guarantees
of SybilGuard as long as the social network remains fast mixing.
On the other hand, researchers have shown that even with rather
small constant node degrees, social networks (or more precisely,
small-world topologies) are fast mixing [6, 11].
SYBILGUARD UNDER DYNAMICS
Our protocol so far assumes that the social network is static. In
decentralized distributed systems, a typical user first downloads
and installs the software (i.e., the user is created). The node corresponding
to the user may then freely join or leave the system
(i.e., become online and offline) many times. Finally, the user may
decide to uninstall the software and never use it again (i.e., the user
is deleted). Node join/leave tends to be much more frequent than
user creation/deletion. For example, dealing with frequent node
join/leave (or “churn”) is often a critical problem faced by DHTs.
SybilGuard is designed such that it needs to respond only to user
creation/deletion, and not to node churn. The social network in this
paper always includes all users/nodes that have been created and not
yet deleted. In other words, many of the nodes in the graph can be
offline at any given time.
Dealing with Offline Nodes
In SybilGuard, a node communicates with other nodes only when
(i) it tries to verify another node, and hence needs to contact the
intersection nodes of the random routes, and (ii) it propagates its
registry and witness tables to its neighbors.
For the first scenario, because both the verifier V and the suspect
S perform multiple random routes (Section 4.4), there will likely
be multiple intersections. In fact, even a single route from V and
a single route from S may still have multiple intersections. The
verification can be done as long as a majority of V’s routes have at
least one intersection point online.
Attacks Exploiting Node Dynamics
This section shows that performing random routes along all directions
(Section 4.4) actually is necessary for security and provides
a defense against potential attacks under node dynamics. We first
explain the potential attack scenario. Suppose each node were to
perform only a single random route, and consider the example in
Figure 8, where w = 3. Here M is malicious and the other nodes are
honest. M’s random route is M !A!B!C. Thus A, B, and C
record M’s public key key1 in their registry tables. Now another honest
node D joins, and establishes edges with A and E. A updates its
routing table, and suppose that routes from M now go to D instead
of B. Being malicious, M launches the attack by changing its public
key to key2. Now A, D, and E will record key2 in their registry
tables. At this point, key1 is registered on w−1 nodes, while key2
is registered on w nodes. Both of them are likely to be successfully
verified with good probability.
The source of the above vulnerability is that when the routing
table on A changes, the system needs to “revoke” the stale entry
of key1 from the registry tables on B and C, because M’s random
route no longer passes through these nodes. Explicitly revoking
stale entries would introduce considerable complexity because B
and C may be offline. An alternative design would be to associate
TTLs with table entries, which unavoidably introduces a trade-off
between security and overheads to refresh expired entries.