[HaBo]

Frosch2006

Anzeige

Ich hab da ma ne frage...
eig. läuft soweit alles, aber hab dennoch eine frage... ich habe vor ne Rainbowtable zu erstellen soweit alles klärchen... allerdings habe ich jetzt vor die arbeit auf verschiedene rechner zu verteilen (soweit ist das ja alles kein problem aber wie muss ich den Syntax schreiben?....) KEIN CLUSTER!


rtgen md5 spezial 1 10 "hier weiß ich net was hier hin muss" 3400 33554432 0
(ich habe mir schon sämtliche sachen durchgelesen aber ich blick des system noch nicht so ganz (tabellendefinition))

http://project-rainbowcrack.com/

rtgen lm alpha-numeric 1 7 0 5400 40000000 #0
rtgen lm alpha-numeric 1 7 0 5400 40000000 #1
rtgen lm alpha-numeric 1 7 0 5400 40000000 #2
rtgen lm alpha-numeric 1 7 0 5400 40000000 #3
rtgen lm alpha-numeric 1 7 0 5400 40000000 #4

rtgen lm alpha-numeric 1 7 1 5400 40000000 #0
rtgen lm alpha-numeric 1 7 1 5400 40000000 #1
rtgen lm alpha-numeric 1 7 1 5400 40000000 #2
rtgen lm alpha-numeric 1 7 1 5400 40000000 #3
rtgen lm alpha-numeric 1 7 1 5400 40000000 #4

rtgen lm alpha-numeric 1 7 2 5400 40000000 #0
rtgen lm alpha-numeric 1 7 2 5400 40000000 #1
rtgen lm alpha-numeric 1 7 2 5400 40000000 #2
rtgen lm alpha-numeric 1 7 2 5400 40000000 #3
rtgen lm alpha-numeric 1 7 2 5400 40000000 #4

rtgen lm alpha-numeric 1 7 3 5400 40000000 #0
rtgen lm alpha-numeric 1 7 3 5400 40000000 #1
rtgen lm alpha-numeric 1 7 3 5400 40000000 #2
rtgen lm alpha-numeric 1 7 3 5400 40000000 #3
rtgen lm alpha-numeric 1 7 3 5400 40000000 #4

rtgen lm alpha-numeric 1 7 4 5400 40000000 #0
rtgen lm alpha-numeric 1 7 4 5400 40000000 #1
rtgen lm alpha-numeric 1 7 4 5400 40000000 #2
rtgen lm alpha-numeric 1 7 4 5400 40000000 #3
rtgen lm alpha-numeric 1 7 4 5400 40000000 #4

Jetzt wäre jeder Rainbow Table in 5 Teile gespalten und wieviel Rainbow Tables haben wir (ganze)? Richtig 5! Insgesamt hätten wir 25 Teile!

Table1 = 5 Dateien
Table2 = 5 Dateien
Table3 = 5 Dateien
Table4 = 5 Dateien
Table5 = 5 Dateien

Sind das 5 mal die selben Tables?


Also es werden für table 1
5 Dateien erstellt die jeweils 700MB haben?

rtgen lm alpha-numeric 1 7 0 5400 40000000 #0
rtgen lm alpha-numeric 1 7 0 5400 40000000 #1
rtgen lm alpha-numeric 1 7 0 5400 40000000 #2
rtgen lm alpha-numeric 1 7 0 5400 40000000 #3
rtgen lm alpha-numeric 1 7 0 5400 40000000 #4

Table 2 hat auch 5 Dateien à 700MB (hat Table 2 den selben inhalt wie table 1? woher weiß die table wo sie weiter macht ohne die selben einträge zu erstellen...)

rtgen lm alpha-numeric 1 7 2 5400 40000000 #0
rtgen lm alpha-numeric 1 7 2 5400 40000000 #1
rtgen lm alpha-numeric 1 7 2 5400 40000000 #2
rtgen lm alpha-numeric 1 7 2 5400 40000000 #3
rtgen lm alpha-numeric 1 7 2 5400 40000000 #4

Ich hoffe jemand kennt sich damit aus...


