Casi la función hash portátil de 64 bits más rápida con una calidad decente.
Esta es una traducción del artículo original de Leonid Yuriev .
En lugar de un descargo de responsabilidadOmitiré la definición de funciones hash junto con la lista detallada de las propiedades y requisitos para su aplicación criptográfica, y supondré que el lector tiene el conocimiento mínimo necesario o lo leerá . También se debe tener en cuenta que, en lo sucesivo, hablaré sobre funciones hash no criptográficas (no adecuadas para la criptografía), a menos que se indique explícitamente lo contrario.
BanalidadesEl hash se usa en muchos algoritmos, y casi siempre se requiere el procesamiento de datos más eficiente (rápido), junto con un cierto nivel mínimo de calidad de hash. Aquí el término "calidad" significa, en primer lugar, una especie de "aleatoriedad" (estocasticidad) en relación con los datos iniciales. Con menos frecuencia se imponen requisitos adicionales, como resistencia a la generación deliberada de colisiones o irreversibilidad.
Para ser un poco más tediosoPara mayor claridad, es necesario definir el concepto de "calidad" de la función hash y el resto de los requisitos con un poco más de detalle:
Calidad de línea de base y efecto de avalancha : cambiar uno o más bits arbitrarios en un conjunto arbitrario de datos de origen hace que cada bit del resultado cambie con una probabilidad de ½.
- Irreversibilidad o primera resistencia previa a la imagen: la imposibilidad de obtener los datos originales o bits individuales del resultado de hash.
- Resistencia a colisiones de primer orden y / o resistencia previa a la segunda imagen: la dificultad de encontrar / ajustar el conjunto de datos original para obtener un resultado específico o parte de él, incluso cuando se conoce el conjunto de datos inicial.
- Resistencia a colisiones de segundo orden: la dificultad de encontrar / ajustar dos conjuntos de datos diferentes que darían el mismo resultado o una coincidencia de una parte significativa.
Omitiendo largas citas de las matemáticas subyacentes, se puede resumir:
- Satisfacer todos los requisitos anteriores al tiempo que garantiza un alto rendimiento es un problema bastante difícil, resolver lo que nos daría una buena función hash criptográfica. Pero todavía no vamos a hacer esto.
- Proporcionar calidad básica requiere un número suficientemente grande de operaciones de ALU. En pocas palabras, la calidad siempre compromete con la velocidad.
- La obtención de un resultado de alta calidad con un ancho de bits mayor que el ancho de bits de las operaciones de ALU requiere un aumento de varias veces en el número de mezclas y, por lo tanto, operaciones básicas de ALU.
- En general, crear una función hash rápida implica lograr un compromiso ponderado entre velocidad, calidad y bitness de resultado .
Por lo tanto, puedo decir que t1ha apareció como resultado de la búsqueda de un compromiso entre calidad y velocidad, al mismo tiempo teniendo en cuenta las capacidades de los procesadores modernos y los métodos ya encontrados (combinaciones lógico-aritméticas) de mezclar y distribuir dependencias ( efecto avalancha).
La versión básica de t1ha es una de las funciones hash portátiles más rápidas para construir tablas hash y otras aplicaciones relacionadas. La versión básica de t1ha se centra en arquitecturas little-endian de 64 bits, toma un valor de sal (semilla) de 64 bits y produce un resultado de 64 bits, que incluye el fortalecimiento por longitud de clave y semilla. Vale la pena señalar que t1ha está diseñado intencionalmente para devolver 0 para datos de entrada cero (una clave de tamaño cero y cero semilla).
Respondiendo las preguntas más popularesOperaciones de 64 bits : Quizás se debe tener en cuenta que son las operaciones de 64 bits las que proporcionan velocidad y calidad sin perjudicar la portabilidad. De hecho, cuanto mayor es la capacidad de dígitos de las operaciones aritméticas, más efecto de avalancha producen y mejor mezclan los datos. Además, el procesamiento de datos, en igualdad de condiciones, es ciertamente más rápido en 8 bytes que en 4. Por otro lado, las operaciones de 64 bits están disponibles de forma nativa en muchos procesadores modernos y pueden traducirse más o menos adecuadamente a 32- los mordidos Todas las demás opciones, incluidas las operaciones SIMD , nos obligan a sacrificar en gran medida la portabilidad y / o velocidad en plataformas no nativas.
Resultado de 64 bits : para construir tablas hash, en muchos casos, un resultado de ancho de bits más pequeño es suficiente. Incluso 32 bits pueden ser más que suficientes. Sin embargo, cuando se utilizan operaciones de 64 bits, el resultado de 64 bits es algo natural. Al mismo tiempo, un resultado hash de 64 bits de calidad suficientemente alta le permite realizar rápidamente una comparación para determinar la no igualdad, y con buena precisión para comparar la igualdad.
La "magia" anterior de reemplazar las comparaciones puede parecer poco clara e innecesaria, o puede aumentar la velocidad de hash en un orden de magnitud solo por medio de la localidad de los datos, es decir, menos contaminación de la memoria caché de la CPU. En pocas palabras, se puede construir una estructura de tabla hash de tal manera que los valores hash calculados se encuentren uno al lado del otro (empaquetados en líneas de caché). La CPU solo tomaría los datos reales si los valores hash coincidieran. Y en este caso, los 64 bits de t1ha permiten obtener el mejor resultado posible . Dicho esto, 128 bits ya no proporcionarán una ventaja, mientras que tomar menos de 64 bits siempre es posible.
Comparación con HighwayHash : Tengo sentimientos encontrados sobre este proyecto no oficial de los empleados de Google .
- Por un lado, tiene un buen código y una excelente implementación técnica. Por otro lado, HighwayHash se posiciona como posiblemente criptográficamente fuerte (al menos igual a SipHash ). Dentro de HighwayHash hay bastantes manipulaciones que nos permiten esperar que el resultado no sea malo. Sin embargo, no hay pruebas que nos permitan decir eso de manera confiable. La prueba provista de "fuerza" se reduce a los resultados de las pruebas estadísticas, pero sin capacidad de reproducirlos (en un punto incluso me permití un comentario algo superfluo).
- HighwayHash es realmente rápido solo en x86_64 con AVX2 o SSE41. ¿No es más fácil simplemente usar la aceleración AES-NI o SHA?
Si todo va bien, se agregarán opciones adicionales a la suite t1ha (principalmente para el bitness resultante) y se optimizarán para E2K. Con esto me gustaría cerrar el tema de las comparaciones con HighwayHash.
Calidad
Evaluar la calidad de una función hash en todos los aspectos puede ser bastante difícil. Se puede hacer analíticamente o implementando varias pruebas estadísticas. Desafortunadamente, el enfoque analítico no es muy efectivo para evaluar las funciones hash con un compromiso entre calidad y velocidad. Además, una evaluación analítica comparativa de tales funciones tiende a ser subjetiva.
En contraste, las pruebas estadísticas pueden proporcionar estimaciones cuantitativas claras. Para tales fines, hay paquetes de prueba bien probados, como SMHasher . Para t1ha , los resultados son simples: todas las opciones de t1ha pasan todas las pruebas sin ningún comentario. Por otro lado, no se debe suponer que t1ha tiene propiedades superiores a las necesarias para la aplicación de destino (creación de tablas hash).
El número de colisiones en todos los niveles (variantes) de t1ha corresponde a la paradoja del cumpleaños . Para formularlo estrictamente, la probabilidad de colisión en t1ha corresponde a la probabilidad de coincidencia de valores discretos aleatorios con el bitness correspondiente.
Se observa una probabilidad similar de colisiones en todas las funciones hash de alta calidad. Sin embargo, esto es solo una probabilidad, por lo que el número real de colisiones puede variar para cada conjunto de datos específico.
Después de que este artículo se publicara por primera vez, Yves Orton descubrió que el primer t1ha1() no siempre cumple con el estricto criterio de avalancha . Este inconveniente es insignificante para aplicaciones específicas de t1ha1() e imperceptible desde un punto de vista práctico. Sin embargo, esta desventaja se elimina en el siguiente nivel / variante t1ha2() , que originalmente se planeó para proporcionar una calidad ligeramente superior. En los nuevos procesadores, que usan versiones actuales de compiladores, t1ha2() es en promedio un ciclo más rápido que t1ha1() , y en el resto de los casos puede ser un ciclo más lento. Vale la pena señalar que t1ha2() también ofrece el modo hash de flujo y un resultado de 128 bits.
Los lectores sin duda apreciarán un análisis exhaustivo y profundo de la calidad y / o resistencia de t1ha . Sin embargo, según las áreas de aplicación de t1ha objetivo, esto parece redundante. En pocas palabras, la velocidad era más importante para nosotros, incluso para las teclas cortas. Por lo tanto, no se consideró la mezcla multi-ronda. La versión actual de t1ha ahorra en ciclos y ofrece un resultado de 64 bits: es prácticamente inútil medir el compromiso encontrado de otra manera que no sea estadísticamente, y sus resultados son simplemente buenos.
De hechoAcabo de seguir a mis colegas de Google en cómo proporcionan su prueba estadística
Puntos de referencia
En cuanto a la afirmación de ser " el más rápido ". Es importante tener en cuenta que obviamente no es probable que haya una función hash que sea al mismo tiempo útil y más rápida en todas las plataformas / arquitecturas. Los diferentes procesadores tienen diferentes conjuntos de instrucciones disponibles y ejecutan instrucciones similares con diferentes eficiencias. Obviamente, la función " universalmente más rápida " probablemente no se puede crear. Sin embargo, parece aceptable usar el término "el
más rápido »para una función que es portátil y al mismo tiempo la más rápida, al menos en la plataforma más común (x86_64), mientras que tiene pocas posibilidades de perder en cualquier procesador moderno con un compilador decente de optimización.
El código fuente del proyecto incluye una prueba que verifica la exactitud del resultado y mide la velocidad de cada variante implementada. Al mismo tiempo, en x86, dependiendo de las capacidades del procesador (y del compilador), se pueden verificar variantes adicionales de funciones, y las mediciones se realizan en ciclos de procesador.
Además, el sitio web del proyecto contiene tablas con los resultados de las mediciones de rendimiento a través de una versión modificada de SMHasher de Reini Urban . Uno puede verificar todas las cifras y / u obtener resultados en un procesador específico utilizando un compilador específico.
Aquí puede comparar t1ha con algunos de sus competidores más cercanos.
Hashing teclas cortas (promedio de 1..31 bytes).
Mire la columna derecha "Ciclos / Hash" (más pequeño es mejor) :
| Función | MiB / Segundo | Ciclos / Hash |
|---|
| t1ha | 12228.80 | 35,55 |
| Fasthash64 | 5578,06 | 43,42 |
| CityHash64 | 11041.72 | 51,77 |
| xxHash64 | 11123.15 | 56,17 |
| Metrohash | 11808.92 | 46,33 |
Hashing claves largas (256 Kb).
Mire la columna central "MiB / Second" (más grande es mejor) :
| Función | MiB / Segundo | Ciclos / Hash |
|---|
| t1ha | 12228.80 | 35,55 |
| Farmhash64 | 12145.36 | 60,12 |
| CityHash64 | 11041.72 | 51,77 |
| xxHash64 | 11123.15 | 56,17 |
| Espeluznante64 | 11820.20 | 60,39 |
Variantes de t1ha
Desarrollo de t1ha El primero de estos objetivos era obtener una función portátil rápida de calidad suficientemente alta para construir tablas hash.
Luego, queríamos tener la versión más rápida de la función hash que ofreciera un resultado de calidad comparable pero que se adaptara a la plataforma objetivo tanto como fuera posible. Por ejemplo, la versión básica de t1ha funciona con el orden de bytes little-endian, debido a lo cual es necesaria una conversión para arquitecturas big-endian con pérdida inevitable de rendimiento. Entonces, ¿por qué no deshacerse de las operaciones innecesarias en una plataforma de destino específica? De esta manera, se agregaron varias opciones más:
- Versión simplificada para plataformas de 32 bits, tanto pequeñas como big endian.
- Variante que utiliza instrucciones AES-NI, pero sin AVX.
- Dos variantes utilizando las instrucciones AES-NI y AVX.
Más tarde se hizo evidente que se necesitarían más opciones diseñadas para diversas aplicaciones, incluidos los diferentes resultados de ancho de bits, calidad y requisitos de durabilidad. Tal diversidad requería una sistematización adecuada. Esto se logró cambiando el esquema de nomenclatura, en el que el sufijo numérico indica el "nivel" de la función:
t1ha0() : es la opción más rápida para el procesador actual.t1ha1() : es la versión básica portátil de 64 bits de t1ha.t1ha2() : es una versión portátil de 64 bits con un poco más de preocupación por la calidad.t1ha3() - es una versión portátil rápida de 128 bits para t1ha3() huellas digitales.- etc.
En este esquema, se supone que t1ha0() es un despachador que implementa la redirección dependiendo de la plataforma y las capacidades del procesador actual. Además, se puede introducir el uso de los sufijos "_le" y "_be" para una elección explícita entre las variantes little-endian y big-endian. Por lo tanto, bajo el letrero "t1ha" ahora hay varias funciones hash, y esta familia crecerá en el futuro, incluida una versión optimizada para E2K ruso "Elbrus".
Una idea general del conjunto actual de funciones y sus propiedades se puede captar mirando la salida de prueba incorporada ( make check ). Vale la pena señalar que todas las funciones pasan todas las pruebas de SM Hasher, y el rendimiento de las variantes AES-NI varía mucho según el modelo de procesador:
Intel(R) Core(TM) i7-6700K CPU @ 3.00GHz Build by GNU C/C++ compiler 8.2 [...] - use RDPMC_40000001 as clock source - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle Bench for tiny keys (7 bytes): t1ha0 : 13.14 cycle/hash, 1.877 cycle/byte, 1.598 Gb/s @3GHz t1ha1_64le : 15.14 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha2_atonce : 15.50 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha1_64be : 16.78 cycle/hash, 2.397 cycle/byte, 1.251 Gb/s @3GHz xxhash32 : 17.17 cycle/hash, 2.453 cycle/byte, 1.223 Gb/s @3GHz StadtX : 17.59 cycle/hash, 2.513 cycle/byte, 1.194 Gb/s @3GHz t1ha0_32le : 18.28 cycle/hash, 2.612 cycle/byte, 1.149 Gb/s @3GHz t1ha0_32be : 20.24 cycle/hash, 2.892 cycle/byte, 1.037 Gb/s @3GHz xxhash64 : 22.17 cycle/hash, 3.167 cycle/byte, 0.947 Gb/s @3GHz t1ha2_atonce128* : 29.93 cycle/hash, 4.277 cycle/byte, 0.701 Gb/s @3GHz t1ha2_stream* : 79.81 cycle/hash, 11.402 cycle/byte, 0.263 Gb/s @3GHz HighwayHash64_avx2 : 83.75 cycle/hash, 11.964 cycle/byte, 0.251 Gb/s @3GHz HighwayHash64_sse41 : 85.25 cycle/hash, 12.179 cycle/byte, 0.246 Gb/s @3GHz t1ha2_stream128* : 99.06 cycle/hash, 14.152 cycle/byte, 0.212 Gb/s @3GHz HighwayHash64_portable: 480.75 cycle/hash, 68.679 cycle/byte, 0.044 Gb/s @3GHz HighwayHash64_pure_c : 652.58 cycle/hash, 93.226 cycle/byte, 0.032 Gb/s @3GHz Bench for large keys (16384 bytes): t1ha0 : 1185.00 cycle/hash, 0.072 cycle/byte, 41.478 Gb/s @3GHz t1ha2_atonce : 3436.00 cycle/hash, 0.210 cycle/byte, 14.305 Gb/s @3GHz t1ha2_atonce128* : 3440.00 cycle/hash, 0.210 cycle/byte, 14.288 Gb/s @3GHz t1ha1_64le : 3449.00 cycle/hash, 0.211 cycle/byte, 14.251 Gb/s @3GHz t1ha2_stream* : 3479.00 cycle/hash, 0.212 cycle/byte, 14.128 Gb/s @3GHz t1ha2_stream128* : 3508.00 cycle/hash, 0.214 cycle/byte, 14.011 Gb/s @3GHz StadtX : 3550.00 cycle/hash, 0.217 cycle/byte, 13.846 Gb/s @3GHz xxhash64 : 4121.00 cycle/hash, 0.252 cycle/byte, 11.927 Gb/s @3GHz t1ha1_64be : 4567.00 cycle/hash, 0.279 cycle/byte, 10.762 Gb/s @3GHz HighwayHash64_avx2 : 4580.00 cycle/hash, 0.280 cycle/byte, 10.732 Gb/s @3GHz HighwayHash64_sse41 : 6412.00 cycle/hash, 0.391 cycle/byte, 7.666 Gb/s @3GHz t1ha0_32le : 7191.00 cycle/hash, 0.439 cycle/byte, 6.835 Gb/s @3GHz t1ha0_32be : 7928.00 cycle/hash, 0.484 cycle/byte, 6.200 Gb/s @3GHz xxhash32 : 8197.00 cycle/hash, 0.500 cycle/byte, 5.996 Gb/s @3GHz HighwayHash64_portable: 41895.27 cycle/hash, 2.557 cycle/byte, 1.173 Gb/s @3GHz HighwayHash64_pure_c : 53296.11 cycle/hash, 3.253 cycle/byte, 0.922 Gb/s @3GHz
Un poco sobre la estructura interna.Para ahondar un poco más en los detalles, t1ha se construye de acuerdo con el esquema Merkle-Damgård (versión "wipe-pipe") con el fortalecimiento del tamaño de los datos y el valor de la semilla. Dentro del bucle de compresión principal, se utiliza un estado de 256 bits, con el mismo tamaño del bloque de entrada. Además, para cada operando de datos hay dos puntos de inyección con polinización cruzada. Al finalizar el ciclo de compresión, el estado de 256 bits se comprime a 128 bits.
Al realizar las acciones anteriores, se utilizan operaciones de 64 bits, combinadas en los mezcladores ARX (Add-Rotate-Xor) y MUX / MRX (Mul-Rotate-Xor). Es importante que todos estos cálculos se construyan de tal manera que se garantice la posibilidad de ejecución paralela de la mayoría de las operaciones y el empaquetamiento estrecho de las operaciones u tanto en la tubería como en las unidades de ejecución x86_64. Debido a esto, se logra una calidad suficientemente buena con una tasa de hash casi máxima para claves largas.
Vale la pena señalar que el bucle de compresión se ejecuta solo para bloques de tamaño suficiente. Si hay menos datos, el estado intermedio de 128 bits consistirá solo en el tamaño de la clave y el valor de sal.
Luego, la cola restante de los datos se mezcla en porciones de 64 bits alternativamente a las mitades del estado de 128 bits. Finalmente, el estado se mezcla y se comprime simultáneamente a un resultado de 64 bits. Una característica importante de t1ha aquí es el uso de un mezclador basado en una multiplicación amplia (producto de 128 bits de dos multiplicadores de 64 bits). Esto permite una mezcla de buena calidad con un buen efecto de avalancha y menos operaciones. Aunque la multiplicación amplia es una operación relativamente costosa, menos operaciones de este tipo permiten que t1ha procese teclas cortas en un número de ciclos de procesador con un registro bajo.
Cabe señalar que el mezclador basado en multiplicación amplia y OR exclusivo no es perfecto. Aunque t1ha pasa todas las pruebas SMHasher , el autor comprende las consecuencias de la no inyectividad ). Sin embargo, la calidad resultante parece ser racionalmente suficiente, y los planes de desarrollo para la línea t1ha ya reflejan la intención de proporcionar opciones de calidad ligeramente superiores.
Puede encontrar más información y código fuente aquí .
Gracias por leer!