Python中的文件校验和

5
我正在创建一个与文件相关的应用程序。我正在寻找计算文件校验和的方法。基于以下标准,我想知道什么是计算文件校验和的最佳哈希方法,是MD5还是SHA-1或其他方法。
  • 校验和应该是唯一的。我知道这是理论上的,但我仍然希望碰撞的概率非常非常小。
  • 如果它们的校验和相等,则可以比较两个文件是否相等。
  • 速度(不是非常重要,但仍然需要考虑)
请尽可能详细地解释。

MD5在校验和方面表现出色...SHA-1也是如此...两者都具有非常小的碰撞概率,尽管我认为SHA-1的碰撞概率略微更小,因为它使用更多的位数。 - Joran Beasley
哪一个更快?如果两个文件具有相同的校验和,那么它们是否相等? - Saransh Mohapatra
1
你可以同时使用校验和(一个是MD5,一个是SHA1),两个都匹配但文件不同的可能性微乎其微(仍然不是100%不可能,但非常非常非常低)。通常情况下(也就是我遇到的每个情况中),只要MD5或SHA1匹配,就足以假定唯一性。 - Joran Beasley
谢谢。如果您能够请发布一个回答,说明所有这些都是更好的方式,那我可以批准它。 - Saransh Mohapatra
@JoranBeasley:检查MD5和SHA1实际上并没有太多的好处。你实际上是做了两倍的工作,而获得的额外好处不到1%。 - abarnert
显示剩余3条评论
4个回答

6

这取决于您的使用情况。

如果您只担心意外碰撞,那么MD5和SHA-1都可以,并且MD5通常更快。实际上,对于大多数用例而言,MD4也足够了,而且通常更快...但它没有被广泛实现。 (特别是它不在hashlib.algorithms_guaranteed中...尽管它应该在大多数股票Mac、Windows和Linux版本的hashlib_algorithms_available中。)

另一方面,如果您担心故意攻击-即有人有意地制作一个与您的哈希匹配的虚假文件-则必须考虑您所保护的价值。 MD4几乎肯定不足,MD5可能不足,但SHA-1接近边界。目前,Keccak(即将成为SHA-3)被认为是最好的选择,但您需要及时了解此事,因为每年都会发生变化。

密码哈希函数的维基百科页面有一张表格,通常会更新得相当频繁。要理解表格:

只需3轮即可生成针对MD4的碰撞,而MD5需要约200万轮,而SHA-1需要15万亿轮。这足以花费几百万美元(按今天的价格)来生成碰撞。这可能对您来说足够好,但对于NIST来说不够好。


此外,请记住,“一般更快”并不像“在我的数据和平台上测试更快”那样重要。考虑到这一点,在我的Mac上的64位Python 3.3.0中,我创建了一个1MB的随机bytes对象,然后执行了以下操作:

In [173]: md4 = hashlib.new('md4')
In [174]: md5 = hashlib.new('md5')
In [175]: sha1 = hashlib.new('sha1')
In [180]: %timeit md4.update(data)
1000 loops, best of 3: 1.54 ms per loop
In [181]: %timeit md5.update(data)
100 loops, best of 3: 2.52 ms per loop
In [182]: %timeit sha1.update(data)
100 loops, best of 3: 2.94 ms per loop

如你所见,md4 比其他算法明显更快。

测试使用 hashlib.md5() 而非 hashlib.new('md5'),以及使用熵较低的 bytes (由1-8个用空格隔开的 string.ascii_letters 运行组成)并没有显示出任何明显的差异。

对于我安装的哈希算法,如下测试结果表明另外的算法都无法超过 md4。

for x in hashlib.algorithms_available:
    h = hashlib.new(x)
    print(x, timeit.timeit(lambda: h.update(data), number=100))

如果速度非常重要,您可以使用一个差但非常快的哈希函数(例如zlib.adler32),仅对每个文件的前256KB应用它来改善速度。 (对于某些文件类型,最后256KB或最接近中间的256KB等可能比第一个更好)。然后,如果发生冲突,请为每个文件生成整个文件的MD4 / SHA-1 / Keccak /任何其他哈希值。
最后,由于有人在评论中询问如何哈希一个不需要将整个文件读入内存的文件:
def hash_file(path, algorithm='md5', bufsize=8192):
    h = hashlib.new(algorithm)
    with open(path, 'rb') as f:
        block = f.read(bufsize)
        if not block:
            break
        h.update(block)
    return h.digest()

如果追求最佳性能,您需要在您的平台上尝试不同的bufsize值(从4KB到8MB的2次幂)。您还可以尝试使用原始文件句柄(os.openos.read),这可能在某些平台上更快。

