Benutzer:Pyrometer/Baustelle/Rainbow Table/Entwurf 1

----------------------------- Notizen, nicht Bestandteil des Artikels ----------------------

Entwurf 1, in Bearbeitung

Artikel verschieben/umbenennen auf "Regenbogentabelle|Regenbogen-Tabelle" und Weiterleitung(en) von "Rainbow Table" zum deutschen Stichwort?

Zum Inhaltsverzeichnis: Benutzer:Pyrometer/Baustelle/Inhalt

Weitere Notizen hier (Mein Notizblock)

Benutzer:Pyrometer/Baustelle/Rainbow Table/

---------------------------------------------- Ende Notizen ---------------------------------

Die Rainbow Table (zu Deutsch: Regenbogentabelle) ist eine von Philippe Oechslin entwickelte Datenstruktur, die eine schnelle, probabilistische Suche nach einem Klartext (i. d. R. ein Passwort) ermöglicht, wenn dessen Hashwert gegeben ist.

Siehe z. B. Hier: http://www.springerlink.com/content/jget2a7m969mt45u/
Das Verfahren auf Passwortangriffe einzuengen, ist etwas zu eng gedacht. Es gibt auch andere Szenarios. (Chosen Plaintext-Angriffe können allgemeine Verschlüsselte Texte brechen.

Bedingung nennen: Hashfunktion und Zeichenvorrat des Klartext müssen bekannt sein.

"probabilistisch" erfordert Erläuterung: Tabellen werden nach Zufallsverfahren angelegt, Verfahren führt deshalb nicht immer ans Ziel."

Recherchieren: Gibt es Tabellen mit Metainformationen zur Tabellenstruktur/Haschfkt/etc., oder sind Tabellen stets immer nur im Kontext der zugehörigen Anwendung verwendbar?

Der sogenannte Time-Memory-Tradeoff gestattet die Suche nach fast allen Klartexten eines bestimmten Zeichenraums innerhalb einer erheblich kürzeren Zeit, als diesen komplett zu bruteforcen und ohne alle für diesen Zeichenraum möglichen Hashwerte speichern zu müssen.

"bruteforcen" ist ja wohl der Knaller :-)

Dieses funktioniert bei Hashfunktionen ohne Salt, wie es z. B. bei den Passwörtern für die Windows-Familie oder vielen Routern der Fall ist. Für LM Hashes und MD5 wurden bereits Regenbogentabellen berechnet und stehen aus diversen Quellen zur Verfügung.

Wesentlich zu nennen: Bekannte Hashfunktion, bekannter Zeichensatz im Originalraum

Evtl. Quellen ausfindig machen und verlinken.

Verwendung finden Rainbow Tables bei der Wiederherstellung von Passwörtern zum Beispiel innerhalb der IT-Forensik, bei Penetrationstests und beim illegitimen Passwortcracken.

Laut http://www.heise.de/security/artikel/Regenbogentabelle-270992.html :
Metaphorisch gesehen wandern die Daten durch einen Regenbogen, wo erst die rote Funktion angewendet wird, dann die orange, die gelbe, grüne und so fort. Dies hat der Technik den Namen Regenbogentabellen (Rainbow Tables) eingebracht.

Überblick[Bearbeiten | Quelltext bearbeiten]

Grundlagen der Regenbogentabellen (Hellman-Methode)[Bearbeiten | Quelltext bearbeiten]

Wenn man die verwendete Hash-Funktion und den Zeichenvorrat des Passwortes kennt, kann man aus einem gegebenen Hashwert ein passendes Passwort nach der sogenannten Brute-Force-Methode (Deutsch: Rohe Gewalt) ermitteln. Dazu geht man alle denkbaren Passworte durch und berechnet versuchsweise den Hash. Für die (nach Stand 2011 inzwischen veralteten) LM-Hashs wären maximal ca. 2 mal 2^43 (= ca. 8,8 Billonen) Versuche für jede der beiden Passworthälften nötig.

