Entwicklertools · SHA-Hash-Rechner
Der Lawineneffekt: Warum ein geänderter Charakter einen SHA-Hash neu schreibt
· Wie es funktioniert
sha-256 Kryptographie Sicherheit Validierung
Ändern Sie einen Buchstaben und ungefähr die Hälfte der Ausgabebits wird umgedreht. In diesem Beitrag wird die Lawineneigenschaft erklärt, warum sie für die Manipulationserkennung unerlässlich ist und wie die Runden von SHA-2 sie erreichen.
Ich erwarte, dass sich der Hash ein wenig ändert – die Intuition, die die meisten Menschen mitbringen, und warum das Design sie absichtlich bricht
Die meisten Menschen erwarten, dass ähnliche Eingaben ähnliche Ausgaben hervorbringen. Ändern Sie ein Zeichen in einer Datei und der Digest sollte sich geringfügig ändern. Stattdessen sollen kryptografische Hashes das Gegenteil bewirken: Eine einzelne Bit-Änderung in der Eingabe sollte unvorhersehbar etwa die Hälfte der Ausgabebits umkehren. Diese Eigenschaft wird Lawineneffekt genannt und ist gewollt. Das Design dient einem bestimmten Zweck: Manipulationserkennung.
Der Lawineneffekt ist der Grund, warum „fast übereinstimmend“ in der Welt des Hashings kein Konzept ist. Ein Hash stimmt genau überein oder nicht. Es gibt kein „nah genug“. Diese Eigenschaft macht Hashing für Integritätsprüfungen und Inhaltsadressierung nützlich und macht schwache Hashing-Algorithmen aus Sicherheitsgründen unbrauchbar.
Avalanche bedeutet breite Output-Diffusion; Dieser Artikel erhebt keine unbegründete exakte Wahrscheinlichkeitsaussage
Formal bedeutet der Avalanche-Effekt, dass sich bei zwei Eingaben, die sich um ein einzelnes Bit unterscheiden, die Ausgabe-Digests in etwa 50 % ihrer Bits unterscheiden sollten. Für SHA-256 (256 bits der Ausgabe) sollte die Änderung eines Eingabebits ungefähr 128 Ausgabebits umkehren. Der Effekt ist nicht exakt; es ist eine statistische Eigenschaft. Aber es ist stark: In der Praxis wird jedes Bit der Eingabe gründlich mit jedem Bit der Ausgabe vermischt.
Warum etwa die Hälfte? Denn eine wirklich zufällige Ausgabe würde sich von einer anderen zufälligen Ausgabe im Durchschnitt genau in der Hälfte ihrer Bits unterscheiden (nach dem Schubladenprinzip und grundlegenden Statistiken). Eine gute Hash-Funktion nähert sich der Zufälligkeit an; Es erzeugt eine Ausgabe, die kein erkennbares Muster zu haben scheint. Die Hälfte der Bits, die im Durchschnitt umgedreht werden, ist das Kennzeichen der Zufälligkeit. Wenn ein Hash nur 10 % der Bits umdreht, könnte ein Angreifer Muster finden und diese ausnutzen.
Warum Manipulationserkennung sie braucht – kleine Änderungen an einem Dokument dürfen keinen nahezu identischen Hash erzeugen, den ein kurzer Blick erkennen würde
Die Manipulationserkennung basiert auf Lawinen. Wenn Sie eine Datei herunterladen und deren SHA-256 berechnen, ist der erwartete Digest ba7816... (als Beispiel). Ein Angreifer modifiziert die Datei, indem er ein Byte ändert. Der neue Digest ändert sich von ba7816... zu etwas wie 3d4e92... (völlig anders). Wenn Sie die Datei anhand des erwarteten Digests überprüfen, ist die Nichtübereinstimmung sofort und vollständig. Es gibt keinen Raum für Fehlinterpretationen: Die Datei wurde manipuliert.
Ohne Avalanche könnte ein Angreifer ein Byte ändern und der Digest würde sich möglicherweise nur geringfügig verschieben, zu ba7817... (eine Hexadezimalzahl anders). Ein beiläufiger Vergleich könnte den Unterschied übersehen. Ein Angreifer könnte sogar nach Eingaben suchen, die einen Digest erzeugen, der mit ba78 beginnt, und behaupten, die Datei sei authentisch. Avalanche macht dies unerschwinglich teuer: Selbst zwei Eingaben zu finden, bei denen die Digests mit den gleichen vier Hexadezimalziffern beginnen, erfordert mehr Arbeit, als das Design zulässt.
Wie sich die Runden ausbreiten, ändert sich – Drehungen, Additionen und nichtlineare Funktionen, die den Einfluss eines Bits auf den gesamten Zustand übertragen
Die Runden in SHA-256 (und die Runden in SHA-512) dienen der Verbreitung von Änderungen. In jeder Runde werden die Daten mithilfe nichtlinearer Funktionen (Auswahl, Mehrheit) und Rotationen gemischt. Eine Einzelbitänderung in der Eingabe geht in den Nachrichtenplan ein und breitet sich durch die Runden aus. Durch Drehungen werden die Bitpositionen verschoben. Nichtlineare Funktionen verbergen den Einfluss des Bits: Das Ändern eines Steuerbits in einer Auswahloperation kann je nach den ausgewählten Daten jedes der Ausgangsbits umdrehen.
Die anfänglichen Hash-Konstanten, die Nachrichtenplankonstanten, die Rotationsbeträge und die Anzahl der Runden wurden alle ausgewählt, um den Lawineneffekt zu maximieren. Diese Zahlen sind nicht willkürlich; Sie stammen aus der Spezifikation SHA-2 und wurden umfassend kryptoanalysiert. Jede Änderung der Konstanten oder der Rundenzahl würde zu einem anderen (wahrscheinlich schwächeren) Algorithmus führen.
Ausgearbeitetes Beispiel – Hashing zweier Eingaben, die sich um ein Zeichen unterscheiden, und Vergleich der Digests Stück für Stück
Das Testen einer Lawine ist unkompliziert. Hashen Sie die Eingabe abc und notieren Sie den Digest. Hashen Sie dann abc, gefolgt von einem Leerzeichen, oder ersetzen Sie ein Zeichen durch etwas anderes: abd. Vergleichen Sie die Hex-Ausgaben. Für SHA-256 unterscheidet sich etwa die Hälfte der Hexadezimalstellen von 64. Zähle sie. Der Testvektor aus dem ToolAcre-Beitrag: abc erzeugt ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. Eine leere Zeichenfolge erzeugt e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. Diese Digests haben keine gemeinsamen Hexadezimalziffern.
Probieren Sie dies mit dem ToolAcre-Rechner mit einer beliebigen Eingabe aus. Hash einen Satz. Dann ändern Sie einen Buchstaben und einen Hash erneut. Zählen Sie die unterschiedlichen Hexadezimalziffern. Sie werden feststellen, dass ungefähr die Hälfte (in den meisten Fällen 32 von 64) unterschiedlich ist. Das ist der Lawineneffekt in Aktion. Es ist eine Eigenschaft des Algorithmusdesigns und kein Zufall.
Avalanche bietet keine Ähnlichkeitssuche und quantifiziert auch nicht die Kollisionsresistenz
Avalanche erstellt keine Ähnlichkeitssuche oder ungefähre Übereinstimmung. Wenn Sie einen Digest ba7816... haben und einen ähnlichen Digest finden möchten, gibt es keine Verknüpfung. Sie müssen Kandidateneingaben erraten oder brutal erzwingen, jede einzelne hashen und auf eine genaue Übereinstimmung prüfen. Der Lawineneffekt sorgt dafür, dass jede Vermutung mit gleicher Wahrscheinlichkeit zu einem ähnlichen oder völlig anderen Ergebnis führt. Einige Hashing-Algorithmen (lokalitätssensitives Hashing genannt) sind darauf ausgelegt, die Ähnlichkeit zu wahren; Sie sind nützlich für die Erkennung und Clusterung von nahezu Duplikaten, es handelt sich jedoch nicht um kryptografische Hashes.
Avalanche schützt auch nicht vor einer gezielten Kollisionssuche. Ein Kryptoanalytiker kann immer noch nach zwei verschiedenen Eingaben suchen, die denselben Digest erzeugen, aber der Suchraum ist riesig. Eine gezielte Kollisionssuche ist eine andere Frage als die visuelle Diffusion. Dieser Artikel zitiert keine Geburtstagszahl oder Hardware-Zeitleiste, da er hier nicht abgeleitet wurde. Die vertretbare Grenze besteht darin, dass Lawinen allein weder die Kollisionsresistenz beweisen noch quantifizieren.
Takeaway: Keine Beinahe-Unfälle – probieren Sie das Ein-Zeichen-Experiment im ToolAcre SHA-Hash-Rechner aus und beobachten Sie, wie sich die gesamte Zusammenfassung ändert
Der ToolAcre SHA-Hash-Rechner führt die SHA-Algorithmen über die Web Crypto-Implementierung des Browsers aus. Sie können damit selbst eine Lawine verifizieren. Jede noch so kleine Präzision des Algorithmus fließt in die Ausgabe ein, und die Web-Crypto-Implementierung wird vom Browser-Anbieter geprüft und gewartet. Sie sehen, wie der echte Algorithmus auf echten Eingaben ausgeführt wird. Die kontraintuitive Eigenschaft, dass eine Zeichenänderung den gesamten Digest neu schreibt, ist kein Fehler; Es ist die Funktion, die dafür sorgt, dass Hashing funktioniert.
Wenn Sie einen Hash zur Integritätsprüfung verwenden, verlassen Sie sich auf Avalanche. Wenn Sie es für die Adressierung von Inhalten verwenden (z. B. Container-Image-Digests), sind Sie auf die Eigenschaft angewiesen, dass winzige Änderungen zu sehr unterschiedlichen Digests führen. Wenn Sie es in einer digitalen Signatur verwenden (wobei die Signatur über einen Hash der Nachricht berechnet wird), stellt der Lawineneffekt sicher, dass eine Manipulation der Nachricht eine erkennbare Änderung hervorruft. Die Eigenschaft ist die Grundlage der Hash-basierten Sicherheit.