Vulnerabilidad de la aplicación debido a funciones hash no aleatorias

El siguiente fragmento es de un artículo que explica la posibilidad de un ataque de Denegación de Servicio (DoS) debido a funciones hash no aleatorias utilizadas en Hash Data Structures.

[…] la condición puede aprovecharse explotando colisiones predecibles en los algoritmos de hashing subyacentes.

Para verificarlo pasé por la implementación de referencia de Java HashMap desde Oracle y de hecho encontré una función hash estática utilizada:

static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

Otro artículo sobre el tema dice:

Un servidor Tomcat 6.0.32 analiza una cadena de 2 MB de claves colisionantes en aproximadamente 44 minutos de tiempo de CPU i7, por lo que un atacante con aproximadamente 6 kbit / s puede mantener un núcleo i7 constantemente ocupado. Si el atacante tiene una conexión Gigabit, puede mantener ocupado alrededor de 100.000 i7 núcleos

¿Cómo podemos protegernos contra esta vulnerabilidad? Además, con tantos softwares usamos el código abierto (Tomcat, etc.) que se basan en esta implementación.

Entender el vector de ataque

Cómo funciona HashMap

Digamos que un formulario de comentarios en un blog acepta los parámetros – first_name, last_name, comment as post parameters. Internamente, Tomcat almacena estos parámetros como HashMap.

La estructura lógica de este HashMap es como esta:

 "first_name" --> "Sripathi" "last_name" --> "Krishnan" "comment" ---> "DoS using poor Hashes" 

Pero la estructura física es diferente. Las claves primero se convierten en un hashCode, y luego el hashCode se convierte en un índice de matriz.

La estructura física ideal se convierte así:

 0 --> "Sripathi" 1 --> "Krishnan" 2 --> "DoS using poor Hashes" 

Pero las claves posibles son infinitas. Entonces, en algún momento, dos claves tendrán el mismo código hash. Esto se convierte en una colisión hash.

Con colisiones, la estructura física se convierte en:

 0 --> "Sripathi" -> "Krishnan" 1 --> Empty 2 --> "DoS using poor hashes" 

Colisiones hash e impacto en el rendimiento

Cuando tienes colisiones hash, insertar una nueva entrada significa iterar sobre todos los elementos secuencialmente solo para descubrir si ya existe en el mapa. Insertar un elemento se convierte en O (n) complejidad. Insertar n elementos lo convierte en O (n * n) complejidad.

En resumen: si inserta miles de claves que tienen el mismo hashCode , el servidor requerirá muchos ciclos de CPU.

¿Cómo se generan claves con el mismo Hash?

En Java, “Aa” y “BB” tienen el mismo código hash.

Debido a una propiedad llamada “Subcadenas equivalentes”, podemos generar varias otras cadenas con el mismo código hash, comenzando con estas 2 cadenas.

Primera iteración: “AAAA”, “AABb”, “BbAA”, “BbBb” tienen el mismo código hash

Ahora, tenemos 4 cadenas con el mismo código hash. Podemos permutarlos para generar 16 cadenas que tendrán el mismo código hash. Por ejemplo :

 "AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa", "BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa", "AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa", "BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa", 

Todas estas 16 cadenas tienen el mismo código hash.

Ahora puede tomar estas 16 cadenas y generar 256 cadenas que tengan el mismo código hash.

En resumen: es muy fácil generar un gran conjunto de cadenas que tendrán el código hash exacto.

¿Cómo atacas el servidor?

  1. Crea miles de cadenas que tengan el mismo código hash (ver arriba)
  2. Construya una solicitud POST como esta – AaAa = & AaBB = & BBAa = & BBBB = ….
  3. Envíe el formulario
  4. Repita en un bucle y cree varios hilos para que todos los recursos del servidor se agoten

Como esto es solo una solicitud POST, un atacante también puede usar navegadores inocentes para atacar un servidor. Simplemente busque un sitio web con una vulnerabilidad de scripting entre sitios, inserte código para hacer una solicitud POST y luego use ingeniería social para extender el enlace a tantos usuarios como pueda.

Prevención

En general, la plataforma subyacente no puede arreglar esto. Esto se considera un problema de marco de aplicación. En otras palabras, Tomcat tiene que arreglar esto, no Oracle / Sun.

Las posibles soluciones incluyen:

  1. Restrinja la cantidad de parámetros POST : Tomcat 6.035+ tiene un nuevo parámetro maxParameterCount . El valor predeterminado es 10,000. Cuanto menor sea, mejor, siempre y cuando no rompa tu funcionalidad.

  2. Restrinja el tamaño de la solicitud POST : para que el ataque funcione, la carga útil debe ser enorme. El POST predeterminado permitido por Tomcat es de 2 MB. Reducir esto para decir 200KB reducirá la efectividad de este ataque. El parámetro en tomcat es maxPostSize

  3. Servidor de seguridad de aplicaciones web : si tiene un firewall de aplicaciones web, puede configurarlo para bloquear las solicitudes que parezcan sospechosas. Esta es una medida reactiva, pero es bueno tenerla en caso de que no pueda usar una de las soluciones anteriores.

FYI – La documentación de Tomcat está aquí – http://tomcat.apache.org/tomcat-6.0-doc/config/http.html

La solución más simple es actualizar a una versión fija de tomcat. Sin embargo, sospecho que quieres saber los detalles de lo que la gente de Tomcat debería cambiar.

Este ataque funciona explotando un detalle de implementación común de estructuras de datos hash, utilizando listas enlazadas para contener todos los valores cuyo hash es el mismo. Agregar valores a esta lista vinculada es ineficaz ya que el tamaño de la lista aumenta. Un atacante puede crear una lista de valores que se sabe que generan hashes en colisión, forzando este comportamiento ineficiente. Para protegerse de esto, tiene algunas opciones:

  • Prevenga las colisiones: evite que el atacante genere valores colisionantes al tener algún factor (pseudo) aleatorio en su función hash. Perl ha hecho esto durante mucho tiempo.

  • Utilice algo además de las listas vinculadas para sus depósitos: el ataque funciona porque la inserción de N elementos en una lista vinculada tiene un crecimiento de N ^ 2. Si usa un árbol balanceado o alguna otra estructura que tenga un crecimiento N logN al insertar, el problema debe ser mitigado. Esto puede sacrificar el rendimiento de un caso mejor / promedio para limitar cuán malo es el peor de los casos.

La versión de Tomcat afectada es Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 según el enlace que proporcionó. La página muestra Apache Tomcat> = 5.5.35,> = 6.0.35,> = 7.0.23 como versiones fijas.

Java HashMap / HashTable puede hacer la operación ‘cambiar tamaño’ cuando el umbral de entrada llenada alcanza. Es difícil decir que hay un HashMap de cubo fijo esperando por ti. Debido a la operación para seleccionar el cubo, tiene dos pasos: uno es tomar el valor hash de la clave especificada; Otro paso principal es el rest de la operación con el tamaño total de la cubeta (el tamaño ha sido cambiado por ‘resize’).

Aquí hay un código de Python para generar esas claves … Aún no lo he probado, pero estaría interesado en obtener comentarios al respecto:

 #!/usr/bin/python import sys alphabet = ["Aa","BB"] def func(str, length): global alphabet if(length != 0): for x in alphabet: new_str = str+x func(new_str, length-1) else: sys.stdout.write(str+"=&") for x in range(1,16): func("",x)