¿Una alternativa más rápida a MD5?

Question

Estoy trabajando en un programa que busca unidades enteras para un archivo determinado. Por el momento, calculo un hash MD5 para el archivo conocido y luego escaneo todos los archivos recursivamente, buscando una coincidencia.

El único problema es que MD5 es extremadamente lento en archivos grandes. ¿Existe una alternativa más rápida que pueda usar, manteniendo una probabilidad muy pequeña de falsos positivos?

Todo el código está en C#.

Gracias.

actualización

He leído que incluso MD5 puede ser bastante rápido y que el disco E/S debería ser el factor limitante. Eso me lleva a creer que mi código podría no ser óptimo. ¿Hay algún problema con este enfoque?

 MD5 md5 = MD5.Create(); 
     StringBuilder sb = new StringBuilder(); 
     try 
     { 
      using (FileStream fs = File.Open(fileName, FileMode.Open, FileAccess.Read)) 
      { 
       foreach (byte b in md5.ComputeHash(fs)) 
        sb.Append(b.ToString("X2")); 
      } 
      return sb.ToString(); 
     } 
     catch (Exception) 
     { 
      return ""; 
     } 

Answer 1

Espero que esté buscando una coincidencia MD5 solo si el tamaño del archivo ya coincide.

Otra optimización es hacer una suma de comprobación rápida del primer 1K (o algún otro número arbitrario, pero razonablemente pequeño) y asegúrese de que coincidan antes de trabajar todo el archivo.

Por supuesto, todo esto supone que solo está buscando una decisión de coincidencia/nominación para un archivo en particular.

Answer 2

¿acaba de leer el archivo de forma lineal? Parece bastante inútil leer el archivo completo, calcular un hash md5 y luego comparar el hash.

Leer el archivo secuencialmente, unos pocos bytes a la vez, le permitiría descartar la gran mayoría de los archivos después de leer, digamos, 4 bytes. Y ahorrará todos los gastos generales de procesamiento al computar una función de hashing que no le da nada en su caso.

Si ya tenía los valores hash para todos los archivos en la unidad, tendría sentido compararlos, pero si tiene que calcularlos sobre la marcha, simplemente no parece haber ninguna ventaja para la hashing.

Me estoy perdiendo algo aquí? ¿Qué te compra hashing en este caso?

Answer 3

Primero considere cuál es realmente su cuello de botella: la función de hash en sí o más bien una velocidad de acceso al disco? Si está delimitado por un disco, cambiar el algoritmo hash no le dará mucho. Según su descripción, insinúo que siempre está escaneando todo el disco para encontrar una coincidencia: considere construir primero el índice y luego solo haga coincidir un hash dado con el índice, esto será mucho más rápido.

Answer 4

Hay un pequeño problema con el uso de MD5 para comparar los archivos: se conocen pares de archivos que se diferente, pero tienen la misma MD5.

Esto significa que puede utilizar MD5 para saber si los archivos son diferente (si el MD5 es diferente, los archivos deben ser diferentes), pero no puede utilizar MD5 para saber si los archivos son igual (si el los archivos son iguales, el MD5 debe ser el mismo, pero si el MD5 es igual, los archivos pueden ser iguales o no).

Debe utilizar una función hash que no se haya roto aún (como SHA-1) o (como se menciona en @SoapBox) usar MD5 solo como una forma rápida de encontrar candidatos para una comparación más profunda.

Referencias:

• http://www.win.tue.nl/hashclash/SoftIntCodeSign/

Answer 5

que sean las necesidades criptográficas, existe la posibilidad de una colisión de hash, así que no hay función hash puede ser utilizado para garantía de que los dos archivos son idénticos.

Hace un tiempo escribí un código similar el cual tuve que ejecutar bastante rápido indexando primero todos los archivos y descartándolos con un tamaño diferente. Luego se realizó una comparación rápida de hash (en una parte de cada archivo) en las entradas restantes (se comprobó que la comparación de bytes para este paso es menos útil; muchos tipos de archivos tienen encabezados comunes que tienen bytes idénticos al principio del archivo). Todos los archivos que quedaron después de esta etapa se verificaron utilizando MD5, y finalmente una comparación de bytes del archivo completo si el MD5 coincidía, solo para garantizar que el contenido fuera el mismo.

Answer 6

Uso MD5CryptoServiceProvider y BufferedStream

 using (FileStream stream = File.OpenRead(filePath)) 
     { 
      using (var bufferedStream = new BufferedStream(stream, 1024 * 32)) 
      { 
       var sha = new MD5CryptoServiceProvider(); 
       byte[] checksum = sha.ComputeHash(bufferedStream); 
       return BitConverter.ToString(checksum).Replace("-", String.Empty); 
      } 
     }