速度并不是非常重要,但也需要考虑。我已经决定使用SHA-1,因为我认为它在速度和安全性方面都有很好的平衡。你觉得这是一个好选择吗? - Saransh Mohapatra
我批准了你的答案,因为我发现它是最具解释性的。谢谢。 - Saransh Mohapatra
@SaranshMohapatra:嗯,我没有足够的信息来确定它是否是您用例的正确权衡……但它通常是一个不错的选择,这就是为什么它如此普遍,所以如果它对您来说是一个好选择,我肯定不会感到惊讶。 - abarnert
我希望你也能帮我解决另一个问题...请看一下,看看你能否提供帮助。http://stackoverflow.com/questions/16816815/authentication-in-android - Saransh Mohapatra
“如何在不将整个文件读入内存的情况下对文件进行哈希”编辑似乎缺少一个while循环,该循环继续读取直到文件完全被消耗。 - jdmcnair

2
拥有足够位数的哈希大小的碰撞可能性是非常小的,从理论上讲:假设哈希值随机且均匀分布,一个包含n个不同数据块和生成b位哈希函数,至少有一对碰撞的概率p由块对数乘以给定块对碰撞概率得出。因此,到目前为止,160位SHA-1碰撞尚未被观察到。假设有10^18字节的数据,每个块为8KB,则理论上发生碰撞的概率为10^-20,非常非常小。
一种有用的快捷方式是通过短路排除已知不同的文件。例如,大致步骤如下:
1. 读取所有感兴趣文件的前X块; 2. 将具有相同前X块哈希的文件视为可能相同的文件数据进行排序; 3. 对于每个具有唯一前X块的文件,您可以假设整个文件与所有其他测试文件都是唯一的--您不需要读取该文件的其余部分; 4. 对于剩余的文件,请继续读取更多块,直到证明签名相同或不同为止。
使用足够大小的X块,95%以上的文件将在第一遍正确地区分为唯一文件。这比盲目地读取每个文件的整个文件并计算完整哈希要快得多。

1

MD5通常用于校验和... SHA-1也是如此...两者都有非常小的碰撞概率,尽管我认为SHA-1的碰撞概率略微更小,因为它使用更多的比特

如果你真的很担心这个问题,你可以同时使用两个校验和(一个md5和一个sha1),两者都匹配但文件不同的概率是微乎其微的(仍然不是100%不可能,但非常非常非常不可能)...(这似乎是一种不好的方式,而且是最慢的解决方案)

通常情况下(读作:在我遇到的每一个实例中),MD5或SHA1的任意一个匹配就足以假定唯一性

除了逐字节比较之外,没有办法百分之百地保证唯一性


如果您可以假设没有人愿意花费14美元的计算机时间攻击您,那么MD5足以假定唯一性。如果没有任何人攻击您的理由,那就没问题了,但这已经非常接近某些无聊的14岁孩子为了好玩而值得付出的努力了... - abarnert
很好,我投了你的答案并且在我看来它是正确的,我之所以把它作为答案发布是因为OP从我的评论中要求这样做。但实际上,你的回答最好地概括了问题。 - Joran Beasley
我的评论并不意味着你的答案是错误的;它只是意味着在任何答案正确之前,OP必须定义他的用例... 如果攻击不是问题(或者它们是问题,但MD5提供足够的保护),那么一切都好。 - abarnert

0
我几天前创建了一个小型的重复文件删除脚本,它会读取文件内容并为其创建哈希值,然后与下一个文件进行比较,即使名称不同,校验和也将相同。
import hashlib
import os

hash_table = {}
dups = []
path = "C:\\images"
for img in os.path.listdir(path):
    img_path = os.path.join(path, img)
    _file = open(img_path, "rb")
    content = _file.read()
    _file.close()
    md5 = hashlib.md5(content)
    _hash = md5.hexdigest()

    if _hash in hash_table.keys():
        dups.append(img)
    else:
        hash_table[_hash] = img    

但是文件的校验和相同时,是否可以确定这些文件一定是相同的? - Saransh Mohapatra
如果文件的内容相同,那么它们就是重复的,这意味着它们将创建相同的校验和。 - abhishekgarg
@abhishekgarg 我并没有询问如何计算的方法,而是你已经写下来了。我只想告诉你,这是一种非常糟糕的计算校验和的方法,特别是当它是一个大文件时,因为你需要将整个文件读入内存中。如果你想知道更好的方法,请发一个问题,我可能会回答更好的方法。 - Saransh Mohapatra
@SaranshMohapatra,请告诉我更好的方法:),我一直乐于学习,我刚刚开始。 - abhishekgarg
@abhishekgarg:我已经更新了我的答案,展示了如何在不将整个文件读入内存的情况下对文件进行哈希处理。 - abarnert
显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接