Los hash rápidos colisionan más de lo que prometen ante entradas adversarias

Pasar un test estadístico no dice nada sobre lo que ocurre cuando las entradas las elige un atacante. Eso es lo que sostiene un análisis de Thomas Dybdahl Ahle, de Normal Computing, que ha revisado buena parte de los hash no criptográficos que se usan a diario y ha encontrado que la mayoría tiene pares de mensajes que colisionan bastante más de lo que prometen sus garantías.

El punto de partida es la definición de hash b-bit universal: dos entradas distintas de longitud L colisionan como mucho con probabilidad L·2^−b para cualquier L. Es una propiedad demostrable, algo raro en criptografía, donde casi nada se puede probar. La pregunta es cuál es el hash más rápido que mantiene esa garantía para el b que necesitas. Ahle usó Claude Fable para analizar una selección amplia de los hash que recoge SMhasher, el proyecto de referencia para medir propiedades estadísticas. El resultado: la mayoría tiene entradas con las que se comporta de forma desastrosa, al menos 20 bits por debajo de lo esperado. En algunos casos, el modelo encontró errores en pruebas ya publicadas; en otros las verificó en Lean.

Lo probado y lo observado

El gráfico que acompaña al análisis separa tres cosas que se suelen mezclar. Los puntos sólidos son garantías demostradas; los huecos, afirmaciones sin probar. Los rombos marcan cotas superiores obtenidas con un par concreto de mensajes que colisiona, y las cruces, pares que colisionan para cualquier semilla. Esa distinción importa: encontrar un par malo no demuestra que exista otro peor, así que estas cotas no ordenan los hash por seguridad. El esfuerzo de búsqueda tampoco fue el mismo para todos.

Los números concretos: un par histórico de 32 bytes daba 9, 12, 11 y 11 colisiones por cada 2^30 claves en wyhash, rapidhash v1, rapidhash v3 y XXH3-64. El par elegido para XXH3-64 se queda en unas 527 de cada 2^36 claves, con muestreo. La velocidad se mide sobre mensajes de 256 KiB y se expresa en bytes por ciclo; xxHash, por ejemplo, presume de 60 GB/s, prácticamente lo que da la memoria.

Para quien elige un hash esto cambia el criterio. Que una función pase SMhasher no la hace resistente a entradas elegidas: son dos cosas distintas, y la segunda es la que te tumba una tabla hash o te abre un DoS cuando el input viene de fuera. Hay excepciones con prueba publicada, como los dos límites de UMASH, y alguna prueba corregida, como el wrapper de HalftimeHash. Para el resto, la pregunta ya no es si colisiona, sino cuánto tarda alguien en encontrar el par. Los detalles de la medición están en el repositorio de reproducción.