Python中的MD5和SHA-2碰撞

Question

我正在写一个简单的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）。这是不是Windows上Python hashlib的一个bug？我在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

Answer 1

正如其他人所说，单个哈希碰撞的可能性很小，而多个碰撞几乎是不可能的，除非这些文件完全相同。我建议使用外部工具来生成哈希值，作为一种检查方法。例如，在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'

Answer 2

你遇到问题的文件几乎可以肯定是一样的，如果多个不同的哈希算法对它们的结果都返回相同的哈希值，或者你的实现可能有bug。

作为一个简单的测试，你可以自己写一个“哈希”函数，直接返回文件的全部内容，看看这个函数生成的“哈希”值是否也一样。

Answer 3

我感觉你可能在读取一个比预期要小的数据块，而且这个数据块在两个文件中恰好是一样的。我不知道具体原因，但你可以试着用'b'来以二进制模式打开文件。read()应该是读取到文件的末尾，但在Windows上表现得有点不同。从文档中可以看到：

在Windows上，模式后面加上'b'会以二进制模式打开文件，所以还有像'rb'、'wb'和'r+b'这样的模式。Python在Windows上区分文本文件和二进制文件；在读取或写入文本文件时，行结束符会被自动稍微修改。这种在后台对文件数据的修改对于ASCII文本文件是没问题的，但会破坏像JPEG或EXE文件这样的二进制数据。所以在读取和写入这些文件时，一定要小心使用二进制模式。在Unix系统上，加上'b'也没什么坏处，所以你可以在所有二进制文件中无论在哪个平台都使用它。