Begriff
Collision (Hash Collision)
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Stell dir vor, eine Hashfunktion ist wie ein Geburtstag. Es gibt 365 mögliche Tage. Es gibt aber 8 Milliarden Menschen. Logisch müssen sich viele Menschen einen Geburtstag teilen. Beim Hashing ist es genauso. Der Output ist begrenzt (z. B. 128 Bit beim MD5). Die möglichen Inputs sind unendlich. Eine Kollision ist der seltene Fall, dass zwei völlig verschiedene Dateien zufällig den gleichen Hashwert ergeben. In der Kryptografie ist das eine Katastrophe: Ich könnte einen harmlosen Vertrag unterschreiben, und du tauschst ihn gegen einen bösen Vertrag aus, der denselben Hash (Fingerabdruck) hat. Die Unterschrift wäre immer noch gültig!
Merksatz: Das Ereignis, wenn zwei unterschiedliche Eingabedaten denselben Hashwert erzeugen. In der Kryptografie gilt eine Hashfunktion als "gebrochen", wenn Kollisionen künstlich erzeugt werden können.
Wenn du HashMaps (Programmier-Datenstruktur) nutzt: Kollisionen sind normal. Die HashMap löst das (z. B. durch Listen im Bucket). Es macht das Programm nur etwas langsamer.
Wenn du Signaturen (Krypto) nutzt: Nutze niemals MD5 oder SHA-1. Forscher haben für beide Verfahren Kollisionen erzeugt ("SHAttered" Attacke: Zwei PDFs haben denselben SHA-1 Hash, zeigen aber unterschiedlichen Text). Nutze SHA-256 oder SHA-3.
1. Birthday Paradox
Warum findet man Kollisionen schneller als gedacht? In einem Raum mit 23 Leuten ist die Chance 50%, dass zwei am gleichen Tag Geburtstag haben. Bei Hashes bedeutet das: Wenn der Hash $N$ Bits lang ist, muss man nicht $2^N$ Versuche machen, sondern nur $2^{N/2}$, um eine Kollision zu finden (Quadratwurzel). Bei MD5 (128 Bit) reicht also ein Aufwand von $2^{64}$, was machbar ist.
2. Preimage vs. Collision Resistance
- Collision Resistance: Ich finde irgendein Paar (A, B) mit
hash(A) == hash(B). (Der Angreifer wählt beide Nachrichten). - Preimage Resistance: Ich gebe dir Hash(A). Du musst A finden. (Viel schwerer!).
- Second Preimage Resistance: Ich gebe dir A. Du musst ein B finden, sodass
hash(A) == hash(B). (Auch sehr schwer). MD5 ist "Collision Broken", aber "Preimage" ist theoretisch noch sehr schwer. Trotzdem: Weg damit.
3. Chosen-Prefix Collision
Der gefährlichste Angriff (Flame Virus). Der Angreifer kann zwei Dateien mit beliebigem unterschiedlichem Anfang so manipulieren, dass sie am Ende den gleichen Hash haben, indem er "Collision Blocks" anhängt. Damit konnte man gefälschte Windows-Update-Zertifikate erstellen.
Differential Cryptanalysis
Wie findet man real Kollisionen für gebrochene Verfahren wie MD5? Brute-Force dauert selbst dort zu lange. Man nutzt Differential Cryptanalysis. Forscher beobachten, wie spezifische, winzige Änderungen im Input (z. B. Bit-Flipping) durch die Runden der Hashfunktion propagieren. Bei schwachen Algorithmen (MD5) pflanzt sich die Differenz so vorhersagbar fort, dass man am Ende exakt die Bits im Input berechnen kann, die genullt oder gesetzt werden müssen, um denselben Output-State wie bei einem anderen Input zu erreichen.
Fixed-Prefix vs. Chosen-Prefix Kollisionen
Eine normale (Fixed-Prefix) Kollision findet zwei Müll-Dateien mit demselben Hash.
Die Chosen-Prefix Kollision ist die Waffe von Geheimdiensten (wie bei Stuxnet / Flame eingesetzt).
Der Angreifer erhält Prefix A (Gültiges Zertifikat für Microsoft Corp) und Prefix B (Böses Malware-Zertifikat).
Beide Prefixe sind vorgegeben (Chosen). Der Algorithmus muss nun jeweils einen "Collision Block" berechnen und anhängen (PrefixA + BlockA und PrefixB + BlockB), sodass am Ende genau derselbe MD5-Hash herauskommt. Dies requiriert massive Rechenzentren, ist aber verheerend, da der Hash für das gute und extrem toxische Zertifikat matcht.
Quantum Computing & Grover's Algorithm
Was bedeuten Quantencomputer für Hashfunktionen? Während Shor's Algorithmus asymmetrische Krypto (RSA) bricht, ist für Hashfunktionen Grover's Algorithmus relevant. Grover beschleunigt die Suche nach Preimages dramatisch (von $O(N)$ auf $O(\sqrt{N})$) und Kollisionen ($O(\sqrt[3]{N})$). Das bedeutet, dass SHA-256 durch Quantencomputer grob auf die Sicherheit eines 128-Bit Hashes halbiert wird. Deshalb weisen Post-Quantum-Direktiven (NIST) an, für langlebige Sicherheit auf SHA-384 oder SHA-512 (oder SHA-3 Äquivalente) umzusteigen, um einen ausreichend großen Output-Raum gegen Grover-basierte Bruteforce-Attacken zu erhalten.
Quick-Check
Git und SHA-1?
Git nutzt SHA-1. Theoretisch gefährlich. Aber Git nutzt einen "Hardened SHA-1", der bekannte Kollisions-Attacken erkennt. Und Git switcht bald auf SHA-256.Ist Hash-Länge alles?
Fast. Länger ist meist besser (wegen Birthday Paradox). Aber der Algorithmus muss auch mathematisch robust sein ("gut mischen").UUID Kollision?
UUIDv4 hat 122 Zufalls-Bits. Die Chance einer Kollision ist so absurd klein, dass man sagt: "Passiert nicht, bevor die Sonne explodiert."