Transcript SOS: Security Overlay Service - Department of Computer Science

SOS: Security Overlay Service
Angelos D. Keromytis, Vishal Misra, Daniel
Rubenstein- Columbia University
ACM SIGCOMM 2002 CONFERENCE, PITTSBURGH PA,
AUG 2002
Presented by Wei Zhou
References
 A. Keromytis, V. Misra and D.
Rubenstein, “SOS: Secure Overlay
Services”, the Proceedings of the ACM
SIGCOMM Conference, August 2002
 D. Cook, “Analysis of Routing
Algorithms for Secure Overlay
Service”, Computer Science
Department Technical Report CUCS010-02, 2002
Outline





Introduction
System Design Rationale
System Architecture
Performance Analysis
Discussion
Introduction – the problem
 The Communication by Emergency Services
 A critical service (the target) that resides in a
well-known location (i.e. IP address).
 A group of pre-confirmed users, located
anywhere in the wide-area network, who have
authentication to communicate with that location.
 Example scenario
 Without protection, such a service can be
easily flooded by DDoS attacks
Design Rationale
 Intuition
 A firewall standing in front of the server
Firewall
Server
 One firewall is NOT enough
Design Rationale (cont.)
 Replicate the firewall functionality, thus have a
distributed firewall network.
 A dedicated router set filtering packets that are
not from one of the firewalls.
Filtering router set
Server
 Assume high-powered routers with light-weight
computation.
Design Rationale (cont.)
 How to deal with spoofed traffic purporting to
originate from one of these firewalls.
 Target selects a small set of these firewalls as
the designated authorized forwarding stations,
and hides their identities to the public.
 Why overlay network?
 Highly dynamic nature – a node can easily join
in or be taken out from an overlay network.
 High level of connectivity – there is a (logic)
link between any pair of participating nodes in
an overlay network.
System Architecture – version 1
Secret
Secret
Servlet
Secret
Servlet
Servlet
Source
Point
Overlay nodes
SOAP
SOAP
Target
Filtered region
System Architecture (cont.)
 Preliminary routing mechanism
 Each node receiving a packet forwards the
packet to another randomly chosen overlay node,
until the packet reaches a secret servlet.
 Not efficient
 suppose N overlay nodes and Ns secret servlets,
the expected number of intermediate overlay
network nodes that a packet will have to go
through is O(N/Ns).
 Enhanced routing mechanism
 Actually CHORD service
 Enhance the routing efficiency to O(logN)
 Need to introduce one more type of nodes, beacon,
who also knows the identity of the secret servlet
System Architecture – version 2
Beacon
Beacon
Beacon
Source
Point
Secret
Secret
Servlet
Secret
Servlet
Servlet
Overlay nodes
SOAP
SOAP
Target
Filtered region
Overlay Routing Algorithm –
CHORD Service
m=5

30
1
3


25
7+1: 10 
7+2: 10
7+4: 12
7 7+8: 16
7+16: 25
22
17+1: 22 17
:
:
10
16
16+1: 17
16+2: 22
16+4: 22
16+8: 25
16+16: 1
12

Each node with an ID via a
hash function.
Suppose 2m possible ids.
Each node contains a table of
m entries.
The ith entry in the table of
node x is the 1st node whose
id is >= (x + 2i-1(mode 2m))
If node x receives a packet
destined to node y, it
forwards the packet to the
node in its table whose id is
closest to, but <= y
For a node y not in the
overlay, the node whose id is
closest to but >= y stores
information about y (i.e.
knows that y is not in the
overlay)
Overlay Routing Algorithm –
CHORD Service
 CHORD guarantees that a packet will get to its
destination through no more than logN nodes, where
N is the size of the overlay.
 Multiple destination nodes for a given identifier can be
created by using different hash functions. (e.g. the
target’s IP can be mapped to several beacons)
 By choosing the right class of hash functions, the
sequences of nodes used to carry a packet from a
node to the destination are independent from one
another. (e.g. the paths from a source to different
beacons are independent)
 CHORD is robust to changes in overlay membership:
each node’s list is adjusted to account for nodes
leaving and joining the overlay.
Architecture Summary





A site (target) selects a number of SOS nodes to act as secret
servlets and sets up its filtering perimeter;
A secret servlet, upon informed of its role in the system (request
authenticity verified), computes the key k for each of a number of
well-known consistent hash functions, based on the target site’s
network address range. Each of these keys will identify a number
of overlay nodes that will act as beacons for that target site.
Beacons, will be informed by either the servlets or the target of
the servlets’ ids (request authenticity verified).
A source must first contact an overlay access point (SOAP). After
authenticating and authorizing the request, the SOAP securely
routes all traffic from the source to the target to one of the
beacons. The SOAP (and all subsequent hops on the overlay) can
route the packet to an appropriate beacon in a distributed fashion
using Chord by applying appropriate hash function to the target’s
address to identify the next hop on the overlay.
The beacon then routes the packet to a secret servlet that then
routes the packet (through the filtering) to the target.
Architecture Summary (cont.)
 If a SOAP is attacked, the confirmed source
point can simply choose an alternate SOAP
by which it enters the overlay.
 If a node within the overlay is attacked, the
node simply exits the overlay until the
attack terminates.
 If a beacon is attacked, it exits and the
CHORD service self-heals by choosing a new
node as that beacon for that hash function.
 If a secret servlet is attacked or its identity
is breached, the target can simply choose
alternate secret servlets.
Performance Analysis of SOS

Assumptions





An attacker knows all the overlay nodes, and can attack any of
them by bombarding them with traffic, however, an attacker
can only manipulate finite resources and bandwidth.
An attacker does not know which nodes are secret servlets or
beacons, nor will they infer these identities.
Attackers have not breached the security protocols of the
overlay, i.e. their packets can always be identified by SOS
nodes as being illegitimate
Each legitimate user can access the overlay through a limited
number of SOAPs, but different users access the overlay
through different SOAPs
Three analysis models



A Static Attack
Dynamic Attacks and Recovery
Attacking the Underlying Network
Performance Analysis (cont.)
 A Static Attack


Ph(a, b, c): the probability that a set of b nodes selected
randomly from a ≥ b nodes contains a specific subset of c
nodes.
Notations:










T – the target
{Si(T)} - the set of secret servlets
Us = |{Si(T)}|
{Ai(T)} – the set of SOAPs
Uo = |{Ai(T)}|
{Bi(T)} – the set of beacons
Ub = |{Bi(T)}|
na - the number of nodes the attacker attacks
US,T – a random variable that equals 1 if S can reach T during
an ongoing attack and 0 otherwise
Pr[UT,S = 1] = (1 – Ph(N, na, Us))(1 – Ph(N, na, Ub))(1 – Ph(N,
na, Uo))
Performance Analysis (cont.)
Us = Uo = Ub = 10, na varies
Discussion
 Combines IP Security, IP router filtering, and Overlay
network routing techniques.
 Proactive mechanism.
 SOAPs and secret servlets both are a part of
distributed firewalls.
 The more the number of nodes in an overlay network,
the more effectively the SOS protects its users from
DDoS attacks.
 Further questions
 Attacks from inside the overlay
 A Shared Secure Overlay – scalability issues
 Timely delivery
Thank you!