4

64fd54ad29 などの 16 進数文字を使用して、画像 URL を 10 文字の文字列にハッシュするプログラムに取り組んでいます。

これは Python で書かれており、ハッシュは次のように計算されます。

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

このような短いハッシュとの衝突が心配です。約 100 万回のハッシュ後に衝突を予想していましたが、ブルート フォースを実行すると 1,000 万回のハッシュが必要になりました。

計算

16 進数には 16 の可能な値、つまり 2^4 があります。10 文字の場合、2^40 の可能性、つまり 40 ビットのエントロピーがあります。

確率を 1 にするには、2^40 + 1 個の URL を確認する必要がありますが (ピジョンホールの原理により)、衝突はもっと早く発生すると予想されます。

n ビット ハッシュの誕生日攻撃 (つまりブルート フォース) は、2^(n/2) 回の試行後に衝突を検出します。したがって、約 2^20 の URL、つまり 1,048,576 の後に衝突が見られます。

ブルートフォース

URL の長いリストを反復処理し、各ハッシュを以前に見たものと比較する単純な Python スクリプトを作成しました。"http://c69025.r25.cf3.rackcdn.com/_image1/_Model/34897.jpg"最初の衝突を見つけるのに 10,800,000 個の URL が必要でした。"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

出力 (1 回実行):

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

明らかに、私のいわゆる URL はそうではありませんが、優れたハッシュ関数があれば違いはありません (SHA1 はこの目的に適しています)。SHA1 の最初の 5 バイトでの衝突率が異常に低いデータセットを見つけた場合は、成功です。最後の 5 バイトでもう一度試してください :-)

あなたはどれほど不運でしたか？ハッシュが 1000 万になるまでに、2**40スペースは 100k 分の 1 の割合でいっぱいになります。したがって、衝突しない確率はおおよそ (指が空中にある) であり(99999.0/100000) ** 10 million、これは3.7e-44です。したがって、私の数学が正しい場合 [編集: 正しくない場合、コメントを参照してください] あなたは天文学的に、合理的な疑いを超えて不運であると有罪判決を受けました。

偶然に衝突が発生しない確率の控えめな上限として、100 万回のハッシュが既に実行された後、900 万回の試行を行いました。衝突が発生しない確率は厳密に 未満で(999999.0 / 1000000) ** 9000000、わずか 0.0001 です。もう少し分割することで、そのような境界を小さくすることができます。900 万のハッシュを使用して 100 万回の試行を行いました。または、確率を正確に計算することもできます (これは CodesInChaos が行いました: 1e-20)

したがって、ベイジアン統計はそれが何であるかであり、コードのバグの可能性は、実際に大きな保守的な境界であっても、これらすべての数値よりも高いと思います:-)

于 2013-11-01T13:32:04.150 に答える