En casi todos los lenguajes de programación hay algún tipo de estructura de datos como una tabla hash (llamados por ejemplo hash map, hash table, dictionary, entre otros). Básicamente permiten asociar un valor a una clave y posteriormente obtener dicho valor proporcionando la clave en un tiempo constante sin importar cuantas claves haya en la estructura.
Para lograr que la búsqueda sea en tiempo constante, los valores se almacenan en una posición de la tabla según el valor de hash de su clave.
Es posible, aunque poco probable, que dos claves distintas generen una colisión, es decir que dos claves distintas generen el mismo valor de hash y por lo tanto dos valores deban guardarse en una misma posición. Una forma de hacer eso es tener una lista de valores en lugar de solo un valor en cada posición. Luego de identificar la posición mediante el valor de hash se hace una búsqueda secuencial entre todos los elementos de esa lista.
Un ataque de denegación de servicio mediante hash o Hash DoS consiste en explotar esas colisiones para hacer que la lista de valores sea muy larga y se requiera mayor tiempo de procesamiento para buscar, agregar y eliminar elementos.
En lenguajes usados para aplicaciones Web como PHP, Python, Java, Ruby o ASP, los valores ingresados mediante un formulario web son cargados en tablas hash para su posterior procesamiento y por eso todos resultaron vulnerables a esos ataques.
En esta transparencia de PHP se muestra un requerimiento POST creado para explotar esta vulnerabilidad: http://talks.php.net/show/phpuk2012/14
Existen tres formas de atacar el problema, con diferentes grados de éxito y complicación.
- PHP, ColdFusion y ASP optaron por «controlar los daños» limitando a 1.000 la cantidad de valores de entrada que pueden llegar en un requerimiento POST. En el php.ini de PHP 5.3.9 en adelante hay una configuración max_input_vars=1000.
- Python [http://bugs.python.org/issue13703], Ruby y Java 7 adoptaron una mejora en el algoritmo de hash para dificultar la generación de colisiones incorporando números pseudoaleatorios en su cálculo.
- Java 8 incorpora un árbol balanceado para almacenar todos los valores cuyas claves tengan el mismo hash [http://openjdk.java.net/jeps/180]. De esa forma con miles de millones de valores, apenas requeriría 50 operaciones para resolver la búsqueda.
Es importante destacar que la solución adoptada por PHP, ASP y ColdFusion de limitar la longitud de la entrada no resuelve por completo el problema ya que por ejemplo si se envía un hash con muchas colisiones dentro de un string JSON, pueden ser menos de 1.000 parámetros e igual disparar el problema. Básicamente las aplicaciones deben igualmente verificar internamente los datos que reciben.
La alternativa de mejorar la función de hash es un bastante más robusta, aunque puede ser más difícil de implementar. En algunos lenguajes podría tener un impacto negativo en la performance o requerir cambios en algún comportamiento ya definido.
La solución elegida en Java 8 (y que vuelve atrás los cambios incorporados en Java 7 para tratar este mismo problema) es muy robusta y elimina la causa fundamental del problema.
Ignorante 