Wie funktioniert Hashing?

Kryptografische Hash-Funktionen sind mathematische Objekte, die als „großes Mischen und Verwürfeln“ bezeichnet werden können von einigen Bits „. Sie nehmen eine Folge von Bits (möglicherweise eine sehr lange) als Eingabe und bieten eine Ausgabe fester Größe. Grob gesagt sind sie so verwirrt, dass, obwohl sie nichts Geheimnisvolles enthalten (das ist nur deterministischer Code), niemand herausfinden kann, wie man sie „invertiert“ (eine passende Eingabe für eine bestimmte Ausgabe findet), außer mit der aufgerufenen Basismethode „Glück“: Versuchen Sie zufällige Eingaben, bis eine Übereinstimmung gefunden wird.

Wie es wissenschaftlich passieren kann, dass Hash-Funktionen überhaupt existieren können, ist eine gute Frage .

Hashing ist keine Verschlüsselung . Es gibt kein Geheimnis, keinen Schlüssel für das Hashing.

Hash-Funktionen haben viele Verwendungsmöglichkeiten. Eine davon ist „Passwortspeicherung“. Eine Hash-Funktion scheint eine gute Sache für die Speicherung von Passwörtern zu sein. Wir möchten Passwörter nicht direkt speichern (andernfalls würde ein gelegentlicher Blick des Angreifers auf unsere Datenbanken zu viele Informationen liefern. Eine Diskussion finden Sie in diesem Blog-Beitrag .) ;; Wir möchten Kennwortüberprüfungstoken speichern: Dies ermöglicht die Überprüfung eines Kennworts (das der Benutzer vorlegt), zeigt jedoch nicht das Kennwort selbst an. Die Idee ist also: Speichern wir den Hash des Passworts. Wenn ein Passwort überprüft werden soll, berechnen wir einfach seinen Hash und prüfen, ob er mit dem gespeicherten Wert übereinstimmt. Es ist jedoch schwierig, das Passwort nur anhand des Hashwerts zu erraten Die Hash-Funktion ist widerstandsfähig gegen „Inversion“ (siehe oben).

Da Passwörter eine spezielle Art von Daten sind (Daten, an die sich Menschen erinnern können), benötigen wir für eine angemessene Sicherheit eine „verstärkte“. Hash-Funktion:

• Wir wollen eine sehr langsame Hash-Funktion.
• Wir wollen keine eine Hash-Funktion, aber viele verschiedene Hash-Funktionen, so dass jedes Passwort mit seiner eigenen Hash-Funktion gehasht wird; Hier geht es darum, parallele Angriffe abzuwehren. Dieser Vorgang, bei dem eine einzelne Hash-Funktion in viele Varianten umgewandelt wird, wird als Salting bezeichnet.

Siehe diese Antwort für eine gründliche Behandlung des Themas Hashing-Passwörter.

Kommentare

• Entschuldigung, aber obwohl Ihre Antwort äußerst gründlich und gut zusammengestellt war, fand ich Die andere Antwort entspricht eher dem, wonach ich gesucht habe.

Hashing ist eine Funktion von einigen Bitfolge (normalerweise variable Länge) zu einer anderen Bitfolge (normalerweise kleiner und fester Länge).

Hashing wird in Datenbanken zum Abrufen von Daten und in speicherinternen Datenstrukturen verwendet, die als Hash-Tabellen bezeichnet werden. Es ermöglicht uns, beliebige Daten wie eine Zeichenfolge oder ein kompliziertes Objekt mit vielen Feldern auf eine Binärzahl zu reduzieren, die dann direkt als Index in ein Array mit geringer Dichte verwendet werden kann, um die zugehörigen Daten abzurufen (mit einigen Details für die Behandlung von Hash Kollisionen).

Die auf die oben beschriebene Weise verwendeten Hashing-Funktionen sind „Cousins“ von kryptografischen Hashing-Funktionen. Sie sind auf unterschiedliche Anforderungen ausgelegt. Sie müssen schnell zu berechnen sein und eine gute Verteilung erreichen.

