Столкновения MD5 и SHA-2 в Python - PullRequest
Новая
       45

Столкновения MD5 и SHA-2 в Python

7 голосов
/ 26 апреля 2011

Я пишу простой каталогизатор 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), и он не вызвал коллизию. Как показывает статистика, файлы не совпадают. Я также скачал 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

Ответы [ 4 ]

8 голосов
/ 26 апреля 2011

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

В Windows 'b' добавляется в режим открывает файл в двоичном режиме, поэтому Есть также такие режимы, как «RB», «WB», и 'r + b'. Python на Windows делает различие между текстом и двоичным файлы; символы конца строки в текстовые файлы автоматически изменяются немного, когда данные читаются или пишутся. Это закулисное изменение данные файла подходят для текста ASCII файлы, но это повредит двоичные данные как это в файлах JPEG или EXE. Быть очень осторожно использовать двоичный режим, когда чтение и запись таких файлов. На Unix, не больно добавлять 'b' в режим, так что вы можете использовать его независимо от платформы для всех двоичных файлов файлы.

2 голосов
/ 26 апреля 2011

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

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

1 голос
/ 26 апреля 2011

Как уже заявляли другие, одно столкновение хешей маловероятно, а множественное почти невозможно, если только файлы не идентичны. Я бы порекомендовал генерировать суммы с помощью внешней утилиты для проверки работоспособности. Например, в 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'
0 голосов
/ 26 апреля 2011

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

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

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

...