33 votos

Aplicación de vulnerabilidad debido a la No Aleatoria de las Funciones de Hash

A continuación es un fragmento de un artículo que explica la posibilidad de Denegación De Servicio(DoS) ataque a causa de la no aleatoria de las funciones de hash se utiliza en Hash Estructuras de Datos.

[...] la condición puede ser aprovechado por la explotación de predicción de colisiones en el subyacente de los algoritmos de hash.

Con el fin de verificar que fui a través de la implementación de referencia de Java HashMap de Oracle y, de hecho, se encontró una estática de las funciones de hash utilizado:

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

Otro documento sobre el tema dice:

Un Tomcat 6.0.32 servidor analiza un 2 MB cadena de chocar claves acerca de 44 minutos de tiempo de CPU i7, por lo que un atacante con cerca de 6 kbit/s puede mantener un core i7 constantemente ocupado. Si el atacante tiene una conexión Gigabit, se puede mantener cerca de 100.000 i7 núcleos ocupados

¿Cómo podemos proteger contra esta vulnerabilidad. Además así con muchos de los softwares de nosotros el uso de código abierto (Tomcat, etc.) los que confían en esta aplicación.

51voto

Sripathi Krishnan Puntos 15402

La Comprensión De Vector De Ataque

Cómo HashMap del trabajo

Decir un formulario de comentarios en un blog acepta los parámetros - first_name, last_name comentario como parámetros post. Internamente, Tomcat tiendas de estos parámetros como un HashMap.

La estructura lógica de este HashMap es como este -


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

Pero la estructura física es diferente. Las llaves se convierten primero en una etiqueta y, a continuación, la etiqueta se convierte en un índice de la matriz.

El ideal de la estructura física se convierte así -


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

Pero las claves posibles son infinitas. Así que en algún punto, dos llaves tendrá el mismo código hash. Esto se convierte en una colisión de hash.

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


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

Colisiones de Hash y el impacto en el rendimiento

Cuando haya colisiones de hash, la inserción de un nuevo medio de entrada de iterar sobre todos los elementos de forma secuencial para averiguar si ya existe en el mapa. La inserción de un elemento se convierte en S(n) la complejidad. La inserción de n elementos hace que sea O(n*n) complejidad.

En resumen : Si usted insertar miles de claves que tienen el mismo hashCode, el servidor requiere una gran cantidad de ciclos de CPU.

¿Cómo se puede generar claves con el mismo Hash?

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

Porque de una propiedad llamada "Equivalente Subcadenas", podemos generar otras varias cadenas con el mismo hashcode, sólo a partir de 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 permutar para generar 16 cadenas que tienen el mismo código hash. Por ejemplo :


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

Todos estos 16 cadenas tienen el mismo código hash.

Ahora usted puede tomar estos 16 cadenas, y generar 256 cadenas que tienen el mismo hashcode.

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

¿Cómo se puede atacar el servidor?

  1. Crear miles de cadena que tienen el mismo código hash (ver arriba)
  2. Construir una solicitud POST como este - AaAa=&AaBB=&BBAa=&BBBB= ....
  3. Enviar el formulario
  4. Repita en un bucle, y crear varios hilos de modo que todos los recursos del servidor son usados

Porque esto es sólo una solicitud POST, un atacante puede utilizar también inocente de los navegadores para atacar a un servidor. Acaba de encontrar un sitio web con un cross site scripting vulnerabilidad, código de inserción para hacer una petición POST, y, a continuación, utilizar la ingeniería social para difundir el enlace a tantos usuarios como usted puede.

Prevención

En general, la plataforma subyacente no puede solucionar este problema. Esto es considerado como un marco de aplicación problema. En otras palabras, Tomcat tiene para solucionar este problema, no de Oracle/Sun.

Posibles soluciones incluyen :

  1. Restringir el número de parámetros POST - Tomcat 6.035+ tiene un nuevo parámetro maxParameterCount. El valor predeterminado es de 10.000. Baja la mejor, siempre y cuando no se rompa su funcionalidad.

  2. Restringir el tamaño de la petición POST - Para que el ataque funcione, la Carga tiene que ser enorme. El valor predeterminado POST permitido por Tomcat es de 2 mb. La reducción de este a decir 200 KB reducirá la eficacia de este ataque. El parámetro en tomcat es maxPostSize

  3. Firewall de Aplicaciones Web - Si usted tiene un firewall de aplicaciones web, se puede configurar para bloquear las solicitudes que parecen sospechosos. Esta es una medida reactiva, pero es bueno tener en caso de que usted no puede utilizar una de las soluciones anteriores.

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

3voto

Peter Recore Puntos 11208

La solución más simple es actualizar a una versión fija de tomcat. Sospecho, sin embargo, usted quiere saber los detalles de lo que el tomcat personas que tendrían que cambiar.

Este ataque funciona mediante la explotación de una aplicación común de detalle de hash estructuras de datos - uso de listas enlazadas para contener todos los valores cuyo hash es el mismo. La adición de los valores de esta lista enlazada es ineficiente como el tamaño de la lista se hace grande. Un atacante puede crear una lista de valores que son conocidos para generar colisión de hash, obligando a este ineficiente comportamiento. Con el fin de protegerse contra esto, usted tiene un par de opciones:

  • Evitar colisiones - evitar que el atacante de la generación de colisión de valores por tener algunos de los (pseudo) aleatorios factor en su función de hash. Perl ha hecho esto por un largo tiempo.

  • El uso de algo además de listas enlazadas para su cubos - el ataque de las obras debido a la inserción de N elementos en una lista enlazada tiene N^2 crecimiento. Si utiliza un árbol equilibrado o alguna otra estructura que tiene N logN de crecimiento a la hora de insertar, el problema debe ser mitigado. Esto puede sacrificar algunas de las mejores/promedio de rendimiento con el fin de limitar lo mal que está el peor caso.

1voto

Peter Lawrey Puntos 229686

Tomcat versión afectados son Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 como por el enlace proporcionado. La página de listas de Apache Tomcat >= 5.5.35, >= 6.0.35, >= 7.0.23 como en versiones Fijas.

0voto

Denny Ye Puntos 6

Java HashMap/HashTable puede hacer el 'resize' operación cuando el llenado de la entrada de alcanzar el umbral. Es difícil decir que no tienen un fijo cubo HashMap esperando por usted. Debido a la operación para la selección de cubo tiene dos pasos: uno es tomar el valor hash de la clave especificada; otro paso primordial es el resto de la operación, con un total de cubo de tamaño(el tamaño ha de ser cambiado por 'resize').

0voto

ossys Puntos 1618

Aquí un poco de código en python para generar las claves... no lo He probado todavía, pero estaría interesado en obtener retroalimentación sobre ella:

#!/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)

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X