ReDoS

Una denegación de servicio de expresión regular o regular expression denial of service (ReDoS), por sus siglas en inglés.^[1]​ Es un ataque de complejidad algorítmica que produce una denegación de servicio al proporcionar una expresión regular y/o una entrada que tarda mucho tiempo en evaluarse. El ataque aprovecha el hecho de que muchas^[2]​ implementaciones de expresiones regulares tienen una complejidad superlineal en el peor de los casos; en ciertos pares de entradas y expresiones regulares, el tiempo necesario puede crecer polinomial o exponencialmente en relación con el tamaño de la entrada. Por lo tanto, un atacante puede hacer que un programa dedique mucho tiempo proporcionando una expresión regular o una entrada especialmente diseñada. Entonces el programa se ralentizará o dejará de responder.^[3]​^[4]​

La coincidencia de expresiones regulares ("regex") se puede realizar construyendo un autómata de estados finitos. Las expresiones regulares se pueden convertir fácilmente en autómatas no deterministas (NFAs), en los que para cada estado y símbolo de entrada, puede haber varios estados siguientes posibles. Una vez construido el autómata existen varias posibilidades:

• El motor puede convertirlo en un autómata determinista de estado finito (DFA) y ejecutar la entrada a través del resultado.
• El motor puede probar una por una todas las rutas posibles hasta que se encuentre una coincidencia o se intenten todas las rutas y fallen ("backtracking o retroceso").^[5]​
• El motor puede considerar todos los caminos posibles a través del autómata no determinista en paralelo.
• El motor puede convertir el autómata no determinista en uno de estado finito (DFA) de forma perezosa (es decir, sobre la marcha, durante la coincidencia).

De los algoritmos anteriores, los dos primeros son problemáticos. La primera es problemática porque un autómata determinista podría tener hasta ${\displaystyle 2^{m}}$ estados posibles, donde ${\displaystyle m}$ es el número de estados en el autómata no determinista; por lo tanto, la conversión de NFA a DFA puede llevar un tiempo exponencial. El segundo es problemático porque un autómata no determinista podría tener un número exponencial de caminos de longitud ${\displaystyle n}$, de modo que caminar a través de una entrada de longitud ${\displaystyle n}$ también tomará un tiempo exponencial.^[6]​Los dos últimos algoritmos, sin embargo, no presentan un comportamiento patológico.

Hay que tener en cuenta que para las expresiones regulares no patológicas, los algoritmos problemáticos suelen ser rápidos y, en la práctica, se puede esperar que "compilen" una expresión regular en tiempo O(m) y la igualen en tiempo O(n); en cambio, la simulación de un NFA y el cálculo diferido del DFA tienen una complejidad de O (m²n) en el peor de los casos.^[7]​ La denegación de servicio de expresiones regulares ocurre cuando estas expectativas se aplican a una expresión regular proporcionada por el usuario, y este tipo de expresiones regulares maliciosas desencadenan la complejidad del peor de los casos en el comparador de expresiones regulares.

Si bien los algoritmos de expresiones regulares se pueden escribir de manera eficiente, la mayoría de los motores de expresiones regulares que existen amplían los lenguajes de expresiones regulares con construcciones adicionales que no siempre se pueden resolver de manera eficiente. Estos patrones extendidos hacen necesario utilizar el backtracking en una implementación de expresiones regulares en la mayoría de los lenguajes de programación.

El tipo de problema más grave ocurre con el backtracking de coincidencia de expresiones regulares, donde algunos patrones tienen un tiempo de ejecución exponencial en la longitud de la cadena de entrada.^[8]​ Para cadenas de textos de ${\displaystyle n}$ caracteres, el tiempo de ejecución es ${\displaystyle O(2^{n})}$ . Esto sucede cuando una expresión regular tiene tres propiedades:

• La expresión regular aplica la repetición (+, *) a una subexpresión.
• La subexpresión puede coincidir con la misma entrada de múltiples formas, o puede coincidir con una entrada de una cadena te texto que es un prefijo de la coincidencia más larga posible.
• Y después de la subexpresión repetida, hay una expresión que coincide con algo que la subexpresión no coincide.

La segunda condición se explica mejor con dos ejemplos:

