我该如何计算需要多少哈希才能找到碰撞？

Question

我该如何计算需要多少哈希才能找到碰撞？

4

我正在开发一个程序，将图像URL哈希为一个由十六进制字符组成的10个字符的字符串，例如64fd54ad29。

这个程序是用Python编写的，哈希值的计算方式如下：

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

我对使用如此短的哈希值存在碰撞问题感到担忧。我预计在大约一百万次哈希后会发生碰撞，但当我进行暴力破解时，我需要进行十万次哈希才发生了碰撞。

计算：

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

要达到概率为1，我们需要查看2^40 + 1个URL（根据鸽巢原理），但我们预计会更早发生碰撞。

一个n位哈希的生日攻击（即暴力破解）将在2^(n/2)次尝试后找到碰撞。因此，我们预计在大约2^20个URL后会看到碰撞，即1,048,576个URL。

暴力破解：

我编写了一个简单的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,)

摘要

我的数学可能有误，也可能是我非常不幸。到底是哪一个？我有多么不幸？

- Wilfred Hughes

1

你尝试过多少次？ - aIKid

你的代码有误。以10^-20的概率来说，只需要那么长时间。 - CodesInChaos

@alKid 我只搜索了一次碰撞，但我使用的是程序中实际的URL。 - Wilfred Hughes

@CodesInChaos，我已经添加了代码。这是相当简单的东西，我没有看到任何明显的错误。 - Wilfred Hughes

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Jessop · Accepted Answer

我认为你的碰撞检测代码有问题：

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并不是真正的URL，但是对于一个好的哈希函数来说（SHA1就是这个目的），这应该没有任何影响。如果你发现了一个数据集，在SHA1的前5个字节上真正具有异常低的碰撞率，那么干得好！再用后5个字节试一次 :-)

你有多倒霉？当你拥有1000万个哈希值时，你的2 ** 40空间大约填满了10万分之一。因此，没有碰撞的概率大约为（手指在空中比划）（99999.0 / 100000）** 10000000 ，即3.7e-44。因此，如果我的数学计算正确[编辑：它不正确，请参见评论]，你是天文数字般的、无可置疑的不幸。

作为无碰撞概率的保守上限，当已经有100万个哈希在运行后，您进行了900万次试验。没有碰撞的概率严格小于(999999.0 / 1000000) ** 9000000，仅为0.0001。您可以通过进一步分割来产生更小的边界：您使用900万个哈希进行了100万次试验。或者您可以精确计算概率（CodesInChaos已经这样做：1e-20）。

因此，由于贝叶斯统计学的特性，我认为您的代码中存在错误的概率比所有这些数字都要高，即使是非常大的保守上限 :-)