¿Se puede construir una función hash "buena" usando CRC32C como base?

intel sse

Question

Dado que SSE 4.2 (piezas Intel Core i7 y i5) incluye una instrucción CRC32, parece razonable investigar si se puede construir una función hash de propósito general más rápida. De acuerdo con this solo 16 bits de un CRC32 están distribuidos uniformemente. Entonces, ¿qué otra transformación se aplicaría para superar eso?

Actualización ¿Qué tal esto? Solo 16 bits son adecuados para un valor hash. Multa. Si su tabla es 65535 o menos, entonces genial. De lo contrario, ejecute el valor CRC a través de la instrucción Nehalem POPCNT (recuento de población) para obtener la cantidad de bits configurados. Luego, utilícelo como un índice en una matriz de tablas. Esto funciona si su tabla está al sur de entradas de 1 mm. Apuesto a que es más barato / rápido que las funciones hash de mejor rendimiento. Ahora que GCC 4.5 tiene un CRC32 intrínseco, debería ser fácil de probar ... si solo tuviera el copioso tiempo libre para trabajar en él.

David

Answer 1

Para fines criptográficos, CRC32 es una mala base porque es lineal (sobre el espacio vectorial GF (2) ^ 32 ) y eso es difícil de corregir. Puede funcionar para fines no criptográficos.

Sin embargo, los núcleos recientes de Intel tienen las instrucciones AES-NI , que básicamente realizan una décima parte de un cifrado de bloques AES en dos ciclos de reloj. Están disponibles en los procesadores i5 e i7 más recientes (consulte la página de Wikipedia para obtener más información). Esto parece un buen comienzo para construir una función hash criptográfica (y una función hash que es buena para la criptografía también servirá para cualquier otra cosa).

De hecho, al menos uno de los candidatos SHA-3 "ronda 2" (la función hash ECHO ) se basa en los elementos AES para que los códigos de operación AES-NI proporcionen un aumento sustancial en el rendimiento. (Desafortunadamente, en ausencia de instrucción AES-NI, el rendimiento de ECHO es algo desagradable).

Answer 2

Siempre y cuando no estés buscando hash criptográfico, podría funcionar.

Answer 3

El artículo al que se hace referencia en otras respuestas saca conclusiones incorrectas basadas en el código buggy crc32. El algoritmo de clasificación de Google aún no se basa en la precisión científica.

Contrario al referido artículo this , las conclusiones CRC32 y CRC32C son aceptables para el uso de la tabla hash . El código de muestra del autor tiene un error en la generación de la tabla crc32. La reparación de la tabla crc32 proporciona resultados satisfactorios con la misma metodología. Además, la velocidad de la instrucción CRC32 la convierte en la mejor opción en muchos contextos. El código que utiliza la instrucción CRC32 es 16 veces más rápido en el pico que una implementación de software óptima. (Tenga en cuenta que CRC32 no es exactamente lo mismo que CRC32C que implementa la instrucción Intel).

CRC32 obviamente no es adecuado para el uso criptográfico. (32 bits es una broma a la fuerza bruta).

Answer 4

Revisado , agosto de 2014
Impulsado por Arnaud Bouchez en un comentario reciente, y en vista de otras respuestas y comentarios, reconozco que la respuesta original debe ser alterada o para los menos calificados. Dejé el original tal como está, al final, como referencia.

Primero, y quizás lo más importante, una respuesta justa a la pregunta depende del uso previsto del código hash : ¿Qué quiere decir "buena" [función hash ...]? ¿Dónde / cómo se usará el hash? (por ejemplo, ¿es para hash una clave de entrada relativamente corta? ¿Es para fines de indexación / búsqueda, para producir resúmenes de mensajes u otros usos? ¿Cuánto tiempo es el código hash deseado en sí, los 32 bits [de CRC32 o sus derivados], más bits, menos ... etc?
El OP cuestiona las solicitudes de " una función hash de propósito general más rápida ", por lo que el foco está en SPEED (algo menos intensivo de CPU y / o algo que puede hacer uso de un procesamiento paralelo de diversa naturaleza). Podemos observar aquí que el tiempo de cálculo para el código hash a menudo es solo una parte del problema en una aplicación de hash (por ejemplo, si el tamaño del código hash o sus características intrínsecas resultan en muchas colisiones que requieren ciclos adicionales para ser tratados con). Además, el requisito de "propósito general" deja muchas preguntas en cuanto a los posibles usos.

Con esto en mente, una respuesta corta y mejor es, tal vez:

Sí , las implementaciones de hardware de CRC32C en procesadores Intel más nuevos se pueden usar para construir códigos hash más rápidos; Sin embargo, tenga en cuenta que, dependiendo de la implementación específica del hash y de su aplicación, los resultados globales pueden ser subóptimos debido a la frecuencia de las colisiones, a la necesidad de usar códigos más largos. También, con seguridad, los usos criptográficos del hash deben ser cuidadosamente investigados porque el algoritmo CRC32 en sí mismo es muy débil en este aspecto.

La respuesta original citaba un artículo sobre la evaluación de las funciones hash de Bret Mulvey y, como se señala en la respuesta de Mdlg, la conclusión de este artículo es errónea en lo que respecta a CRC32 ya que la implementación de CRC32 se basaba en fallos / imperfecciones. A pesar de este gran error con respecto a CRC32, el artículo proporciona una guía útil en cuanto a las propiedades de los algoritmos de hash en general. La URL de este artículo está ahora extinta; Lo encontré en el archive.today pero no sé si el autor lo tiene en otra ubicación y también si lo actualizó.

Otras respuestas aquí citan CityHash 1.0 como ejemplo de una biblioteca hash que usa CRC32C. Aparentemente, esto se usa en el contexto de algunos códigos hash más largos (de 32 bits) pero no para la función CityHash32 () misma. Además, el uso de CRC32 por las funciones City Hash es relativamente pequeño, en comparación con todas las operaciones de cambio y arrastramiento y otras operaciones que se realizan para producir el código hash. (Esta no es una crítica de CityHash para la cual no tengo experiencia práctica. Voy a dar un paso, a partir de una revisión superficial del código fuente que las funciones de CityHash producen bien, por ejemplo, códigos distribuidos, pero no son significativamente más rápidas que varias otras funciones hash).

Finalmente, también puede encontrar información sobre este tema en una pregunta cuasi duplicada sobre SO .

Respuesta original y edición (abril de 2010)

A priori , ¡ esto suena como una mala idea! .

CRC32 no se diseñó con fines hash, y es probable que su distribución no sea uniforme, por lo que es un código hash relativamente pobre. Además, su poder de "cifrado" es relativamente débil, lo que lo convierte en un hash unidireccional muy pobre, como se usaría en aplicaciones criptográficas.

[BRB: Estoy buscando referencias en línea para ese efecto ...]

El primer hit de [palabras clave = distribución CRC32] de Google parece confirmar esto:
this

Editar : La página citada anteriormente, y de hecho el artículo completo proporciona una buena base de lo que debe buscar en las funciones Hash .
Leyendo [rápidamente] este artículo, confirmó la afirmación general de que, en general, CRC32 no debería usarse como un hash, sin embargo, y dependiendo del propósito específico del hash, puede ser posible usar, al menos en parte, un CRC32 como un código hash

Por ejemplo, los 16 bits inferiores (o superiores, según la implementación) del código CRC32 tienen una distribución relativamente uniforme, y, siempre que no se trate de las propiedades criptográficas del código hash (es decir, por ejemplo, el hecho de que claves similares producen códigos muy similares), es posible construir un código hash que utiliza, por ejemplo, una concatenación de los 16 bits inferiores [o superiores] para dos códigos CRC32 producidos con las dos mitades (o cualquier división) de la clave original.
Uno necesitaría ejecutar pruebas para ver si la eficiencia de la instrucción CRC32 incorporada, relativa a una función hash alternativa, sería tal que la sobrecarga de llamar a la instrucción dos veces y empalmar el código, etc., no daría como resultado una función general más lenta.

Answer 5

Sí. CityHash 1.0.1 incluye algunas nuevas "buenas funciones hash" que usan instrucciones CRC32.