Beim sicheren Rechnen werden kryptografische Hashes verwendet, um Daten in einen repräsentativen kleinen Bitstring zu verarbeiten. Kryptografische Funktionen haben unterschiedliche Anforderungen. Sie sind so konzipiert, dass sie schwer rückgängig zu machen sind (als „Falltür“ – oder „Einweg“ -Funktionen). Nicht nur das, sondern eine wichtige Voraussetzung ist, dass es schwierig sein muss, für einen bestimmten Klartext- und Hashwert einen anderen Klartext zu finden, der denselben Hash erzeugt.

Hashing kann nicht nur für Passwörter verwendet werden. aber als Prüfsumme zur Überprüfung der Datenintegrität und als Teil der Implementierung digitaler Signaturen. Um ein großes Dokument digital zu signieren, müssen wir das Dokument einfach hashen, um einen „Digest“ zu erstellen (ein Name, der für die Ausgabe einer Hashing-Funktion verwendet wird, wenn etwas sehr Langes gehasht wird). Dann wird nur dieser Digest durch das Kryptosystem mit öffentlichem Schlüssel geleitet, um eine Signatur zu erzeugen. Sie können die Schwäche dort sehen: Was ist, wenn es einem Angreifer gelingt, ein Dokument mit demselben Digest zu erstellen? Dann sieht es so aus, als ob die über dem Originaldokument erstellte Originalsignatur tatsächlich eine Signatur eines gefälschten Dokuments ist: Eine Fälschung, bei der eine Signatur transplantiert wurde, wurde effektiv durchgeführt.

Durch das Passwort-Hashing können Systeme die Nur-Text-Version von nicht speichern Sie können jedoch überprüfen, ob der Benutzer, der versucht, einen Eintrag zu erhalten, dieses Kennwort kennt. Durch Hashing können Systeme nicht nur die Klartextkennwörter nicht speichern (was sehr sorgfältig geschützt werden müsste), sondern es besteht auch die Möglichkeit, dass die Kennwörter auch dann sicher sind, wenn die Hashes öffentlich zugänglich gemacht werden (ähnlich wie bei der Krypto mit öffentlichen Schlüsseln) Systeme können öffentliche Schlüssel offenlegen). In der Praxis sind Hashes dennoch vor öffentlichem Zugriff geschützt: Zum Beispiel /etc/shadow -Dateien auf Unix-ähnlichen Systemen, die weltweit lesbare /etc/passwd -Dateien ergänzen

Die Hashing-Funktion ist alles andere als zufällig. Die Randomisierung wird jedoch verwendet, um Angreifer zu vereiteln, die große Wörterbücher mit Kennwörtern und Hashes erstellen, die es ihnen ermöglichen, einen Hash-Code nachzuschlagen und das entsprechende Kennwort abzurufen.

Um ein Kennwort sicherer zu hashen, können wir einfach hinzufügen Einige zufällige Teile davon werden als „Salz“ bezeichnet. Unterschiedliche Salze, die demselben Passwort hinzugefügt werden, führen natürlich zu unterschiedlichen Hashes (hoffentlich mit wenigen oder keinen Kollisionen).

Wenn das zufällige Salz beispielsweise 32 Bit breit ist, bedeutet dies, dass ein Kennwort theoretisch auf über vier Milliarden verschiedene Arten gehasht werden kann, was es sehr unpraktisch macht, ein vorberechnetes Wörterbuch aller möglichen Hashes zu haben von einer großen Anzahl von Passwörtern.

Wenn der Benutzer authentifiziert wird, weiß er natürlich nichts über dieses Salz. Dies ist in Ordnung, da das Salt zusammen mit dem Hash im Benutzerprofil gespeichert wird (häufig kombiniert mit dem Hash zu einem einzigen kompakten Bitstring). Wenn die Passworteingabe des Benutzers überprüft wird, wird das Salt zu einem beliebigen Passwort hinzugefügt sie trat ein, so dass das Hashing mit dem richtigen Salz durchgeführt wird. Wenn das Passwort korrekt ist, stimmt der Hash überein, da das verwendete Salz auch das richtige ist und aus dem Benutzerprofil gezogen wurde.