Wenn man diese Berechnung einmal durchführt, könnte man die Passwort-Hash-Paare abspeichern und könnte in Zukunft einfach in der Tabelle nachschlagen. Allerdings hätte eine solche Tabelle einen Umfang von 8,8 Billionen Paaren aus Schlüssel (7 Byte) und Hash (8 Byte) und würde rund 132 Terabyte Speicher benötigen.

Hellman schlug 1980 eine besondere Datenstruktur vor, mit der man Zwischenergebnisse einer Brute-Force-Berechnung in sehr viel kleineren Dateien abspeichern kann. Dazu werden die Information zu allen Gliedern einer langen Kette von Passwörtern durch die beiden Endglieder einer solchen Kette repräsentiert. Mit dieser Technik wurden "komprimierte" Tabellen möglich, die auf Festplatten des damaligen Standes der Technik gespeichert werden konnten. Zur Verwendung der "komprimierten" Information ist es notwendig, die weggelassenen Informationen zu rekonstruieren. Erstens muss man die Hash-Funktion so oft abarbeiten, wie die Speicherkette lang ist und dabei im selben Schritt eine sogenannte Reduktionsfunktion aufrufen. Zweitens muss man jedes so erhaltene Zwischenergebnis mit der rechten Spalte der gespeicherten Tabelle vergleichen. Drittens muss man für gefundene Übereinstimmungen die Erzeugung der Kette aus ihren Startwert reproduzieren. Schlussendlich liegt es in der Natur des Verfahrens, dass "falsche Alarme" erzeugt werden. Deshalb verbringt die "Entschlüsselung" einen großen Teil der Rechenleistung bei der vergeblichen Reproduktion von Ketten.

Das ursprüngliche Hellman-Verfahren verwendete für alle Schritte innerhalb einer Kette die

Eine Rainbow Table ist eine kompakte Repräsentation von zusammenhängenden Passwortsequenzen, sogenannten Ketten (chains). Jede dieser Ketten startet mit einem initialen Kennwort, welches durch eine Hashfunktion geleitet wird. Auf den Hash wird durch eine Reduktionsfunktion angewendet und liefert als Ergebnis ein weiteres potentielles Klartextkennwort. Dieser Prozess wird für eine vorgegebene Anzahl von Paaren (Hash/Reduktion) wiederholt. Am Ende wird das erste Kennwort der Kette zusammen mit dem letzten Kennwort in einer Datei, der Regenbogentabelle, gespeichert.

Zur Erzeugung der Ketten werden die Startwerte möglichst zufällig aus dem erlaubten Zeichenvorrat zusammengestellt. Auch die weiteren Glieder der Kette werden mittels der Reduktionsfunktion so aus den Hash-Werten berechnet, dass der Wertebereich der möglichen Passworte möglichst gleichmäßig abgedeckt ist. Dieses Verfahren sorgt dafür, dass die Menge der möglichen Passworte nicht mit Sicherheit vollständig abgedeckt wird. Es besteht nur eine gewisse Wahrscheinlichkeit, dass ein bestimmtes Passwort erfasst ist. Die Tabellen werden nur einmalig erstellt und dienen dann als Nachschlagetabelle.

Um ein Kennwort herauszufinden, wird ein zweistufiger Prozess benötigt. Zunächst wird der Hash des herauszufindenden Kennworts durch die oben beschriebene Hash-Reduktion-Sequenz geführt, bis das Kennwort als „rechte Seite“ in der Tabelle vorkommt. Oder, bis - im Falle eines Misserfolgs - die Kettenlänge abgearbeitet wurde, ohne dass ein Kennwort errechnet wurde, welches in der rechten Seite der Tabelle aufgeführt war. Im Erfolgsfall erhält man aus der linken Spalte das Startkennwort der Kette, und kann im zweiten Schritt von diesem ausgehend die Hash-Reduktion-Sequenz anwenden, um das gesuchte Kennwort zu erhalten.

Probleme um Zyklen und Kollisionen[Bearbeiten | Quelltext bearbeiten]

Funktionsweise[Bearbeiten | Quelltext bearbeiten]

