colisiones MD5 y SHA-2 en Python

Question

Estoy escribiendo un simple catalogador de MP3 para mantener un registro de los MP3 que hay en mis diversos dispositivos. Estaba planeando usar claves MD5 o SHA2 para identificar los archivos coincidentes, incluso si se han renombrado/movido, etc. No estoy tratando de hacer coincidir los MP3 que son lógicamente equivalentes (es decir, la misma canción pero codificada de manera diferente). Tengo alrededor de 8000 MP3. Solo alrededor de 6700 de ellos generaron claves únicas.

Mi problema es que me encuentro con colisiones independientemente del algoritmo hash que elijo. En un caso, tengo dos archivos que pasan a ser las pistas n. ° 1 y n. ° 2 en el mismo álbum, tienen diferentes tamaños de archivo y producen claves hash idénticas si utilizo MD5, SHA2-256, SHA2-512, etc.

Esta es la primera vez que realmente uso claves hash en los archivos y este es un resultado inesperado. Siento que algo sospechoso está pasando aquí por lo poco que sé sobre estos algoritmos de hash. ¿Podría ser este un problema relacionado con la implementación de MP3 o Python?

Aquí está el fragmento de código que estoy usando:

data = open(path, 'r').read() 

    m = hashlib.md5(data) 

    m.update(data) 

    md5String = m.hexdigest() 

Cualquier respuesta o reflexión, a qué está sucediendo esto sería muy apreciada. Gracias por adelantado.

--UPDATE--:

Me trataron de ejecutar este código en Linux (con Python 2.6) y no produjo una colisión. Como lo demuestra la llamada stat, los archivos no son lo mismo. También descargué WinMD5 y esto no produjo una colisión (8d327ef3937437e0e5abbf6485c24bb3 y 9b2c66781cbe8c1be7d6a1447994430c). ¿Es esto un error con Python hashlib en Windows? Intenté lo mismo en Python 2.7.1 y 2.6.6 y ambos proporcionan el mismo resultado.

import hashlib 
import os 

def createMD5(path): 

    fh = open(path, 'r') 
    data = fh.read() 
    m = hashlib.md5(data) 
    md5String = m.hexdigest() 
    fh.close() 
    return md5String 

print os.stat(path1) 
print os.stat(path2) 
print createMD5(path1) 
print createMD5(path2) 

>>> nt.stat_result(st_mode=33206, st_ino=0L, st_dev=0, st_nlink=0, st_uid=0, st_gid=0, st_size=6617216L, st_atime=1303808346L, st_mtime=1167098073L, st_ctime=1290222341L) 
>>> nt.stat_result(st_mode=33206, st_ino=0L, st_dev=0, st_nlink=0, st_uid=0, st_gid=0, st_size=4921346L, st_atime=1303808348L, st_mtime=1167098076L, st_ctime=1290222341L) 
>>> a7a10146b241cddff031eb03bd572d96 
>>> a7a10146b241cddff031eb03bd572d96 

Answer 1

en cierto modo me tiene la sensación de que se está leyendo un fragmento de datos que es menor que la esperada, y este trozo pasa a ser el mismo para ambos archivos. No sé por qué, pero intente abrir el archivo en binario con 'rb'. read() debería leer hasta el final del archivo, pero windows se comporta de manera diferente. A partir de los documentos

En Windows, 'B' anexa al modo abre el archivo en modo binario, por lo también hay modos como 'rb', 'wb', y 'r + b'. Python en Windows hace una distinción entre archivos de texto y binarios ; los caracteres de fin de línea en los archivos de texto se modifican automáticamente cuando se leen o escriben los datos. Esta modificación entre bastidores de los datos de archivo está bien para los archivos de texto ASCII , pero dañará los datos binarios de esa manera en los archivos JPEG o EXE. Sea tenga mucho cuidado al usar el modo binario cuando lea y escriba dichos archivos. En Unix, no está de más añadir una 'b' al modo, por lo que puede usarla plataforma independientemente para todos los archivos binarios .

Answer 2

Los archivos que está teniendo un problema con idénticos son casi con toda seguridad si varios diferentes algoritmos hash todos los mismos resultados de hash sobre ellos, o hay un error en su aplicación.

Como prueba de cordura, escriba su propio "hash" que simplemente devuelve los contenidos del archivo por completo, y vea si este genera los mismos "hash".

Answer 3

Me gusta @Delan Azabani dijo, hay algo sospechoso aquí; las colisiones están destinadas a suceder, pero no tan a menudo. Compruebe si las canciones son las mismas y actualice su publicación, por favor.

Además, si considera que no tiene suficientes claves, puede usar dos (o incluso más) algoritmos hash al mismo tiempo: utilizando MD5 por ejemplo, tiene 2**128, o claves. Al usar SHA-1, tiene las claves 2**160 o 1461501637330902918203684832716283019655932542976. Al combinarlos, tiene 2**128 * 2**160 o 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056.

(Pero si me preguntas, MD5 es más que suficiente para sus necesidades.)

Answer 4

Como otros han dicho, una sola colisión de hash es poco probable, y múltiple casi imposible, a menos que los archivos son idénticos. Yo recomendaría generar las sumas con una utilidad externa como una especie de control de cordura. Por ejemplo, en Ubuntu (y la mayoría de todas las otras distribuciones de Linux /):

blair@blair-eeepc:~$ md5sum Bandwagon.mp3 
b87cbc2c17cd46789cb3a3c51a350557 Bandwagon.mp3 
blair@blair-eeepc:~$ sha256sum Bandwagon.mp3 
b909b027271b4c3a918ec19fc85602233a4c5f418e8456648c426403526e7bc0 Bandwagon.mp3 

Una rápida búsqueda en Google muestra que hay utilidades similares para máquinas Windows. Si ve las colisiones con las utilidades externas, entonces los archivos son idénticos.Si no hay colisiones, estás haciendo algo mal. Dudo que la implementación de Python está mal, como consiga los mismos resultados cuando se hace el hash en Python:

>>> import hashlib 
>>> hashlib.md5(open('Bandwagon.mp3', 'r').read()).hexdigest() 
'b87cbc2c17cd46789cb3a3c51a350557' 
>>> hashlib.sha256(open('Bandwagon.mp3', 'r').read()).hexdigest() 
'b909b027271b4c3a918ec19fc85602233a4c5f418e8456648c426403526e7bc0'