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 | Quelltext bearbeiten]

Eine Hashfunktion liefert zu einem Dokument , aufgefasst als beliebig lange Bitfolge, eine Bitfolge fester (von abhängiger) Länge . Falls zwei Dokumente und verschiedene Hashwerte haben, ist gewiss, dass die Dokumente unterschiedlich sind (). Die Umkehrung gilt jedoch nicht, da es viel mehr verschiedene mögliche Dokumente als mögliche Hashwerte gibt. Zwei Dokumente mit 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 | Quelltext bearbeiten]

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

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

Bemerkungen[Bearbeiten | Quelltext 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 Bits lang ist, muss von circa 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 Versuchen gefunden werden (Kollisionsangriff). Es ist also wesentlich einfacher, die Kollisionsresistenz zu brechen, als die schwache Kollisionsresistenz. Sofern 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 | Quelltext bearbeiten]