Transcript Darpa Presentation - Bad Request

Routing and Denial of Service:
Attacks and Defenses
Vyas Sekar
Carnegie Mellon University
Acks: David Brumley, Adrian Perrig, Nicolas Christin, Srini Seshan
Recap so far
• We looked at firewalls and intrusion detection
• Offer “edge” security against Internet attacks
– E.g., defense against infect/exfiltrate attacks
• But, network is not just about the “Edge”
2
What is Network Security?
Public Channel
Alice
Bob
The Network,
typically runs IP “protocol”
1. Providing a “reliable” channel
 If the network protocols have flaws, crypto may not save you
3
http://www.computerworld.com/article/2516953/enterprise-applications/a-chinese-isp-momentarily-hijacksthe-internet--again-.html
4
5
What is Network Security?
Public Channel
Alice
Bob
The Network,
typically runs IP “protocol”
2. Providing an “available” channel
 Can Alice talk to Bob? Can Eve deny service to Alice/Bob?
6
7
8
Goals of this lecture
• Understand routing attacks and defenses
• Understand denial of service and defenses
9
Routing Overview
Internet organization
• The Internet comprises of Autonomous Routing
Domains (ARDs)
• An ARD is a collection of resources under the
administrative control of a single entity
–
–
–
–
–
CMU network is an ARD
Routers, links, networks, etc
Policies, interconnections with other ARDs
Big or small: Campus, corporate, ISP networks
Allocated numbers, names and addresses
11
Autonomous Systems
• An Autonomous System (AS) is an ARD with
an AS number assigned by IANA
– 16-bit, 1 to 64511 are public, 64512 to 65535 are
private
– CMU has ASN 9, UUNet has ASN 701, 702, 703,
704, 705
– Last count, there are more than 46,000 ASs
(CIDR report, mar 2014)
• Not every ARD has a public AS number
– Only if talks to more than one ASs
– Nowadays, must justify to IANA why you need
one
12
Internet routing
• Internet relies on hierarchical routing
– An Interior Gateway Protocol (IGP) is used to route
packets within an AS: Intra-domain routing
– An Exterior Gateway Protocol (EGP) to maintain
Internet connectivity among ASs: Inter-domain routing
AS400
AS100
BGP
BGP
BGP
BGP
AS300
IGP
AS200
13
How does BGP work?
Internet routers communicate using the Border
Gateway Protocol (BGP):
• Destinations are prefixes (CIDR blocks)
– Example: 128.2.0.0/16 (CMU)
• Routes through Autonomous Systems (ISPs)
• Each ISP is uniquely identified by a number
– Example: 25 (UC Berkeley)
• Each route includes a list of traversed ISPs:
– Example: 9 ← 5050 ← 11537 ← 2153
14
Principles of operation
• Exchange routes
– AS100 announces 128.1.1.0/24 prefix to
AS200 and AS300, etc
• Incremental updates
192.208.10.2
AS200
AS400
192.208.10.1
AS100
128.1.1.0/24
129.213.1.2
129.213.1.1
AS300
15
BGP UPDATE message
• Announced prefixes (aka NLRI)
• Path attributes associated with annoucement
• Withdrawn prefixes
192.208.10.2
AS200
AS400
192.208.10.1
AS100
128.1.1.0/24
129.213.1.2
129.213.1.1
AS300
16
UPDATE message example
NLRI: 128.1.1.0/24
Nexthop: 192.208.10.1
ASPath: 100
192.208.10.2
AS200
AS400
192.208.10.1
AS100
128.1.1.0/24
129.213.1.2
129.213.1.1
AS300
NRLI:128.1.1.0/24
Nexthop: 129.213.1.2
ASPath: 100
17
Route propagation
NLRI: 128.1.1.0/24
Nexthop: 192.208.10.1
ASPath: 100
192.208.10.2
NLRI: 128.1.1.0/24
Nexthop: 190.225.11.1
ASPath: 200 100
AS200
190.225.11.1
AS400
192.208.10.1
AS100
128.1.1.0/24
150.211.1.1
129.213.1.2
129.213.1.1
NRLI:128.1.1.0/24
Nexthop: 129.213.1.2
ASPath: 100
AS300
NLRI: 128.1.1.0/24
Nexthop: 150.212.1.1
ASPath: 300 100
18
BGP route selection algorithm
•
•
•
•
•
Drop routes with inaccessible Nexthops
Prefer route with largest LocalPref
Prefer route with shortest ASPath
Prefer lowest origin type IGP<EGP<Incomplete
Prefer route with smallest MED Compare MEDs
from same AS only
• Prefer path with lowest IGP metric
• Prefer path by lowest BGP IDs
• (vendor-specific hacks …)
19
BGP Attacks
All you need is one
compromised BGP speaker
Routers run an
operating system,
which hackers now
target
21
Potential attack objectives
• Blackholing – make something unreachable
• Redirection – e.g., congestion,
eavesdropping
• Instability
22
Unauthorized origin ISP (prefix theft)
G
Destination
Route
Destination
Route
Google
G←B
Google
M
B
C
M
M’s route to G is
better than B’s
23
AS-path truncation
Destination
Route
Destination
Route
Google
G←B←C
Google
G←B←M
G
B
C
Destination
Route
Google
G←B←D
M
D
E
M’s route to G is
better than D’s
24
AS path alteration
G
Destination
Route
Destination
Route
Google
G←B←C
Google
G←B←X←M
B
C
M
E
M’s route avoids C
25
Securing BGP
Authentication at BGP layer
• MD5 checksum option protects TCP layer
connection in BGP, provides authentication
between BGP speakers
• How much security does MD5 checksum option
provide?
– Prevents external attacker from injecting bogus
information into TCP connection, e.g., TCP poisoning
– Does not provide authenticity for routing information,
all 3 attacks are still possible!
28
Route filtering
• Use Internet routing registries
– Database of who owns what prefix
• Typically route filtering used for “business”
– E.g., don’t want to go through this AS
– E.g., don’t want to reveal route to this AS
• Can be used for security
• Ingress filters
– Does AS own the prefix? If no, don’t accept
• Problem?
29
BGP Security Requirements
• Verification of address space “ownership”
• Authentication of Autonomous Systems (AS)
• Router authentication and authorization
(relative to an AS)
• Route and address advertisement authorization
• Route withdrawal authorization
• Integrity and authenticity of all BGP traffic on
the wire
• Timeliness of BGP traffic
S-BGP design overview
• IPsec: authenticity and integrity of peer-to-peer communication,
automated key management
• Public Key Infrastructures (PKIs): secure identification of BGP
speakers and of owners of AS’s and of address blocks
• Attestations  authorization of the subject (by the issuer) to
advertise specified address blocks
• Validation of UPDATEs based on a new path attribute, using
certificates and attestations
• Distribution of countermeasure data: certificates, CRLs, attestations
31
Certificates and route attestations
• ICANN issues certificates for AS ownership to ISPs and
organizations that run BGP
• AS operators issue certificates to routers, as AS
representatives
• Holders of AS (or router) certificates generate route
attestations, authorizing advertisement of a route by a
specified next hop AS
• Route attestations are used to express a secure route as
a sequence of AS hops
32
Sample BGP Update Messages
R16
R1
R11
R6
R12
R2
R3
R7
R13
R9
R8
R4
R5
C1
R10
C2
R15
R14
C3
33
Secure BGP Update Message
R1
R11
R6
R12
R2
R3
R7
R13
R9
R8
R4
R5
C1
R10
C2
R15
R14
C3
34
Has this been adopted?
• Sadly, no
• Needs all AS-es to adopt
• Crypto still expensive at line rate
• Other options are still being explored
– SO-BGP, RPKI
35
Take away slide
• BGP was built on the assumption of cooperation
– Assumption does not apply anymore
• Many routing misconfigurations, bugs, and even attacks (several per
day)
• Proposed fixes are many, but all have some limitations
– TTL hacks, MD5 signatures
– S-BGP
• Relies on a PKI
• Potentially significant overhead
• Very hard to retrofit security in an existing model!
36
Denial of Service
DoS: General definition
• DoS is not access or theft of information or
services
• Instead, goal is to stop the service from
operating
• Deny service to legitimate users
• Why?
– Economic, political, personal etc ..
38
DDoS Attacks
• Distributed Denial of Service (DDoS) attack
is a coordinated DoS with many attackers
• Homogeneity of computing systems enables
an attacker to compromise tens of
thousands of hosts
39
Why is DDoS a hard problem
• Simple form of attack
– No complex technique, just send a lot of traffic
– Toolkits readily available
• Prey on the Internet’s strengths
– Simplicity of processing in routers
– Total reachability
• Attack machines readily available
– Easy to find 10,000’s vulnerable machines of the Internet
• Attack can look like normal traffic
– E.g., HTTP requests
• Lack of Internet enforcement tools
– No traceability
• Lack of cooperation between targets
– ISPs are competitive, and cooperation only at human timescales
• Effective solutions hard to deploy
– We can’t change the core of the Internet easily
40
DoS Attacks Characteristics
• Link flooding causes high loss rates for
incoming traffic
• TCPthroughput
MSS  C
BW 
RTT  q
• During DoS few
legitimate clients
served
41
DDoS Attack Taxonomy
• Exploited weakness
– Semantic vs Brute Force
• Victim resource type
– E.g., application vs host vs access link vs
infrastructure
• Detectability/Filterability
42
DoS can happen at any layer
• Sample DoS at different layers (by order):
•
•
•
•
Link
TCP/UDP
Application
Payment
43
Warm up: 802.11b DoS bugs
• Radio jamming attacks: trivial, not our
focus.
• Protocol DoS bugs:
[Bellardo, Savage, ’03]
– NAV (Network Allocation Vector):
•
•
•
•
15-bit field. Max value: 32767
Any node can reserve channel for NAV seconds
No one else should transmit during NAV period
… but not followed by most 802.11b cards
– De-authentication bug:
• Any node can send deauth packet to AP
• Deauth packet unauthenticated
• … attacker can repeatedly deauth anyone
44
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:
– Every host on target network generates a ping
reply (ICMP Echo Reply) to victim
Prevention: reject external packets to broadcast address
45
Modern day example
DNS Amplification attack:
DNS Query
SrcIP: Dos Target
(60 bytes)
DoS
Source
(May ’06)
( 50 amplification )
EDNS Response
(3000 bytes)
DNS
Server
DoS
Target
580,000 open resolvers on Internet (Kaminsky-Shiffman’06)
46
Survey of amplificators
(Rossow NDSS’14)
47
TCP SYN Flood I: low rate
C
S
(DoS bug)
Single machine:
SYNC2
• SYN Packets with
random source IP
addresses
SYNC3
• Fills up backlog queue
on server
SYNC1
SYNC4
SYNC5
• No further connections
possible
48
SYN Floods
(phrack 48, no 13, 1996)
OS
Linux 1.2.x
FreeBSD 2.1.5
WinNT 4.0
Backlog timeout:
Backlog
queue size
10
128
6
3 minutes
 Attacker need only send 128 SYN