• En (a|a)+$, la repetición se aplica a la subexpresión a|a, que puede coincidir con a de dos maneras en cada lado de la alternancia.
• En (a+)*$, la repetición se aplica a la subexpresión a+, que puede coincidir a o aa, etc.

En ambos ejemplos usamos $ para hacer coincidir el final de la cadena, satisfaciendo la tercera condición. Pero también es posible usar otro carácter para esto. Por ejemplo (a|aa)*c tiene la misma estructura problemática.

Las epresiones regulares anteriores exhibirán un tiempo de ejecución exponencial cuando se apliquen a las cadenas de texto de la forma ${\displaystyle a...a!}$ . Por ejemplo, si intentas compararlos con aaaaaaaaaaaaaaaaaaaaaaaa! en un motor de expresión de backtracking, tardará mucho tiempo en completarse y el tiempo de ejecución se duplicará aproximadamente por cada a adicional antes de !.

También es posible tener backtracking, que es tiempo polinomial. ${\displaystyle O(n^{x})}$, en lugar de exponencial. Esto también puede causar problemas durante entradas lo suficientemente largas, aunque se le ha prestado menos atención a este problema, ya que las entradas maliciosas deben durar mucho más tiempo para tener un efecto significativo. Un ejemplo de tal patrón es "a*b?a*x ", cuando la entrada es una secuencia arbitrariamente larga de "a".

Se han encontrado expresiones regulares llamadas "malvadas" o vulnerables en repositorios de expresiones regulares en línea. Tenga en cuenta que es suficiente con encontrar una subexpresión vulnerable para atacar la expresión regular completa:

1. RegExLib, id=1757 (validación de correo electrónico) - ver la parte roja: ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
2. Repositorio de expresiones regulares de validación de OWASP - nombre de clase Java - ver la parte roja: ^(([a-z])+.(([a-z])+.[A-Z]([a-z])+$

Estos dos ejemplos también son susceptibles a la entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

Si la misma expresión regular se ve afectada por la entrada del usuario, como un servicio web que permite a los clientes proporcionar un patrón de búsqueda, entonces un atacante puede inyectar una expresión regular maliciosa para consumir los recursos del servidor. Entonces, en la mayoría de los casos, la denegación de servicio mediante expresiones regulares se puede evitar eliminando la posibilidad de que el usuario ejecute patrones arbitrarios en el servidor. En este caso, las aplicaciones web y las bases de datos son las más vulnerables. Por otro lado, también es posible que una página maliciosa pueda bloquear el navegador web del usuario o hacer que utilice cantidades arbitrarias de memoria.

Sin embargo, si ya existe una expresión regular vulnerable del lado del servidor, entonces un atacante puede proporcionar una entrada que desencadene su peor comportamiento. En este caso, los escáneres de correo electrónico y los sistemas de detección de intrusos también podrían ser vulnerables. Afortunadamente, en la mayoría de los casos, las expresiones regulares problemáticas se pueden reescribir como patrones "no malvados". Por ejemplo, (.*a)+ se puede reescribir como ([^a]*a)+.

En el caso de una aplicación web, el programador puede utilizar la misma expresión regular para validar la entrada tanto en el lado del cliente como en el lado del servidor. Un atacante podría inspeccionar el código del cliente, buscar expresiones regulares malignas y enviar información manipulada directamente al servidor web para bloquearlo.^[9]​

• Ataque de denegación de servicio
• Guerra cibernética
• Low Orbit Ion Cannon
• High Orbit Ion Cannon

• Ejemplos de ataques ReDoS en aplicaciones de código abierto:
  • ReDoS en DataVault
  • ReDoS en EntLib
  • ReDoS en NASD CORE. NET Terelik
• Algunos puntos de referencia para ReDoS:
  • Achim Hoffman (2010). "ReDoS: punto de referencia para DoS de expresiones regulares en JavaScript". Consultado el 6 de noviembre de 2023.
• Documento sobre la implementación de expresiones regulares no vulnerables a ciertas clases de ataques ReDoS:
  • Russ Cox (2007). "La coincidencia de expresiones regulares puede ser sencilla y rápida". Consultado el 6 de noviembre de 2023.
• Herramientas para detectar vulnerabilidades ReDoS:
  • B. van der Merwe, N Weideman (2017). "Análisis estático de expresiones regulares". Consultado el 6 de noviembre de 2023.