Last Friday, Cloudflare posted a detailed blog post that described about how a poorly implemented software deployment caused a massive CPU spike, rendering the Cloudflare service unavailable. Because Cloudflare servers couldn’t handle incoming HTTP requests, global customer websites were unavailable for approximately 30 minutes.[1]
The root cause of the issue was a regular expression (regex) that allows developers to create and search for a pattern. Regex patterns are heavily used in software development today to match emails, phone numbers, zip codes, etc. Additionally, regex patterns are used in Web Application Firewalls. Public clouds often have a WAF as a feature, and both AWS and Azure allow you to add regex rules for blocking specific traffic patterns. Regex patterns can be written in insecure ways, which often lead to security issues such as DoS attacks.[2] In the case of Cloudflare, the regex pattern was accidentally invoked by the software developers.
At Security Innovation, we have seen instances where an external user (attacker) could give a malicious input which would be compared against an insecure regex pattern leading to complete Denial of Service (DoS) on the service. This is why code-assisted penetrations tests are invaluable as it’s easier to test for regex related functions when you have direct access to the source code.
When I get access to a codebase, I start with searching for regex related strings such as ‘re’, ‘re.compile’, ‘re.search’ (these examples are Python specific). For Java we can search for ‘pattern.compile’, ‘pattern.matcher’ etc. Once we find a regex pattern in the client code, we can copy that snippet for further analysis.
My recommended tool is RegEx101. Because I don’t want to share any vulnerable patterns from client assessments, I am going to demonstrate the testing using a vulnerable pattern from the OWASP page.[3]
Consider that a developer is comparing an attacker provided input against the following regex pattern.
` ^(([a-z])+.)+[A-Z]([a-z])+$`
Enter this pattern into the regex101.com website for analysis. We will start our testing with a simple input string: aack. As we can see from the image, this operation required 42 steps to match the input string.
Next we will enter a complex string, and check if the number of steps needed to compare the string increases exponentially. For this input string, the number of steps required to determine a match is 156813. This number is significantly larger than the number of steps required for the first input. The number of steps required corresponds to the CPU usage on the server. Additionally, we can see how much time (in milliseconds) it takes for this input to process. With this input, an attacker can consume substantially more computing resources of the server using a fairly simple request.
Next, enter an input even longer than the last payload. As we can see here, the regex engine cannot match this input string and instead complains that the pattern introduces a catastrophic backtracking. If an attacker manages to cause a catastrophic backtracking, the server might crash and become completely unavailable.
On the regex101 website, we can choose any engine we want to test against. We can check for the behavior of simple pattern used by Cloudflare against two different engines as shown here:
As we can see, depending on the engine used for parsing the regex, you can check if you have a critical vulnerability. The GitHub page for this project differentiates between the regex engines used by Python and JavaScript.[4]
During the actual penetration test, we know the language and frameworks used by the service. With this internal knowledge of the service, we can identify the correct payload required to demonstrate this vulnerability. If a client wants to see the worst-case scenario, we can easily extend the payload so that it takes an enormous amount of computing resources.
Testing and exploiting these uncommon issues is what differentiates an in-depth, expert led penetration test from a standard one that relies more heavily on scanning. When we deliver findings like these to our customers, they are always appreciative of our persistence and ability to find these compound issues that often elude automation and other vendor assessments.
If you want to learn more about the exact issue, scroll down to the bottom of Cloudflare's post for technical details. Additionally, you can learn more about regex on Somdev Sangwan's Exploiting Regular Expressions post.
Resources:
- https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
- https://medium.com/@somdevsangwan/exploiting-regular-expressions-2192dbbd6936
- https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS
- https://github.com/firasdib/Regex101/wiki/FAQ#how-close-does-regex101-emulate-the-engines