Auf diese Weise wird Zufälligkeit in das Passwort-Hashing einbezogen.

Was es schwierig macht, Hashes zu knacken, ist, dass sie aus „Falltür“ – oder „Einweg“ -Funktionen aufgebaut sind. In der Mathematik gibt es viele Beispiele für solche Dinge. Zum Beispiel Eine einfache Addition ist eine Falltür. Wenn wir einige Ganzzahlen hinzufügen, um eine Summe zu erzeugen, ist es unmöglich, die ursprünglichen Zahlen wiederherzustellen, wenn nur die Summe bekannt ist.

Passwort-Hashes sind keine verschlüsselten Passwörter. Wenn ein Angreifer hat Wenn der Hash und das Salt eines Passworts zufällig das Passwort erraten, kann sie dies leicht bestätigen, genau so wie es die Login-Authentifizierungssoftware tut: Sie führt das Passwort plus Salt über die Hashing-Funktion aus und stellt fest, dass das Passwort korrekt ist Hash entsteht.

Kommentare

• Ausgezeichnete Schreibfähigkeiten und eine wirklich einfache y um eine Antwort zu verstehen, die durchweg sachlich korrekt ist, aber alle Punkte angeht und einen natürlichen Fluss beibehält, der sie so viel umfassender macht. Das ‚ ist keine leichte Aufgabe, vielen Dank für Ihre Antwort!
• sehr informativ. Sie haben alle Aspekte abgedeckt.

Einer der Schlüssel zum Hashing ist, dass Informationen weggeworfen werden. Sie können einen Hash nicht umkehren, da das erforderliche Wissen nicht mehr vorhanden ist. Hier einige Beispiele für funktionsfähige (aber ziemlich wertlose) Hashing-Funktionen. Wenn Sie mir ein Passwort geben, könnte ich Folgendes tun:

• Zählen Sie die Anzahl der Vokale
• Nehmen Sie den ASCII-Code für jeden Buchstaben und XOR sie alle zusammen
• Nehmen Sie die CRC32-Prüfsumme der binären Darstellung des Passworts (dies ist tatsächlich ein echter Hash, nur kein kryptografischer)

In jedem dieser Fälle kann ich den Prozess nicht umkehren. Stattdessen muss ich den Prozess erneut ausführen, wenn Sie mir das Kennwort später erneut geben, um festzustellen, ob die von mir ausgeführte Berechnung übereinstimmt.

Für Beispiel: Wenn Sie mir anfänglich das Passwort „Affe“ geben, speichere ich möglicherweise die Nummer 3 (3 Vokale). Wenn ich später versuche, das Passwort „Drache“ zu authentifizieren, führe ich dieselbe Prüfung erneut durch und finde 2, die stimmt nicht mit 3 überein. Ich weiß also, dass Sie mir das falsche Passwort gegeben haben. Aber wenn Sie mir das Passwort „melissa“ geben, würde ich fälschlicherweise annehmen, dass Sie das richtige Passwort eingegeben haben. Dies ist ein Hash Kollision .

Die Regeln, die Sie anwenden, um die Nummer zu ermitteln, die stellt ein gegebenes Passwort dar, ist Ihre Hash-Funktion . Diese werden als „Einweg“ -Funktionen betrachtet, da Sie sie nicht umkehren sollten. Hochwertige Hash-Funktionen sollen die Anzahl potenzieller Kollisionen begrenzen, sodass Sie sich nicht um dieses Problem kümmern müssen. Einen Schritt weiter sind kryptografische Hash-Funktionen so konzipiert, dass es schwierig ist, eine Zeichenfolge zu finden, die möglicherweise mit einer bestimmten Ausgabe übereinstimmt ( und möglicherweise absichtlich Kollisionen verursachen). Sie sollen auch die Menge an Informationen begrenzen, die Sie über eine bestimmte Eingabe nur aus der Hash-Ausgabe abrufen können.