packets every 3 minutes.
 Low rate SYN flood
49
Low rate SYN flood defenses
• Non-solution:
– Increase backlog queue size or decrease timeout
• Correct solution
(when under attack) :
– Syncookies: remove state from server
– Small performance overhead
50
Backscatter analysis
• Internet telescope/backscatter measurement
(example: SYN flood)
Attacker
Network “telescope”, e.g.,
empty /8 network
SYN, from IP = A
SYN-ACK, to IP = A
• By monitoring unused portion of address space, possibility to see
evidence of backscatter and infer type/number of DDoS attacks
• Does this work with botnet-based attacks?
51
Calculating attack
rate from backscatter
Attack of m packets
n monitored addresses
2^32 = total IPv4
52
DNS DoS Attacks
(e.g. bluesecurity ’06)
• DNS runs on UDP port 53
– DNS entry for victim.com hosted at victim_isp.com
• DDoS attack:
– flood victim_isp.com with requests for victim.com
– Random source IP address in UDP packets
• Takes out entire DNS server:
damage)
(collateral
– bluesecurity DNS hosted at Tucows DNS server
– DNS DDoS took out Tucows hosting many many sites
53
Root level DNS attacks
• Feb. 6, 2007:
– Botnet attack on the 13 Internet DNS root servers
– Lasted 2.5 hours
– None crashed, but two performed badly:
• g-root (DoD), l-root (ICANN)
• Most other root servers use anycast
Attack in Oct. 2002 took out 9 of the 13 TLD
servers
54
DoS at higher layers
• SSL/TLS handshake
[SD’03]
Client Hello
Server Hello (pub-key)
RSA
Encrypt
Web
Server
Client key exchange
RSA
Decrypt
– RSA-encrypt speed  10 RSA-decrypt speed
 Single machine can bring down ten web servers
• Similar problem with application DoS:
– Send HTTP request for some large PDF file
 Easy work for client, hard work for server.
55
Evolution of (D)DoS in history
Time
– Point-to-point DoS attacks
• TCP SYN floods, Ping of death, etc..
–
–
–
–
–
Smurf (reflection) attacks
Coordinated DoS
Multi-stage DDoS
P2P botnets
Novel amplification attacks
(Return of the smurf)
56
Smurf attacks
1.
2.
3.
4.
Attacker spoofs
victim’s IP address
Attacker sends
error-generating
packets to reflectors
Reflectors all report
errors to victim
Victim is killed by
error messages
Attacker’s machine
Reflectors
(Amplifiers)
(more on this in the next
lecture – special case of
“reflection attacks”)
Victim
57
Coordinated DoS
• Simple extension of
DoS
Attackers’
machines
• Coordination
between multiple
parties
– Can be done off-band
– IRC channels,
email…
Victims
58
Typical DDoS setup circa 2005
Attacker’s machine
Masters
(Handlers)
Slaves
(Agents)
Victim
59
Typical DDoS setup circa 2005
Attacker’s machine
Masters
(Handlers)
Slaves
(Agents)
Infection/recruitment
Command & control
Assault
Victim
60
Modern Botnet setup
Zombies
(P2P)
Attackers
Attackers
Attackers
Peer-to-peer communication
Command & control
Assault
Victim
61
DDoS Defense Taxonomy
• Location
– Host vs network vs protocol
• Response timescale
– Preventive vs Reactive
• Response action
– E.g., filter, rate limit, multiply, bug fix/patch
62
Syncookies
[Bernstein, Schenk]
• Idea: use secret key and data in packet to gen.
server SN
• Server responds to Client with SYN-ACK cookie:
– T = 5-bit counter incremented every 64 secs.
– L = MACkey (SAddr,
SPort, DAddr, DPort, SNC, T)
[24 bits]
• key: picked at random during boot
– SNS = (T . mss . L)
( |L| = 24 bits )
– Server does not save state (other TCP options are lost)
• Honest client responds with ACK ( AN=SNS , SN=SNC+1 )
– Server allocates space for socket only if valid SNS.
63
DNS DoS solutions
• Generic DDoS solutions:
– Later on. Require major changes to DNS.
• DoS resistant DNS design:
– CoDoNS: [Sirer’04]
• Cooperative Domain Name System
– P2P design for DNS system:
• DNS nodes share the load
• Simple update of DNS entries
• Backwards compatible with existing DNS
64
Client puzzles
• Idea: slow down attacker
• Moderately hard problem:
– Given challenge C find X such that
n
LSBn ( SHA-1( C || X ) ) = 0
– 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:
– Everyone must submit puzzle solution with
requests
– When no attack: do not require puzzle solution
65
Examples
• TCP connection floods (RSA ‘99)
– Example challenge: C = TCP server-seq-num
– First data packet must contain puzzle solution
• Otherwise TCP connection is closed
• SSL handshake DoS: (SD’03)
– Challenge C based on TLS session ID
– Server: check puzzle solution before RSA decrypt.
• Same for application layer DoS and payment
DoS.
66
CAPTCHAs
• Idea: verify that connection is from a human
• Applies to application layer DDoS [Killbots ’05]
– During attack: generate CAPTCHAs and process request only
if valid solution
– Present one CAPTCHA per source IP address.
67
Content Distribution Networks (CDNs)
• CDN company installs hundreds of CDN servers throughout Internet
• Replicated customers’ content
origin server
in North America
CDN distribution node
• How can this help DDoS?
• Legitimate requests can still go through
• Attack scale must be higher
CDN server
in S. America
CDN server
in Europe
CDN server
in Asia
What do net operators do?
• Best common operational practices:
• http://nabcop.org/index.php/DDoS-DoSattack-BCOP
• Often, blackholing malicious looking IPs and
rerouting to custom “Scrubbers”
69
Take home message:
• Denial of Service attacks are real.
Must be considered at design time.
• Sad truth:
– Current Internet is ill-equipped to handle DDoS
attacks
• Many good proposals for redesign
– But threat still remains
70
Questions?
71
END
Thought
73