Warum ist es nicht möglich umzukehren, eine kryptographische hash?

MD5 ist entworfen, um kryptographisch irreversibel. In diesem Fall, die wichtigste Eigenschaft ist, dass es rechnerisch undurchführbar zu finden auf der Rückseite des hash, aber es ist leicht zu finden, die den Hashwert von beliebigen Daten. Zum Beispiel, denken wir etwa nur auf zahlen (binäre Dateien, nachdem alle, könnte so interpretiert werden, nur eine sehr lange Zahl).

Sagen wir, wir haben die Zahl "7", und wir wollen den hash davon. Vielleicht ist die erste Sache, die wir versuchen so unsere hash-Funktion ist "mal zwei". Wie wir sehen werden, ist dies nicht eine sehr gute hash-Funktion, aber wir werden es versuchen, zu verdeutlichen. In diesem Fall wird der hash der Nummer "14". Das war ziemlich einfach zu berechnen. Aber jetzt, wenn wir uns anschauen, wie schwer es ist, umzukehren, so finden wir, dass es auch genauso einfach! Angesichts einer hash, können wir nur dividieren Sie durch zwei, um die ursprüngliche Zahl! Dies ist nicht eine gute hash, denn der springende Punkt bei der ein hash ist, dass es ist viel schwieriger zu berechnen, die inverse, als es um den hash zu berechnen (dies ist die wichtigste Eigenschaft, die zumindest in einigen Kontexten).

Nun, versuchen Sie einen anderen hash. Für diesen einen, ich bin zu haben, um die Einführung der Idee des clock-Arithmetik. Auf einer Uhr ist, gibt es nicht eine unendliche Menge der Zahl. In der Tat, es geht nur von 0 bis 11 (denken Sie daran, dass 0 und 12 sind die gleichen auf einer Uhr). Also, wenn Sie "hinzufügen", um 11, bekommst du nur null. Verlängern Sie die Ideen der Multiplikation, addition und Potenzierung zu einer Uhr. Z. B. 8+7=15, sondern 15 auf einer Uhr ist wirklich nur 3! Also auf eine Uhr, Sie würde sagen, 8+7=3! 6*6=36, aber auf eine Uhr, 36=0! also 6*6=0! Nun, für das Konzept der Kompetenzen, die Sie tun können, die gleiche Sache. 2^4=16, aber 16 ist nur 4. Also 2^4=4! Nun, hier ist, wie es knüpft an das hashing. Wie wäre es, wenn wir versuchen, die hash-Funktion f(x)=5^x, aber mit clock-Arithmetik. Wie Sie sehen werden, führt dies zu einigen interessanten Ergebnissen. Lassen Sie uns versuchen, unter der hash-Wert von 7 vor.

Sehen wir, dass 5^7=78125 aber auf einer Uhr, die gerade mal 5 (wenn Sie die Mathematik zu tun, sehen Sie, wir haben eingewickelt rund um die Uhr 6510 mal). So erhalten wir f(7)=5. Nun, die Frage ist, wenn ich Ihnen sagte, dass der hash der meine Nummer 5 war, würden Sie in der Lage sein, um herauszufinden, dass meine Nummer war die 7? Gut, es ist eigentlich sehr schwer zu berechnen, die Umkehrung dieser Funktion, im Allgemeinen Fall. Menschen, die viel klüger als ich, haben bewiesen, dass in bestimmten Fällen die Umkehrung dieser Funktion ist Weg schwieriger als die Berechnung es vorwärts. (EDIT: Nemo hat darauf hingewiesen, dass diese in der Tat wurde nicht "bewiesen"; in der Tat, die einzige Garantie, die Sie bekommen, ist, dass eine Menge kluger Leute, die versucht haben, eine lange Zeit zu finden, eine einfache Möglichkeit, dies zu tun, und keiner von Ihnen ist es gelungen.) Das problem der Umkehrung dieser Vorgang wird als "Diskrete Logarithmus Problem". Schauen Sie für mehr in die Tiefe der Berichterstattung. Dies ist zumindest der Beginn einer gute hash-Funktion.

Mit der realen Welt von hash-Funktionen, die Idee ist im Grunde das gleiche: Sie suchen eine Funktion, die schwer rückgängig zu machen. Menschen, die viel klüger als ich, haben entwickelt, MD5 und anderen hashes, um Sie nachweislich schwer umzukehren.

