CS 155

Spring 2013

Unwanted Traffic: Denial of Service Attacks

Dan Boneh

What is network DoS?

! Goal: take out a large site with little computing work ! How: Amplification
n

Small number of packets big effect

! Two types of amplification attacks:

n

DoS bug: w Design flaw allowing one machine to disrupt a service DoS flood: w Command bot-net to generate flood of requests
2

A high profile example: Estonia

Attacked sites: (started apr. 2007, lasted two weeks) Estonian ministerial sites Various Estonian commercial sites (more on this later)
3

DoS can happen at any layer

! This lecture:
n

n n

Sample Dos at different layers (by order): w Link w TCP/UDP w Application w Payment Generic DoS solutions Network DoS solutions

! Sad truth:
n

Current Internet not designed to handle DDoS attacks

4

Warm up:

802.11b

DoS bugs

! Radio jamming attacks: ! Protocol DoS bugs:

n

trivial, not our focus.

[Bellardo, Savage, 03]

NAV (Network Allocation Vector): w 15-bit field. Max value: 32767 w Any node can reserve channel for NAV seconds w No one else should transmit during NAV period w but not followed by most 802.11b cards De-authentication bug: w Any node can send deauth packet to AP w Deauth packet unauthenticated w attacker can repeatedly deauth anyone
5

Smurf amplification DoS attack

1 ICMP Echo Req Src: Dos Target Dest: brdct addr DoS Source 3 ICMP Echo Reply Dest: Dos Target

gateway

DoS Target

! Send ping request to broadcast addr (ICMP Echo Req) ! Lots of responses:
n

Every host on target network generates a ping reply (ICMP Echo Reply) to victim
6

Prevention: reject external packets to broadcast address

Modern day example

DNS Amplification attack:
DNS Query SrcIP: Dos Target (60 bytes) DoS Source

(Mar 13)

( 50 amplification )

EDNS Reponse (3000 bytes)

DNS Server

DoS Target

2006: 0.58M open resolvers on Internet (Kaminsky-Shiffman) 2013: 21.7M open resolvers (openresolverproject.org) 3/2013: DDoS attack generating 300 Gbps
7

e, Targeting and Frequency of Attacks

strated in Figure 1 (page 5) and again in Figure 13, the highest-bandwidth attack observed by respondents du period was a 100 Gbps DNS reflection/amplification attack. This represents a 102 percent increase over the is also the single largest increase in attack bandwidth year over year since the first report in 2005 and a 100 se in attack bandwidth since the reports inception.

Scale, Targeting and Frequency of Attacks

100
100 Gbps

90 80

Bandwidth (Gbps)

70 60 50 40 30 20 10 0 2005 2006 2007 2008 2009 2010

Figure 13
Source: Arbor Networks, Inc.

Review: IP Header format

0 31 Version Header Length Type of Service Total Length Identification Fragment Offset Time to Live Protocol Header Checksum Source Address of Originating Host Destination Address of Target Host Options Padding IP Data
9

! Connectionless
n n

Unreliable Best effort

Flags

Review: TCP Header format

! TCP:
n n n

Session based Congestion control In order delivery

31

Source Port Dest port SEQ Number ACK Number U A P P S F R C S S Y I G K H R N N Other stuff

10

Review: TCP Handshake

C SYN: ANC 0 C SYN/ACK:
SN randC

S Listening Store SNC , SNS Wait

SNSrandS ANSSNC

ACK:

SNSNC ANSNS

Established
11

TCP SYN Flood I: low rate

C SYNC1 SYNC2 SYNC3 SYNC4 SYNC5 S

(DoS bug)

Single machine: SYN Packets with random source IP addresses Fills up backlog queue on server No further connections possible

12

SYN Floods
OS Linux 1.2.x FreeBSD 2.1.5 WinNT 4.0

(phrack 48, no 13, 1996)

Backlog queue size 10 128 6 3 minutes

Backlog timeout:

Attacker need only send 128 SYN packets every 3 minutes. Low rate SYN flood
13

A classic SYN flood example

! MS Blaster worm
n

(2003)

Infected machines at noon on Aug 16th: w SYN flood on port 80 to windowsupdate.com

w 50 SYN packets every second.
n

each packet is 40 bytes.

w Spoofed source IP: a.b.X.Y where X,Y random.

! MS solution:
n n

new name: windowsupdate.microsoft.com Win update file delivered by Akamai

