Recorrido narrado

El peor caso y el atacante

El O(1) de una tabla hash es esperado: supone que la función hash reparte las claves como si fueran al azar. Si todas las claves caen en la misma cubeta, buscar es recorrer n claves: O(n) en el peor caso, e insertar n claves cuesta O(n²).

Con claves normales esto casi no pasa. Pero si un atacante conoce la función hash, puede fabricar miles de claves con el mismo hash y enviarlas a un servidor que las guarde en una tabla. Cada petición se vuelve lenta y el servidor deja de responder. Es un ataque conocido como HashDoS (2011).

La defensa: una semilla aleatoria que se elige al arrancar el programa y entra en el cálculo del hash. Sin conocer la semilla, el atacante no puede fabricar colisiones.

hash(k) ← función_resistente(semilla, k)