Denial of Service

CS 161 Fall 2021 - Lecture 34

Computer Science 161

Popa and Weaver

Announcements

• Project 2 has been extended and is now due Friday, November 19th at 11:59 PM.
• Homework 6 has been released and is due Friday, November 19th at 11:59 PM.

2

Computer Science 161

Popa and Weaver

Last Time: DNSSEC

• DNSSEC: An extension of the DNS protocol that ensures integrity on the results
• Provides object security (unlike DNS over TLS, which would provide channel security)
• Uses signatures to cryptographically verify records
• Uses a hierarchical public key infrastructure to delegate trust from the trust anchor (root)
• DNSSEC Implementation
• Each name server replies with its public key (DNSKEY type)
• When delegating trust, each name server signs the public key of the next name server�(DS and RRSIG types)
• When providing a final answer, the name server signs the final answer (RRSIG type)
• Zones are split into key-signing keys and zone-signing keys
• NSEC signs a message saying no domains exist alphabetically between two records

3

Computer Science 161

Popa and Weaver

Today: Denial of Service and Firewalls

• Denial of service
• Availability
• Application-level DoS
• Algorithmic complexity attacks
• Network-level DoS
• Distributed DoS (DDoS)
• Amplified DoS
• SYN flooding
• SYN cookies
• Defenses
• Firewalls
• Packet filters
• Stateless/stateful packet filters
• Proxy firewalls

4

Computer Science 161

Popa and Weaver

Denial of Service (DoS)

5

Computer Science 161

Popa and Weaver

Availability and Denial of Service (DoS)

• Availability: Making a service on the network available for legitimate users
• Denial of service (DoS): An attack that disrupts availability of a service, making it unavailable for legitimate users
• Reasons for a DoS attack
• Competitors might DoS each other to benefit their own services
• Criminals might DoS services unless the services pay a ransom
• People might DoS services to make a political statement
• Entities might DoS each other as part of warfare tactics
• Some people might DoS for fun or revenge (e.g. online games)
• Some people might offer this as a service for others

6

Computer Science 161

Popa and Weaver

DoS in the News

7

Computer Science 161

Popa and Weaver

DoS in the News

8

Computer Science 161

Popa and Weaver

DoS in the News

9

Computer Science 161

Popa and Weaver

DoS Attacks: Strategies

• Exploiting program flaws
• Software vulnerabilities can cause a service to go offline
• Example: Exploit a buffer overflow to execute a shutdown command to the system
• Example: Exploit a SQL injection vulnerability to delete the database
• Resource exhaustion
• Everything on the network has limited resources
• The attacker consumes all the limited resources so legitimate users can’t use them
• Mitigations for exploitation may still result in a DOS
• C memory mitigations: ASLR, stack canaries, Pointer Authentication codes…
• Enabling them doesn’t stop a memory error from crashing the program, it only prevents remote code execution

10

Computer Science 161

Popa and Weaver

DoS Attacks: Strategies

• Bottlenecks
• Different parts of the system might have different resource limits
• The attacker only needs to exhaust the bottleneck: the part of the system with the least resources

11

Bottleneck

Computer Science 161

Popa and Weaver

DoS Targets

• Application-level DoS: Target the high-level application running on the host
• Network-level DoS: Target network protocols to affect the host’s Internet

12

Computer Science 161

Popa and Weaver

Application-Level DoS

13

Computer Science 161

Popa and Weaver

Application-Level DoS

• Target the resources that the application uses
• Exploit features of the application itself
• Some attacks rely on asymmetry: A small amount of input from the attack results in a large amount of consumed resources!
• Others rely just on volume: An attacker can compromise a gazillion devices to use in an attack

14

Computer Science 161

Popa and Weaver

Resource Consumption

• Idea: Force the server to consume all its resources

15

int fd = open('/tmp/junk');

char buf[4096];

while (1) { write(fd, buf, 4096); };

while (1) { malloc(1000000000); }

while (1) { fork(); }

Exhausts filesystem space

Exhausts RAM

Exhausts processing threads

while (1) {

int fd = open(random_file());

write(fd, "abcde", 5);

close(fd);�}

Exhausts disk I/O operations

Computer Science 161

Popa and Weaver

Algorithmic Complexity Attacks

• Consider an application that runs a sort on user-chosen data
• What if the attacker intentionally chooses inputs that cause the worst-time runtime to occur?
• Algorithmic complexity attack: Supplying inputs that trigger worst-case complexity of algorithms and data structures
• Requires the attacker understand the algorithm
• Requires the attacker to be able to trigger the worst case behavior

16

Computer Science 161

Popa and Weaver

Example Algorithmic Complexity Attacks

• A hashtable
• Expected lookup time: O(1)
• Worst case lookup time: O(n)
• Occurs when all entries hash to the same bucket, so if the attacker knows the hash...
• Quicksort
• Take first element as the pivot
• Expected execution time: O(n lg n)
• Worst case execution time: O(n2)
• Occurs when you try to resort an already sorted array
• For both, the solution is make sure the attacker can’t control the worst-case!
• Use a good hash (SHA1, GHASH) + salt
• Select a random pivot rather than the first element
• Takeaway: Consider the control the attacker has over the input and make sure the worst case is random, not a function of the input