14

Low rate SYN flood defenses

! Non-solution:
n

Increase backlog queue size or decrease timeout : Syncookies: remove state from server
(when under attack)

! Correct solution
n n

Small performance overhead

15

Syncookies

[Bernstein, Schenk]

! Idea: use secret key and data in packet to gen. server SN ! Server responds to Client with SYN-ACK cookie:
n n

T = 5-bit counter incremented every 64 secs. L = MACkey (SAddr, SPort, DAddr, DPort, SNC, T)
w key: picked at random during boot
[24 bits]

n n

SNS = (T . mss . L) ( |L| = 24 bits ) Server does not save state (other TCP options are lost)
, SN=SNC+1 )

! Honest client responds with ACK ( AN=SNS

n

Server allocates space for socket only if valid SNS

16

SYN floods: backscatter

[MVS01]

! SYN with forged source IP SYN/ACK to random host

17

Backscatter measurement
/8 network

[MVS01]

! Listen to unused IP addresss space (darknet)

0 monitor 232

! Lonely SYN/ACK packet likely to be result of SYN attack ! 2001: ! 2013:

n

400 SYN attacks/week 773 SYN attacks/24 hours

(arbor networks ATLAS)

Larger experiments: (monitor many ISP darknets) w Arbor networks

18

SYN Floods II: Massive flood

(e.g BetCris.com 03)
! Command bot army to flood specific target: (DDoS)
n

20,000 bots can generate 2Gb/sec of SYNs (2003) At web site: w Saturates network uplink or network router
w Random source IP

attack SYNs look the same as real SYNs

n

What to do ???
19

Prolexic /

Verisign

! Idea: only forward established TCP connections to site

Lots-of-SYNs Lots-of-SYN/ACKs Prolexic
Proxy

Few ACKs

Forward to site

Web site

20

Other junk packets

Attack Packet TCP SYN to open port TCP SYN to closed port TCP ACK or TCP DATA TCP RST TCP NULL ICMP ECHO Request UDP to closed port Victim Response TCP SYN/ACK TCP RST TCP RST No response TCP RST ICMP ECHO Response ICMP Port unreachable 50 387 Rate: attk/day
[ATLAS 2013]

773

Proxy must keep floods of these away from web site

21

Estonia attack
! Attack types detected:
n

(ATLAS 07)

115 ICMP floods,

4 TCP SYN floods

! Bandwidth:
n

12 attacks:

70-95 Mbps for over 10 hours

! All attack traffic was coming from outside Estonia

n

Estonias solution: w Estonian ISPs blocked all foreign traffic until attacks stopped => DoS attack had little impact inside Estonia
22

Stronger attacks: TCP con flood

! Command bot army to:
n n n

Complete TCP connection to web site Send short HTTP HEAD request Repeat

! Will bypass SYN flood protection proxy ! but:

n

Attacker can no longer use random source IPs. w Reveals location of bot zombies Proxy can now block or rate-limit bots.
23

DNS DoS Attacks

! DNS runs on UDP port 53
n

(e.g. bluesecurity 06)

DNS entry for victim.com hosted at victim_isp.com

! DDoS attack:
n n

flood victim_isp.com with requests for victim.com Random source IP address in UDP packets (collateral damage) bluesecurity DNS hosted at Tucows DNS server DNS DDoS took out Tucows hosting many many sites

! Takes out entire DNS server:

n n

! What to do ???
24

Root level DNS attacks

! Feb. 6, 2007:
n n n

Botnet attack on the 13 Internet DNS root servers Lasted 2.5 hours None crashed, but two performed badly: w g-root (DoD), l-root (ICANN) w Most other root servers use anycast

Attack in Oct. 2002 took out 9 of the 13 TLD servers

25

DNS DoS solutions

! Generic DDoS solutions:
n

Later on. Require major changes to DNS.

! DoS resistant DNS design:

n

CoDoNS: [Sirer04] w Cooperative Domain Name System P2P design for DNS system: w DNS nodes share the load w Simple update of DNS entries w Backwards compatible with existing DNS
26

DoS via route hijacking

! YouTube is 208.65.152.0/22 (includes 210 IP addr)
youtube.com is 208.65.153.238,

! Feb. 2008:
n

n n

Pakistan telecom advertised a BGP path for 208.65.153.0/24 (includes 28 IP addr) Routing decisions use most specific prefix The entire Internet now thinks 208.65.153.238 is in Pakistan

! Outage resolved within two hours

but demonstrates huge DoS vuln. with no solution!
27

DoS at higher layers

! SSL/TLS handshake
[SD03] Client Hello Server Hello (pub-key) RSA Encrypt Client key exchange RSA Decrypt Web Server

RSA-encrypt speed 10 RSA-decrypt speed Single machine can bring down ten web servers
n

! Similar problem with application DoS:

Send HTTP request for some large PDF file Easy work for client, hard work for server.
n
28

Google DoS
qFirefox phishing/malware protection:

Browser downloads blacklisted list from Google

http://safebrowsing.clients.google.com/safebrowsing/gethash

List contains hashes of (prefixes) of badware sites Firefox consults list before following a URL Google adds / to blacklist

! Jan. 31, 2009:

For 55 minutes, all web sites marked as malware Reason: human error

qBrowser bug: Firefox no longer checks for / on list

29

Google DoS:

results

Amsterdam peering point

30

DoS Mitigation

31

1. Client puzzles
! Idea: slow down attacker ! Moderately hard problem:
n

Given challenge C find X such that

LSBn ( SHA-1( C || X ) ) = 0n
n n n

Assumption: takes expected 2n time to solve For n=16 takes about .3sec on 1GhZ machine Main point: checking puzzle solution is easy.

! During DoS attack:

n n

Everyone must submit puzzle solution with requests When no attack: do not require puzzle solution

32

Examples
! TCP connection floods (RSA 99)
n n

Example challenge: C = TCP server-seq-num First data packet must contain puzzle solution w Otherwise TCP connection is closed Challenge C based on TLS session ID Server: check puzzle solution before RSA decrypt.

! SSL handshake DoS: (SD03)

n n

! Same for application layer DoS and payment DoS.

33

Benefits and limitations

! Hardness of challenge:
n

n Decided based on DoS attack volume.

! Limitations:
n n

Requires changes to both clients and servers Hurts low power legitimate clients during attack: w Clients on cell phones and tablets cannot connect
34

Memory-bound functions
! CPU power ratio:
high end server / low end cell phone = 8000 Impossible to scale to hard puzzles
n

! Interesting observation:
n

Main memory access time ratio: w high end server / low end cell phone = 2 Solution requires many main memory accesses w Dwork-Goldberg-Naor, Crypto 03 w Abadi-Burrows-Manasse-Wobber, ACM ToIT 05
35

! Better puzzles:
n

2. CAPTCHAs
! Idea: verify that connection is from a human

! Applies to application layer DDoS

n

[Killbots 05] During attack: generate CAPTCHAs and process request only if valid solution Present one CAPTCHA per source IP address.

36

3. Source identification
Goal: identify packet source Ultimate goal: block attack at the source

37

1. Ingress filtering
! Big problem:

(RFC 2827,

2000)

DDoS with spoofed source IPs

! Question: how to find packet origin?

ISP

Internet

! Ingress filtering policy: ISP only forwards packets

with legitimate source IP.
(see also SAVE protocol)

38

Implementation problems
!
ALL ISPs must do this. Requires global trust. n If 10% of ISPs do not implement no defense

! Another non-solution: enforce source IP at peer AS

R1 Source AS

R2

R3

R4

dest Dest AS

Transit AS

Transit AS cannot validate packet source IP

39

2. Traceback
! Goal:
n n

[Savage et al. 00]

Given set of attack packets Determine path to source

! How: change routers to record info in packets ! Assumptions:

n n n

Most routers remain uncompromised Attacker sends many packets Route from attacker to victim remains relatively stable
40

Simple method
! Write path into network packet
n n

Each router adds its own IP address to packet Victim reads path from packet

! Problem:
n

Requires space in packet w Path can be long w No extra fields in current IP format
n

Changes to packet format too much to expect

41

Better idea
! DDoS involves many
packets on same path A1 A2 R6 A3 R7 A4 R8 R10 R12 V
42

A5

! Store one link in each

packet
n

Each router probabilistically stores own address Fixed space regardless of path length

R9

Edge Sampling
! Data fields written to packet:
n n

Edge: start and end IP addresses Distance: number of hops since edge stored

! Marking procedure for router R

if coin turns up heads (with probability p) then write R into start address write 0 into distance field else if distance == 0 write R into end field increment distance field
43

Edge Sampling: picture

! Packet received
n n

R1 receives packet from source or another router Packet contains space for start, end, distance

packet R1

e d R2 R3

44

Edge Sampling: picture

! Begin writing edge
n n

R1 chooses to write start of edge Sets distance to 0

packet R1

R1

0 R2 R3

45

Edge Sampling
! Finish writing edge
n n

R2 chooses not to overwrite edge Distance is 0 w Write end of edge, increment distance to 1 packet R1 R1 R2 1 R2 R3

46

Edge Sampling
! Increment distance
n n

R3 chooses not to overwrite edge Distance >0 w Increment distance to 2 packet R1 R2 R3 R1 R2 2

47

Path reconstruction
! Extract information from attack packets ! Build graph rooted at victim
n

Each (start,end,distance) tuple provides an edge

! # packets needed to reconstruct path

ln(d) E(X) < p(1-p)d-1 where p is marking probability, d is length of path

48

Details: where to store edge

! Identification field
n n n

Version

Used for fragmentation Fragmentation is rare 16 bits

Flags

Header Length Type of Service Total Length Identification Identification Fragment Offset Time to Live Protocol Header Checksum

! Store edge in 16 bits?

offset distance edge chunk 0 23 78 15

Source Address of Originating Host Destination Address of Target Host Options

n n

Break into chunks Store start + end

Padding IP Data
49

More traceback proposals

! Advanced and Authenticated Marking Schemes for IP
Traceback n Song, Perrig. IEEE Infocomm 01 n Reduces noisy data and time to reconstruct paths

! An algebraic approach to IP traceback

n

Stubblefield, Dean, Franklin. NDSS 02

! Hash-Based IP Traceback
n

Snoeren, Partridge, Sanchez, Jones, Tchakountio, Kent, Strayer. SIGCOMM 01

50

Problem: Reflector attacks

! Reflector:
n n

[Paxson 01]

A network component that responds to packets Response sent to victim (spoofed source IP)

! Examples:
n

DNS Resolvers: UDP 53 with victim.com source w At victim: DNS response Web servers: TCP SYN 80 with victim.com source w At victim: TCP SYN ACK packet Gnutella servers
51

DoS Attack
! Single Master ! Many bots to

generate flood

! Zillions of reflectors to
hide bots n Kills traceback and pushback methods

52

Capability based defense

53

Capability based defense

! Anderson, Roscoe, Wetherall.
n

Preventing internet denial-of-service with capabilities. SIGCOMM 04.

! Yaar, Perrig, and Song.

n

Siff: A stateless internet flow filter to mitigate DDoS flooding attacks. IEEE S&P 04.

! Yang, Wetherall, Anderson.

n

A DoS-limiting network architecture. SIGCOMM 05

54

Capability based defense

! Basic idea:
n

Receivers can specify what packets they want

! How:
n

n n n

Sender requests capability in SYN packet w Path identifier used to limit # reqs from one source Receiver responds with capability Sender includes capability in all future packets Main point: Routers only forward: w Request packets, and w Packets with valid capability
55

Capability based defense

! Capabilities can be revoked if source is attacking
n

Blocks attack packets close to source

R1 Source AS

R2

R3

R4

dest Dest AS

Transit AS

Attack packets dropped

56

Pushback Traffic Filtering

57

Pushback filtering
! Mahajan, Bellovin, Floyd, Ioannidis, Paxson, Shenker.
Controlling High Bandwidth Aggregates in the Network. Computer Communications Review 02.

! Ioannidis, Bellovin.

Implementing Pushback: Router-Based Defense Against DoS Attacks. NDSS 02

! Argyraki, Cheriton.

Active Internet Traffic Filtering: Real-Time Response to Denial-of-Service Attacks. USENIX 05.
58

Pushback Traffic Filtering

! Assumption: DoS attack from few sources

! Iteratively block attacking network segments.

59

Overlay filtering

60

Overlay filtering
! Keromytis, Misra, Rubenstein.
SOS: Secure Overlay Services. SIGCOMM 02.

! D. Andersen. Mayday.
Distributed Filtering for Internet Services. Usenix USITS 03.

! Lakshminarayanan, Adkins, Perrig, Stoica.

Taming IP Packet Flooding Attacks. HotNets 03.

61

Take home message:

! Denial of Service attacks are real.
Must be considered at design time.

! Sad truth:
n

Current Internet is ill-equipped to handle DDoS attacks

! Many good proposals for core redesign.

62

THE END

63