Preimage-Resistenz und Kollisionsresistenz erklärt

Definition

Kryptografische Hash-Funktionen fungieren als digitale Fingerabdrücke für Daten. Sie nehmen eine Eingabe beliebiger Größe entgegen und erzeugen eine Ausgabe fester Größe, bekannt als Hash-Wert oder Nachrichten-Digest. Dieser Prozess ist deterministisch, was bedeutet, dass dieselbe Eingabe immer dieselbe Ausgabe erzeugt. Ein entscheidender Aspekt sicherer Hash-Funktionen ist jedoch ihre Einweg-Eigenschaft: Es ist rechnerisch undurchführbar, den Prozess umzukehren und die ursprüngliche Eingabe aus ihrer Hash-Ausgabe abzuleiten. Diese Eigenschaft untermauert zwei vitale Sicherheitsmerkmale: die Preimage-Resistenz und die Kollisionsresistenz.

Die Preimage-Resistenz bedeutet, dass es für eine gegebene Hash-Ausgabe rechnerisch undurchführbar ist, die ursprüngliche Eingabenachricht zu finden, die sie erzeugt hat. Einfacher ausgedrückt: Wenn man nur den digitalen Fingerabdruck hat, kann man die Originaldaten praktisch nicht rekonstruieren.

Die Kollisionsresistenz bedeutet, dass es rechnerisch undurchführbar ist, zwei verschiedene Eingabenachrichten zu finden, die genau dieselbe Hash-Ausgabe erzeugen. Obwohl mathematisch Kollisionen existieren müssen, da die Ausgabegröße fest und die Eingabegröße potenziell unendlich ist (Schubfachprinzip), macht eine starke Hash-Funktion das Finden eines solchen Paares praktisch unmöglich.

Kernaussage

Preimage-Resistenz und Kollisionsresistenz bilden das Fundament der kryptografischen Sicherheit, insbesondere innerhalb der Blockchain-Technologie. Sie gewährleisten die Integrität von Daten, die Authentizität digitaler Signaturen und die Unveränderlichkeit von Transaktionsaufzeichnungen. Ohne diese Eigenschaften wären die grundlegenden Vertrauensmechanismen, die Kryptowährungen und dezentrale Systeme untermauern, schwerwiegend gefährdet, was zu potenziellem Betrug und Systeminstabilität führen könnte.

Mechanik

Die "Einweg"-Eigenschaft einer kryptografischen Hash-Funktion bezieht sich nicht auf mathematische Unmöglichkeit, sondern auf rechnerische Undurchführbarkeit. Dies bedeutet, dass es zwar theoretisch möglich ist, einen Hash umzukehren oder eine Kollision zu finden, der dafür erforderliche Rechenaufwand und die benötigte Zeit jedoch so immens wären, dass sie mit der aktuellen Technologie praktisch unerreichbar sind.

Die Preimage-Resistenz wird hauptsächlich durch einen Preimage-Angriff herausgefordert, der im Wesentlichen eine Brute-Force-Suche darstellt. Bei einer gegebenen Hash-Ausgabe y würde ein Angreifer verschiedene Eingaben x ausprobieren, bis eine gefunden wird, bei der h(x) = y. Für eine sichere Hash-Funktion mit einer Ausgabegröße von n Bits (z.B. 256 Bits für SHA-256) beträgt die durchschnittliche Anzahl der erforderlichen Versuche ungefähr 2^n. Für SHA-256 bedeutet dies 2^256 Versuche, eine Zahl, die die Rechenkapazität aller Computer auf der Erde bei weitem übersteigt. Dies macht das Finden eines spezifischen Preimages praktisch unmöglich.

Die Kollisionsresistenz wird durch einen Kollisionsangriff herausgefordert. Im Gegensatz zu einem Preimage-Angriff, der eine spezifische Eingabe für eine spezifische Ausgabe sucht, zielt ein Kollisionsangriff darauf ab, irgendwelche zwei unterschiedliche Eingaben x und x' zu finden, sodass h(x) = h(x'). Dies ist aufgrund des Geburtstagsparadoxons erheblich einfacher als ein Preimage-Angriff. Das Geburtstagsparadoxon besagt, dass in einer Gruppe von nur 23 Personen eine Wahrscheinlichkeit von über 50 % besteht, dass zwei Personen denselben Geburtstag haben. Auf Hash-Funktionen angewendet bedeutet dies, dass man zum Finden einer Kollision nur etwa 2^(n/2) Hashes berechnen muss, nicht 2^n. Für SHA-256 reduziert sich der Aufwand dadurch auf 2^128, was immer noch eine astronomisch große Zahl ist, aber erheblich weniger als 2^256. Selbst mit dieser Reduzierung bleibt 2^128 für moderne Systeme rechnerisch undurchführbar.