Eine Hashfunktion ordnet einer Binärfolge beliebiger Länge eine Binärfolge fester Länge zu. Bei der Hashfunktion MD5 zum Beispiel ist die Ausgabelänge 128 Bit oder 32 4-Bit-Zeichen.

Ein paar Worte zu "Einwegfunktion".

Zu einer zufälligen Zeichenkette mit Länge $n$ wird durch eine Hashfunktion H ein Hashwert berechnet. Dieses Ergebnis der Hashfunktion (mit Länge 32) wird durch eine Reduktionsfunktion R in eine neue Zeichenkette umgewandelt, die wieder Länge $n$ besitzt. Weil die Hintereinanderausführung von Hashfunktion und Reduktionsfunktion die Länge der Zeichenkette nicht ändert, können diese beiden Schritte beliebig oft abwechselnd wiederholt werden. Die Folge der Zwischenergebnisse bildet am Ende eine Kette (Chain). Gespeichert werden Anfangs- und Endwert dieser Kette. Diese Schrittfolge wird ebenfalls $x$ -mal wiederholt und bildet eine universelle Rainbow Table.

Reduktionsfunktion[Bearbeiten | Quelltext bearbeiten]

Diese Funktion reduziert als Beispiel den 128 bit langen MD5-Hash auf $n$ Zeichen. Jede dieser Reduktionen liefert dank MD5 eine neue, „eindeutige“ Zeichenkette oder eine Kollision. Um Kollisionen zu vermeiden, verwendet man verschiedene Reduktionsfunktionen, die periodisch angewendet eine eindeutige Zuordnung der Eingangs-Zeichenkette und des Ausgangshashes ermöglichen. Dieses Verfahren stellt eine effizientere Methode für n-stellige Zeichenketten dar als beispielsweise ein Brute-Force-Angriff mit Schlüsselsuche von [a-//////], da bei letzterem viele Zeichenketten in Hashes umgewandelt werden, die mit hoher Wahrscheinlichkeit niemals fallen, bzw. gewählt, werden.

Anwendung[Bearbeiten | Quelltext bearbeiten]

Gesucht wird die Zeichenfolge, deren MD5-Hashwert in der Hexadezimaldarstellung 97fae39bfd56c35b6c860aa468c258e0 ist (Domino). Der herkömmliche Weg, alle MD5-Hashes für alle möglichen Variationen zu berechnen und diese zu vergleichen, ist sehr rechenintensiv und muss bei neuen Suchläufen wiederholt werden.

Sinnvoll wäre es nun, die bereits berechneten Hashes in einer Datenbank zu speichern und bei erneuten Suchläufen nur noch vergleichen zu müssen, ob der gesuchte Hash schon bekannt ist. Bei einer Suche über 64 mögliche Zeichen [A-Za-z0-9./], die jede Stelle des Eingangstextes haben könnte, ergeben sich bei 6 Stellen $64^{6}$ Variationen. Werden nun Text und Hash in einer Datenbank gespeichert, so werden pro Paar 16 Byte für den Hash und 6 Byte für den Plaintext benötigt und somit für die kompletten Daten etwa 1,4 Terabyte.

Diese Datenmengen lassen sich meistens nicht verarbeiten und müssen reduziert werden.

Sinnvoller Mittelweg: Rainbow Table[Bearbeiten | Quelltext bearbeiten]

Anstatt alle Werte samt Schlüsseln zu speichern, werden nur die anfängliche Zeichenkette und der letzte Hashwert einer $n$ -elementigen Kette gespeichert. Auf diese Weise lassen sich $n$ Hashes durch einen Start- und Endwert repräsentieren und in vergleichsweise kurzer Zeit neu berechnen und damit der Eingabetext wiederfinden. Bildet sich aus einem reduzierten Hash (= Plaintext) durch erneutes Hashen ein Final-Hash, so wird diese Kette vom Startwert aus neu berechnet, bis sich der gegebene Hash ergibt; der diesem vorausgehende Text ist der gesuchte Ursprungstext. Bei einer Ketten-Länge von $n=10.000$ werden also nur 10.000 Hash-Berechnungen gebraucht, um den Ursprungstext zu einem Hash zu finden.

Bei schlecht programmierten oder trivialen Reduktionsfunktionen treten nach wenigen Läufen Kollisionen auf, die zu Wiederholungen der reduzierten Texte und somit auch der Hashes führen. Solche internen Schleifen tragen dann dazu bei, dass der Algorithmus versagt: Man berechnet mühsam Tausende von Elementen und nur einige wenige davon sind eindeutig unterscheidbar.

Die Wahrscheinlichkeit, aus den reduzierten Hashes genau den gesuchten Eingangstext zu erhalten, ist abhängig von der Güte der Reduktionsfunktion(en) und den Parametern bei der Erstellung der Rainbow Table, da nur die reduzierten Hashes (= Plaintexts) später gefunden werden können. Wenn die Reduktionsfunktion(en) beispielsweise nur auf Zahlen reduzieren, kann der Plaintext „Domino“ nicht gefunden werden. Wenn die Reduktionsfunktion(en) auf sieben Stellen reduzieren (von 32), dann werden 6-stellige Plaintexts nicht berechnet und auch hier kann „Domino“ nicht gefunden werden.

Gegenmaßnahmen[Bearbeiten | Quelltext bearbeiten]

Klar machen: RT sind nur Abkürzungen, welche auf vorberechneten Tabellen beruht, deren Erstellung den Aufwand eines Brute-Force-Angriffs in der Regel deutlich übersteigt. Ist ein Brute-Force-Angriff undurchführbar, so geht auch nichts mit RT.

Die Größe einer Rainbow Table steigt mit der Länge der Kennwörter, für die sie generiert werden soll. Je nach Hashtyp ist ab einer gewissen Kennwortlänge die Berechnung einer Rainbow Table nicht mehr wirtschaftlich, sowohl was die Dauer der Generierung als auch den Platzbedarf der Tabellen angeht. Lange Kennwörter entstehen z. B. bei der Verwendung von Sätzen statt eines Wortes (siehe Passphrase).

Eine weitere Methode, die Generierung von Rainbow Tables unwirtschaftlich zu machen, ist der Einsatz von Salt. Es handelt sich um eine einfache Veränderung des Passworts durch einen – im Idealfall – zufällig generierten Wert. Für jedes Passwort, welches die Rainbow Table abdecken soll, müsste nun ebenfalls alle durch das Salt-Verfahren möglichen Kombinationen ebenfalls erzeugt werden. Damit würde sich der Aufwand um die Zahl der möglichen Salts vervielfachen, was die Generierung einer Tabelle ebenfalls unwirtschaftlich oder auch auf längere Sicht technisch nicht realisierbar macht.

Was will uns der Autor mit dem folgenden Satz sagen? Denkt er vielleicht, Salts seien grundsätzlich auf ein einziges Zeichen beschränkt?

Salts können aber kurze Passwörter nicht schützen – sie erhöhen nur den Aufwand beim Brute-Forcen, wenn mehrere vorliegen, verhindern es aber keineswegs. Dieser Aufwand kann aber weiter erhöht werden, wenn ein Passwort nicht einfach, sondern mehrfach gehasht wird - üblich sind mehrere tausend Iterationen. Erst beide Methoden kombiniert ergeben ein Hashing-Verfahren, welches eine gewisse Resistenz gegen typische Angriffsmethoden aufweist. Das Salt macht das Erstellen von Tabellen unwirtschaftlich oder gar unmöglich, zusammen mit den Iterationen werden Brute-Force-Angriffe erheblich verlangsamt. Eine erfolgreiche Implementierung ist z. B. MD5 (crypt). Das Verfahren basiert auf MD5, verwendet aber sowohl Salts in einer Länge von 12 bis 48 Bit sowie 1000 Iterationen. Das Erstellen von Rainbow Tables für dieses Verfahren ist aufgrund der Länge des Salts unter realen Bedingungen unwirtschaftlich, und reines Bruteforcen ebenfalls.