4

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

它是用 Python 编写的，哈希计算如下：

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,)

概括

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

4

1 回答 1

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空间已满大约 10 万分之一。所以没有碰撞的概率大致是（手指在空中），(99999.0/100000) ** 10 million即3.7e-44。因此，如果我的数学是正确的[编辑：不是，请参阅评论]，您在天文学上被定罪-超越-合理-怀疑是不幸的。

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

因此，贝叶斯统计就是这样，我认为您的代码中出现错误的概率高于所有这些数字，即使是非常大的保守界限:-)

于 2013-11-01T13:32:04.150 回答