Daher können Sie nur feststellen, welches Kennwort mit einem bestimmten kryptografischen Hash übereinstimmt, indem Sie alle Möglichkeiten ausprobieren, bis Sie auf eines stoßen, das funktioniert. Weitere Gegenmaßnahmen (Salt, BPKDF2 usw.) erschweren diesen Vermutungsprozess noch mehr, indem die Person, die das Kennwort errät, bei jedem Versuch durch mehr Rahmen springt.

Beachten Sie, dass ich die Funktionsweise einer kryptografischen Hash-Funktion vollständig beschönigt habe Es ist schwierig, ein funktionierendes Passwort zu finden (auch wenn es nicht das ursprüngliche ist). Dies wird als „ Preimage-Angriff „. Im obigen trivialen Beispiel ist die Angabe von“ melissa „als Kandidatenkennwort mit 3 Vokalen ein Beispiel für einen solchen Angriff.

Kryptografische Hash-Funktionen tun dies normalerweise, indem sie die Eingabe über mehrere“ Runden „eines bestimmten Prozesses, wobei die Ausgabe jeder Runde Teil der Eingabe für die nächste Runde wird.Um die Eingabe der ersten Runde herauszufinden, müssten Sie die Eingabe der zweiten Runde herausfinden, was wiederum erfordert, dass Sie die Eingabe der dritten Runde usw. herausfinden, was bedeutet, dass jede Vermutung jeder Komponente muss durch eine lange und komplexe Reihe von Berechnungen überprüft werden. Thomas Pornin hat eine ziemlich ausführliche Erklärung , wie dieser Widerstand funktioniert; ziemlich nützliche Lektüre, wenn Sie wirklich wollen Verstehe es.

1. Bestimmen Sie den konstanten Wert von z, der diese Gleichung erfüllt: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Benötigen Sie Hilfe? OK, x = 32. Können Sie es immer noch nicht lösen? Dann sollten Sie die Antwort überhaupt nicht kennen.

   Der Wert von y, der dies auf eine einzelne Variablengleichung reduziert und die Lösung für diese einzelne Variable für jeden 6. Schüler trivial macht (möglicherweise) einen Taschenrechner brauchen), ist ein Geheimnis, das ich nur mit Menschen geteilt habe, denen ich vertraue. Ohne es könnte z alles sein; sein Wert hängt von y ab und kann daher ohne ein konstantes, bekanntes y nicht zufriedenstellend gelöst werden. Ich kenne Ihren Wert nicht, weil ich Ihnen nicht genug vertraut habe, um ihn Ihnen privat zu geben.

   Dies ist das Grundprinzip der Kryptographie; die mathematische Formel oder ein anderer deterministischer Prozess ist gut -dokumentiert, und eine oder mehrere der möglichen Variablen der Formel dürfen auch öffentlich bekannt sein, so dass sich die beiden Parteien auf eine Möglichkeit einigen können, ihre Chiffren so einzurichten, dass jede entschlüsseln kann, was die anderen verschlüsseln. Allerdings zwei Variablen Bleib geheim, wenn du eines kennst, kannst du das andere entdecken. Das, das du kennen solltest, ist der Schlüssel und das, was du bist kann mit dem Schlüssel feststellen, ist die Nachricht.

   Für einen Hash ist es ein wenig anders. Ein Hash erfordert nicht, dass ein Geheimnis aufbewahrt wird, um ein anderes zu bewahren. Stattdessen arbeiten Hashes auf der Grundlage einer irreversiblen mathematischen Transformation. Für jedes H (x) = y ist kein H -1 (y) = x, außer um H (x) für alle möglichen x zu versuchen, bis Sie y erhalten. Normalerweise liegt dies daran, dass mehrere Zwischenergebnisse der Gleichung nicht eindeutig sind. Beispielsweise ergibt die Berechnung der Quadratwurzel einer positiven Zahl technisch beides ein positives und ein negatives Ergebnis, da jede Zahl mit sich selbst multipliziert werden könnte, um das Ergebnis zu erzeugen. Die Umkehrung eines Moduls ist ähnlich mehrdeutig, die durch x mod 3 erzeugte Zahl 1 könnte durch jedes x = 3k + 1 erzeugt worden sein. Diese Arten von „Einweg“ -Transformationen werden so kombiniert, dass der Versuch, die inverse Hash-Funktion zu berechnen, unendlich viele Möglichkeiten bietet. Der einfachere (einfachste) Weg, sie zu lösen, besteht daher darin, einfach jede mögliche Eingabe zu versuchen, bis eine Ausgabe übereinstimmt dauert immer noch lange.

