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 ${\textstyle m_{0}}$ eine weitere Nachricht ${\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 ${\textstyle m_{0}}$ eine weitere Nachricht ${\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 ${\textstyle \mathbb {H} }$ eine Familie von Einwegfunktionen, ${\textstyle H}$ eine einzelne Einwegfunktion, ${\textstyle \mathbb {M} }$ ihren Urbildraum, ${\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 ${\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 ${\textstyle m}$ ein weiteres ${\textstyle m'\in \mathbb {M} }$ zu finden, so dass ${\textstyle m\neq m'}$ und beide auf denselben Wert abgebildet werden:

$$\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 ${\textstyle m_{0}}$ und ${\textstyle m_{1}}$ zu finden, so dass ${\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 ${\textstyle m_{0},m_{1}}$ mit ${\textstyle H(m_{0})=H(m_{1})}$ und ${\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: ${\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 ${\textstyle \mathbb {H} }$ gezogene Funktion ${\textstyle H}$ mit mehr als vernachlässigbarer Wahrscheinlichkeit zwei verschiedene Urbilder ${\textstyle m_{0}}$ und ${\textstyle m_{1}}$ ausgeben kann, so dass ${\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 ${\textstyle 2^{128}}$ Rechenoperationen benötigen), so benötigt sie eine Ausgabe von 256 Bit, da ${\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 ${\textstyle H}$ injektiv, so existieren keine Kollisionen, was zur Folge hat, dass ${\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 ${\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 ${\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 ${\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 ${\textstyle x=x+p}$ für alle ${\textstyle x}$ gilt, handelt es sich bei ${\textstyle x,x+p}$ streng genommen nicht um eine Kollision. Wird der Exponent andererseits als reguläre Ganzzahl aufgefasst, so gilt selbstverständlich ${\textstyle x\neq x+p}$, womit ${\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 ${\textstyle H}$ eine kollisionsresistente Funktion, so ist die Funktion ${\textstyle H'}$, die für eine Eingabe ${\textstyle m}$ die Zeichenkette ${\textstyle H(m)||0000}$ (wobei ${\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).