17

Computer Science 161

Popa and Weaver

Application-Level DoS: Defenses

• Identification: Step 0 of any defense
• You must be able to distinguish requests from different users before you can do anything else!
• Requires some method to identify/authenticate users
• Authenticating users might be expensive and itself vulnerable to DoS
• Isolation: Ensure that one user’s actions do not affect another user’s experience
• Quotas: Ensure that users can only access a certain proportion resources
• Example: Only trusted users can execute expensive requests
• Example: Limit each user to 4 GB of RAM and 2 CPU cores

18

Computer Science 161

Popa and Weaver

Application-Level DoS: Defenses

• Proof-of-work: Force users to spend some resources to issue a request
• Idea: Make a DoS attack more expensive for the attacker, who now needs to spend resources
• Example: Add a CAPTCHA, which the attacker will now have to solve (or pay for solving services)
• Overprovisioning: Allocate a huge amount of resources
• Can cost the server a lot of money!
• Depends on your threat model
• Often the most effective defense (“security is economics”)
• Content delivery network (CDN): A service that allocates a huge amount of resources for you
• Example of a CDN: Cloudflare
• Cloudflare runs your front-end (or entire) service for you with a huge amount of resources
• Takes advantage of economies of scale: Only some people are attacked at a given time

19

Computer Science 161

Popa and Weaver

Network-Level DoS

20

Computer Science 161

Popa and Weaver

Network-Level DoS

• Approaches target network protocols to affect the victim’s Internet access
• Example: Send a huge amount of packets to the victim
• Overwhelm the victim’s bandwidth (amount of data it can upload/download in a given time)
• Example: The server can only upload/download 10 MB/s. The attacker sends the server 20 MB/s.
• Lots of maximum-sized packets
• Overwhelm the victim’s packet processing capacity
• Example: The server can process 10 packets/second. The attacker sends the server 20 packets/second.
• Lots of minimum-sized packets

21

Computer Science 161

Popa and Weaver

Distributed Denial-of-Service (DDoS)

• Distributed denial-of-service (DDoS): Use multiple systems to overwhelm the target system
• Controlling many systems gives the attacker a huge amount of bandwidth
• Sending packets from many sources makes it hard for packet filters to distinguish DDoS traffic from normal traffic
• Botnet: A collection of compromised computers controlled by one attacker
• The attacker can tell all the computers on the botnet to flood a given target

22

Victim

Attacker

Attacker

Attacker

Attacker

Attacker

Attacker

Computer Science 161

Popa and Weaver

Amplified Denial-of-Service

• Amplified denial-of-service: Use an amplifier to overwhelm the target more effectively
• Idea: Some services send a large response when sent a small request
• Spoofing a small request that appears to come from the victim results in a large amount of data sent to the victim
• Example: DNS amplification
• Requests contain only the question
• Responses contain answer records, authority records, and additional records

23

Attacker

DNS Name Server

Victim

From: Victim, To: Server

request

From: Server, To: Victim

RESPONSE

Computer Science 161

Popa and Weaver

Amplified Denial-of-Service

• Benefits:
• The attacker’s identity is concealed because the packets come from the amplification server
• The attacker is able to overwhelm more bandwidth with relatively little bandwidth
• Amplification servers often have massive bandwidths to support large numbers of users
• Drawbacks:
• Requires blind spoofing capability
• Cannot work over TCP, since TCP spoofing is assumed to be hard, only UDP protocols
• 3/4s of ISPs limit the ability to spoof packets through egress filtering:�Stopping outbound packets who’s source IP is not from the ISP itself

24

Computer Science 161

Popa and Weaver

Network-Level DoS: Defenses

• Packet filter: Discard any packets that are part of the DoS attack
• Discard packets where the source IP is the attacker’s IP address
• Find some pattern in the content of the DoS packets to distinguish DoS packets from legitimate packets
• The packet filter must be before the bottleneck
• Subverting packet filters
• Spoof DoS packets so that packets look like they’re coming from many IP addresses
• Packet filters can’t use IP addresses to filter packets anymore!
• Hard to defend against
• Rely on anti-spoofing mechanisms on the network
• Distributed DoS actually send packets from many IP addresses
• Packet filters need to be much more sophisticated to defend against DDoS attacks
• Packet filter needs to be before the bottleneck

25

Computer Science 161

Popa and Weaver

Network-Level DoS: Defenses

• Overprovisioning: Purchase enough networking bandwidth and equipment to make it harder for attackers to overwhelm the network
• Again, depends on your threat model
• Overprovisioning is aided by services which do this for you…
• 10,000 customers. But only one or two is ever “attacked” at one time
• Being a piece of popular content (Flash Crowd) is often indistinguishable from an attack!
• Content Delivery Networks provide this:
• Use DNS to redirect requests to “closest” CDN server
• CDN’s authority name-servers decide based on the IP doing the query…�Which usually identifies the ISP if not finer geography
• CDN server caches all content possible
• Only if not in the cache or uncacheable does it forward to the real (hidden) webserver
• CDN can also implement filtering

26

Computer Science 161

Popa and Weaver