Kollisionsresistenz

Eine Funktion (in diesem Zusammenhang fast immer eine Einwegfunktion) wird als kollisionsresistent bezeichnet, wenn es „schwer“ ist, verschiedene Eingaben zu finden, die auf denselben Wert abgebildet werden. Insbesondere bei kryptographischen Hashfunktionen handelt es sich hierbei um eine übliche Anforderung, deren Bruch in der Regel als Bruch der kompletten Hashfunktion betrachtet wird.

Hintergrund

Kryptographische Hashfunktionen sind ein wichtiges Primitiv in zahlreichen praktischen Anwendungen, insbesondere im Zusammenhang von digitalen Signaturen im Rahmen des „Hash-then-Sign“-Paradigmas. Hierbei ist es naheliegenderweise wünschenswert, dass niemand in der Lage ist, zu einer gültigen Signatur für eine Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0} eine weitere Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_1} zu finden, für die die Signatur ebenfalls gültig wäre; da die Nachricht in der Regel vor dem Signieren gehasht wird, muss folglich auch die Hashfunktion sicherstellen, dass es nicht möglich ist, zu einer gegebenen Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0} eine weitere Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_1} zu finden, die zum selben Hash führt. Diese Eigenschaft wird als Resistenz gegen das Finden weiterer Urbilder oder auch als schwache Kollisionsresistenz bezeichnet.

Etwas weniger offensichtlich ist die stärkere Forderung nach (starker) Kollisionsresistenz, welche das Finden irgendwelcher Kollisionen verhindert: hier genügt es für das Fälschen einer Signatur im Allgemeinen nicht mehr, eine vorhandene zu finden, stattdessen muss der Besitzer des geheimen Schlüssels dazu gebracht werden, eine vom Angreifer gewählte Nachricht zu signieren. Dies mag auf den ersten Blick eher unplausibel erscheinen, insbesondere da die meisten praktisch auffindbaren Kollisionen zunächst keinen sinnvollen Inhalt zu haben scheinen. Durch Ausnutzung verschiedener Eigenschaften verbreiteter Dateiformate (z. B. PDF) und typische Konstruktionen der meisten Hashfunktionen können jedoch gezielt zwei nahezu frei wählbare Dokumente erstellt werden, die nur bei einer Untersuchung durch Experten verdächtig erscheinen. Ein denkbares Szenario wäre in diesem Fall etwa, dass man einen Politiker dazu veranlasst, ein speziell präpariertes Dokument mit vermeintlich harmlosem Inhalt (digital) zu unterschreiben, wodurch eine echte Signatur entsteht, die ein Angreifer auch für ein anderes Dokument mit (oberflächlich betrachtet) nahezu beliebig anderem Inhalt verwenden kann.

Notation

Im Folgenden bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathbb{H}} eine Familie von Einwegfunktionen, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H} eine einzelne Einwegfunktion, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathbb{M}} ihren Urbildraum, Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\textstyle \mathrm {Pr} [X]} die Wahrscheinlichkeit, dass ein Ereignis ${\textstyle X}$ eintritt, und ${\textstyle {\mathcal {A}}}$ einen, potentiell propabilistischen, Algorithmus mit polynomieller Laufzeit im Sicherheitsparameter und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\textstyle \mathrm {negl.} } eine im Sicherheitsparameter vernachlässigbare Wahrscheinlichkeit.

Schwache Kollisionsresistenz

Eine Einwegfunktion wird als schwach (im Sinne von „leichter zu erreichen“) kollisionsresistent bezeichnet, wenn kein Angreifer in der Lage ist, zu einem gegebenen Urbild ein zweites zu finden, das auf denselben Wert abgebildet wird. Verbreitet ist hier auch die englische Bezeichnung „second-preimage-resistance“ (etwa „Resistenz gegen zweite Urbilder“).

