String zum hash annähern

P

polle

0
Hallo Leute ich suche einen String der diesen Hash ergibt: "1307907743251498231" = 19 bit
Den Quellcode für den hash hab ich angefügt.
Code: 
def calculate_hash(input):
    h = 0;
    lenge = len(input);
    for element in xrange(lenge):
        h = 31 * h + ord(input[element]);
    return h;

Ich hab also ein bisschen rumexperimentiert und in einer Tabelle einige Werte verglichen, dabei ist mir aufgefallen, das man dieses Problem warscheinlich ohne Bruteforce lösen kann. Ich hab mal einige Strings angenähert die bis auf die 7 stelle genau passen.

Max hash: 1307908077598578441
'Max element: ', ('0', 'h', 'p', 'p', 'o', ' ', ' ', ' ', ' ', ' ', ' ', ' ')
Amar seed: 1307907743251498231
Min hash: 1307907695173242296
'Min element: ', ('0', 'h', 'p', 'p', '_', '_', '_', '_', '_', '_', '_', '_')

Was meint Ihr, wie komme ich auf den String?
 
Es lässt sich auch kürzer schreiben ;)
Code: 
def calculate_hash(input):
    h = 0;
    for element in input:
        h = h * 31 + ord(element)
    return h
oder gleich
Code: 
def calc_hash(input):
   return reduce(lambda x, y: x * 31 + ord(y), input,0)
Ansonsten ist 31 eine Primzahl ;) und "gross" genug.

D.h:
Es gibt insgesamt 256 mögliche Werte pro Zeichen. Da das (Hash - Zeichen) ein Vielfaches von 31 ergeben muss,
lässt sich das ziemlich einschränken.
Hash modulo 31 ergibt einen "Kandidaten" für eine Lösung
cand = hash % 31
mögl. Zeichen = cand +31 * x mit x = 0 .. 9.

Dies und die Tatsache, dass der Hashwert nicht "abgeschnitten" wird, schränken den Suchraum ziemlich ein.
Es lässt sich zumindest ein Bruteforcer schreiben, der alle Lösungen in annehmbarer Zeit findet - vor allem
wenn man davon ausgeht, dass die Zeichen "printable" sein sollten ;)

Code: 
>>> def clever_bf(x, solution, printable):
...   if x < 0:
...     return
...   elif x == 0:
...     res.append(solution)
...     return
...   for i in xrange(10):
...     candidate = (x % 31) + 31 * i
...     if candidate < 256 and (chr(candidate) in printable):
...       clever_bf((x-candidate) / 31, chr(candidate) + solution, printable)
...
>>> res = []
>>> my_chars = string.uppercase + string.lowercase + string.digits
>>> clever_bf(1307907743251498231, "", my_chars)
man sieht, es ist relativ hässlicher (da auf die schnelle in der Py-Console zusammengehackter) Code ;)

Ergebnisse:
Code: 
>>> len(res)
29160
>>> res[0]
'1K43C9FL9869'
>>> res[2]
'1JS3C9FL9869'
>>> calculate_hash(res[0])
1307907743251498231L
>>> calculate_hash(res[10])
1307907743251498231L
>>> res=[]
>>> clever_bf(1307907743251498231, "", string.uppercase)
>>> len(res)
0
>>> clever_bf(1307907743251498231, "", string.lowercase)
>>> len(res)
0
>>> clever_bf(1307907743251498231, "", string.lowercase+string.digits)
>>> len(res)
64
>>> res[0]
'0j42b8dk9869'
>>> clever_bf(1307907743251498231, "", string.printable)
>>> len(res)
332488
>>> res[0]
'0j42b8dk9869'
>>> res[1000]
'3\r42`wG-9869'
Edit: ok, man sollte eine Lösung nur dann akzeptieren, wenn x == 0 ist.
 
Zuletzt bearbeitet:
Sehr beindruckend, ich hätte nicht gedacht das jemand so schnell auf eine Lösung kommt. Die Annäherung hatte ja gezeigt das es sehr wahrscheinlich ein String mit 12 Zeichen sein muss.
Ehrlich gesagt bin ich noch dabei den Code zu verdauen wie kommst du auf
mögl. Zeichen = cand +31 * x mit x = 0 .. 9.
Zum Vergrößern anklicken....
mit x [0:9]

Wenn ich einen beliebigen String nehme mit a0**exp11+a**exp10 usw komme ich auch auf das Ergebnis, nur warum ist dein x [0:9], ich hätte ein x von [0:12] gewählt. Da aber deine Funktion auch mit einem x=4 richtige Ergebnisse auspuckt bin ich nun verwirrt.

Vielen Dank nochmals der Code ist sehr Lehrreich für mich.
Gruß polle
 
polle hat gesagt.:
Wenn ich einen beliebigen String nehme mit a0**exp11+a**exp10 usw komme ich auch auf das Ergebnis, nur warum ist dein x [0:9], ich hätte ein x von [0:12] gewählt. Da aber deine Funktion auch mit einem x=4 richtige Ergebnisse auspuckt bin ich nun verwirrt.
Zum Vergrößern anklicken....

Das mit x ist etwas anders gemeint ;)
Ich versuche nicht als Polynom zu betrachten, sondern den Hash "zurückzurechnen".

Wir haben ja sowas:
Code: 
h=0
for char in input:
  h = 31 * h + char
wir wissen also, es startet mit 0 und ganz zum Schluss
wird h * 31 + char => 'endgültiger Hash' gebildet.
bzw:
h' * 31 + val = h | mit h' = Vorgänger von h und h ist bekannt