Frosc)-(

Elderan

Hallo,
nein, alle Tabellen sind unterschiedlich.

Es gibt nette Artikel die das Prinzip von Rainbow-Tables erklärt. Ich hab hier im Forum mal welche gepostet, sonst evt. bei Wikipedia anfangen.

"woher weiß die table wo sie weiter macht ohne die selben einträge zu erstellen..."
Gar nicht. Die Rainbow-Tables enthalten zufällige Startwerte, die dann gehasht werden. Der Hashwert wird wieder auf ein Passwort abgebildet. Dieses wird dann wieder gehast. Das passiert z.B. mehrere tausend mal und das Ergebnis wird abgespeichert.

Somit überschneiden sich alle Tabellen in bestimmten Bereichen, aber eben nicht vollständig.
Ebenso kann man mit Rainbow-Tables nicht jedes Passwort knacken, sondern man hat meist nur ne Chance von z.B. 98%.

Frosch2006

THHHHHHHXXXX wenn du wüsstest wie lang ich schon nach der antwort gesucht habe die du mir grad gegeben hast ICH LIEBE DICH :-D nee scherz ich glaub ich habs jetzt verstanden...

Die seite die du meinst kenn ich :-)^^


Also Rechner 1...
Generiert mir 5 mal 700mb Dateien
Das wäre Table 1

Rechner 30...
Generiert mir 5 mal 700mb Dateien
Das wäre Table 30...

(rtsort sotiert mir die Tables inwie fern?! toll wäre wenn er doppelte einträge löschen würd macht er das?)

wie kann ich ungefair rausbekommen wie lang das dauert bis die table fertig ist?


