Wie kann ich eine Kollision für eine Spielzeug-Hash-Funktion finden?

Question

Ich möchte eine Kollision für eine einfache Hash-Funktion unter (Python) finden:

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 

hier ist auch eine js Implementierung in jsbin

ich this question on SO gefunden habe, aber die Antwort war nicht da für mich nachvollziehbar.

Die Länge der Ausgabe der Funktion ist immer gleich 8 a, b, c und d Variablen ganze Zahlen sind, die in Hex-Werte in Ende umgewandelt werden die resultierende Hash zu bilden, dh 123 -> 7b, 46 -> 2e, 13 -> 0d und bald.

---

Könnten Sie mir helfen, eine Kollision für diese Funktion zu finden?

Answer 1

Eine einfache Möglichkeit, Strings mit dem gleichen Hash zu finden, besteht darin, zufällige Strings zu generieren, diese zu hashen und die Ergebnisse in einem dict zu speichern, wobei der Hash als Schlüssel und der String als Wert verwendet wird. Wenn Sie einen Hash erhalten, der bereits in der dict ist, drucken Sie es.

Ich habe Ihre hash_function leicht optimiert und den Code Python 2/3 kompatibel gemacht.

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 

Ausgang

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