如何找到玩具哈希函數的碰撞？

我想找到下面一個簡單的散列函數（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

這裏也是一個js實現in jsbin

我發現this question on SO，但得到的答覆有沒有對我來說很容易理解。

的函數的輸出的長度始終等於8 a，b，c和d變量是被轉換成十六進制值的末端以形成所得到的散列整數，即123 -> 7b，46 -> 2e，13 -> 0d和等等。

那麼，你能幫我找到這個功能的碰撞嗎？

來源

2016-04-12 Denis Yakovenko

結果空間是32位，並且存在生日悖論，所以窮舉它不應該是可能的。 –

查找具有相同散列值的字符串對的一種簡單方法是生成隨機字符串，將它們散列並將結果存儲在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 #[email protected] ;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-12 12:07:13

如何找到玩具哈希函數的碰撞？

回答

相關問題