Hash-Kollisionswahrscheinlichkeit
Eingaben
| Hash-Größe | 128 |
|---|---|
| Anzahl der Elemente | 1.000.000 |
Hash-Kollisionswahrscheinlichkeit
Kollisionswahrscheinlichkeit unter einer Menge von Hash-Werten abschätzen und ermitteln, wie viele Elemente für eine 50-%-Kollisionschance bei einer gegebenen Hash-Größe benötigt werden.
Eingaben
Hash-Parameter
Ergebnisse
Geben Sie einen Wert ein, um die Ergebnisse zu sehen.
Kollisionswahrscheinlichkeit
Hash-Kollisionswahrscheinlichkeit
Eine Hash-Funktion bildet eine Eingabe beliebiger Länge auf einen Ausgabewert fester Länge ab, den sogenannten Digest. Im Idealfall erzeugen keine zwei verschiedenen Eingaben denselben Digest — eine Eigenschaft, die als Kollisionsresistenz bezeichnet wird. Da der Ausgaberaum endlich ist, müssen Kollisionen jedoch existieren; die entscheidende Frage ist, wie viele Eingaben gehasht werden müssen, bis eine Kollision wahrscheinlich wird. Dieser Rechner quantifiziert diese Wahrscheinlichkeit mithilfe der Geburtstagsnäherung.
Das Geburtstagsparadoxon
In einer Gruppe von 23 zufällig ausgewählten Personen besteht bereits eine Wahrscheinlichkeit von über 50 %, dass zwei davon am selben Tag Geburtstag haben — obwohl es 365 mögliche Geburtstage gibt. Die Wahrscheinlichkeit ist so viel höher als intuitiv erwartet, weil sie für jedes Paar innerhalb der Gruppe gilt und nicht nur für eine Übereinstimmung mit einem vorgegebenen Datum. Dieselbe Asymmetrie bestimmt Hash-Kollisionen: Zwei Eingaben mit demselben Hash zu finden (Kollision) ist weit einfacher als eine Eingabe zu finden, die einen bestimmten Ziel-Hash erzeugt (Urbild).
Formel
Für eine Hash-Funktion mit Ausgabe-Bits hat der Suchraum gleichwahrscheinliche Werte. Bei zufällig gehashten Elementen ist die exakte Kollisionswahrscheinlichkeit das Komplement der Wahrscheinlichkeit, dass alle Ausgabewerte verschieden sind:
p=1−k=0∏n−1(1−2bk)Für großes und moderates liefert die Geburtstagsnäherung eine einfachere geschlossene Form:
p≈1−e−n2/(2⋅2b)Die Anzahl der Elemente, bei der die Wahrscheinlichkeit 50 % erreicht:
n50%=2⋅2b⋅ln2Rechenbeispiel
Für einen 32-Bit-Hash (wie CRC32 bei Prüfsummen):
n50%=2×232×ln2=2×4294967296×0,6931≈5954124768≈77163Bereits bei 77.163 Dateien in einem Archiv besteht eine Wahrscheinlichkeit von etwa 50 %, dass zwei denselben 32-Bit-CRC teilen. Zur Bestätigung mit der Näherungsformel:
p=1−e−771632/(2×232)≈1−e−0,693≈0,50Dies erklärt, warum CRC32 als eindeutiger Bezeichner in großen Sammlungen ungeeignet ist, obwohl es ein ausgezeichneter Fehlererkennungscode für kurze Datenströme ist.
Sicherheitsimplikationen
Die Geburtstagschranke legt fest, dass eine Hash-Funktion mit Bits nur Bits Kollisionsresistenz bietet. Ein Angreifer benötigt etwa Hash-Auswertungen, um eine Kollision zu finden — nicht . Deshalb werden kryptografische Hash-Funktionen mit mehr Ausgabe-Bits als das angestrebte Sicherheitsniveau entworfen:
| Hash-Funktion | Ausgabe | Kollisionsresistenz |
|---|---|---|
| MD5 | 128 Bits | ~ (in der Praxis gebrochen) |
| SHA-1 | 160 Bits | ~ (in der Praxis gebrochen) |
| SHA-256 | 256 Bits | ~ (aktueller Standard) |
| SHA-3-512 | 512 Bits | ~ (hohe Sicherheit) |
MD5 und SHA-1 gelten nicht allein wegen der Geburtstagschranke als gebrochen, sondern weil Forscher algorithmische Schwächen entdeckt haben, mit denen sich Kollisionen weit schneller als mit Operationen finden lassen. MD5-Kollisionen lassen sich auf handelsüblicher Hardware mit veröffentlichten Methoden in Minutenschnelle erzeugen.
Für eine verwandte Analyse von Passwort-Suchräumen siehe Passwort-Entropie-Rechner.
Häufig gestellte Fragen (FAQ)
Was ist das Geburtstagsparadoxon in der Kryptografie?
Das Geburtstagsparadoxon beschreibt das kontraintuitive Ergebnis, dass in einer Gruppe von nur 23 Personen die Wahrscheinlichkeit, dass zwei davon am selben Tag Geburtstag haben, bereits über 50 % liegt — obwohl es 365 mögliche Geburtstage gibt.
Dieselbe Mathematik gilt für Hash-Funktionen: Ein Angreifer benötigt nur etwa √(2^b) = 2^(b/2) gehashte Elemente, um mit 50-prozentiger Wahrscheinlichkeit zwei mit demselben Ausgabewert zu finden. Dies bezeichnet man als Geburtstagsangriff. Bei einem 128-Bit-Hash wie MD5 liegt dieser Schwellenwert bei etwa 2^64 ≈ 1,8 × 10¹⁹ Elementen — weit weniger als die 2^128 Kombinationen, die ein Urbild-Angriff erfordern würde.
Warum benötigt ein Geburtstagsangriff nur halb so viele Bits?
Ein Urbild-Angriff muss einen bestimmten Hash-Wert finden und muss daher den gesamten Raum der Größe 2^b durchsuchen. Ein Geburtstagsangriff benötigt lediglich irgendein Paar von Eingaben mit demselben Hash. Nach der Geburtstagschranke übersteigt die Wahrscheinlichkeit, ein solches Paar zu finden, 50 % nach etwa 2^(b/2) Stichproben.
Deshalb werden kryptografische Hash-Funktionen typischerweise mit doppelt so vielen Ausgabe-Bits wie das angestrebte Sicherheitsniveau entworfen: Ein 256-Bit-Hash bietet 128-Bit-Kollisionsresistenz.
Warum gelten MD5 und SHA-1 als unsicher?
MD5 (128 Bits) und SHA-1 (160 Bits) wurden durch praktische Kollisionsangriffe gebrochen — nicht nur durch probabilistische Geburtstags-Angriffe, sondern durch algorithmische Schwächen, die Kollisionen weit effizienter finden, als die Geburtstagschranke vorhersagt. Im Jahr 2004 demonstrierten Forscher MD5-Kollisionen; 2017 produzierte Googles SHAttered-Projekt die erste öffentlich bekannte SHA-1-Kollision.
Für nicht-kryptografische Zwecke wie Prüfsummen und inhaltsbezogene Adressierung sind diese Funktionen weiterhin geeignet, sollten aber nicht mehr dort eingesetzt werden, wo Kollisionsresistenz gefordert ist, etwa bei digitalen Signaturen oder Zertifizierungsstellen.
Was ist der Unterschied zwischen Kollision und Urbild?
Eine Kollision bedeutet, zwei verschiedene Eingaben x und y zu finden, für die hash(x) = hash(y) gilt. Ein Urbild bedeutet, eine Eingabe x zu finden, die einen bestimmten Zielwert h erzeugt — schwieriger, weil beide Eingaben nicht frei gewählt werden können. Ein zweites Urbild bedeutet, eine andere Eingabe y mit demselben Hash wie eine bekannte Eingabe x zu finden.
Diese Eigenschaften sind in aufsteigender Schwierigkeit geordnet: Kollisionsresistenz ist die schwächste, Zweites-Urbild-Resistenz die stärkste Eigenschaft. Hash-Funktionen für digitale Signaturen müssen Zweites-Urbild-Angriffe widerstehen; solche für Hash-Tabellen oder Bloom-Filter benötigen nur eine schwache Kollisionsresistenz.