Kollisionssicherheit

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Kollisionssicherheit oder Kollisionsresistenz bezeichnet man im Rahmen der Kryptographie eine Eigenschaft von Hashfunktionen, einen Schutz gegen bestimmte Angriffe auf das Verfahren zu bieten.

Motivation[Bearbeiten]

Eine Hashfunktion h liefert zu einem Dokument x, aufgefasst als beliebig lange Bitfolge, eine Bitfolge h(x) fester (von h abhängiger) Länge n. Falls zwei Dokumente x_1 und x_2 verschiedene Hashwerte h(x_1)\ne h(x_2) haben, ist gewiss, dass die Dokumente unterschiedlich sind (x_1\ne x_2). Die Umkehrung gilt jedoch nicht, da es viel mehr verschiedene mögliche Dokumente als mögliche Hashwerte gibt. Zwei Dokumente x_1\ne x_2 mit  h(x_1)=h(x_2) werden als Kollision bezeichnet. Soweit der Bereich der (zulässigen) Dokumente nicht eingeschränkt wird, kann eine Hashfunktion also nicht echt kollisionsfrei sein. Inwieweit es zumindest in der praktischen Anwendung dennoch gerechtfertigt ist, aus gleichen Hashwerten auf gleiche Dokumente zu schließen, hängt von der verwendeten Hashfunktion ab.

Definition[Bearbeiten]

Die Hashfunktion h wird als schwach kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, zu einem gegebenen Dokument x_1 ein zweites Dokument x_2\ne x_1 zu finden, das mit x_1 kollidiert (für das also h(x_1)=h(x_2) gilt).

Die Hashfunktion h wird als (stark) kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, überhaupt eine Kollision, also zwei beliebige (aber verschiedene) x_1, x_2 mit h(x_1)=h(x_2), zu finden.

Bemerkungen[Bearbeiten]

In den Definitionen taucht der Begriff der praktischen Durchführbarkeit auf. Da nur endlich viele mögliche Hashwerte existieren, aber unendlich viele Dokumente, ist es grundsätzlich möglich, durch fortlaufendes Ausprobieren eine Kollision zu finden. Wenn der Hashwert n Bits lang ist, muss von circa 2^n Dokumenten der Hashwert berechnet werden um zu einem gegebenen Dokument eine Kollision zu finden (Zweites-Urbild-Angriff). Wenn beide Urbilder frei gewählt werden dürfen, wird aufgrund des Geburtstagsparadoxons eine Kollision typischerweise sogar nach nur 2^{n/2} Versuchen gefunden werden (Kollisionsangriff). Es ist also wesentlich einfacher, die Kollisionsresistenz zu brechen, als die schwache Kollisionsresistenz. Sofern n hinreichend groß ist, übersteigt der Rechenaufwand dieser Probiermethode dennoch jede Grenze der Praktikabilität. Wenn kein Verfahren bekannt ist, das wesentlich rascher eine Kollision findet, wird die Suche nach einer Kollision als praktisch undurchführbar angesehen.

Es ist zu beachten, dass ein zunächst als kollisionssicher angesehenes Verfahren durch Entwicklung neuer Algorithmen „geknackt“ werden kann und dann nicht mehr kollisionssicher ist. In kryptographischen Anwendungen sollten nur solche Hashfunktionen zur Anwendung kommen, die nach bisherigem Stand der Forschung als kollisionssicher anzusehen sind.

Weblinks[Bearbeiten]