Nun, vielleicht früher der Gedanke, die zu Ihnen aufgetreten ist: "es wäre einfach zu berechnen, die inverse! Ich würde einfach den hash jeder Zahl, bis ich einen gefunden, der abgestimmt!" Nun, für den Fall, wo die zahlen sind alle weniger als zwölf, das wäre machbar. Aber für die analog zu einer real-world-hash-Funktion, stellen Sie sich all die damit verbundenen zahlen sind riesige. Die Idee ist, dass es noch relativ leicht berechnen den hash-Funktion für diese großen zahlen, aber die Suche über alle möglichen Eingaben wird härter, viel schneller. Aber das, was Sie stolperte, ist das immer noch eine sehr wichtige Idee, obwohl: auf der Suche durch die Eingabe Speicherplatz für eine Eingabe die passende Ausgabe. Rainbow tables sind eine komplexere variation auf die Idee, die vorausberechneten Tabellen die input-output-Paare in der smart-Möglichkeiten, um es möglich zu machen, um schnell zu suchen und durch eine große Anzahl von möglichen Eingaben.

Lassen Sie uns jetzt sagen, dass Sie eine hash-Funktion zum speichern von Passwörtern auf Ihrem computer. Die Idee ist diese: Der computer speichert nur den hash-Wert das richtige Kennwort ein. Wenn ein Benutzer versucht, sich anzumelden, Sie vergleichen den hash der Eingabe das Passwort zu dem hash-Wert das richtige Kennwort ein. Wenn Sie übereinstimmen, übernimmt der Benutzer das richtige Kennwort ein. Der Grund, warum das vorteilhaft ist, weil wenn jemand Stiehlt Ihrem computer, die Sie noch nicht haben, Zugang zu Ihrem Passwort, nur den hash davon. Weil die hash-Funktion wurde von intelligenten Menschen zu schwer, die Rückseite, können Sie nicht einfach abrufen, Ihr Passwort von ihm.

Einem Angreifer die beste Wette ist ein bruteforce-Angriff, wo Sie versuchen, eine Reihe von Passwörtern. Genau wie Sie vielleicht versuchen, die zahlen weniger, die 12 im vorherigen problem, könnte ein Angreifer versuchen, alle Passwörter nur aus zahlen und Buchstaben, die weniger als 7 Zeichen lang ist, oder alle Wörter, die im Wörterbuch. Die wichtige Sache hier ist, dass er nicht versuchen alle möglichen Passwörter, da gibt es zu viele möglich-16 Zeichen-Passwörter, zum Beispiel, um immer test. Der Punkt ist also, dass der Angreifer die Einschränkung der möglichen Kennwörter, die er testet, sonst wird er nie checken ein kleiner Prozentsatz von Ihnen.

Nun, wie für Salz, die Idee ist diese: Was passiert, wenn zwei Benutzer hatten das gleiche Passwort? Hätten Sie den gleichen hash. Wenn Sie darüber nachdenken, den Angreifer nicht wirklich zu knacken ist, jedem Benutzer das Passwort individuell. Er geht einfach durch jede mögliche Eingabe Passwort und vergleicht den Hashwert, um alle hashes. Wenn es passt einer von Ihnen, dann er hat ein neues Passwort. Was möchten wir wirklich, ihn zu zwingen, zu tun, ist die Berechnung eines neuen Hashwertes für jeder Benutzer+Passwort-Kombination, die er überprüfen will. Das ist die Idee, ein Salz, ist, dass die hash-Funktion etwas unterschiedlich sein für jeden Benutzer, so kann er nicht erneut verwendet einen einzigen Satz von vorausberechneten Werte für alle Benutzer. Der einfachste Weg, dies zu tun ist, um tack auf einige zufällige Zeichenfolge, die jedem Benutzer das Passwort, bevor Sie den hash, wo die zufällige Zeichenfolge ist unterschiedlich für jeden Benutzer. So, zum Beispiel, wenn mein Passwort "shittypassword", meine hash kann als MD5("6n93nshittypassword") und, wenn Ihr Passwort "shittypassword", den hash kann als MD5("fa9elshittypassword"). Dieses kleine bisschen "fa9el" wird als "Salz", und es unterscheidet sich für jeden Nutzer. Zum Beispiel, mein Salz ist "6n93n". Nun, das bisschen, das ist geheftet, um Ihr Passwort wird nur auf Ihrem computer gespeichert als gut. Wenn Sie versuchen, sich mit dem Passwort X, der computer kann nur berechnen von MD5("fa9el"+X) und sehen, ob Sie mit dem gespeicherten hash.

