Transcript Slide 1

This is not an impossible architecture – Incremental Deployment Compatible
Unlike any previous papers, this paper addresses a lot of issues connected to DoS
attacks
This paper comes from the author of Active Networks! Remember the 835 citations?
This paper has 83 citations and was regarded as a powerful technique by many authors.
These techniques are powerful because they seek to block
or explicitly limit unauthorized users…
This presentation was inspired from D. Witherall’s original work
Presentation by: Rahul Potharaju
•
Ingress filtering
Discards packets with widely spoofed
addresses at the edge of the network
Attack packets are dropped before
they arrive at the destination!
•
Traceback
Uses routers to create state so that
receivers can reconstruct the path
of unwanted traffic
•
Fair Queuing
Each flow gets its fair share of
Bottleneck bandwidth
k hosts attacking a destination would
lower the bandwidth by 1/k
•
SOS, MayDay
Rely on an offline authenticator
Requires prior-arrangement
•
SIFF
Refines the previously proposed
capability approach
Doesn’t concentrate much on
security of proposed method
The base already existed and improving – TVA is a robust approach to the earlier
proposed methods using capabilities
It allows the destination to control what it receives – No more false bills!
Overcomes the shortcomings of current packet filtering techniques
Automated validation of senders without prior arrangement
Ensures that any two nodes can communicate regardless of the ‘k’ malicious nodes
Capabilities must be granted by the destination to the sender, so that they can be
stamped on packets.
Capabilities must be unforgeable and not readily transferable across senders and
destinations
Routers must be able to verify capabilities without trusting hosts.
Capabilities must expire so that a destination can cut off a sender from whom it no
longer wants to receive packets.
Capabilities must add little overhead in the common case.
The network must discard unwanted packets before they reach the destination
 Each packet must carry information that tells a router whether it is wanted by
the destination in the first place.
And that’s it… couldn’t be much simpler than this!
The explicit identification information is known as Capability
Adds capabilities
Request
(Part of TCP SYN packet)
Sender
Router
Router
Destination
Response
(Part of TCP SYN/ACK packet)
Routers add pre-capabilities
Initial request channel should not be open to DoS attacks either by:
Flooding the destination
Rate limit requests at all network locations so that they cannot consume all
bandwidth
Request packets comprise only 5% of the total link capacity
Blocking the requests of legitimate senders
Use per-source fair queuing to ensure that no source can overwhelm others
Spoofing? No problem because PSFQ requires authenticated source
identifier
Path Identifier – Each router at the trust boundary tags (16—bit values) the packet
with a small value derived from its incoming interface – Identifies the upstream party
Fair queue requests using the tag to identify a queue
Two Advantages:
Tag space is bounded
 Number of queues is bounded
 Router resources are bounded
