python - 如何计算我需要多少哈希值才能找到冲突？

Question

我正在开发一个程序，该程序使用十六进制字符将图像 URL 散列为 10 个字符的字符串，例如64fd54ad29.

它是用Python写的，hash是这样计算的:

def hash_short(self, url):
     return hashlib.sha1(url).hexdigest()[:10]

我担心与如此短的哈希值发生冲突。我预计在大约 100 万次哈希后会发生碰撞，但当我运行蛮力时我需要 1000 万次哈希。

计算

一个十六进制数字有 16 个可能的值，即 2^4。对于十个字符，我有 2^40 种可能性，或 40 位熵。

要获得 1 的概率，我们需要查看 2^40 + 1 个 URL(根据鸽巢原理)，但我们预计会更快发生冲突。

n 位哈希的生日攻击(即暴力破解)将在 2^(n/2) 次尝试后发现冲突。因此，我们将在大约 2^20 个 URL(即 1,048,576 个)后看到冲突。

暴力破解

我编写了一个简单的 Python 脚本，该脚本遍历一长串 URL，并将每个哈希值与我之前看到的哈希值进行比较。我花了 10,800,000 个 URL 才找到我的第一个碰撞:"http://c69025.r25.cf3.rackcdn.com/_image1/_Model/34897.jpg" 和 "http://media.editd.com/assets/matrix/full/72f9a997b67c65c66f4adc769ee0a127d1db25eb.jpg" 均散列为 "ba2be44bd1"。

import hashlib
import json

def calculate_short_hash(url):
    return hashlib.sha1(url).hexdigest()[:10]


def url_from_json(json_string):
    return json.loads(json_string)['image_url']

if __name__ == '__main__':
    short_hashes = set()

    for i, line in enumerate(open('urls.all')):
        short_hash = calculate_short_hash(url_from_json(line))

        if short_hash in short_hashes:
            print "Already seen: %s" % short_hash
            break
        else:
            short_hashes.add(short_hash)

        if i % 100000 == 0:
            print "Processed %d lines" % (i,)

总结

要么我的数学不正确，要么我很不走运。是哪个？我有多倒霉？

Answer 1

我认为你的碰撞检测代码是错误的:

import hashlib
import random
import string

def hash_short(url):
     return hashlib.sha1(url).hexdigest()[:10]

hashes = dict()
while True:
    if len(hashes) % 10000 == 0:
        print len(hashes)
    newurl = ''.join(random.choice(string.lowercase) for _ in xrange(30))
    newhash = hash_short(newurl)
    if newhash in hashes and newurl != hashes[newhash]:
        print 'found a collision!'
        print newhash
        print newurl
        print hashes[newhash]
        print len(hashes)
        break
    hashes[newhash] = newurl

输出(运行一次):

...
770000
780000
found a collision!
216be03ec7
txnbkwrfkpkmiexloxrifdsnjumkex
xlnmlhobtsswjvmqnjupaybkspptpo
780758

显然我所谓的 url 不是，但是应该与良好的哈希函数没有区别(SHA1 非常适合此目的)。如果您发现一个数据集在 SHA1 的前 5 个字节上确实具有异常低的冲突率，那么干得好!用最后 5 个字节再试一次:-)

你有多倒霉？当您拥有 1000 万个哈希值时，您的 2**40 空间已满大约 100k 分之一。所以没有碰撞的概率大概是(手指在空中)，(99999.0/100000) ** 1000万，也就是3.7e-44。因此，如果我的数学是正确的 [编辑:事实并非如此，请参阅评论] 从天文数字上看，您被定罪了，这无疑是不幸的。

作为不会偶然发生碰撞的概率的保守上限，您在已经有 100 万个哈希值后进行了 900 万次试验。不发生碰撞的概率严格小于(999999.0/1000000) ** 9000000，仅为0.0001。您可以通过进一步拆分来产生更小的边界:您进行了 100 万次试验，占用了 900 万个哈希值。或者您可以精确计算概率(CodesInChaos 所做的:1e-20)

所以，贝叶斯统计就是这样，我认为您的代码中出现错误的可能性高于所有这些数字，甚至是非常大的保守界限 :-)