2. Hashes sind nicht zufällig. Wie ich bereits sagte, sind Hashes das Ergebnis einer irreversiblen mathematischen Operation. Diese Operation muss immer noch deterministisch sein; Bei einer konstanten Eingabe ist die Ausgabe konstant, unabhängig davon, wie oft Sie die Operation ausführen. Es gibt keine zufällige Komponente.

   Wo Sie möglicherweise verwirrt waren, steht der Begriff für das, was ein Hash simuliert, nämlich ein zufälliges Orakel . Stellen Sie sich eine Black Box vor, in der sich ein kleiner Mann mit einem fotografischen Gedächtnis und einer mystischen Methode zur Erzeugung perfekt zufälliger Zahlen befindet. Sie schreiben etwas auf ein Stück Papier und schieben es durch einen Schlitz, in den der Mann es bekommt. Er liest es und eines von zwei Dingen passiert. Entweder hat er es noch nicht gelesen. In diesem Fall generiert er eine neue Zufallszahl und gibt sie Ihnen, wobei er sowohl Ihre Nachricht als auch die Nummer in sein Gedächtnis schreibt. Oder er hat genau genau gelesen Nachricht vorher, in welchem Fall er sich an die Nummer erinnert, die er beim ersten Lesen generiert hat, und Ihnen diese Nummer gibt. Der Zufallszahlengenerator generiert niemals eine Nummer, die er bereits generiert hat, er hat eine unendlich mögliche Größe und die des kleinen Mannes Das Gedächtnis ist unbegrenzt und unfehlbar. Daher wird der kleine Mann niemals denken, dass er zuvor eine Nachricht gelesen hat, wenn er dies nicht getan hat, niemals vergessen, dass er zuvor eine Nachricht gelesen hat, und wird daher niemals zwei verschiedene Zahlen für genau dieselbe Nachricht oder dieselbe produzieren Nummer für zwei verschiedene Nachrichten.

   Dies ist, was Hash-Funktionen zu simulieren versuchen. Sie können diesen kleinen Mann nicht mit dem fotografischen Speicher modellieren, da dies unendlichen Speicherplatz und unbegrenzte, universelle Verfügbarkeit erfordern würde Geräte, die auf keine andere Weise mit einem anderen Gerät verbunden sind. Stattdessen stützen sie sich auf eine deterministische, aber zufällig aussehende Berechnung, die die Nachricht in ihren Hashwert „verdaut“. Dieselbe Hashfunktion, Wenn dieselbe Nachricht verwendet wird, wird derselbe Digest erzeugt. Diese Funktionen sind jedoch in der Anzahl der Hash-Werte begrenzt, die sie zurückgeben dürfen. Dies schafft die Möglichkeit von sogenannten Hash-Kollisionen. Es gibt also mehr mögliche Nachrichten als Hash-Werte früher oder später (hoffentlich später), zwei verschiedene mich ssages erzeugt denselben Hash.

