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.