Summary
An Algorithmic Complexity (AC) attack is a resource exhaustion attack that takes advantage of worst-case performance in server-side algorithms. This post introduces the concept of algorithmic complexity vulnerabilities. We will define and characterize what makes a vulnerability an algorithmic complexity vulnerability, discuss some of the potential risks and mitigations, and provide some historical examples of serious algorithmic complexity vulnerabilities.
At Black Hat USA 2019, researchers from Two Six will be giving two presentations that detail the past and present threats of AC vulnerabilities.
- Nathan Hauke and David Renardy will give a 50 minute briefing on Thurs. at 9:30 AM titled Denial of Service with a Fistful of Packets: Exploiting Algorithmic Complexity Vulnerabilities. In this talk, they will unveil three new algorithmic complexity vulnerabilities in the PDF specification, Linux-based VNC servers, and in Dropbox’s zxcvbn password strength estimation algorithm. Their abstract can be found here.
- Adam Jacobson and Will Vega will present updates to the ACsploit open source tool on Thurs. at 11:30 AM. This presentation will include PoCs of exploits unveiled at the Fistful of Packets briefing, as well as a new module for finding worst-case inputs for vulnerable regular expressions (REDoS). Details can be found here.
What is an Algorithmic Complexity Vulnerability?
Developers select algorithms for performance, for ease of implementation, or because they’re the top answer on StackOverflow. Most developers test their algorithms for average-case performance, checking against the kinds of inputs a typical user would provide. Algorithmic complexity vulnerabilities arise when the worst-case performance for a back-end algorithm results in resource exhaustion of the server.
AC vulnerabilities come in a few flavors. An AC Time vulnerability causes denial of service by exhausting CPU. AC Space vulnerabilities exhaust RAM or disk space.
How do AC Vulnerabilities Differ from Other DoS Attacks?
In a typical distributed denial-of-service (DDOS) attack, the attacker must dedicate significant resources to the attack. Attackers will most commonly use a botnet of thousands or millions of nodes, each of which initiates a conversation with the target server. In this case, there is a symmetric effort on part of the attacker vs. the effect on the target. In contrast, AC attacks can typically be conducted by a single user, with a relatively small payload, to cause a disproportionately powerful effect. AC vulnerabilities are much cheaper than a traditional DDOS attack.
Additionally, unlike most DDOS attacks, AC vulnerabilities can be “quieter” than traditional denial of service attacks. Because AC vulnerabilities arise from intended functionality, normal indicators of compromise, such as thrown exceptions, unusually high traffic, and excessive logging, may not be present. Many AC Time attacks cause temporary denial of service, with normal functionality resuming afterwards. This allows AC attacks to escape notice, flying under the standard cyber security radar.
Throughout our research, we observed even security researchers would ignore algorithmic complexity vulnerabilities as irrelevant anomalies. Because the symptoms of these attacks are typically resolved by restarting the target server, system administrators and security experts may easily overlook an AC attack.
Some Historical Examples
This short historical list AC vulnerabilities gives a sketch of the AC vulnerability landscape. For each of these vulnerability classes, ACsploit can generate test cases for researchers, developers, and penetration testers.
Hashtable DoS Attacks
In 2011, researchers Alexander ‘alech’ Klink and Julian ‘zeri’ Wälde found vulnerabilities in several hash table implementations, including the built-in hash tables in Java, PHP, and Python. These hash tables utilized a linked list for storing hash collisions. By creating inputs that collide under the hash functions, an attacker can insert arbitrarily many hash table keys into the same linked list. Klink and Wälde additionally identified several web-servers using these hash tables to store user-supplied request data. In response to this, the developers of the affected languages made fundamental changes to their hash table implementations. Java, for instance, switched from linked lists to balanced red-black trees. Check out their presentation at 28c3 below.
Decompression Bombs
Decompression bombs exploit the ability of efficient compression algorithms to compress a large amount of (typically low entropy) data into a small package. Decompression bombs exist in almost any format that allows compression, from images (png, jpeg) to archives (gz, zip) and other documents (pdf, xml). A decompression bomb typically causes an AC Space effect on the memory use of the file parser: as the bomb is decompressed, it expands to consume all of the system’s memory. Modern parsers offer some protections against decompression bombs, e.g. (optional) safeguards and sandboxes to limit resource consumption during parsing.
One great resource for learning about decompression bombs is the website https://bomb.codes/. You can also generate decompression bombs using ACsploit.
Cara Marie gave a briefing at Black Hat USA 2016 exploring many different decompression bombs. Check out her presentation below.
REDoS
REDoS, or Regular Expression Denial of Service, refers to a class of vulnerabilities in regular expression parsing engines. If a regular expression allows for “catastrophic backtracking”, then the parser will require processing time that grows exponentially with the candidate string’s length. Interestingly, most regular expression parsing engines accept REDoS as a cost of doing business and warn their users against using “bad” (i.e. DoS-able) regular expressions.
You can find a written introduction to REDoS here. For a relatively recent presentation on the topic, check out Eric “XlogicX” Davisson’s presentation at DefCon23: REvisiting RE DoS.
Maybe Not So Historical Examples
REDoS has been a well-known issue for many years at this point, so it may surprise you to hear that some high profile applications still fall victim to this class of vulnerability.
- In 2016, StackExchange experienced a half hour outage due to a bad regex. Remarkably, the StackExchange team was able to resolve the issue without consulting StackOverflow. You can read their post-mortem here.
- More recently, on July 2 2019, Cloudflare experienced a blackout due to a poorly implemented regex. You can read their post-mortem here.
What Can Be Done About AC Vulnerabilities?
AC vulnerabilities arise because of design decisions, so solutions have to address these issues in design. Solutions include:
- Select a new algorithm. As a result of the hash table collision attacks in 2011, most programming languages changed the data structure, used as bins, for their hash table implementation.
- Use input sanitization. Sometimes the AC vulnerability present in a given algorithm only happens for a specific class of inputs. You can restrict the input space a user can submit by placing explicit limits in your application (e.g. limit the length of input, the use of certain options or characters, etc.).
- Implement hard resource limits. Occasionally, you need the strength and flexibility of an algorithm that is vulnerable to attack, and the input space is too difficult to restrict with input sanitization. In this case, you can implement hard resource limitations for your application. Many applications will abort decompression when they encounter a decompression bomb by refusing to extract data beyond a certain size.
But you can’t know what safeguards to put in place if you don’t know how you’re vulnerable. Come check out our Black Hat briefing and Arsenal presentation to stay up-to-date on AC security for designing, developing, and pen-testing your applications.
Bridging the gap between the impossible and the practical with innovative technology solutions in cyber, data science, mobile, microelectronics and information operations and a full spectrum of products and capabilities to advance national security missions.