Comprender el ataque ReDoS

ReDoS significa Denegación de servicio de expresiones regulares. El ReDoS es un ataque de complejidad algorítmica que produce una denegación de servicio al proporcionar una expresión regular que lleva mucho tiempo evaluar. El ataque explota el hecho de que la mayoría de las implementaciones de expresiones regulares tienen una complejidad de tiempo exponencial en el peor de los casos, por lo que para strings de entrada más grandes (la ‘regex malvada’), el tiempo que tarda un motor de expresiones regulares en encontrar una coincidencia aumenta exponencialmente. 

El objetivo del atacante es proporcionar tales expresiones regulares para que tome una cantidad indefinida de tiempo de cálculo, lo que a su vez ralentizará la aplicación o la detendrá por completo. 
Entonces, este ataque básicamente aprovecha el hecho de que el motor de expresiones regulares probará todas las permutaciones y combinaciones posibles de caracteres para encontrar una coincidencia. 

Las expresiones regulares se pueden encontrar en toda la web y se puede usar un ataque ReDoS para apuntar a varios componentes de la web. 

Ejemplo de expresión de ataques ReDOS

Regex: ^((ab)*)+$(esta expresión regular busca ab y su repetición) 
Entrada: ababab 
En este caso, el motor de expresiones regulares encontrará una coincidencia en el primer intento, ya que ababab coincide con el patrón de expresiones regulares. Ahora podemos complicar las cosas muy fácilmente agregando abababa como entrada. Esta a adicional al final causará todo tipo de problemas ya que no coincide con el patrón y hará que el motor de expresiones regulares ejecute todo tipo de permutaciones en busca de una posible coincidencia. 
 

(ababab) - NOT A MATCH
(abab)(ab) - NOT A MATCH
(ab)(abab) - NOT A MATCH
(ab)(ab)(ab) - NOT A MATCH
()(ababab) - NOT A MATCH
()(abab)(ab) - NOT A MATCH
()(ab)(abab) - NOT A MATCH
()(ab)(ab)(ab) - NOT A MATCH

Puede probarlo usted mismo en este editor de expresiones regulares en línea . Ahora imagina si esa entrada fuera más larga, algo así como 
 

abababababababababababababababababababababababababab......

qué tipo de caos creará. 
 

expresión regular malvada

Son las expresiones regulares que hacen que una aplicación sea vulnerable a los ataques ReDoS, ocurren cada vez que ocurren estos factores: 
 

• la expresión regular aplica repetición (“+”, “*”) a una subexpresión compleja
• para la subexpresión repetida, existe una coincidencia que también es un sufijo de otra coincidencia válida.

Los ejemplos de expresiones regulares maliciosas incluyen los siguientes: 
 

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

Ataque de aplicación web a través de Evil Regex: 
 

• Abra un JavaScript y encuentre el Evil Regex
• Elabore una entrada maliciosa para el Regex encontrado y envíe un valor válido a través de un proxy interceptor
• Cambie la solicitud para que contenga una entrada maliciosa y estará listo para un ataque ReDos

ReDoS mediante inyección Regex

El siguiente ejemplo verifica si el nombre de usuario es parte de la contraseña ingresada por el usuario. 
 

String userName = textBox1.Text;
String password = textBox2.Text;
Regex testPassword = new Regex(userName);
Match match = testPassword.Match(password);
if (match.Success)
{
MessageBox.Show("Do not include name in password.");
}
else
{
MessageBox.Show("Good password.");
}

Si un atacante ingresa ^(([az])+.)+[AZ]([az])+$ como nombre de usuario y   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! como contraseña, el programa se colgará. 

Prevención: 
 

1. Use la agrupación atómica en su expresión regular. Un grupo atómico es un grupo que, cuando el motor de expresiones regulares sale de él, descarta automáticamente todas las posiciones de retroceso recordadas por cualquier token dentro del grupo.
2. Si una expresión regular tarda demasiado, elimínela de inmediato e informe al usuario que la expresión regular estaba tardando demasiado.
3. Preformatee/valide sus expresiones regulares o permita que las personas busquen texto directamente, en lugar de ingresar una expresión regular directamente.

Referencias: 
 

• https://www.linkedin.com/pulse/redos-attacks-python-application-architectures-akshat-mahajan
• http://stackoverflow.com/questions/12841970/how-can-i-recognize-an-evil-regex
• https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS
• Fuente de la imagen: https://www.owasp.org/index.php/Main_Page

Este artículo es una contribución de Palash Nigam . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.