Was ist der Avalanche Effect?
Wenn du bei einer kryptografischen Hashfunktion nur eine winzige Änderung an der Eingabe vornimmst, kann sich der resultierende Hashwert sehr stark verändern.
Genau dieses Verhalten beschreibt der Avalanche Effect, auf Deutsch auch Lawineneffekt.
Ein einfaches Beispiel:
Hello World
und:
hello World
Die beiden Texte unterscheiden sich nur durch einen einzigen Buchstaben: Aus einem großen H wurde ein kleines h.
Berechnen wir für beide Texte den SHA-256-Hash, erhalten wir:
Hello World
a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
und:
hello World
db4067cec62c58bf8b2f8982071e77c082da9e00924bf3631f3b024fa54e7d7e
Obwohl sich die Eingaben kaum unterscheiden, sehen die beiden Hashwerte völlig unterschiedlich aus.
Das ist kein Zufall, sondern eine wichtige Eigenschaft beim Design kryptografischer Hashfunktionen.
Was eine Hashfunktion grundsätzlich macht, erkläre ich im Artikel Was ist eine Hashfunktion?.
Was bedeutet Avalanche Effect?
Der Begriff beschreibt vereinfacht folgendes Verhalten:
Eine kleine Änderung an der Eingabe führt zu einer großen Änderung der Ausgabe.
Beim Avalanche Effect betrachtet man insbesondere, was passiert, wenn ein einzelnes Bit der Eingabe verändert wird.
Bei gutem Avalanche-Verhalten erwartet man, dass sich dabei im Durchschnitt ungefähr die Hälfte der Ausgabebits verändert.
Bei SHA-256 besteht die Ausgabe aus 256 Bit.
Das bedeutet:
256 × 0,5 = 128
Über viele entsprechende Vergleiche würde man daher im Mittel ungefähr 128 veränderte Bits erwarten.
Wichtig ist dabei das Wort im Mittel.
Der Avalanche Effect bedeutet nicht, dass bei jeder einzelnen Änderung exakt 128 der 256 Bits wechseln müssen.
Dieses Beispiel verändert tatsächlich nur ein Bit
Bei:
Hello World
und:
hello World
wurde sichtbar ein Zeichen verändert.
Interessanterweise unterscheiden sich H und h in ihrer ASCII- und UTF-8-Darstellung tatsächlich nur in einem einzigen Bit.
H = 01001000
h = 01101000
↑
Damit ist dieses Beispiel nicht nur eine Änderung eines einzelnen Zeichens, sondern tatsächlich ein Single-Bit-Flip in der Eingabe.
Das macht es besonders geeignet, um den Avalanche Effect zu demonstrieren.
Probier den Avalanche Effect selbst aus
Am einfachsten lässt sich der Effekt verstehen, wenn du ihn selbst ausprobierst.
Ändere in einer der beiden Eingaben beispielsweise nur einen Buchstaben, eine Zahl oder ein Leerzeichen.
Avalanche Effect
Schon eine minimale Änderung der Eingabe – hier nur ein einziger Buchstabe – führt bei SHA-256 zu einem komplett anderen Hash. Das nennt man den Avalanche-Effekt (Lawineneffekt).
Bei einem idealen Avalanche-Effekt weichen im Schnitt rund 50 % der Bits ab – gemessen über viele Eingaben hinweg. Das ist ein statistischer Durchschnitt, keine Garantie für jede einzelne Änderung.
Du findest dieses Tool auch im Tools-Bereich.
Die Komponente berechnet beide SHA-256-Hashwerte direkt in deinem Browser und vergleicht anschließend alle 256 Bits miteinander.
Für:
Hello World
hello World
unterscheiden sich 124 von 256 Bits.
Das entspricht:
124 / 256 × 100
≈ 48,4 %
Eine Änderung von nur einem Eingabebit führt hier also dazu, dass sich fast die Hälfte des gesamten Hashwerts verändert.
Dieses einzelne Beispiel veranschaulicht den Avalanche Effect. Es ist jedoch kein Beweis für die kryptografische Qualität von SHA-256. Dafür müsste das Verhalten systematisch über viele Eingaben und Bitänderungen untersucht werden.
Was verändert sich eigentlich?
Hashwerte sehen wir meistens als Hexadezimaldarstellung:
a591a6d40bf420404a011733cfb7b190d...
Der SHA-256-Hashwert besteht jedoch aus 256 Bits.
Ein Hex-Zeichen repräsentiert vier Bits.
Deshalb entsprechen:
256 Bit
÷ 4
= 64 Hex-Zeichen
Ein vollständiger SHA-256-Hash wird daher normalerweise als 64 Hex-Zeichen dargestellt.
Wenn ich beim Avalanche Effect von veränderten Bits spreche, vergleiche ich nicht einfach die sichtbaren Hex-Zeichen der beiden Hashwerte.
Stattdessen werden die tatsächlichen 256 Bits miteinander verglichen.
Für jede Position wird geprüft:
Bit A = Bit B?
oder:
Bit A ≠ Bit B?
Anschließend lässt sich zählen, wie viele der 256 Positionen unterschiedlich sind.
Genau das macht auch die interaktive Demonstration weiter oben.
Warum ungefähr 50 Prozent?
Beim Avalanche Effect soll eine kleine Änderung der Eingabe möglichst breit über die Ausgabe verteilt werden.
Ändert man ein einzelnes Eingabebit, sollte sich bei gutem Avalanche-Verhalten im Durchschnitt ungefähr die Hälfte der Ausgabebits verändern.
Für einen 256-Bit-Hash entspricht das im Mittel:
256 × 0,5
= 128
veränderten Bits.
Die 50 Prozent sind dabei eine statistische Erwartung über viele Beobachtungen und keine feste Vorgabe für einen einzelnen Hashvergleich.
Das Strict Avalanche Criterion
Eine verwandte, strengere Eigenschaft ist das Strict Avalanche Criterion, kurz SAC. Es wurde von Webster und Tavares in ihrer Arbeit zum Design von S-Boxen eingeführt und grenzt den Avalanche Effect von einer strengeren, bitweisen Anforderung ab.
Vereinfacht verlangt das SAC, dass sich jedes einzelne Ausgabebit beim Ändern eines einzelnen Eingabebits mit einer Wahrscheinlichkeit von 50 Prozent verändert.
Damit sollte man zwei Aussagen unterscheiden:
Avalanche Effect:
Beim Ändern eines Eingabebits verändert sich im Durchschnitt ungefähr die Hälfte der Ausgabebits.
Strict Avalanche Criterion:
Jedes einzelne Ausgabebit verändert sich bei einem solchen Bit-Flip mit einer Wahrscheinlichkeit von 1/2.
Die beiden Konzepte hängen eng zusammen, sind aber nicht identisch.
Warum sind es nicht immer genau 50 Prozent?
Bei diesem Beispiel verändern sich 124 von 256 Bits.
Das sind ungefähr 48,4 Prozent.
Bei anderen Eingaben können es beispielsweise 121, 130 oder 136 Bits sein.
Das widerspricht dem Avalanche Effect nicht.
Man kann sich das ähnlich wie bei vielen Münzwürfen vorstellen.
Wenn du eine faire Münze zehnmal wirfst, müssen nicht exakt fünf Würfe Kopf und fünf Würfe Zahl ergeben.
Über viele Versuche wird jedoch das zugrunde liegende statistische Verhalten sichtbar.
Auch beim Avalanche Effect geht es deshalb nicht darum, bei einem einzelnen Beispiel exakt 50 Prozent zu erreichen.
Entscheidend ist das Verhalten über viele unterschiedliche Eingaben und Bitänderungen hinweg.
Eine kleine Änderung breitet sich durch die Berechnung aus
Der Name Avalanche Effect beschreibt dieses Verhalten anschaulich.
Eine kleine Veränderung löst eine Art Lawine aus:
kleine Änderung
↓
Verarbeitung durch die Hashfunktion
↓
Änderungen breiten sich aus
↓
viele veränderte Ausgabebits
Bei SHA-256 wird die Eingabe in Blöcken verarbeitet und durch mehrere Verarbeitungsschritte und Runden transformiert.
Dabei beeinflussen Zwischenergebnisse wiederum spätere Berechnungen.
Eine Änderung an der Eingabe kann sich dadurch durch die weitere Berechnung ausbreiten und schließlich viele Bits des resultierenden Hashwerts beeinflussen.
Warum ist der Avalanche Effect wichtig?
Stell dir eine schlecht konstruierte Hashfunktion vor, bei der eine kleine Änderung der Eingabe auch nur eine kleine, systematische Änderung des Hashwerts verursacht.
Bei kryptografischen Hashfunktionen möchte man solche einfachen lokalen Zusammenhänge vermeiden.
Eine kleine Änderung soll sich stattdessen stark über die Ausgabe ausbreiten.
Der Avalanche Effect ist deshalb eine wichtige Eigenschaft beim Design kryptografischer Funktionen.
Er allein beweist allerdings noch nicht, dass eine Hashfunktion kryptografisch sicher ist.
Eine Hashfunktion kann ein gutes Avalanche-Verhalten zeigen und trotzdem andere kryptografische Schwächen besitzen.
Avalanche Effect bedeutet nicht Zufall
Wenn zwei SHA-256-Hashwerte völlig unterschiedlich aussehen, könnte man vermuten, dass SHA-256 zufällige Ergebnisse erzeugt.
Das ist jedoch nicht der Fall.
SHA-256 ist deterministisch.
Das bedeutet:
gleiche Eingabe
+
gleicher Algorithmus
=
gleicher Hashwert
Immer.
Wenn du heute den SHA-256-Hash von:
Hello World
berechnest und morgen erneut exakt dieselbe Eingabe verwendest, erhältst du denselben Hashwert.
Der Avalanche Effect bedeutet also nicht, dass die Hashfunktion zufällig arbeitet.
Die Ausgabe verändert sich bei kleinen Änderungen der Eingabe stark, obwohl die Berechnung selbst vollständig deterministisch ist.
Was Determinismus und weitere grundlegende Eigenschaften von Hashfunktionen bedeuten, erkläre ich ausführlicher im Artikel Was ist eine Hashfunktion?.
Avalanche Effect ist nicht Collision Resistance
Eine weitere wichtige Abgrenzung betrifft Hash Collisions.
Der Avalanche Effect beschreibt, wie stark sich der Hashwert verändert, wenn sich die Eingabe verändert.
Collision Resistance beschäftigt sich dagegen mit einer anderen Frage:
Wie schwierig ist es, zwei unterschiedliche Eingaben zu finden, die denselben Hashwert erzeugen?
Das sind zwei unterschiedliche Eigenschaften.
Ein gutes Avalanche-Verhalten bedeutet deshalb nicht automatisch, dass eine Hashfunktion ausreichend kollisionsresistent ist.
Was eine Hash Collision ist und warum Kollisionen bei Hashfunktionen mathematisch unvermeidbar sind, erkläre ich ausführlich im Artikel Was ist eine Hash Collision?.
Kann man den Avalanche Effect messen?
Ja.
Eine einfache Demonstration besteht darin:
- eine Eingabe zu erzeugen,
- genau ein Bit der Eingabe zu verändern,
- beide Hashwerte zu berechnen,
- die unterschiedlichen Ausgabebits zu zählen.
Bei SHA-256 erhält man anschließend einen Wert zwischen 0 und 256 unterschiedlichen Bits.
Der prozentuale Unterschied lässt sich berechnen mit:
unterschiedliche Bits
──────────────────── × 100
256
Bei diesem Beispiel:
124
─── × 100
256
ergibt das:
48,4375 %
gerundet also:
48,4 %
Ein einzelner solcher Wert reicht allerdings nicht aus, um die Qualität einer Hashfunktion zu beurteilen.
Dafür müsste man das Verhalten systematisch über viele unterschiedliche Eingaben und Bitänderungen untersuchen.
Die Demonstration auf dieser Seite soll deshalb vor allem sichtbar machen, was mit Avalanche Effect gemeint ist.
Ist ein hoher Prozentwert automatisch besser?
Nein.
Wenn sich bei einem Vergleich beispielsweise 70 Prozent der Bits unterscheiden, bedeutet das nicht automatisch, dass dieses Ergebnis besser ist als eines mit 51 Prozent.
Das gewünschte Verhalten besteht nicht darin, möglichst viele Bits zu verändern.
Deshalb sollte man den Prozentwert der Demonstration nicht wie einen Qualitäts-Score lesen:
48 % = schlecht
50 % = perfekt
70 % = besonders sicher
So funktioniert der Avalanche Effect nicht.
Der angezeigte Wert beschreibt lediglich den konkreten Unterschied zwischen den beiden gerade berechneten Hashwerten.
Das Wichtigste in Kürze
Der Avalanche Effect beschreibt, wie stark sich die Ausgabe einer kryptografischen Funktion bei einer kleinen Änderung der Eingabe verändert.
Die wichtigsten Punkte:
- Bereits die Änderung eines einzelnen Eingabebits kann viele Bits des Hashwerts verändern.
- Bei gutem Avalanche-Verhalten erwartet man über viele Beobachtungen ungefähr 50 Prozent veränderte Ausgabebits.
- Bei SHA-256 wären das im Mittel ungefähr 128 von 256 Bits.
- Bei einem einzelnen Vergleich müssen es nicht exakt 128 Bits sein.
- Der Vergleich erfolgt auf Bit-Ebene und nicht anhand der sichtbaren Hex-Zeichen.
- Das Strict Avalanche Criterion stellt eine stärkere verwandte Anforderung an einzelne Ausgabebits.
- SHA-256 bleibt trotz des Avalanche Effects deterministisch.
- Avalanche Effect und Collision Resistance sind unterschiedliche Eigenschaften.
- Ein gutes Avalanche-Verhalten allein beweist nicht die kryptografische Sicherheit einer Hashfunktion.
Der Lawineneffekt macht damit eine wichtige Eigenschaft kryptografischer Hashfunktionen sichtbar:
Eine winzige Änderung am Anfang kann sich durch die gesamte Berechnung ausbreiten und am Ende einen stark veränderten Hashwert erzeugen.
Wie geht es weiter?
Mit Hashfunktionen, Hash Collisions und dem Avalanche Effect sind einige wichtige Grundlagen gelegt.
Als Nächstes kannst du dir genauer ansehen:
- Was ist Preimage Resistance?
- Was ist Second-Preimage Resistance?
- Was ist Collision Resistance?
- Wie funktioniert SHA-256?
- Das Birthday Paradox
- Warum ist MD5 unsicher?
- Warum gilt SHA-1 als unsicher?
Quellen und weiterführende Standards
Die folgenden Primär- und Normquellen bilden die Grundlage für die technischen Aussagen dieses Artikels:
-
National Institute of Standards and Technology (NIST), FIPS 180-4 – Secure Hash Standard (SHS) Offizielle Spezifikation von SHA-256 und der SHA-2-Familie.
-
National Institute of Standards and Technology (NIST), Hash Functions Übersicht über kryptografische Hashfunktionen und ihre Sicherheitseigenschaften.
-
A. F. Webster, S. E. Tavares, On the Design of S-Boxes, CRYPTO '85. Wissenschaftliche Arbeit zur Untersuchung des Avalanche Effects und zur Einführung des Strict Avalanche Criterion.