Es ist auch wichtig, die Second-Preimage-Resistenz zu unterscheiden. Diese Eigenschaft besagt, dass es bei einer gegebenen Eingabe x und ihrem Hash h(x) rechnerisch undurchführbar ist, eine andere Eingabe x' (x' ≠ x) zu finden, sodass h(x') = h(x). Dies ist schwieriger als ein generischer Kollisionsangriff (bei dem man nur irgendwelche zwei Eingaben benötigt), wird aber im Allgemeinen als ähnlich schwierig wie ein Preimage-Angriff (2^n) angesehen. Eine Hash-Funktion, die kollisionsresistent ist, ist per Definition auch second-preimage-resistent.

Trading-Relevanz

Im Bereich der digitalen Assets und der Blockchain ist die durch Preimage- und Kollisionsresistenz gewährleistete Integrität von größter Bedeutung. Jede Transaktion in einer Blockchain wird gehasht, und diese Hashes werden dann miteinander verknüpft, um Blöcke zu bilden. Der Hash eines Blocks enthält den Hash des vorherigen Blocks, wodurch eine unveränderliche Kette entsteht.

Die Preimage-Resistenz stellt sicher, dass ein Angreifer einen Transaktions-Hash nicht rückentwickeln kann, um eine gültige Transaktion zu fälschen. Wenn ein Angreifer leicht eine Eingabenachricht finden könnte, die eine spezifische, gewünschte Hash-Ausgabe erzeugt (z.B. einen Hash, der eine Geldüberweisung an seine Adresse darstellt), könnte er potenziell betrügerische Transaktionen erstellen, die legitim erscheinen. Diese Eigenschaft ist auch für digitale Signaturen von entscheidender Bedeutung, bei denen ein privater Schlüssel den Hash einer Nachricht signiert. Wenn der Hash leicht umgekehrt werden könnte, wäre die Sicherheit der Signatur gefährdet.

Die Kollisionsresistenz ist ebenso kritisch. Wenn ein Angreifer zwei verschiedene Transaktionen finden könnte, die denselben Hash erzeugen, könnte er potenziell eine durch die andere ersetzen, ohne entdeckt zu werden. Man stelle sich zum Beispiel eine Transaktion A vor, die 1 BTC an Alice sendet, und eine Transaktion B, die 1 BTC an den Angreifer sendet. Wenn h(A) = h(B) ist, könnte der Angreifer A dem Netzwerk präsentieren, es bestätigen lassen und dann später behaupten, B sei die "echte" Transaktion gewesen, oder umgekehrt. Dies würde Doppelausgaben oder andere Formen von Betrug ermöglichen und das Vertrauen in die Blockchain grundlegend untergraben. Die Unveränderlichkeit der Blockchain beruht maßgeblich darauf, dass selbst die Änderung eines einzigen Bits in einer Transaktion oder einem Block zu einem völlig anderen Hash führen würde, wodurch jede Manipulation sofort offensichtlich würde.

Risiken

Das Versagen der Preimage- oder Kollisionsresistenz in einer kryptografischen Hash-Funktion, die in einem Blockchain-System verwendet wird, hätte katastrophale Folgen und würde zu einem vollständigen Zusammenbruch von Sicherheit und Vertrauen führen.

Wäre die Preimage-Resistenz kompromittiert, könnte ein Angreifer, ausgehend von einem Transaktions-Hash, die ursprünglichen Transaktionsdetails rekonstruieren oder sogar eine neue Transaktion erstellen, die denselben Hash erzeugt. Dies könnte dazu führen, dass digitale Signaturen gefälscht werden können, was einem Angreifer effektiv ermöglichen würde, Gelder von Wallets auszugeben, die er nicht kontrolliert, einfach indem er den Hash einer früheren Transaktion kennt. Das gesamte Konzept der privaten Schlüssel-Sicherheit, das auf der rechnerischen Undurchführbarkeit beruht, den Schlüssel aus seinem öffentlichen Hash oder einer signierten Nachricht abzuleiten, würde zerstört.

Ein Bruch der Kollisionsresistenz wäre noch verheerender. Ein Angreifer könnte zwei unterschiedliche Versionen einer Transaktion oder eines Blocks erstellen, eine legitime und eine betrügerische, die beide denselben Hash erzeugen. Zum Beispiel könnten sie eine Transaktion Tx1 erstellen, die Gelder an einen legitimen Empfänger sendet, und Tx2, die dieselben Gelder an sich selbst sendet, sodass hash(Tx1) = hash(Tx2) gilt. Wenn es ihnen gelingt, Tx1 bestätigen zu lassen, könnten sie später behaupten, Tx2 sei die gültige gewesen, wodurch sie effektiv Doppelausgaben tätigen oder Gelder umleiten könnten. Im Kontext von Block-Hashes könnte ein Angreifer potenziell einen bösartigen Block erstellen, der denselben Hash wie ein legitimer Block hat, was es ihm ermöglichen würde, die Historie umzuschreiben oder betrügerische Daten unentdeckt in die Blockchain einzufügen. Ein solches Ereignis würde die Integrität des Ledgers zerstören, alle digitalen Assets unsicher machen und wahrscheinlich zum Zusammenbruch der betroffenen Kryptowährung oder des Blockchain-Netzwerks führen.

Geschichte und Beispiele

Die Entwicklung kryptografischer Hash-Funktionen veranschaulicht den fortwährenden Kampf zwischen Sicherheit und Rechenleistung. Frühe Hash-Funktionen waren zwar innovativ, erfüllten aber oft nicht die strengen Anforderungen an moderne Sicherheit.

Ein bemerkenswertes Beispiel ist MD5 (Message-Digest Algorithm 5). MD5 wurde 1991 entwickelt und war weit verbreitet für Datenintegritätsprüfungen und digitale Signaturen. Im Jahr 2004 wurden jedoch erhebliche Schwachstellen entdeckt, und praktische Kollisionsangriffe wurden machbar. Forscher demonstrierten die Fähigkeit, zwei verschiedene Eingaben zu finden, die relativ schnell denselben MD5-Hash erzeugen. Dieser Kompromiss bedeutete, dass MD5 nicht mehr für Anwendungen geeignet war, die Kollisionsresistenz erforderten, wie z.B. digitale Zertifikate oder Code-Signierung, da ein Angreifer eine bösartige Datei mit demselben MD5-Hash wie eine legitime erstellen konnte.

Ein weiterer wichtiger Fall ist SHA-1 (Secure Hash Algorithm 1), der von der NSA entworfen und 1995 veröffentlicht wurde. Viele Jahre lang galt SHA-1 als robust. Es wurden jedoch theoretische Schwachstellen identifiziert, und 2017 kündigte Google den ersten praktischen Kollisionsangriff gegen SHA-1 an, der zeigte, dass es möglich war, Kollisionen mit erheblichem, aber erreichbarem Rechenaufwand zu finden. Dies markierte das Ende der Verwendbarkeit von SHA-1 für sicherheitskritische Anwendungen.

Im Gegensatz dazu bleibt SHA-256 (Secure Hash Algorithm 256), Teil der SHA-2-Familie, der Eckpfeiler der Sicherheit für viele moderne Kryptowährungen, insbesondere Bitcoin. SHA-256 wurde mit einer größeren Ausgabegröße (256 Bit) und einer komplexeren internen Struktur entwickelt, wodurch es deutlich widerstandsfähiger gegen Preimage- und Kollisionsangriffe ist. Bislang wurden keine praktischen Angriffe gegen die Preimage- oder Kollisionsresistenz von SHA-256 demonstriert. Seine Stärke ist ein grundlegender Grund, warum die Bitcoin-Blockchain seit ihrer Einführung im Jahr 2009 ihre Integrität bewahrt hat, trotz kontinuierlicher Versuche böswilliger Akteure. Die fortlaufende Forschung in der Kryptografie verschiebt ständig die Grenzen und führt zur Entwicklung noch stärkerer Algorithmen wie SHA-3, um sicherzustellen, dass die grundlegenden Sicherheitseigenschaften robust gegenüber sich entwickelnden Bedrohungen bleiben.

Häufige Missverständnisse

Beim Diskutieren von Preimage- und Kollisionsresistenz treten oft mehrere Missverständnisse auf. Ein häufiger Fehler ist die Verwechslung von rechnerischer Undurchführbarkeit mit mathematischer Unmöglichkeit. Während es mathematisch gewiss ist, dass Kollisionen für jede Hash-Funktion existieren (da es unendlich viele mögliche Eingaben, aber nur eine endliche Anzahl möglicher Ausgaben gibt), ist das Finden dieser Kollisionen für eine sichere Hash-Funktion aufgrund des immensen Rechenaufwands praktisch unmöglich. Die Unterscheidung ist entscheidend: Eine sichere Hash-Funktion verhindert nicht, dass Kollisionen existieren, sie verhindert, dass sie mit bekannten praktischen Mitteln gefunden werden.

Ein weiteres häufiges Missverständnis liegt in den subtilen Unterschieden zwischen Preimage-Resistenz, Second-Preimage-Resistenz und Kollisionsresistenz.

• Preimage-Resistenz bezieht sich auf das Umkehren des Hashes: Gegeben y, finde irgendein x, sodass h(x) = y.
• Second-Preimage-Resistenz bezieht sich auf das Finden einer Alternative für eine spezifische Eingabe: Gegeben x und h(x), finde x' (x' ≠ x), sodass h(x') = h(x). Dies ist vergleichbar mit dem Finden eines anderen Dokuments, das genau denselben Fingerabdruck wie ein bekanntes Dokument erzeugt.
• Kollisionsresistenz bezieht sich auf das Finden von irgendwelchen zwei verschiedenen Eingaben, die zum selben Wert hashen: Finde irgendwelche x und x' (x' ≠ x), sodass h(x) = h(x'). Dies ist vergleichbar mit dem Finden von zwei beliebigen Dokumenten, die zufällig denselben Fingerabdruck haben, ohne sich darum zu kümmern, was die Originaldokumente sind.

Es ist wichtig zu beachten, dass eine Hash-Funktion, die kollisionsresistent ist, auch automatisch second-preimage-resistent ist. Eine Funktion, die second-preimage-resistent ist, ist jedoch nicht unbedingt kollisionsresistent. Das "Geburtstagsparadoxon" reduziert den Aufwand, irgendeine Kollision zu finden, erheblich im Vergleich zum Finden eines Second-Preimages für eine spezifische Eingabe, wodurch Kollisionsresistenz im Allgemeinen die stärkere und anspruchsvollere Eigenschaft ist, die eine Hash-Funktion erreichen muss.

Zusammenfassung

Preimage-Resistenz und Kollisionsresistenz sind zwei unverzichtbare Eigenschaften kryptografischer Hash-Funktionen, die das Fundament der Sicherheit in modernen digitalen Systemen, insbesondere innerhalb der Blockchain-Technologie, bilden. Die Preimage-Resistenz stellt sicher, dass es praktisch unmöglich ist, eine ursprüngliche Nachricht aus ihrem Hash zu rekonstruieren, wodurch der Datenschutz und die Integrität digitaler Signaturen gewährleistet werden. Die Kollisionsresistenz garantiert, dass das Finden zweier unterschiedlicher Nachrichten, die dieselbe Hash-Ausgabe erzeugen, rechnerisch undurchführbar ist, wodurch böswillige Akteure daran gehindert werden, Transaktionen zu fälschen oder Blockchain-Aufzeichnungen zu manipulieren. Obwohl mathematisch Kollisionen existieren, macht der immense Rechenaufwand, der erforderlich ist, um sie für robuste Hash-Funktionen wie SHA-256 zu finden, diese in der Praxis sicher. Die kontinuierliche Entwicklung und Einführung starker kryptografischer Primitive sind unerlässlich, um Vertrauen und Sicherheit in der sich entwickelnden Landschaft des dezentralen Finanzwesens und digitaler Assets aufrechtzuerhalten.