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.
Nathan Hauke is a Senior Research Engineer at Two Six Labs. He started working on algorithmic complexity challenges as a member of the control team for the DARPA STAC program and is a co-author of ACsploit, a tool for generating worst-case inputs to common algorithms. He has worked on projects involving symbolic execution and network reconnaissance. Nathan earned a B.S. in Computer Science and Mathematics from the University of Chicago and an M.S. in Computer Science from Georgetown University. He is an avid tennis and hockey player, and a broomball national champion.
Dr. David Renardy is a Senior Research Scientist and Mathematician at Two Six Labs. He became interested in algorithmic complexity vulnerabilities while working on the control team for the DARPA STAC program. His work focuses on vulnerability research, cryptography, and network reconnaissance. He received his PhD in Mathematics from the University of Michigan in 2016.