¿Cuáles son algunos de los mejores algoritmos hash para usar para la deduplicación y la integridad de datos?

Question

Estoy tratando de hash una gran cantidad de archivos con datos binarios dentro de ellos para: (1) comprobar si hay daños en el futuro, y (2) eliminar archivos duplicados (que pueden tener nombres completamente diferentes y otros metadatos).

Conozco md5 y sha1 y sus familiares, pero tengo entendido que estos están diseñados para la seguridad y, por lo tanto, son deliberadamente lentos para reducir la eficacia de los ataques de fuerza bruta. Por el contrario, quiero algoritmos que corran lo más rápido posible, mientras reduzco las colisiones tanto como sea posible.

¿Alguna sugerencia?

Answer 1

Usted es el más correcto. Si su sistema no tiene ningún adversario, el uso de funciones hash criptográficas es excesivo debido a sus propiedades de seguridad.

---

colisiones dependen del número de bits , b, de su función hash y el número de valores de troceo , N, se estiman de calcular. La literatura académica defiende que esta probabilidad de colisión debe ser inferior a la probabilidad de error de hardware, por lo que es menos probable que se produzca una colisión con una función hash que comparar datos byte por byte [ref1, ref2, ref3, ref4, ref5]. La probabilidad de error de hardware está en el rango de 2^-12 y 2^-15 [ref6]. Si esperas para generar N = 2^q valores hash entonces su probabilidad de colisión puede ser dada por esta ecuación, que ya tiene en cuenta la birthday paradox:

El número de bits de la función hash es directamente proporcional a su complejidad computacional. Por lo tanto, le interesa encontrar una función hash con los bits mínimos posibles, a la vez que puede mantener la probabilidad de colisión a valores aceptables.

---

He aquí un ejemplo de cómo hacer que el análisis:

• Digamos que usted tiene f = 2^15 archivos;
• El tamaño medio de cada archivo lf es 2^20 bytes;
• Finge dividir cada archivo en fragmentos de tamaño medio lc igual a 2^10 bytes;

• Cada archivo se dividirá en c = lf/lc = 2^10 trozos;

• A continuación, hash q = f * c = 2^25 objetos.

De esa ecuación la probabilidad de colisión para varios tamaños de hash es la siguiente:

• P (de hash = 64 bits) = 2^(2 * 25-64 + 1) = 2^-13 (menor que 2^-12)
• P (hash = 128 bits) = 2^(2 * 25-128 + 1) 2^-77 (mucho menos que 2^-12)

Ahora solo tiene que decidir qué función hash no criptográfica de 64 o 128 bits que usará, saber que 64 bits es bastante cercano a la probabilidad de error de hardware (pero será más rápido) y 128 bits es una opción mucho más segura (aunque más lenta).

---

A continuación puede encontrar una pequeña lista eliminada de la wikipedia de las funciones hash no criptográficas. Sé Murmurhash3 y es mucho más rápido que cualquier función hash criptográfica:

1. Fowler–Noll–Vo: 32, 64, 128, 256, 512 y 1024 bits
2. Jenkins: 64 y 128 bits
3. MurmurHash: 32, 64, 128 y 160 bits
4. CityHash: 64, 128 y 256 bits

Answer 2

MD5 y SHA1 no están diseñados para la seguridad, no, por lo que no son particularmente seguros, y por lo tanto, tampoco son muy lentos. He usado MD5 para la deduplicación (con Python) y el rendimiento fue bueno.

This article máquinas de reclamaciones hoy pueden calcular el hash MD5 de 330 MB de datos por segundo.

SHA-1 se desarrolló como una alternativa más segura a MD5 cuando se descubrió que se podían crear entradas que harían hash al mismo valor con MD5, pero creo que para sus propósitos MD5 funcionará bien. Ciertamente lo hizo por mí.

Answer 3

Si la seguridad no es una preocupación para usted puede tomar una de las funciones hash seguras y r educir el número de rondas. Esto hace que la criptografía sea poco sólida, pero aún perfecta para la prueba de igualdad.

Skein es muy fuerte. Tiene 80 rondas. Intenta reducir a 10 o menos.

O encripte con AES y XOR los bloques de salida juntos. AES es acelerado por hardware en CPUs modernas e increíblemente rápido.