Denial of Service with a Fistful of Packets: Exploiting Algorithmic Complexity Vulnerabilities

The presentation discusses algorithmic complexity vulnerabilities and the need for awareness and mitigation techniques.

• Algorithmic complexity vulnerabilities result in denial of service due to unacceptable worst-case performance of a back-end algorithm processing user input.
• These vulnerabilities are often overlooked by application designers, developers, and pen testers.
• Vulnerability researchers often discover the same vulnerabilities repeatedly due to the lack of awareness and mitigation techniques.
• The DARPA stack research program was designed to hunt for algorithmic complexity vulnerabilities.
• Algorithmic complexity vulnerabilities are cheaper and quieter than DDoS attacks.
• Mitigation techniques include incorporating AC vulnerabilities into testing, developing with worst-case inputs in mind, and making AC security a habit for developers.
• The audience is encouraged to identify and report AC vulnerabilities to improve the community's security.

The presenters give an example of a server implementing insertion sort on user-submitted input, assuming that users usually submit sorted data. However, an attacker could submit a reverse-sorted list, causing quadratic time and denial of service. This illustrates the need to consider worst-case inputs when designing algorithms.

How many bytes do you need to take down a web server? The answer might be fewer than you think. Algorithmic complexity (AC) vulnerabilities allow an attacker to submit a small amount of input to an algorithm and cause the target to perform a large amount of work. By leveraging AC vulnerabilities, an attacker can create a denial of service effect without the large resource requirements of a traditional DDoS attack. AC vulnerabilities present attractive DoS opportunities for attackers because they aren't bugs, and are therefore difficult to fix. Exploits may be valid input and hence may not produce observables such as unusual log messages or errors.In this talk we will reveal three distinct zero-day AC vulnerabilities affecting PDF readers, common linux VNC servers, and a popular user authentication library. We'll show how to generate low-RAM, CPU DoS attacks against online OCR platforms, how to remotely exhaust the disk space on a VNC server without ever logging in, and how to launch a DoS attack against a web server from the user signup page. We will dive deep into the technical details of each exploit, examine the paths we followed that led to their discovery, and demonstrate each exploit against a range of vulnerable targets.Through these examples, we will show how AC vulnerabilities can be born out of intended functionality, and how existing security testing procedures fail to defend against AC attacks. In addition to providing specific mitigations against the attacks we discovered, we will introduce general strategies for improving your security posture against AC attacks. In coordination with our talk we will release PoC code for auditing your own applications as part of our ongoing contribution to the ACsploit project, an open-source platform introduced at Black Hat Asia 2019 for generating worst-case inputs to common algorithms.