Kollisionssicherheit

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

Motivation

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₁ und x₂ 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₁) = h(x₂) 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

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

Die Hashfunktion h wird als kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, überhaupt eine Kollision zu finden.

Bemerkungen

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 umfasst, muss hierzu von maximal 2ⁿ + 1 Dokumenten der Hashwert berechnet werden. Aufgrund des Geburtstagsparadoxons wird eine Kollision typischerweise sogar nach erheblich weniger Versuchen gefunden werden (siehe Kollisionsangriff). 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

• Kryptograhische Hashfunktionen (Skript der FH Flensburg)