Formaler ausgedrückt bedeutet dies, dass es keinen in propabilistischer Polynomialzeit (${\textstyle PPT}$) laufenden Angreifer gibt, der eine mehr als vernachlässigbare Chance hat, zu einem zufällig aus ${\textstyle \mathbb {M} }$ gewählten Urbild Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\textstyle m} ein weiteres Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m' \in \mathbb{M}} zu finden, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m \neq m'} und beide auf denselben Wert abgebildet werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall \mathcal{A} \in PPT: \mathrm{Pr}\left[m \leftarrow \mathbb{M}; m' := \mathcal{A}(m):\ H(m) = H(m') \land m \neq m'\right] < \mathrm{negl.}}

Praxisrelevante Angriffe gegen diese Eigenschaft bei üblichen Hashfunktionen sind vergleichsweise selten.

Starke Kollisionsresistenz

Unter starker Kollisionsresistenz wird in der Regel anschaulich verstanden, dass es praktisch unmöglich ist, zwei verschiedene Urbilder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_1} zu finden, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H(m_0) = H(m_1)} .

Hierbei handelt es sich streng genommen aber um eine unerfüllbare Übervereinfachung: für jede nicht-injektive Funktion existiert mindestens ein Wertepaar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0, m_1} mit Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\textstyle H(m_{0})=H(m_{1})} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0 \neq m_1} . Damit existiert auch ein Angreifer, der diese Kollision ausgibt. Dieser würde damit mit Wahrscheinlichkeit 1 (also immer) eine Kollision in polynomieller Zeit (nämlich der Zeit die er braucht, um die Kollision aufzuschreiben) finden. Es mag zwar praktisch unmöglich sein, diesen Angreifer zu „finden“ (da hierfür ja zunächst eine Kollision gefunden werden müsste), es existiert aber keine bekannte Möglichkeit, wie sich dieser Einwand formalisieren ließe.

Um dieses Problem zu umgehen, wird in Zusammenhängen, in denen eine strikte Formalisierung notwendig ist, über Familien von Einwegfunktionen und zufällig aus diesen gezogene Funktionen gesprochen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathbb{H}} ist dann eine Familie von kollisionsresistenten Einwegfunktionen wenn gilt, dass es keinen effizienten Angreifer gibt, der für eine zufällig aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathbb{H}} gezogene Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H} mit mehr als vernachlässigbarer Wahrscheinlichkeit zwei verschiedene Urbilder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_1} ausgeben kann, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H(m_0) = H(m_1)} :

$$\forall {\mathcal {A}}\in PPT:\mathrm {Pr} \left[H\leftarrow \mathbb {H} ;m_{0},m_{1}:={\mathcal {A}}(H):\ H(m_{0})=H(m_{1})\land m_{0}\neq m_{1}\right]<\mathrm {negl.}$$

Aufgrund des Geburtstagsparadoxons ist es in der Regel deutlich leichter, beliebige Kollisionen zu finden als zweite Urbilder, weswegen die Ausgabelänge der meisten Hashfunktionen der doppelten Länge des gewünschten Sicherheitslevels entspricht: Soll eine Hashfunktion etwa 128 Bit Sicherheit gegen Kollisionen bieten (das finden einer Kollision durch Brute Force also etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 2^{128}} Rechenoperationen benötigen), so benötigt sie eine Ausgabe von 256 Bit, da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \sqrt{2^{256}} = 2^{128}} . Dies steht im direkten Gegensatz zur schwachen Kollisionsresistenz, für die bereits 128 Bit an Ausgabe genügen würden. In der Folge bieten die meisten klassischen Hashfunktionen dann auch eine (intendiert) doppelt so hohe Sicherheit gegen das Finden erster oder zweiter Urbilder als gegen das Finden beliebiger Kollisionen.

Dies hat sich jedoch mit der Entwicklung von SHA-3 und der zugehörigen „Schwamm“-Konstruktion dahingehend geändert, dass es nun möglich ist, die Resistenz gegen das Finden erster und zweiter Urbilder auf definierte Weise so abzusenken, dass sie der der starken Kollisionsresistenz entspricht, was eine höhere Performance ermöglicht. Dies ändert jedoch nichts an der benötigten doppelten Länge der Ausgabe, sondern reduziert lediglich die Sicherheit an anderer Stelle.

