Técnica de búsqueda automatizada de funciones hash de enteros

Hash Function Prospector

Esta es una herramienta pequeña para la búsqueda automatizada de funciones hash de enteros. Selecciona aleatoriamente entre 9 operaciones reversibles para generar miles de millones de funciones hash de enteros. Las funciones generadas se compilan con JIT y se evalúa su comportamiento Avalanche. La mejor función se muestra en sintaxis C en el momento.

• Puntuación Avalanche: número promedio de bits de salida que permanecen sin cambiar cuando se invierte un solo bit de entrada. Cuanto menor sea la puntuación, mejor. Lo ideal es 0. Es decir, al invertir un único bit de entrada, todos los bits de salida deberían invertirse con probabilidad 50%.
• Prospector puede generar funciones hash de enteros de 32 y 64 bits. Consulta el uso (-h) para ver todas las opciones. Debido al compilador JIT, solo se admite x86-64, pero las funciones encontradas pueden usarse en cualquier parte.

Funciones hash encontradas

Prospector y otras utilidades auxiliares aquí presentes encontraron dos familias de funciones hash útiles. Ambas usan una estructura xorshift-multiply-xorshift, pero con distinto número de rondas.

Función de 2 rondas

TheIronBorn usó optimización combinatoria para encontrar los mejores parámetros conocidos para esta estructura.

• Esta permutación de 2 rondas de 32 bits tiene un sesgo particularmente bajo y supera al finalizer de 32 bits de MurmurHash3 por una diferencia pequeña.
• La estructura de la función hash fue encontrada por Prospector, y los parámetros se ajustaron con Hill Climbing y algoritmo genético.
• Hay más constantes de 2 rondas con sesgo bajo, y algunas son mejores que lowbias32.

Función de 3 rondas

Agregar una ronda extra de multiply-xorshift a esta estructura puede alcanzar el límite teórico de sesgo con parámetros cuidadosamente elegidos. Por ejemplo, esta función hash es indistinguible de un PRF perfecto.

• triple32 no solo resuelve el problema de hash(0) = 0, sino que también reduce más el sesgo.
• Hay más constantes de 3 rondas con sesgo bajo.

Medición de sesgo precisa

El modo -E evalúa el sesgo de una función hash dada (-p o -l). Por defecto, Prospector usa una estimación para medir rápidamente el sesgo de la función, pero es no determinista y añade bastante ruido al resultado. Para medir el sesgo exacto de forma exhaustiva, usa la opción -e.

• Puedes definir la función a probar con -p y un patrón, o con una biblioteca compartida que incluya una función hash() y -l.
• No hay prueba exhaustiva exacta para funciones hash de 64 bits porque tarda demasiado.

Selección de operaciones reversibles

Se usan las siguientes operaciones reversibles:

• x = ~x;
• x ^= constant;
• x *= constant | 1; (solo constantes impares)
• x += constant;
• x ^= x >> constant;
• x ^= x << constant;
• x += x << constant;
• x -= x << constant;
• x <<<= constant; (rotación a la izquierda)
• x = bswap(x) (intercambia bytes altos y bajos)

Técnicamente, x = ~x queda cubierto por x ^= constant; sin embargo, ~x es único y especialmente útil.

Hash de 16 bits

Como las restricciones para hashes de 16 bits son distintas, existe una herramienta separada llamada hp16 para generar este tipo de hashes.

• A diferencia de los Prospector de 32/64 bits, esta implementación es totalmente portable y se ejecuta en casi cualquier sistema.
• También permite generar y evaluar una S-box de 128KiB.
• Los hashes de 16 bits pueden ser más útiles en máquinas sin instrucciones de multiplicación rápida, por lo que se puede omitir una operación específica durante la búsqueda (-m, -r).

Algunos resultados interesantes:

• Hash xorshift-multiply de 2 rondas
• Hash xorshift-multiply de 3 rondas
• Hash sin multiplicación (solo xorshift-add)

Una buena hash xorshift de 3 rondas (búsqueda corta con hp16 -Xn3) se acerca a una buena S-box (hp16 -S).

Al realizar operaciones de 16 bits hay que tener en cuenta las reglas de promoción de enteros en C. El programa C que se genera en esta herramienta presta atención a promover las operaciones de 16 bits a unsigned int cuando sea necesario.

Opinión de GN⁺

