Блог

Я пишу простой каталогизатор MP3, чтобы отслеживать, какие MP3 есть на моих различных устройствах. Я планировал использовать ключи MD5 или SHA2 для идентификации соответствующих файлов, даже если они были переименованы / перемещены и т.д. Я не пытаюсь сопоставлять MP3, которые логически эквивалентны (т. Е. Одна и та же песня, но закодированная по-разному). У меня около 8000 MP3. Только около 6700 из них сгенерировали уникальные ключи.

Моя проблема в том, что я сталкиваюсь с коллизиями независимо от выбранного алгоритма хеширования. В одном случае у меня есть два файла, которые являются треками # 1 и # 2 в одном альбоме, они разного размера, но выдают одинаковые хэш-ключи, независимо от того, использую ли я MD5, SHA2-256, SHA2-512 и т.д…

Это первый раз, когда я действительно использую хэш-ключи для файлов, и это неожиданный результат. Я чувствую, что здесь происходит что-то подозрительное из того немногого, что я знаю об этих алгоритмах хеширования. Может ли это быть проблемой, связанной с реализацией MP3 или Python?

Вот фрагмент кода, который я использую:

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

    m = hashlib.md5(data)

    m.update(data)

    md5String = m.hexdigest()
  

Любые ответы или понимание того, почему это происходит, были бы высоко оценены. Заранее спасибо.

—ОБНОВИТЬ—:

Я попытался выполнить этот код в Linux (с Python 2.6), и это не привело к коллизии. Как продемонстрировано вызовом stat, файлы не совпадают. Я также загрузил WinMD5, и это не привело к коллизии (8d327ef3937437e0e5abbf6485c24bb3 и 9b2c66781cbe8c1be7d6a1447994430c). Является ли это ошибкой с Python hashlib в Windows? Я попробовал то же самое в Python 2.7.1 и 2.6.6, и оба дают одинаковый результат.

 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
  

У меня такое ощущение, что вы читаете фрагмент данных, который меньше ожидаемого, и этот фрагмент оказывается одинаковым для обоих файлов. Я не знаю почему, но попробуйте открыть файл в двоичном формате с помощью ‘rb’. read() должна читать до конца файла, но Windows ведет себя по-другому. Из документов

В Windows ‘b’, добавленный к режиму, открывает файл в двоичном режиме, поэтому существуют также такие режимы, как ‘rb’, ‘wb’ и ‘r b’. Python в Windows проводит различие между текстовыми и двоичными файлами; символы конца строки в текстовых файлах автоматически слегка изменяются при чтении или записи данных. Это скрытое изменение данных файла подходит для текстовых файлов ASCII, но оно приведет к повреждению двоичных данных, подобных тем, что в файлах JPEG или EXE. Будьте очень осторожны при использовании двоичного режима при чтении и записи таких файлов. В Unix не помешает добавить ‘b’ к режиму, чтобы вы могли использовать его независимо от платформы для всех двоичных файлов.

Файлы, с которыми у вас возникла проблема, почти наверняка идентичны, если несколько разных алгоритмов хеширования возвращают для них одинаковые результаты хэширования или в вашей реализации есть ошибка.

В качестве теста на работоспособность напишите свой собственный «хэш», который просто возвращает содержимое файла полностью, и посмотрите, генерирует ли он те же «хэши».

Как заявляли другие, столкновение одного хэша маловероятно, а нескольких почти невозможно, если только файлы не идентичны. Я бы рекомендовал генерировать суммы с помощью внешней утилиты в качестве чего-то вроде проверки работоспособности. Например, в Ubuntu (и большинстве / всех других дистрибутивах Linux):

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

Быстрый поиск в Google показывает, что для компьютеров с Windows доступны аналогичные утилиты. Если вы видите коллизии с внешними утилитами, то файлы идентичны. Если коллизий нет, вы делаете что-то неправильно. Я сомневаюсь, что реализация Python неверна, поскольку я получаю те же результаты при выполнении хэша в Python:

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

Как сказал @Delan Azabani, здесь есть что-то подозрительное; коллизии обязательно случаются, но не так часто. Проверьте, совпадают ли песни, и обновите свой пост, пожалуйста.

Кроме того, если вы чувствуете, что у вас недостаточно ключей, вы можете использовать два (или даже больше) алгоритма хеширования одновременно: например, используя MD5, у вас есть ключи 2**128 , или 340282366920938463463374607431768211456 . При использовании SHA-1 у вас есть ключи 2**160 или 1461501637330902918203684832716283019655932542976 . Объединив их, вы получите 2**128 * 2**160 , или 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056 .

(Но если вы спросите меня, MD5 более чем достаточно для ваших нужд.)