Im Gegensatz zur relativ unspektakulären Sicherheitsgeschichte der Urbildresistenzen wurde die Kollisionsresistenz vieler etablierter und praktisch eingesetzter Hashfunktionen wie MD5 oder SHA-1 praktisch gebrochen. Da diese Brüche teilweise auf die in jenen Funktionen meist verwendete Merkle-Damgård-Konstruktion zurückgeführt wurde, die auch Grundlage von SHA-2 war, wurde vom NIST der SHA3-Wettbewerb ins Leben gerufen, dessen Ziel das Entwickeln einer neuen Hashfunktion mit idealerweise andersartiger Struktur war, um im Falle eines (bis heute nicht eingetretenen und mittlerweile als eher unwahrscheinlich eingeschätzten) Bruchs von SHA2 eine fertige Alternative zu haben.

Perfekte Kollisionsresistenz

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H} injektiv, so existieren keine Kollisionen, was zur Folge hat, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H} informationstheoretisch kollisionsresistent ist.

Der große Nachteil ist hierbei, dass Injektivität im direkten Widerspruch zu den üblichen Anforderungen an allgemeine Hashfunktionen steht: Damit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H} injektiv sein kann, muss die Ausgabe im Mittel mindestens so lang wie die Eingabe sein, was bei Funktionen, die Zeichenketten beliebiger Länge auf eine feste Länge abbilden, offensichtlich nicht der Fall sein kann. Darüber hinaus impliziert perfekte Kollisionsresistenz nicht, dass es schwer ist, Urbilder zu finden, was in sehr vielen Anwendungen von Hashfunktionen aber eine äußerst wichtige Eigenschaft ist.

Das einfachste Beispiel für eine solche Funktion, das auch gleichzeitig die Beschränktheit dieses Begriffs offenbart, ist die Identität, also die Funktion die ihr Argument unverändert zurückgibt: da jedes Abbild genau sein eigenes Urbild ist, kann es zu keinem Abbild ein zweites Urbild geben; gleichzeitig ist es trivial zu einem Abbild das zugehörige Urbild zu finden.

Ein weiteres Beispiel, welches je nach Betrachtungsweise entweder perfekte Kollisionsresistenz bietet oder aber trivial unsicher ist, stellt das Potenzieren von Elementen in endlichen, zyklischen Gruppen primer Ordnung Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\textstyle p} dar. Wird in einer festen Gruppe ein fester Erzeuger mit dem Urbild potenziert, so ist diese Operation frei von Kollisionen, falls der Exponent als Element der (endlichen) Restklassengruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathbb{Z}_p} betrachtet wird, der durch die in der eigentlichen Berechnung verwendete Ganzzahl lediglich repräsentiert wird. Da in diesem Fall in gewisser Weise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x = x + p} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x} gilt, handelt es sich bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x, x+p} streng genommen nicht um eine Kollision. Wird der Exponent andererseits als reguläre Ganzzahl aufgefasst, so gilt selbstverständlich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x \neq x + p} , womit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x, x+p} eine triviale Kollision darstellen.

Beziehungen zu anderen Eigenschaften von Hashfunktionen

Wie bereits im vorherigen Abschnitt dargestellt, impliziert Kollisionsresistenz nicht zwingend, dass es sich bei einer Funktion um eine Einwegfunktion handelt. Vor diesem Hintergrund sollte nicht überraschen, dass die Abbilder auch nicht zwingend pseudozufällig aussehen: ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H} eine kollisionsresistente Funktion, so ist die Funktion Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\textstyle H'} , die für eine Eingabe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} die Zeichenkette Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle H(m) || 0000} (wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle ||} die Konkatenation bezeichnet) liefert, ebenfalls kollisionsresistent, endet aber immer auf vier Nullen und wirkt daher in Abhängigkeit von der Vergleichsmenge nicht mehr zwingend pseudozufällig.

Literatur

• Phillip Rogaway und Thomas Shrimpton: Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. 2004, S. 371–388, doi:10.1007/978-3-540-25937-4_24 (englisch).