Uses Trust domains
Rate-limited
Preferential
Remaining Bandwidth
This is a matter of policy, and it depends on the role, the destination plays in the
network.
Client -> Server possible but other way not possible (firewalls, NAT etc.)
Public server -> Clients: Grant all requests with a default number of bytes and
timeout, using the path identifier to fairly serve different sources when the load is
high.
If ( senders_action == misbehave )
Add sender to blacklist
As a result: Sender’s capability will expire
Hashing Mechanism = f ( source IP, destination IP, timestamp, router secret)
Each router that forwards a request packet generates its own pre-capability and attaches
it to the packet.
Router secret is changed at twice the rate of the timestamp rollover, and uses the
previous secret to validate capability.
Pre-Capability expires within at most the timestamp rollover period and each is valid
for about the same time period
Receiver: Oops… I authorized some unwanted traffic
Attacker: Good… I can flood until my capability expires!
Fatal problem:
Evan a small number can raise a DoS attack
Solution:
Grant the right to send up to N bytes along a path within the next T seconds.
Routers verify their portion of the capabilities by re-computing the hashes
much as before, expect that now two hashes are required instead of one.
The router now perform two checks, one for N and one for T.
Bounding Algorithm:
If ( flow rate for a valid capability > N/T )
Keep router state
If ( pkt_rcvd && no_state_for_pkt)
Track byte count and associate a minimal ttl with state = L*T/N
If ( ttl == 0)
Reclaim the state for use with a new capability
Max bytes used
Creates state
ttl hits 0  Reclaim state
Worst case
Total of 2N bytes
before capability
expires
•
Efficient Capabilities:
– Security benefits from long capabilities ( a long key length).
•
Route Changes and Failures:
– Demote packets to be the same priority as legacy traffic by changing a bit
in the capability header.
•
Balancing Authorized Traffic:
– Floods of authorized traffic: A pair of colluding attackers can authorize
high-rate transfers between themselves and disrupt other authorized
traffic that shares the bottleneck – Use Fair Queuing
•
Short, Slow or Asymmetric Flows:
– TVA is designed to run with low overhead for long, fast flows that have a
reverse channel. Short or slow connections will experience a higher
relative overhead. But wait:
• Most bytes belong to long flows  Effect on aggregate efficiency would be small
• Design does not introduce any latency on handshaking  Remember piggybacking?
• Short flows are less likely because flows are defined from a sender to a destination basis
There are no separate capability packets! All packets carry a header that extends the
behavior of IP.
Adds capabilities
Request
(Part of TCP SYN packet)
Two types of capability packets:
Sender
Router
Destinatio
n
Router
Response
(Part of TCP SYN/ACK packet)
Request Packets: Carry a list of blank
capabilities and path identifiers that are filled
in by routers as requests travel towards
destination
Routers add pre-capabilities
Regular Packets: Two types, packets that carry
both a flow nonce and a list of valid
capabilities, and packets that carry only a flow
nonce
If a regular packet does not pass the capability
check, it may be demoted to low priority traffic
that is treated as legacy traffic.
Packets
carrying
capability
information
TVA
Protocol
Hosts that
act as
senders and
destinations
Routers that
process
capability
information
Indicate the type and format of the
packet
Each capability has a 64-bit value,
broken down into 8 bits of router
timestamp in seconds ( a modulo 256
clock) and 56 bits of a keyed hash
19
Adds capabilities
Request
(Part of TCP SYN packet)
Sender
Router
Router
Destination
Response
(Part of TCP SYN/ACK packet)
Packets
carrying
capability
information
Routers add pre-capabilities
Sender Side:
If ( no valid capability )
Piggyback request onto TCP SYN
TVA
Protocol
Destination Side
If ( willing to authorize )
Piggyback capabilities onto TCP SYN/ACK
Send request for reverse directions
Else
Return empty capability list piggybacked onto
TCP RST
Hosts that
act as
senders and
destinations
Routers that
process
capability
information
Routers route and forward packets as required by IP and additionally process packets
according to the capability information that they carry..
Adds capabilities
Request
(Part of TCP SYN packet)
To process a request packet
Sender
if( at trust boundary )
add pre-capability to the end of the list and add
a new path identifier
Router
Destinatio
n
Router
Response
(Part of TCP SYN/ACK packet)
Routers add pre-capabilities
To process a regular packet
If ( pkt_authorized )
update cached information & schedule for
forwarding
Packets
carrying
capability
information
Locate an entry for the flow using source &
destination IPs
if ( cached entry )
update byte count
else
check capability and allocate entry
if ( valid_capability & renewal pkt)
mint pre-capability
TVA
Protocol
Hosts that
act as
senders and
destinations
Routers that
process
capability
information
Uses ns to simulate TVA, SIFF, pushback and legacy Internet
Rate-limit capability requests to 1% of link capacity (down from default 5% to stress the design)!
Setup fixed length transfer between legitimate users and destination under various attacks and
measure:
i) the average fraction of completed transfers
ii) the average time of the transfers that complete
Reason: DoS attacks cause heavy loss  Slow transfers and eventual application abortion
SIFF - treats capacity requests as legacy traffic, does
not limit the number of times a capability is used to
forward traffic, and does not balance authorized
traffic sent to different destinations
Pushback - recursively pushes destination-based
network filters backwards across the incoming link
that contributes most of the flood.
Dumbbell Topology
Simulation Results
Attacker floods the destination with legacy traffic at 1 Mb/s
TVA:
Legacy traffic has a lower priority compared to
request traffic
SIFF:
Treats both legacy and request packets as
equally low priority traffic
Pushback:
Performs well but as the number of attackers
increase, it cannot isolate attack & legitimate
traffic
Attacker floods the destination with request packets at 1 Mb/s
TVA:
Request packets are rate-limited
SIFF:
Treats both legacy and request packets as
equally low priority traffic
Pushback:
Treats requests as regular data
Attacker is supported by a colluder
TVA:
Transfer time slightly increases but no user will
be starved
SIFF:
Treats both legacy and request packets as
equally low priority traffic  Users are
completely starved
Pushback:
Treats requests as regular data
Prototyped TVA using the Linux netfilter framework
Host Portion – Implemented as a user-space proxy :: Allows legacy applications to run
without modifications
Router Portion
Kernel module using the AES-hash for pre-capabilities and SHA1 for
capabilities
Dual-processor 3.2 GHz Pentium Xeon machine running Linux 2.6.8 Kernel
Kernel packet generator to generate different types of packets
Each run: One million packets of each type.
Five Runs: Recorded the average number of instruction cycles for the router to process
each type of packet
Regular with a cache entry is the most
common so not a big deal!
Regular without a cached entry – Two
has functions
Renewal without cached entry – Three
hash functions
Output rate α Input rate
Reaches a peak depending on the type
of input packet
Problem of spoofed short renewal
packets can be solved using Lazy
Receiver Processing
Implementation can handle 100 Mbps
interfaces and intend to demonstrate
gigabit handling in the near future
Breaking the hash scheme
• TVA uses standard cryptographic functions with sufficient
amount of keys material and changes keys every 128
seconds!
• TVA uses a packet format that does not expose precapabilities in the first 8 bytes that are visible in ICMP error
(using ICMP error messages)
messages
Observe pre-capabilities
Steal Capabilities
• Attacker will not generally be able to send packets along the
same path as the authorized sender because capabilities are
bound to a specific source, destination and router.
Eavesdropping
(includes a compromised
router)
• The compromised router is another attacker! As long as there
are capability routers in the middle, DoS attacks are still
limited.
Spoof authorized traffic
• This attack has little effect on a sender’s traffic if perdestination queuing is used, which is TVA’s default.
•
No Flag Day: The design requires both routers and host to be upgraded, but does
not require a flag day.
•
Incremental Deployment Compatible : Routers can be upgraded incrementally, at
trust boundaries and locations of congestion, i.e., the ingress and egress of edge
ISP’s
•
Host must be upgraded. This can be occurred with proxies at the edges of customer
networks in the manner of a NAT box or Firewall.
•
Expect to use DNS to signal which hosts can handle capabilities in the same manner
as upgrades
•
There are three components in a network: Sender, Receiver and Destination. If one
considers DoS as a serious problem, then we have to alters one of the three
components!
•
Main contribution is to flesh out the design of a comprehensive and practical
capability system for the first time
•
Practical design with an implementation to support it
•
Constrained design to be easy to transition into practice – Incremental deployment
•
We have a website! http://www.ics.uci.edu/~xwy/doslimit.html
•
Agreed that this is a new architecture but wait… it has its advantages and is
incrementally deployable
•
This architecture can be implemented and tested either internally or globally
•
We considered attackers to be like-minded and are working on getting results for
dynamic behavior patterns
•
The attacker number we used will be increased by the next paper!
•
Hash functions affect the performance but then there is a law of equivalence: One
cannot gain anything without first giving something in return!
–
•
If there’s a better way, let us know and we’ll evaluate it…
We don’t claim this to be the best design, its just a better design…