[HaBo]

polle · 13.12.11, 20:53

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?

**CDW** · 13.12.11, 22:06

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.

Anzeige

- Anzeige -

polle · 14.12.11, 00:13

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

Zitat:

mögl. Zeichen = cand +31 * x mit x = 0 .. 9.

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

**CDW** · 14.12.11, 01:36

Zitat:

Zitat von polle

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.

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

eine mögiche Version

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.

Anzeige

- Anzeige -

13.12.11, 20:53	#1 (permalink)
polle Registriert seit: 26.04.11 Likes: 0	String zum hash annähern Anzeige 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?

13.12.11, 22:06	#2 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 202	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. polle likes this. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt. Geändert von CDW (13.12.11 um 22:18 Uhr) Grund: korrigiert

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Unbekannter String/Hash	Vafthrudnir	Cryptography & Encryption	6	30.09.11 23:32
Was für ein hash?	-Tux-	Cryptography & Encryption	3	10.02.09 08:33
[C/C++] MD5 Hash von String	Nimda05	Code Kitchen	9	31.05.07 22:24
Was ist das für ein Hash ?	Cylence	Cryptography & Encryption	3	10.05.07 21:31
SAM Hash	master_tux	Windows	2	19.03.06 20:43

[HaBo]

String zum hash annähern