¿Se puede usar CRC32 como función hash?

Question

¿Se puede utilizar CRC32 como función hash? ¿Algún inconveniente para este enfoque? ¿Alguna cancelación comercial?

Answer 1

CRC32 funciona muy bien como un algoritmo hash. El punto entero de un CRC consiste en hash una secuencia de bytes con el menor número posible de colisiones. Dicho esto, hay algunos puntos a considerar:

• CRC no son seguros. Para hash seguro, necesita un algoritmo mucho más computacionalmente costoso. Para un hasher de cubo simple, la seguridad generalmente no es un problema.

• Existen diferentes sabores CRC con diferentes propiedades. Asegúrese de utilizar el algoritmo correcto, p. con hash polinomial 0x11EDC6F41 (CRC32C) que es la elección óptima para propósitos generales.

• Como una compensación de velocidad/calidad hash, la instrucción x86 CRC32 es difícil de superar. Sin embargo, esta instrucción no existe en las CPU antiguas, así que ten cuidado con los problemas de portabilidad.

---- ---- EDITAR

Mark Adler proporciona un enlace a un artículo útil para la evaluación de hash por Bret Mulvey. Usando el código fuente provisto en el artículo, ejecuté la "prueba de cubo" para CRC32C y Jenkins96. Estas tablas muestran la probabilidad de que una distribución verdaderamente uniforme sea peor que el resultado medido solo por casualidad. Por lo tanto, números más altos son mejores. El autor consideró 0.05 o más bajo para ser débil y 0.01 o más bajo para ser muy débil. Confío completamente en el autor en todo esto y solo estoy informando los resultados.

Coloqué un * por todas las instancias donde CRC32C funcionó mejor que Jenkins96. Por este simple recuento, CRC32C era un hash más uniforme que Jenkins96 54 de 96 veces. Especialmente si puede utilizar la instrucción x86 CRC32, la compensación de rendimiento de velocidad es excelente.

 
CRC32C (0x1EDC6F41) 

     Uniform keys  Text keys   Sparse keys 

Bits Lower Upper  Lower Upper  Lower Upper 
1 0.671 *0.671 *1.000 0.120 *0.572 *0.572 
2 *0.706 *0.165 *0.729 *0.919  0.277 0.440 
3 *0.878 *0.879 *0.556 0.362 *0.535 *0.542 
4 0.573 0.332  0.433 0.462 *0.855 0.393 
5 0.023 *0.681  0.470 0.907  0.266 0.059 
6 *0.145 *0.523  0.354 *0.172 *0.336 0.588 
7 0.424 0.722  0.172 *0.736  0.184 *0.842 
8 *0.767 0.507 *0.533 0.437  0.337 0.321 
9 0.480 0.725 *0.753 *0.807 *0.618 0.025 
10 *0.719 0.161 *0.970 *0.740 *0.789 0.344 
11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003 
12 *0.979 *0.239 *0.709 0.786  0.171 *0.865 
13 *0.515 0.395  0.192 0.600  0.869 *0.238 
14 0.089 *0.609  0.055 *0.414 *0.286 *0.398 
15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300 
16 0.015 *0.946 *0.467 0.459  0.372 *0.793 

Y para Jenkins96, que el autor del artículo considera que es una excelente almohadilla:

 
Jenkins96 

     Uniform keys   Text keys   Sparse keys 

Bits Lower Upper  Lower Upper  Lower Upper 
1 0.888 0.572  0.090 0.322  0.090 0.203 
2 0.198 0.027  0.505 0.447  0.729 0.825 
3 0.444 0.510  0.360 0.444  0.467 0.540 
4 0.974 0.783  0.724 0.971  0.439 0.902 
5 0.308 0.383  0.686 0.940  0.424 0.119 
6 0.138 0.505  0.907 0.103  0.300 0.891 
7 0.710 0.956  0.202 0.407  0.792 0.506 
8 0.031 0.552  0.229 0.573  0.407 0.688 
9 0.682 0.990  0.276 0.075  0.269 0.543 
10 0.382 0.933  0.038 0.559  0.746 0.511 
11 0.043 0.918  0.101 0.290  0.584 0.822 
12 0.895 0.036  0.207 0.966  0.486 0.533 
13 0.290 0.872  0.902 0.934  0.877 0.155 
14 0.859 0.568  0.428 0.027  0.136 0.265 
15 0.290 0.420  0.915 0.465  0.532 0.059 
16 0.155 0.922  0.036 0.577  0.545 0.336 

Answer 2

Obviamente usted podría, pero no debería. Un crc32 distribuye pobremente los bits de entrada al hash. Además, ciertamente nunca debería usarse como un hash de un solo sentido, ya que no es uno. Es muy fácil modificar un mensaje para producir un crc dado.

Usa un algoritmo hash diseñado para el propósito que tienes en mente, sea lo que sea.

Answer 3

No sé qué Mark Adler dijo que "CRC32 mal distribuye los bits de entrada para discutir" . No hay un solo bit en el hash crc32 que sea exactamente igual a los bits de entrada. Cualquier bit del hash es una combinación lineal de los bits de entrada. En segundo lugar, crc siempre asigna el mismo número de secuencias de entrada a un valor hash determinado. Por ejemplo, si tiene un mensaje de 1000 bits de longitud, después de crc32, siempre puede encontrar 2^(1000-32) secuencias que producen un valor de hash dado, ni más ni menos.

Si no necesita la función de seguridad, crc puede servir como hash a la perfección.

En realidad, creo que otras funciones hash no seguras pueden ser más simples que crc, si necesita tener un crc más largo, por ejemplo crc-256.