para - tipos de funciones hash

La forma más rápida de calcular hash de archivos?

Question

Se almacenarán una gran cantidad de archivos en la base de datos y necesito hashes de archivos para identificar de manera única que el archivo no se modificó. (En general, se usará como la parte de Windows Personal Firewall)

Answer 1

Esto es, por supuesto, no es posible en general. Muchas personas todavía usan hashing para este propósito, y MD5 es un algoritmo popular, que le da una "firma" de 128 bits para el archivo con una alta probabilidad de cambiar cuando cambia el contenido del archivo.

En el caso general, necesita ver cada bit del archivo para incluirlo en el hash, y el rendimiento probablemente será limitado por E / S. Se trata de un barrido secuencial de todos los datos del archivo, actualizando el estado del algoritmo hash que utilice para cada nuevo byte. En una CPU moderna, esta última será más rápida que la anterior. Este análisis bastante antiguo muestra alrededor de ~ 45 MB / s en una CPU Pentium de 90 MHz.

Answer 2

Si entiendo bien la parte "usado como Firewall personal de Windows", MD5 no es una buena opción como algoritmo.

Existe un ataque exitoso al algoritmo MD5 que le permite encontrar un mensaje diferente que produce el mismo hash con relativamente poco trabajo (en comparación con la fuerza bruta). Ese ataque solía no tener una influencia real, por ejemplo, cuando se usaba MD5 para cifrar contraseñas o cosas por el estilo. Mientras tanto, se han encontrado nuevos ataques, por lo que tanto MD5 como SHA-1 pueden mezclarse / colisionar a velocidades aterradoras, y descifrar bases de datos completas de contraseñas de usuario "correctamente salados" y de un solo hash con estos hashes "antiguos" no es solo completamente factible pero ya ha sido demostrado.
Sin embargo, en la aplicación particular de "asegúrese de que este archivo no haya sido alterado" , este tipo de ataque siempre ha sido un problema, no solo recientemente. MD5 detectará de forma bastante segura un error de bit o una modificación accidental, pero un malware que intente eludir su muro de archivos personal podría evitar trivialmente toda su seguridad encontrando una colisión para el binario infectado para que el hash coincida con el original.

Deberías usar SHA-256 para este caso [ Actualización: mientras tanto, SHA-3 está fuera, y aunque personalmente no estoy de acuerdo con la elección del NIST de un ganador (o los criterios oscuros para descartar una muy buena ronda 2) candidatos), es una opción mucho más segura usar SHA-3 (Keccak) o alternativamente uno de los finalistas de SHA-3. Todos los finalistas han sido cuidadosamente diseñados por equipos experimentados, han sido muy minuciosamente analizados, y hasta ahora ninguno tiene un ataque realista o un problema conocido que podría conducir a un ataque realista, y todos tienen "más bits" también ( que en sí mismo no significa mucho, pero más bits no duelen)].

Además, recuerde siempre guardar la longitud del archivo además de un hash, esto endurece considerablemente incluso un hash pobre a un costo descuidable. Si puede, calcule dos hashes diferentes. Es mucho más fácil para un atacante encontrar algún mensaje que produce una colisión en un hash que encontrar un mensaje que produce una colisión y que tiene exactamente la misma longitud, o incluso un mensaje que colisiona en dos hash diferentes y tiene la misma longitud .
Como el ancho de banda (tanto el disco como la memoria) es un factor no despreciable al calcular un hash, incluso es posible que el cálculo de un solo hash o dos hashes se ejecute simultáneamente a una velocidad comparable.
He observado tal efecto al calcular un CRC y encriptar los mismos bloques con un cifrado de bloque luego. Si el CRC se calculó o no hizo menos del 1% de diferencia en el tiempo de ejecución general, por lo que era básicamente una operación gratuita.

Si cree que tiene una buena razón para no usar un hash estándar conocido (¿limitaciones de rendimiento?), Podría construir su propio hash seguro. Usando el constructo Merkle-Damgård (o más recientemente, HAIFA), puede convertir cualquier cifrado de bloque seguro en una función segura de hash. Por ejemplo, encripte cada bloque de entrada con AES usando una clave fija y xor la salida al siguiente bloque antes de cifrarlo también. La salida después del último bloque es su valor hash.

Si bien "construir uno propio" generalmente no es una buena idea, puede haber razones válidas en este caso, ya que AES es rápido y está soportado en hardware en los procesadores más recientes. En mi máquina, AES funciona a aproximadamente 130MB / s. En un i7 (que tiene soporte de hardware) se informa alrededor de 570MB / s en Internet.

En cuanto a la limitación de E / S, el desenrollado es correcto, el disco puede ser el factor limitante, aunque no necesariamente. El mapeo de memoria es tu amigo, especialmente en tu caso particular.

Si revisa los archivos que solicitan derechos en el firewall, esos serán ejecutables que se han cargado en la RAM (¿cómo podría ser diferente, se están ejecutando después de todo!). Por lo tanto, mapear las páginas que ya están en la RAM simplemente agregará una entrada a la tabla de páginas, más o menos una no operativa. E incluso si los datos no están en la memoria RAM, el rendimiento (y la facilidad) de la asignación de memoria es francamente impresionante, rara vez uso otra cosa en estos días cuando la velocidad es una preocupación.