So dass die grundlegende mechanik der Anmeldung unverändert bleiben, aber für einen Angreifer, Sie stehen nun vor eine gewaltige Herausforderung: anstatt eine Liste von MD5-hashes, Sie sind konfrontiert mit einer Liste von MD5-Summen und Salze. Sie müssen im wesentlichen zwei Optionen:

1. Können Sie die Tatsache ignorieren, dass die hashes sind gesalzen, und versuchen, Sie zu knacken die Passwörter mit Ihren lookup-Tabelle, wie Sie ist. Doch die Chancen, dass Sie tatsächlich zu knacken ein Passwort sind stark reduziert. Zum Beispiel, auch wenn "shittypassword" ist auf der Liste der Eingänge zu überprüfen, wahrscheinlich "fa9elshittypassword" nicht. Um auch einen kleinen Prozentsatz der Wahrscheinlichkeit der Rissbildung ein Passwort, das Sie vorher hatte, Sie werde testen müssen, die um Größenordnungen mehr möglich Passwörter.

2. Können Sie die Neuberechnung der Hashwerte auf einer pro-Benutzer-basis. Anstatt also die Berechnung von MD5(passwordguess), für jeden Benutzer X berechnen Sie MD5( Salt_of_user_X + passwordguess). Nicht nur, dass diese Kraft, die Sie zur Berechnung eines neuen Hashwertes für jeden Benutzer, die Sie wollen zu knacken, aber auch die meisten wichtiger ist, es verhindert, dass Sie in der Lage, die Verwendung von vorberechneten Tabellen (wie rainbow-Tabelle, zum Beispiel), weil Sie nicht wissen, was Salt_of_user_X ist, bevor die hand, so können Sie nicht vorberechnen, die hashes zu testen.

Also im Grunde, wenn Sie versuchen, die Verwendung von vorberechneten Tabellen, mit Salz effektiv erhöht die möglichen Eingaben, die Sie haben, um zu testen, um, das Kennwort zu knacken, und selbst wenn Sie nicht mit vorberechneten Tabellen, ist es noch verlangsamt durch einen Faktor N, wobei N die Anzahl der Kennwörter, die Sie speichern.

Ich hoffe, dies beantwortet alle Ihre Fragen.

Einen großen Grund, warum Sie können nicht umkehren die hash-Funktion ist, da Daten verloren gehen.

Betrachten wir ein einfaches Beispiel-Funktion: 'ODER'. Wenn Sie sich bewerben, dass Ihre Eingabedaten von 1 und 0, es ergibt 1. Aber jetzt, wenn Sie wissen, dass die Antwort '1', wie Sie wieder aus den ursprünglichen Daten? Das können Sie nicht. Es hätte 1,1 oder vielleicht 0,1 oder vielleicht 1,0.

Als für das Salzen und die rainbow-Tabellen. Ja, theoretisch könnten Sie haben eine Regenbogen-Tabelle die würde umfassen alle möglichen Salze und Passwörter, aber praktisch, das ist einfach zu groß. Wenn Sie versucht jede mögliche Kombination aus Kleinbuchstaben, Großbuchstaben, zahlen und zwölf Satzzeichen, bis zu 50 Zeichen lang sein, das ist (26+26+10+12)^50 = 2.9 x 10^93 verschiedene Möglichkeiten. Das ist mehr als die Anzahl der Atome im sichtbaren Universum.

Die Idee hinter rainbow-Tabellen ist die Berechnung der hash für eine ganze Reihe von möglichen Passwörtern im Voraus, und Passwörter sind wesentlich kürzer als 50 Zeichen, so dass es möglich ist, dies zu tun. Das ist, warum Sie möchten, fügen Sie Salz vor: wenn Sie add-on '57sjflk43380h4ljs9flj4ay' auf der Vorderseite des Kennworts. Während jemand vielleicht schon berechnet den hash für "pa55w0rd", niemand wird bereits berechnet, die hat für '57sjflk43380h4ljs9flj4aypa55w0rd'.

md5 ist 128bit, das ist 3.4*10^38 Kombinationen.

die Gesamtzahl von acht Zeichen Länge Passwörter:

• nur Kleinbuchstaben und zahlen: 36^8 = 2.8*10^12
• niedriger&Großbuchstaben und zahlen: 62^8 = 2.18*10^14

Haben Sie zum speichern von 8 Byte für das Passwort, 16 für den md5-Wert, d.h. ist 24 bytes insgesamt pro Eintrag.

Also müssen Sie ca 67000G oder 5200000G Speicher für Ihre rainbow-table.
Der einzige Grund, es ist tatsächlich möglich, um herauszufinden, Passwörter, da verwenden die Leute offensichtlich lieben.