1

以下の単純なハッシュ関数の衝突を見つけたい(python):

def hash_function(s=''):   # 'Hello World!' -> 7b2ea1ba
    a, b, c, d = 0xa0, 0xb1, 0x11, 0x4d
    result_hash = ''

    for byte in bytes(s, 'ascii'):
        a ^= byte
        b = b ^ a ^ 0x55
        c = b ^ 0x94
        d = c ^ byte ^ 0x74

    for i in [d, c, a, b]:
        tmp = str(hex(i))[2:]
        result_hash += tmp if len(tmp) is 2 else '0' + tmp

    return result_hash

ここにもjsbinの js 実装があります

SO でこの質問を見つけましたが、そこの答えは私にはあまり理解できませんでした。

関数の出力の長さは常に 8 です。a、b、cおよびd変数は整数であり、最終的に 16 進数値に変換されて結果のハッシュが形成されます (つまり123 -> 7b、46 -> 2e、13 -> 0dなど)。

それで、その関数の衝突を見つけるのを手伝ってくれませんか?

4

1 に答える 1

1

同じハッシュを持つ文字列のペアを見つける簡単な方法は、ランダムな文字列を生成し、それらをハッシュしdictて、ハッシュをキーとして、文字列を値として使用して、結果を に格納することです。にすでにあるハッシュを取得した場合はdict、それを出力します。

少し最適化してhash_function、コードを Python 2 / 3 互換にしました。

from __future__ import print_function
from random import choice, randrange, seed 

def hash_function(s=''):   # 'Hello World!' -> 7b2ea1ba
    a, b, c, d = 0xa0, 0xb1, 0x11, 0x4d

    for byte in bytearray(s):
        a ^= byte
        b = b ^ a ^ 0x55
        c = b ^ 0x94
        d = c ^ byte ^ 0x74

    return format(d<<24 | c<<16 | a<<8 | b, '08x') 

s = b'Hello World!'
print(s, hash_function(s))

#ASCII chars that print nicely
ascii = b''.join([chr(i) for i in range(33, 127)])

seed(37)

found = {}
for j in range(5000):
    #Build a random 4 byte random string
    s = b''.join([choice(ascii) for _ in range(4)])
    h = hash_function(s)
    if h in found:
        v = found[h]
        if v == s:
            #Same hash, but from the same source string
            continue
        print(h, found[h], s)
    found[h] = s

出力

Hello World! 7b2ea1ba
0944dbd0 TXN9 YXC9
105a9dce wA5> rA0>
7a29e4bd %+m' -+e'
7776b2e2 u&4u n&/u
7c3ea3aa D-\6 z-b6
6d46d1d2 `<r_ "<0_
6a26e0b2 ;;x8 ";a8
1033eda7 ,AwW =AfW
627395e7 #3@e ;3Xe
7d6ee7fa D,Hg `,lg
3c2bb2bf NmRc Cm_c
1e31b9a5 nOc[ oOb[
1a49f7dd MKv' ]Kf'
161beb8f )G\y IG<y
0247bbd3 !SX1 VS/1
于 2016-04-12T12:07:13.967 に答える