Frosc)-(

GrafZahl

für rtgen mag das stimmen, ist aber nicht allgemeingültig für rainbowtables

wenn man eine abbildung erzeugen kann, die den gesammten ergebnisraum überlappungsfrei partitioniert, und die tabellen auf diese weise aufbaut, wäre das ergebnis eine anzahl überlappungsfreier rainbowtables ... das problem liegt in der erzeugung einer solchen abbildung, und ist keinesfalls trivial ... mir ist keine solche abbildung für aktuelle hashfunktionen bekannt ... aber ausschließen kann man die möglichkeit nicht ...

nachtrag:
rtsort sortiert die ketten(enden) aus denen die tabelle besteht ... das ist prinzipiell sinnvoll weil du anschließend darin suchen willst ... die suche nach einem namen in einem telefonbuch ist deutlich einfacher wenn das telefonbuch alphabetisch sortiert ist, und nicht nach telefonnummer ...

wie lange es dauert bis eine tabelle fertig ist, hängt essenziel von der verfügbaren systemleistung ab ... unter der vorraussetzung gleichbleibender verfügbarer rechenleistung, unter vernachlässigung von I/O-Operationen, und der annahme, dass alle reduktionsfunktionen gleich lang dauern kann man sagen:

(zeit für die berechnung eines hashwerts + zeit für eine reduktion)* ketten länge * anzahl der ketten pro tabelle

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

Frosch2006

zunächst ersteinmal danke....

habe da aber noch eine frage...
wieso steht bei rtgen hash length 16 anstatt 32?! (MD5)




Uploaded with ImageShack.us



Frosc)-(

Elderan

Hallo,
weil md5 nunmal Hash-Werte mit 128 Bit erzeugt, was 16 Byte erzeugt.

Was du ansprichst ist die Hexadezimal-Repräsentation einen Hashwertes, welcher aus 32 Zeichen besteht.

Nachtrag:
Eine einzelne Abbildung würde nicht reichen, denn es lässt sich ja sowohl die Chain-Länge als auch das verwendete Alphabet beliebig einstellen.
Sofern man diese Werte nicht fixieren möchte, müsste man sogar eine entsprechende parameterisierte Abbildung besitzen, welche zu finden nochmal erheblich schwieriger ist.

Das komplizierte ist eigentlich, den Hashwert wieder zurück zur Menge möglicher Passwörter abzubilden, denn diese ist im vergleich erheblich kleiner womit Kollisionen wahrscheinlich werden.
Und setzt man eine sichere Hashfunktion voraus, dann ist eine solche Funktion zu finden fast unmöglich.

GrafZahl

dass die abbildung parametrisiert ist, stellt keine wirkliche hürde dar...

es existiert immer eine triviale abbildung auf den schlüsselraum der durch das alphabet sowie die länge des klartextes vorgegeben ist:

dabei stellt die alphabetgröße die zahlenbasis dar, und die zeichen des alphabets die ziffern der zahlenbasis. die maximale länge führt zur oberen schranke ...

Bsp:
das alphabet "ABC" mit einer länge von 5 führt zur Basis 3 mit
A=0; B=1; C=2;
^ ist der exponential operator

A*3^4+A*3^3+A*3^2+A*3^1+A*3^0 = 0 = AAAAA
A*3^4+A*3^3+A*3^2+A*3^1+B*3^0 = 1 = AAAAB
...
C*3^4+C*3^3+C*3^2+C*3^1+C*3^0 = 236 = CCCCC

in dem so dargestellten endlichen schlüsselraum herscht eine totale ordnung, weswegen eine partitionierung in beliebig viele teile (bis zur oberen schranke) trivial ist.

somit kann man die parameter bezüglich des schlüsselraums getrost abharken.

die kettenlänge allerdings ist da schon nicht mehr trivial:

die partitionierung schreibt vor, dass alle elemente der kette in der partition liegen müssen, ansonsten könnte der 2. wert einer kette in partition A der startwert einer kette in partition B sein, was zu einer partitionsüberlappung führt.

aber auch hierfür gibt es lösungen:

es bedarf je partition einer abbildung vom schlüsselraum ausserhalb der partition auf die partition. eine solche abbildung existiert zwangsläufig, da der schlüsselraum endlich ist und eine totale ordnung besitzt. beispielsweise kann man für jedes element einer partition seinen relativen index in der partition bestimmen, und das element der fremdpartition auf das element aus der eigenen partition abbilden, dass den gleichen relativen index hat.

unter der annahme, dass die haschfunktion einer gleichverteilung folgt, sollte sich die kollisionschance nicht geändert haben

kollisionen von ketten lassen sich somit zwar nicht verhindern, aber immerhin kollisionen von partitionen (sprich tabellen)

aber ich gebe dir recht, dass die abbildung in den schlüsselraum immer zu kollisionen führen wird, solange der schlüsselraum kleiner ist, als der ergebnisraum der hashfunktion ... daran kann keine abbildung der welt etwas ändern ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

Elderan

Hallo,
Leider nicht.

Eine Chain ist im Grunde h(f(h(f(h(startwert))))), wobei h meine Hashfunktion ist und f die Funktion, die einen Hashwert wieder zurück in die Menge möglicher Passwörter abbildet. Wobei natürlich h und f natürlich viel öfter angewendet werden.

Das Problem ist nun, dass man h(f(x)) berechnet. Da f(x) von den Parametern des Schlüsselraumes abhängt (also verwendete Buchstaben und Passwortlänge), ist somit auch der Hashwert h(f(x)) von diesen Parametern abhänig. Denn der Hashwert von 'aaa' ist unterschiedlich zu dem von 'AAA'.
Somit könnte h(f(x)) und h(f(y)) mit dem Alphabet 'ABC' zur Kollision bei der Hashfunktionen führen, wärend es mit dem Alphabet 'abc' keine Kollision gäbe (x ungleich y). Diese Chance ist wahrlich klein, da ist die Wahrscheinlichkeit bei f(h(f(x)) und f(h(f(y)) deutlich größer, dass das Alphabet 'ABC' eine Kollision erzeugt während es bei 'abc' keine Kollsion gibt (Kollision im Sinne von f(h(f(x)) == f(h(f(y)) für x != y).

GrafZahl

im wesentlichen läuft dies auf den unterschied zwischen h('aaa') und h('AAA') hinaus

du vergleichst allerdings hier die kollisionschancen zweier verschiedener alphabete. genauer: die kollisionschance der abbildung h(m1)==h(n1) mit m1,n1 element M1 gegen die kollisionschance h(m2)==h(n2) mit m2,n2 element M2 ...

grundannahme für alle "guten" hashfunktionen sollte gleichverteilung sein...

folglich hast du für die elemente jeder Teilmenge T1 von M1 die gleiche Kollisionswahrscheinlichkeit wie für die elemente jeder gleichgroßen Teilmenge T2 von M2 ...

wenn nun die abbildung f() keine häufungspunkte im schlüsselraum hat, wie soll das zu einer änderung der kollisionswahrscheinlichkeit führen?

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

Elderan

Gar nicht.

Es ging mir nur um darum zu ergänzen, dass es eigentlich unmöglich ist für eine halbwegs vernünftige Hashfunktion eine Abbildung zu finden, bei der es garantiert keine Überlappung in den Chains gibt und mit der man den gesamten Schlüsselraum abdecken kann.

Denn diese Funktion muss zusätzlich noch mit den Parametern des Schlüsselraums und mit der Chain-Länge paramterisiert werden.

GrafZahl

sagen wir es so ... wenn man eine solche abbildung einfach finden könnte, die sicherstellt, dass es innerhalb aller chains zu keinen kollisionen kommt, hätte man vermutlich keine kryptografisch einsetzbare hashfunktion vor sich ...

betrachtet man das ideal einer hashfunktion, dann sollte eine eingabe menge die von ihrer größe dem ergebnisraum entspricht bijektiv abgebildet werden können ...

bezogen auf reale hashfunktionen muss man sich allerdings damit begnügen, dass diese bijektivität nur für eine möglichst große teilmenge des ursprungsraumes gilt.

"dummer" weise ist der ursprungsraum für texte aller art quasi unendlich, die bildmenge der hashfunktion aber aus praktischen gründen endlich ... dies alleine begründed schon kollisionen von chains ... selbst bei einer idealen hashfunktion

das bedeutet zwar, dass man bei genügender kenntnis der abbildung der hashfunktion eine abbildung erzeugen kann, die kollisionsfreie chains erlaubt, sofern der schlüsselraum kleiner oder maximal gleich groß ist wie der ergebnisraum, allerdings ist dies nicht für jeden schlüsselraum möglich, da die abbildung den schlüsselraum nicht verlassen darf und es erwiesener maßen schlüsselräume gibt, die kollisionsbehaftete teilmengen enthalten.

mit anderen worten: eine derartige abbildung, ob parametrisiert oder nicht, existiert nicht für alle schlüsselräume

für die schlüsselräume für die sie existiert, ist die berechnung einer solchen abbildung vermutlich NP vollständig, da die hashfunktion eine pseudo zufällige abbildung ist für die (zumindest im fall kryptografischer hashfunktionen) als designkriterium NP-vollständigkeit für die kollisions-suche gefordert wird. daraus folgt dass zumindest der test ob eine solche abbildung existiert, also der gewählte ursprungsraum kollisionsfrei ist, ein NP-vollständiges problem ist...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

Elderan

Hallo,
Das finden einer Kollision sollte auf alle Fälle in NP \ P liegen (sofern NP !=P), damit die Hashfunktion sicher ist.

Es gibt Hash-Funktionen, bei denen die Kollisionssuche NP-vollständig ist (sogenannte beweisbar sichere Hashalgorithmen wie z.B. FSB), allerdings sind diese zu ineffizient und finden somit kaum/keine praktische Anwendung. Für SHA-1 und SHA-2 gibt es diesen Beweis der NP-Vollständigkeit nicht und wird es vermutlich auch nie geben. Unter den SHA-3 Semi-Finalisten ist ebenfalls kein Hashalgorithmus mit dabei, der NP-Vollständigkeit verspricht bzw. sogar beweist. Dies ist auch vom NIST nicht explizit gefordert worden.

Aber selbst wenn die Sicherheit einer Hashfunktion NP-Vollständig ist, lässt sich daraus nicht schließen dass diese Hashfunktion dann auch wirklich sicher ist. Viele NP-Vollständige Probleme sind nur im Worst-Case-Fall wirklich in NP und für (teilweise) große Untermengen in P bzw. leicht lösbar. Ein Beispiel wäre 2-SAT, welches eine Untermenge von SAT ist, nur dass ebenen 2-SAT sehr leicht lösbar ist während allgemeines SAT eben NP-vollständig ist.

Das bedeutet für eine beweisbare sichere Hashfunktion, die sich auf ein NP-vollständiges Problem reduzieren lässt, dass es bestimmte Nachrichtenmengen (bzw. Teilmengen des Nachrichtenraumes/Definitionsraumes) gibt, für die es sehr einfach ist ein Urbild (Preimage) zu finden.
Kryptographische Hashfunktionen dürfen solch eine Schwäche nicht besitzen. Egal wie der Eingaberaum aussieht / definiert ist, es muss weiterhin faktisch unmöglich sein das Urbild zu finden (natürlich stets under der Voraussetzung, dass der Eingaberaum eine ausreichende Größe besitzt). Dies ist bei beweisbar sicheren Hashalgorithmen nicht stets der Fall.

Für mehr Infos zu FSB:
Linearization Attacks Against Syndrome Based Hashes

GrafZahl

das thema ist interessant, aber schweift für diesen thread zu weit ab ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas