Hash Collision

Was ist Hash Collision?

Hash Collision liegt vor, wenn zwei unterschiedliche Eingaben exakt denselben Hash ergeben. Stell dir zwei verschiedene Schlüssel vor, die ausgerechnet dasselbe digitale Schloss öffnen. Selten, aber wenn es mit einem ungeeigneten Algorithmus passiert, kann es problematisch werden.

Wie Hash Collision funktioniert

Denk an einen Hash als kleines Etikett für große Daten. Hier eine kurze Tour von Eingabe bis zum Fehler.

1. Eingabe: Man beginnt mit einer Nachricht, Datei oder Transaktion.
2. Hash: Eine Funktion aus der Familie der kryptographischen Hashfunktionen wandelt diese Eingabe in eine Zeichenfolge fester Länge um.
3. Kollision: Da Ausgaben begrenzt, Eingaben jedoch unbegrenzt sind, können zwei unterschiedliche Eingaben auf dieselbe Ausgabe abgebildet werden.
4. Angriff: Eine ernsthafte Bedrohung tritt ein, wenn jemand gezielt zwei unterschiedliche Eingaben erzeugen kann, die kollidieren, und dann eine gegen die andere austauscht.
5. Abwehr: Gute Algorithmen machen diese Suche astronomisch teuer, so dass zufälliges Raten Zeit und Geld kostet.

Genau, das ist die Idee.

Warum Hash Collision wichtig ist

Warum sollte man sich für diese unauffällige Ecke der Mathematik und des Codes interessieren?

• Vorteil: Hohe Kollisionsresistenz sorgt dafür, dass Datenkennzeichnungen eindeutig bleiben, sodass weniger Raum für verschlagene Tricks bleibt.
• Perspektive: Kollisionen gefährden die Integrität von Dingen wie Blockchain, Softwareupdates und Dateiüberprüfungen.
• Relevanz: Man trifft es in Wallets, Exchanges, Beweisen und Prüfwerkzeugen, die auf Hashgleichheit vertrauen.

Hauptmerkmale von Hash Collision

Was dieses Phänomen auszeichnet und warum es sich zu merken lohnt:

• Unvermeidbar: Bei endlichen Ausgaben und unbegrenzten Eingaben kollidiert nach dem Schubfachprinzip irgendwann ein Paar.
• Schwierig: Bei modernen Hashes ist das gezielte Finden einer Kollision rechnerisch extrem aufwendig.
• Signaturen: Viele digitale Signaturen signieren einen Hash, daher schützt Kollisionsresistenz Unterzeichner vor Täuschung durch Austausch von Nachrichten.

Wie wird Hash Collision berechnet?

Man kann den Aufwand mit der Geburtstagsidee schätzen. Für einen k Bit Hash ist die Anzahl zufälliger Versuche, die für etwa fünfzigprozentige Chance auf eine beliebige Kollision nötig sind, ungefähr die Quadratwurzel von zwei hoch k, multipliziert mit etwa 1.1774.

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

Beispiel: Bei k gleich 256 sind die erforderlichen Versuche unvorstellbar zahlreich, weshalb durch Bruteforce eine Kollision zu erzielen kein Wochenendprojekt ist.

Varianten

Verschiedene Varianten tauchen in Forschung und Angriffen auf:

• Kollision: Zwei verschiedene Eingaben teilen denselben Hash.
• Second: Gegeben eine Eingabe, finde eine andere, die denselben Hash besitzt.
• Preimage: Gegeben einen Hash, finde eine Eingabe, die darauf abgebildet wird.
• Prefix: Bei gewähltem Präfix werden zwei Nachrichten mit unterschiedlichen gewählten Präfixen erzeugt, die am Ende denselben Hash haben.

Beispiel

Wenn ein Angreifer zwei unterschiedliche Transaktionen mit derselben txid erzeugen könnte, könnte er versuchen, durch Double Spending zu betrügen, indem er das eine Duplikat nach Ihrer Signatur austauscht.

Interessante Tatsache

MD5 Kollisionen wurden vor Jahrzehnten gezeigt, und das SHAttered Projekt erzeugte eine öffentliche SHA1 Kollision mit zwei verschiedenen PDFs, ein eindrucksvoller Beleg, der die Branche dazu brachte, den Algorithmus außer Gebrauch zu setzen.

Fazit

Kurz gesagt: Hash Collision ist der seltene Fall, dass zwei unterschiedliche Eingaben denselben digitalen Fingerabdruck teilen, und moderne Kryptografie sorgt dafür, dass das mehrheitlich Trivia bleibt.