ReDoS

De Wikipedia, la enciclopedia libre

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]​

Descripción[editar]

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 estados posibles, donde 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 , de modo que caminar a través de una entrada de longitud 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 (m2n) 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.

Ejemplos[editar]

Backtracking exponencial[editar]

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 caracteres, el tiempo de ejecución es . 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 . 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. , 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".

Expresiones regulares vulnerables en repositorios en línea[editar]

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!.

Ataques[editar]

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]​

Véase también[editar]

Referencias[editar]

  1. ↑ OWASP (10 de febrero de 2010). «Regex Denial of Service». Consultado el 16 de abril de 2010. 
  2. ↑ Davis, James; Louis, Michael; Coghlan, Christy; Servant, Francisco; Lee, Dongyoon (2019). «Why Aren't Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions». The ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering: 443-454. 
  3. ↑ RiverStar Software (18 de enero de 2010). «Security Bulletin: Caution Using Regular Expressions». Archivado desde el original el 15 de julio de 2011. Consultado el 16 de abril de 2010. 
  4. ↑ Ristic, Ivan (15 de marzo de 2010). ModSecurity Handbook. London, UK: Feisty Duck Ltd. p. 173. ISBN 978-1-907117-02-2. Archivado desde el original el 8 de agosto de 2016. Consultado el 7 de noviembre de 2023. 
  5. ↑ Crosby and Wallach, Usenix Security (2003). «Regular Expression Denial Of Service». Archivado desde el original el 1 de marzo de 2005. Consultado el 13 de enero de 2010. 
  6. ↑ Static Analysis for Regular Expression Denial-of-Service Attacks. Springer. 2013. pp. 135-148. doi:10.1007/978-3-642-38631-2_11. 
  7. ↑ Lazy computation of the DFA can usually reach the speed of deterministic automatons while keeping worst case behavior similar to simulation of an NFA. However, it is considerably more complex to implement and can use more memory.
  8. ↑ Jim Manico and Adar Weidman (7 de diciembre de 2009). «OWASP Podcast 56 (ReDoS)». Consultado el 2 de abril de 2010. 
  9. ↑ Barlas, Efe; Du, Xin; Davis, James (2022). «Exploiting Input Sanitization for Regex Denial of Service». ACM/IEEE International Conference on Software Engineering: 1-14. arXiv:2303.01996. 

Enlaces externos[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=ReDoS&oldid=157215573»