Enter Search Query:

REDOS

REDOS

Hace algo más de 2 meses, concretamente el día 2 de Julio de 2019, se produjo uno de los sucesos con mayor impacto en la historia reciente de internet; la caída global del servicio CDN CloudFlare, dejó fuera de servicio más del 10% de los sitios web a nivel mundial.

En los primeros momentos se especuló sobre un gran ataque de denegación de servicio distribuido contra el servicio, como ya pasó en 2016 con el ataque de la botnet “Mirai” contra el proveedor de DNS Dyn, que afectó a grandes sitios como Twitter o Spotify, aunque no fue eso lo que ocurrió.

Efectivamente el día 2 de julio algo provocó que los servidores de Cloudflare cayesen a nivel mundial y los sitios web a los que debería cubrir de ataques externos quedaron inaccesibles durante aproximadamente 2 horas.

Como más tarde aclararía el CTO de Cloudflare, John Graham-Cumming, en el blog oficial de la compañía, la interrupción del servicio fue debido a una actualización que, entre otras cosas, añadía una expresión regular mal formada que mediante un backtracking no controlado causó una denegación de servicio local en todos y cada uno de los clusters que fueron actualizados, como muestra la siguiente imagen aportada por la empresa, donde se verifica el uso del 100% del CPU.

REDOS 1

Si bien, las vulnerabilidades de denegación de servicio a través de backtracking no son algo nuevo, ya que el problema subyace en que los motores que gestionan las expresiones regulares en la mayoría de lenguajes están basados en la clausura de Kleene, del matemático estadounidense Stephen Kleene, la cual se define como “la operación unitaria de lenguajes que identifica a la concatenación sucesiva de ninguna o más veces de todas y cada una de las cadenas que conforman al lenguaje en cuestión”.

Aplicando este concepto a las expresiones regulares, puede verse fácilmente que dada la cadena ab y comprobándola contra la expresión regular (a | b | ab)* , existirían dos rutas posibles para llegar a conseguir una comprobación válida. En cambio, si la cadena que se quiere comprobar es abab el número de rutas se duplica.

Llevando este concepto a la computación y a las expresiones regulares como las conocemos, entonces:

ab*c dará un resultado positivo al comprobar tanto abbbbc como ac

ab+c dará un resultado positivo al comprobar abbbbc pero negativo con ac

En el caso de necesitar una expresión regular que de positivo para la cadena aqjihkwrjhc, una solución válida será a.*c

Con estos ejemplos, si se comprueba la cadena abbbcbbca contra la expresión regular a.*c el comportamiento esperado es que la comprobación marque la cadena abbbc como válida pero no es así, ya que, por defecto, los motores de regex basados en la clausura de Kleene devuelven el subconjunto más grande, en este caso, el resultado será abbbcbbc.

Este comportamiento puede modificarse haciendo uso del operador: ‘?’, en el segundo cuantificador, para que quede una expresión como a.*?c que devolverá el subconjunto más pequeño, esto es, abbbc.

El hecho de que el motor de regex trate de encontrar el subconjunto más grande posible si no se marca específicamente lo contrario alterando el comportamiento de los cuantificadores, incluye un nuevo concepto a todo esto, el backtracking.

Si como usuarios tenemos la cadena aaaaaaaaaa y queremos comprobarla contra la expresión regular a*b el comportamiento de la máquina será el siguiente:

REDOS 2

aaaaaaaaaa -> No coincide.

aaaaaaaaaa -> Hace backtrack para buscar un subconjunto más pequeño.

aaaaaaaaa -> No coincide.

aaaaaaaaa -> Hace backtrack para buscar un subconjunto más pequeño.

aaaaaaaa -> No coincide.

aaaaaaaa -> Hace backtrack para buscar un subconjunto más pequeño.

aaaaaaa -> No coincide.

aaaaaaa -> Hace backtrack para buscar un subconjunto más pequeño.

……………………….

aa -> No coincide.

aa -> Hace backtrack para buscar un subconjunto más pequeño.

a-> No coincide.

a-> Subconjunto de uno, no puede realizar backtrack.

En este punto el ordenador “sabe” que entre el carácter 0 y los demás no hay un subconjunto válido, pero ahora debe realizar la misma operación, aunque empezando desde el carácter 1 y así sucesivamente hasta llegar al carácter número 9. Este comportamiento provoca que el número de comprobaciones aumente rápidamente conforme se añadan más a la cadena.

Este comportamiento se agrava aún más cuando se juntan dos cuantificadores, como por ejemplo en la expresión regular (a+)*b  de la cual se obtendría el siguiente resultado:

Cadena Pasos As
c 6 0
ac 12 1
aac 24 2
aaaaac 192 5
aaaaaaaaaac 6144 10
aaaaaaaaaaaaaaaaaaaac 749997 20

En el caso de CloudFlare la expresión regular que causó el backtracking catastrófico estaba destinada a la prevención de ataques del tipo Cross Site Scripting y era la siguiente (?:(?:\»|’|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

La parte que causó el problema fue el subconjunto: .*(?:.*=.*)

REDOS 3

El exploit para esta expresión consiste en hacer uso de un payload que comience con x= y un número elevado de x . De este modo, para la cadena x=x, el elemento: .* capturará toda la cadena, forzando el fallo y el backtrack del motor que tratará de validar =x  contra el resto de elementos forzando un crecimiento exponencial de pasos necesarios para hallar la validación proporcional al número de x que se añadan a la derecha del igual.

Como solución a esta problemática existen varias posibilidades, la primera, y por la cual ha optado el equipo de desarrollo de Cloudflare es implementar un motor de expresiones regulares que no utilice el mecanismo de backtracking basado en la clausura de Kleene. De manera alternativa en caso de no disponer de esa posibilidad debe evitarse a toda costa el uso de patrones donde existan cuantificadores de forma consecutiva, especialmente si uno de los patrones está dentro de un subconjunto que será tratado como una expresión independiente por el motor antes de evaluar de forma global. Para evaluar o debuggear las expresiones regulares existen varias alternativas, tanto gratuitas y libres como de pago; las más interesantes son RegexBuddy (comercial) y Regexp::Debugger[1] (open source) , además con la herramienta también open source rxxr[2] puede comprobarse de forma fácil un listado de expresiones regulares para detectar operadores que resulten en un backtracking exponencial.


[1] metacpan.org/pod/Regexp::Debugger

[2] github.com/ConradIrwin/rxxr2

REDOS 4
Escrito por: @SADFUD 
MODERADOR UNDERC0DE
Analista de ciberseguridad en ITQ latam. Interesado en seguridad ofensiva e inteligencia. Contacto: underc0de.org/foro/profile/sadfud Redes Sociales: twitter.com/SadFud75 github.com/SadFud www.hackthebox.eu/profile/2155

Articulo publicado en UnderDOCS – Septiembre 2019, Número 2

https://underc0de.org/foro/e-zines/underdocs-septiembre-2019-numero-2/

Comentarios

Comentarios

19 febrero, 2020

Posts Relacionados

0 comentarios

Comentarios en: REDOS

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *