Transcript SybilGuard Overview

SybilGuard: Defending Against
Sybil Attacks via Social Networks
Haifeng Yu
Michael Kaminsky
Phillip B. Gibbons
Abraham Flaxman
Presented by
John Mak, Janet Yung
1
Outline
•
•
•
•
•
•
Introduction to Sybil Attack
Model & Problem formulation
Sybil Guard Overview
Simulation Result & Analysis
Conclusion
Our views
2
Introduction to Sybil Attack
• P2p and decentralized, distributed
systems particularly vulnerable
• Malicious user obtains multiple fake
identities
• Gain large influence by “out vote” honest
users
3
Introduction to Sybil Attack
• Malicious user obtains multiple fake
identities
• Malicious behavior becomes a norm (e.g.
Byzantine failures)
• Many protocols assume < 1/3 malicious
nodes
• Easily create 1/3 nodes  Break defense
4
Introduction to Sybil Attack
• Centralized authority:
– Control Sybil attack easily
– Verify real life credential
– Hard for worldwide to trust
– Single point of failure – bottleneck, DOS
– Scare away potential users – requires
sensitive information
5
Introduction to Sybil Attack
• Decentralized approach is hard:
– Harvest (Steal) IP addresses
• No common IP prefix  Hard to filter
– Advertise BGP route on unused block of IP
address
– Botnet - Co-opt large number of end-user
machines
6
Introduction to Sybil Attack
• Not very successful defense approaches:
– Resource-challenge approach (computational
puzzles)
– Network coordinates
– Reputation system based on historical
behavior
7
Model & Problem Formulation
• Users:
– n honest users: single identity
– 1+ malicious user: multiple identities
• Identity:
– Also called “node”
– Sybil identity: malicious user’s identity
• Defense system
– Verifier node V accept another node S
– Ideally, V only accept honest nodes.
8
Model & Problem Formulation
• Bounding no. of sybil groups
– Divide all nodes into at most g equivalence
groups
– Sybil Group: equivalence group contains at
least one Sybil node
– Defense system guarantees no. of groups,
without need to know if the group is sybil
9
Model & Problem Formulation
• Bounding size of Sybil Group
– at most w nodes in a group
– limit no. of sybil nodes accepted each node can
accept
• Summary
– decentralized
– honest node accepts, and is accepted by most other
honest nodes
– honest node accepts a bounded number of sybil
nodes.
10
Social Network
•
•
•
•
Consists of users (nodes)
Human established trust relationships
Nodes connected by an edge (friend)
Real life relationship can bound both the number
and size of sybil groups
– Usually degree ~ 30
• Malicious user fools honest user to trust him/her
– an attack edge connected a malicious user and an
honest user
11
SybilGuard Overview
• Ensures honest user share at most one edge
with sybil nodes created by a malicious user
• A protocol enables honest nodes to accept a
large fraction of the other honest nodes
• SybilGuard does not increase or decrease the
number of edges in the social network as a
result of its execution
12
SybilGuard Overview
• Random routes direct random walk for all nodes
• Pre-computed random permutation
– one-to-one mapping from incoming edges to outgoing edges
• Random routes
– convergence property
– back-traceable property
• Multiple random routes of a certain length (w)
13
Random route
• Basis of SybilGuard
• Honest node (verifier) decides whether or
not to accept another node (suspect)
• Honest node’s random route
– highly likely to stay within the honest region
– Highly likely to intersect within (w) steps
• If there are (g) attack edges, the number
of sybil groups is bounded by (g)
14
Fast mixing property
• Assume social networks tend to be fast
mixing, which necessarily means that
subsets of honest nodes have good
connectivity to the rest of the social
network
• Assume the verifier is itself an honest
node
15
Attack edge
16
Key exchange
• Each pair of friendly nodes shares a unique
symmetric secret key (password) called the
edge key
• Key distribution is done out-of-band
• Each honest node constrains its degree within
some constant (e.g. 30) in order to prevent the
adversary from increasing the number of attack
edges (g) dramatically
17
Limits attack edges
• Limited number of attack edges (g)
• Adding new attack edge needs out-ofband verification
• Malicious users:
– Hard to convince honest users to be friends
– Quite difficult to do on a large scale
18
Common ways adversary may use
to increase g
• Befriending with honest users in real life
• Convince honest node to accept sybil nodes as
friends
• Compromises a large fraction of nodes in the
system.
– The adversary does not even need to launch a sybil
attack. SybilGuard will not help here.
• Botnet
– Challenging to acquire a botnet containing many
nodes that already in the system.
19
Random route
• Convergence property
– Once two routes traverse the same edge
along the same direction, they will merge and
stay merged (i.e. the convergence property)
• Back-traceable property
– Using a permutation as the routing table
further guarantees that the random routes are
back-traceable
• There can be only one route with length (w)
that traverses the same section of route (e)
20
Problems of random route
• Loop (same edge more than once)
– Unlikely to form in a fast mixing graph
• Enters the sybil region
– Unlikely according to:
THEOREM 1. For any connected and non-bipartite
social network, the probability that a length-w random
walk starting from a uniformly random honest node
will ever traverse any of the g attack edges is upper
bounded by gw/n. In particular, when w = Θ(√nlogn)
and g = o(√n/logn), this probability is o(1).
21
SybilGuard Design
• Use redundancy
– Instead of performing one random route
– A node with degree (d) performs random
routes along each of its edges
• Verifier V accept suspect S
– If exist d/2 routes from the verifier node
– One of V’s route accept S if that route
intersect with one of S’s route
22
Registry table
• Each node will maintain and propagate one’s
registry tables and witness tables to its
neighbors
• SybilGuard requires a node to register with all (w)
nodes along each of its routes by using public
key cryptography
• When a verifier V wants to verify S, V will ask
the intersection point between S’s route and V’s
route whether S is indeed registered
23
Registry & Witness tables
24
Bandwidth consumption
•
•
•
•
Studying a one million nodes social network
w=2000
Data sent by each node for registry table is small
Bandwidth consumption acceptable
– since the registry table updates are needed only
when social trust relationships change
25
Witness table
• Propagated and updated in a similar fashion as
the registry table
• Backward
• Updated when a node’s IP address changes
• Can be done lazily in the verification process
26
Verify process
• For a node V to verify a node S
– find the intersection nodes for all of its routes by the
witness tables downstream
– Authenticates the intersection node one by one by the
private key
– Ask that node to check if S’s public key is store in one
of its registry tables.
– If S’s public key is found, that route of V will accept S
27
Verify Process
• If more than half of the route from V accept S,
– node V will accept node S
– V will interact will S later by request S to encrypt its
message by its private key
• For the sybil nodes region with (g) attack edges,
– Polluted entries in registry tables bounded by g*w*w/2
– still less than half of the total number of entries n*d*w
– even with g*w tends to (n) with (d) being the degree
of each node (d >= 2) and (n) being the total number
of nodes
28
Route length w
Constraints:
• Must be sufficiently small to ensure remains
entirely within the honest region
• Must be sufficiently large to ensure that routes
will intersect with high probability
• w related to n
– Challenging because we do not know n for a
decentralized system
29
Route length w
• Determine locally by sampling
• Node A performs short random walk (e.g.
10 hops) at node B
• Assume B is honest (with high probability)
• A checks no. of hops for intersection with
their random routes
– A asks for the witness tables from B.
• Repeat above, calculate median value.
30
Sybil Guard under Dynamics
• Bypass offline nodes
– V verify other node S
• Probably multiple intersection points
• V have at least one intersection point online
– Propagate registry & witness tables
• User creation / deletion / ip address change
• Infrequent changes
– Lookahead route table
• Store information of next K hops
31
Sybil Guard under Dynamics
• Incremental routing table maintenance
– Instead of re-create a new permutation
– Make changes in current permutation
• Add
– X1  X2  X3  X4  (insert at end)
– X1  X2  (insert here)  X4  X3
• Delete “3”
– Before: X1  X2  X3  X4  X5
– After: X1  X2  X5  X4
32
Attacks Exploiting Node Dynamics
• Potential attacks under Node Dynamics
–
–
–
–
–
Malicious user M change public key to key2
Suppose DABC
Suppose revoke key1
Random routes along all directions
D’s key3 will overwrite key2
33
Probability of Intersection
• Kleinberg’s synthetic social network model
• a million-node graph with average node
degree of 24
34
Results with no Sybil Attackers
• Probability of random routes being loops
– Loop reduces effective length of random route
– Loop is very rare
– 99.3% of the routes do not form loops in their
first 2500 hops
35
Results with no Sybil Attackers
• Probably of honest node being accepted
– at least one intersection point online
– If at least 10 online/offline intersection points
 verification succeeds
– In 1 million-node graph
• w = 300
• probability = 99.96% having >=10 intersections
36
Results with no Sybil Attackers
• Estimate random route length w
–
–
–
–
Sampling technique to determine w
Node A choose a node B to determine w
Node B – not necessarily uniformly random
Need to re-estimate daily
37
Probability of routes in honest
region
• 1 million-node graph
• 100% for g <=2000; 99.8% for g=2500
• 0.2% -- Nodes befriending with sybil
attackers
38
Probability of honest nodes being
accepted
• Still 99.8% with 2500 attack edges
• Redundancy is necessary
39
Our views
• Hard to link real life to virtual network?
– My real life friends may not join the virtual
network
– Maybe centralized authentication better?
• 99.8% honest nodes accepted, but 0.2%
not accepted.
– The 0.2% is honest
40
Others’ views
• Fast mixing assumption in social network
– Japanese’s social network may not mix with
US social network?
41