Dabei:
h' * 31 + val = h
<=>
h - val = h' * 31
<=> (h - val) / 31 = h'
<=> h/31 - val/31 = h'
wäre val jetzt eine "normale" natürliche Zahl, hätten wir ein Problem.
Allerdings wissen wir, dass val ein ASCII Zeichen bzw. Byte ist mit einem Wertebereich [0..255]
Und wir wissen, dass alle h, h', h'' .. 0 ganzzahlig sind
d.h
h MOD 31 = "Überschuss/Rest" r
val kann also logisch betrachtet nur r, r+31, r+31*2, r+31*3 ... r+31*n
mit r + 31*n < 256 sein (da es sonst nicht mehr in 1 Byte passen würde)
(entspricht im vorherigen Post: cand + 31*x)
Wenn r = 0 ist, so müssen wir im Worstcase n = höchstens 256/31 = 9 betrachten.
Das sind die Kandidaten für ein mögliches Zeichen (insgesamt 10)

also h' = h - (r + 31*n mit n [0..9])
r2 = h' MOD 31
h'' = h' - (r2 + 31 * n)
...
0 = h''''' - (r_len + 31 * n)

Im Algo wird die BF-Funktion dann rekursiv für alle Kandidaten aufgerufen
Code: 
clever_bf((x-candidate) / 31, chr(candidate) + solution, printable)

Noch weiter lässt sich das ganze filtern, wenn man annimmt, dass es "printable" Zeichen sind (Pi mal Daumen 52+10+Sonderzeichen = 80)
Unser BF-Aufwand hängt zwar immer noch von der Länge ab, beträgt aber nicht
255**n bzw. 80**n
sondern
10**n bzw. 4**n (Pi * Daumen abgeschätzt, da ich k.A mehr habe, wie ich hier die tatsächliche Verteilung der printable ASCIIs berücksichtigen sollte ;) ).

Wobei der BF Algo zum einen den kompletten Lösungsraum ausgibt und zum anderen ziemlich naiv läuft.
Imho lässt der Hashalgo so viele Kollisionen zu, dass sich eine entsprechende Heuristik schreiben lassen sollte, die fast alles "zurückrechnet" und die verbliebenen paar Zeichen (entsprechen den ersten paar Zeichen der Eingabe) "bruteforced", so dass auch das erste Zeichen der Eingabe "printable" ist. Der Aufwand dürfte damit prinzipiell linear sein.
Als erste Annäherung sollte allerdings auch ausreichen, mit dem BF aufzuhören, sobald 1 gültige Lösung gefunden wurde ;)

Es wird nur eine gültigige Lösung gesucht, zudem ein paar kleine Verbesserungen ("printable" ist nun ein Set)
Code: 
def bf(h, printable):
  sol = [-1] * 100
  printable = set([ord(c) for c in printable])
  def clever_bf(x, pos):
    if x <= 0:
      return x == 0
    for i in xrange(10):
      cand = (x % 31) + 31 * i
      if cand < 256 and (cand in printable):
        sol[pos] = cand
        if clever_bf((x - cand) / 31, pos + 1):
          return True
        else:
          sol[pos] = -1
  if clever_bf(h, 0):
    sol.reverse()
    return "".join([chr(c) for c in sol if c > -1])
  else:
    return False
Ergebniss:
Code: 
>>> bf(calculate_hash("hello world"),string.whitespace + string.lowercase)
'hello world'
>>> bf(calculate_hash("hello world!!!"),string.whitespace + string.lowercase + "
!")
'hello world!!!'

>>> my_hash = calculate_hash("Dies ist ein sehr, sehr, sehr langer String mit Zi
ffern wie 1234 und Sonderzeichen wie #+*?!!!")
>>> my_hash
35556568747689965062184182482200606326093544760258595625537817781575584879958533
1028559580563414543150846414664344675922344579100214600209641L
>>> bf(my_hash, string.letters)
False
>>> bf(my_hash, string.letters + string.digits)
False
>>> bf(my_hash, string.printable)
'F.\n5"-76#\n-0"8\x0b\r5\r"8\x0b\r5\r"8\x0b\r4"0%3\r\n4!686-3\n"1-6!=.\x0c\x0c\n
60";-\' 1234"92&!633\n\n7 \n-\'-\n0";-\' $\r\x0c !!!'
>>> res  = bf(my_hash, string.printable)
>>> calculate_hash(res) == my_hash
True
oder mit "Cheaten" ;)
Code: 
>>> res=bf(my_hash, string.lowercase + "SZD" "1234" + " #+*?!,")
>>> calculate_hash(res) == my_hash
True
>>> res
'Dies ist g+n sg,4, sg,4, sg,4 n#ngg4!4tt+ng o+t Ziffg4n!Z+e 1234 und!4ondg4zg+e
*en!Z+e #++ !!!'


>>> my_hash2 = calculate_hash("ein ganz ganz ganz langer lowercase string ganz o
hne sonderzeichen oder irgendwelche ziffern")
>>> my_hash2
54080644461340822033881698311321011355761689153298963774209277012631699053380030
0168894940793376079768388790977474245952905555539664238695L
>>> bf(my_hash2,string.lowercase + " ")
'ein ganz ganz ganz langer lowercase string ganz ohne sonderzeichen oder irgendw
elche ziffern'
Wobei der Zeitaufwand für "bruteforcing" kaum messbar ist ;)

Edit/PS: der Java-Hash Algo (der hier scheinbar zugrunde liegt ;) ) nutzt im übrigen keine "unlimited" Zahlen (wodurch die Zahl immer im 32 bzw. 64 bit Bereich verbleibt).
Eine Kollision sollte sich zwar immer noch recht Problemlos finden, allerdings ist es kein Crypto-Hashverfahren, sondern nur eins für eine ausreichend
eindeutige Zuordnung String -> Zahl. Wird für Stringpools/Associative Arrays/HasMaps/Dicts usw. genutzt.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben