Regular Expression

Regular Expression Denial of Service (ReDoS) is a type of attack that exploits the fact that certain regular expressions can take an extremely long time to process, causing applications or services to become unresponsive or crash.

Summary

Tools
Methodology
- Evil Regex
- Backtrack Limit
References

Tools

tjenkinson/redos-detector - A CLI and library which tests with certainty if a regex pattern is safe from ReDoS attacks. Supported in the browser, Node and Deno.
doyensec/regexploit - Find regular expressions which are vulnerable to ReDoS (Regular Expression Denial of Service)
devina.io/redos-checker - Examine regular expressions for potential Denial of Service vulnerabilities

Methodology

Evil Regex

Evil Regex contains:

Grouping with repetition
Inside the repeated group:
- Repetition
- Alternation with overlapping

Examples:

(a+)+
([a-zA-Z]+)*
(a|aa)+
(a|a?)+
(.*a){x} for x > 10

These regular expressions can be exploited with aaaaaaaaaaaaaaaaaaaaaaaa! (20 'a's followed by a '!').

aaaaaaaaaaaaaaaaaaaa!

For this input, the regex engine will try all possible ways to group the a characters before realizing that the match ultimately fails because of the !. This results in an explosion of backtracking attempts.

Backtrack Limit

Backtracking in regular expressions occurs when the regex engine tries to match a pattern and encounters a mismatch. The engine then backtracks to the previous matching position and tries an alternative path to find a match. This process can be repeated many times, especially with complex patterns and large input strings.

PHP PCRE configuration options:

Name	Default	Note
pcre.backtrack_limit	1000000	100000 for `PHP < 5.3.7`
pcre.recursion_limit	100000	/
pcre.jit	1	/

Sometimes it is possible to force the regex to exceed more than 100 000 recursions which will cause a ReDOS and make preg_match returning false:

$pattern = '/(a+)+$/';
$subject = str_repeat('a', 1000) . 'b';

if (preg_match($pattern, $subject)) {
    echo "Match found";
} else {
    echo "No match";
}

References

Uh oh!