Transcript Games and the Impossibility of Realizable Ideal Functionality

Sybil attacks as a mitigation strategy
against the Storm botnet
Authors:Carlton R. Davis, Jos´e M. Fernandez,
Stephen Neville†, John McHugh
Presenter: Chia-Li Lin
Outline
Introduction
Storm botnet




DHT
k-buckets && lists
Dynamic lists
Four message types
Sybil attack
Goals and parameter
Simulation Data
Fail Factor
Conclution
2
Introduction
The Storm botnet is currently one of the most
sophisticated botnet infrastructures.
IRC bot

easy to detect and disrupt once the server is identified
peer-to-peer (P2P) bot

3
more resilient
Storm Botnet
Storm uses a modified Overnet P2P protocol
for its communication architecture.
The main difference between the Storm and overnet
P2P infrastructure


4
Overnet P2P network is that Storm nodes XOR encrypts their
messages using a 40-bit encryption key
The regular Overnet nodes do not encrypt their messages
DHT
Overnet implements a distributed hash table
algorithm called “Kademlia”
Each node participating in an Overnet network
generates a 128-bit ID for itself when it first joins the
network.
5
k-buckets and lists
Each node in an Overnet network stores contact
information about some of the other nodes in the
network, in order to appropriately route query
messages. This information is organised in lists
Lists of (IP address, UDP port, ID) triplets
The triplets are in the form <ID>=<IP><port>00


<ID> is the 128-bit node ID
<IP><port>00 is the IP address and UDP port in
hexadecimal format
format:008052D5853A3B3D2A9B84190975BAFD=53855152054A00
6
Dynamic k-bucket (lists)
If a peer is already in the recipient k-bucket
Move it to the tail of the k-bucket.
Otherwise



If there are rooms left in the k-bucket, the peer’s triplet is
simply added to the tail of the k-bucket.
If there is no room left, ping the head node
 If a node does not respond, it is evicted from the k-bucket and
the recipient adds the peer to the tail.
 If all nodes respond, the peer contact is discarded.
7
Four Message Types
The Kademlia protocol (which Overnet implements)
provides the four message types outlined below:
PING: if it is on-line
STORE: store a <key, value> pair
FIND_NODE: search for a node ID
FIND_VALUE: search for a <key, value> pair
8
Sybil Attack
Holz, Steiner, Dahl, Biersack, and Freiling presented
“Measurements and Mitigation of Peer-to-Peer-based
Botnets: A Case Study on Storm Worm” showing how
to use sybils to infiltrate the Storm botnet.
That is able to create thousands of sybils on one
single physical machine
9
Simulation step
(a) Send PING, FIND_NODE, and FIND_VALUE
messages to non-sybil nodes in attempt to
get their IDs in the peerlist of the nodes
(b) Respond to FIND_NODE and
FIND_VALUE queries with false information
10
Three Goals
What effects do Sybil growth rate is :
a)
b)
c)
equal to the botnet growth rate
half the botnet growth rate
twice the botnet growth rate
What effects do time duration of Sybil attacks have
on the degree of success in disrupting the botnet
communication
Do botnet design choices, such as the size of the
peerlist, have any bearing on the effectiveness of the
Sybil attacks
11
R-Reachability
To assess the effectiveness of the Sybil attack
in disrupting the botnet C&C infrastructure
12
Insertion Ratio of Sybils
(IR) : insertion ratio of sybils in the peer-lists
(SI) : the total occurrences of sybils in the
peer-lists
(N) : the product of the final number of
nodes
(l) : the peer-list size
13
Parameter
Sybil birth rate (SBR) varies

from 0 to 2 times the net botnet growth rate
(BGR)
Peer list sizes l {100, 200, 300}
Time-steps {10, 20, 30}
R-Reachability (r = 1 radius)
14
Simulation Data[1/2]
15
SBR/BGR
total sybils
0.5
1000
1
2000
2
4000
r = 1 radius, l = 200,time-step=10
insertion ratio(IR)
4.22%
8.34%
15.43%
standard deviation
0.5123%
0.5293%
0.8730%
SBR/BGR
total sybils
0.5
3000
1
6000
2
12000
r = 1 radius, l = 200,time-step=30
insertion ratio(IR)
10.53%
18.67%
30.94%
standard deviation
0.5422 %
0.6922
1.2172
SBR/BGR
total sybils
0.5
2000
1
4000
2
8000
r = 1 radius, l = 100,time-step=20
insertion ratio(IR)
7.62%
13.94%
24.74%
standard deviation
0.8577 %
1.2987%
1.6265%
SBR/BGR
total sybils
0.5
2000
1
4000
2
8000
r = 1 radius, l = 200,time-step=20
insertion ratio(IR)
7.88%
14.34%
24.82%
standard deviation
0.6078%
0.6668%
1.0678%
SBR/BGR
total sybils
0.5
2000
1
4000
2
8000
r = 1 radius, l = 300,time-step=20
insertion ratio(IR)
7.88%
14.35%
24.83
standard deviation
0.6050
0.9602
0.7827
Simulation Data[2/2]
16
Fail Factor
Fault tolerant voting schemes
Fastest response path and time
Detectable by the botnet operators
17
Fastest Response Path
18
Conclution
Sybil atack is not very efficient to mitigate
Storm worm peer-to-peer botnet.
19