• La seguridad de las funciones hash es clave en criptografía y seguridad informática, así que este tipo de herramientas de búsqueda parece útil para la investigación. En particular, es interesante encontrar funciones hash de sesgo bajo mediante búsqueda aleatoria.
• Pero la seguridad de una función hash no puede garantizarse solo por características estadísticas. Los hashes criptográficos deberían ser seguras frente a ataques como PreImage Resistance, Second PreImage Resistance y Collision Resistance, así que probablemente también haga falta ese tipo de análisis.
• Los hashes de 16 bits parecen útiles en entornos limitados como IoT o sistemas embebidos. Es llamativo que se puedan crear funciones hash con solo ADD/XOR/SHIFT para poder usarlas también en CPUs sin instrucciones de multiplicación.
• Aplicar técnicas de búsqueda heurística como Hill Climbing o algoritmos genéticos al diseño de funciones hash también es una idea novedosa. El uso de IA para integrar en el diseño de algoritmos criptográficos está activo, y estas técnicas de optimización probablemente jugarán un papel aún más importante en el futuro.
• Sin embargo, debido a las limitaciones de una función hash, aunque tenga excelentes propiedades Avalanche, todavía parece difícil decir que sea criptográficamente segura; eso se ve como la principal limitación de este proyecto. Aun así, una herramienta así puede ayudar a analizar y mejorar las debilidades de funciones hash existentes.

[GN⁺]

Comentario de Hacker News

• Motivos por los que le gusta el código de ese desarrollador
  • Le agradan la librería JSON, la librería de parseo de opciones, el decodificador UTF-8 sin ramas, la pila lock-free y la librería trie.
  • También le gustó que todas esas librerías estén publicadas bajo la licencia Unlicense.
• Comentario del autor de MurmurHash
  • Comentó que le parecía interesante que la operación multiply-shift-xor haya resistido por tanto tiempo.
• Compartió ideas para la búsqueda automática de funciones hash
  • Sugirió evaluar la salida automáticamente en combinación con SMHasher3
    • Se pueden usar solo algunas pruebas para priorizar velocidad y permitir fallos rápidos.
  • También sería bueno expandirlo a hashes de 64 y 128 bits (aunque el espacio de búsqueda sea mayor).
  • Preparó un código en NodeJS para medir el efecto avalanche de la multiplicación por primos de 64 bits en la librería Rain.
• Compartió su experiencia implementando el problema 1brc en Go
  • Intentó encontrar una función hash perfecta personalizada para colocar cada estación en su propio bucket sin colisiones, pero dejó de hacerlo por una regla: no puedes personalizar la función hash para tus datos antes de iniciar el programa.
  • Hizo una herramienta de pruebas que revisa constantes aleatorias y muestra la mejor constante encontrada hasta el momento según la cantidad de buckets colisionados y el número de colisiones.
    • Pudo reducir a un solo bucket con solo 2 valores colisionados con una tasa de carga de alrededor del 40%.
    • Encontró interesante que, independientemente de otras constantes, aparecieron valores similares para el número de desplazamientos hacia buckets dentro de la mejor constante de rendimiento.
• Solicitó una explicación de por qué el código es atractivo y para qué se usa.
• Preguntó exactamente qué hace el código: si busca la mejor función hash o, de no ser así, por qué la mejor función hash cambia cada vez que se ejecuta.
• Solicitó información sobre el mecanismo para encontrar buenas funciones hash para valores enteros dentro de un rango específico.
  • Por ejemplo, si conoces valores enteros entre 10,000 y 200,000 y quieres hashearlos hacia el número óptimo de buckets.
• Mencionó que limitarse a operaciones reversibles tiene ventajas matemáticas, pero descarta muchas posibilidades.
  • Pensó en hashing perfecto al conocer de antemano el conjunto de entradas.
  • Normalmente se usan arreglos de constantes, pero quería saber si se podía comprimir más si las entradas ya son enteros pequeños.
  • Preparó una lista de unas 100 operaciones básicas y dejó de continuar el proyecto cuando se aburrió.
• Opinó que usar la misma constante en ambas multiplicaciones podría reducir el tamaño del código y hacer el cálculo un poco más rápido.
• Aunque reconoció que estas funciones no son adecuadas para criptografía, preguntó qué impacto tiene el "sesgo" medido en el análisis criptográfico.
  • Quería saber si alguien familiarizado con criptografía diferencial podría explicarlo.
  • Quería saber si un hash con bajo sesgo podría invalidar un análisis criptográfico con menos rondas o menos cálculo.
  • Preguntó si esta herramienta podría ayudar a encontrar funciones hash criptográficas mejores.
• Presentó un proyecto similar
  • La calidad de la función es mejor, aunque la velocidad sea más lenta (usa un intérprete).
  • Sin embargo, no encontró nada mejor que las funciones hash existentes.