3. Hashes können aus drei grundlegenden Gründen geknackt werden.Erstens, weil sie eine deterministische, mathematische Ableitung ihrer Nachricht sind, finden Mathematiker (und damit Angreifer) schließlich eine mathematische Beziehung zwischen einer Nachricht und ihrem Hash oder zwischen zwei Nachrichten und ihren resultierenden Hashes. Was einmal zufällig aussah, ist nicht mehr so. Dies würde eine Reihe von Angriffen ermöglichen, die auf der Art der gefundenen Schwäche beruhen. Wenn es eine algorithmische Möglichkeit gibt, bei gegebener Nachricht und ihrem Hash eine kollidierende Nachricht zu generieren, ist dies ein Problem. Wenn es eine Möglichkeit gibt, eine Nachricht zu manipulieren und den resultierenden Hash vorherzusagen, ist dies ein anderes Problem. Wenn es tatsächlich eine Möglichkeit gibt, den Hash umzukehren und eine Nachricht aus dem Hash zu erzeugen, die beim erneuten Hashing denselben Hash erzeugt, ist dies ein „ernstes Problem.

   Zweitens, da Hashes früher oder später eine begrenzte Digest-Größe haben, erzeugen zwei Nachrichten denselben Hash. Dies bedeutet, dass ein Angreifer nicht die Nachricht finden muss, mit der Sie einen bestimmten Hash erzeugen ;; Alles, was er tun muss, ist, eine Nachricht zu finden, die denselben Hash erzeugt. Die Chancen dafür sind gering, theoretisch eine Chance von so vielen möglichen Hashes, aber immer noch besser als eine im Unendlichen.

   Schließlich gibt es, obwohl es viele mögliche Nachrichten gibt, eine weitaus kleinere Anzahl der wahrscheinlichen Nachrichten. Die Nachrichten, die wir normalerweise an Hash-Funktionen weitergeben, haben normalerweise eine gewisse Struktur (basierend auf Sprache, Inhalt, elektronischer Formatierung und Zweck), was bedeutet, dass wir bei einem bestimmten Teil der Nachricht andere Teile der Nachricht genauer erraten können. In informationswissenschaftlichen Begriffen bedeutet dies, dass Nachrichten, die in Hashes konvertiert werden, häufig eine niedrigere Entropie aufweisen als die Hash-Funktion selbst; Einfach ausgedrückt kann eine Hash-Funktion, die 256-Bit-Digests erzeugt, theoretisch jede Permutation dieser Bits erzeugen, 2 ^ 256. Wenn es jedoch beispielsweise nur 10.000 mögliche Nachrichten gibt, die jemals von einem auf Angriffe untersuchten System in diese Hash-Funktion eingegeben werden könnten, werden nur 10.000 der 2 ^ 256 möglichen Hash-Werte jemals gesehen, und was noch wichtiger ist, eine Der Angreifer müsste im schlimmsten Fall nur alle 10.000 möglichen Eingaben versuchen, um diejenige zu finden, die den gesuchten Hashwert erzeugt.

Kommentare

• Und aus diesem Grund liebe ich die Sache mit der Stapelaustausch-Site der IT-Sicherheit ‚.
• Auch Ihre Erklärung von # 1 ist genau das, was ich brauchte. Ich habe jedoch eine Frage. Es scheint, dass “ Hashes “ wie Zahlenversionen für eine bestimmte Sache sind (in diesem Fall Passwörter). Wenn ich also eine Website habe und 100000 Leute sich anmelden. Dann verwenden 50% das Passwort “ Passwort “ Ich kann eine Menge Platz sparen, indem ich nur den Hash-Wert von “ Passwort “ tonnenweise anstelle von Passwort?
• Nun, wenn Sie ‚ verwendet einen sicheren Hash (> = 256-Bit-Digest-Größe) und speichert dann den Hash-Wert von “ password “ erhöht Ihre Speichergröße. Wenn ein Angreifer jemals feststellen sollte, dass 50% der Benutzerkonten denselben Kennwort-Hash haben, weiß er ‚, dass alles, was er ‚ Ich muss nur ein Passwort knacken und er hat Zugriff auf 50% der Benutzerkonten. Sie sollten “ salzen “ Ihre Passwort-Hashes; Es gibt verschiedene Methoden, aber das Endergebnis ist, dass dasselbe Passwort, das von demselben Algorithmus gehasht wurde, aufgrund eines zusätzlichen eindeutigen Salt-Werts für jedes Konto einen anderen Digest erzeugt.