Kollisionssicherheit

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.

Inhaltsverzeichnis

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 x1 und x2 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(x1) = h(x2) 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 x1 ein Dokument x_2\ne x_1 zu finden, das mit x1 kollidiert (für das also h(x1) = h(x2) 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 2n + 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


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • DBAG-Baureihe 430 — Anzahl: 83 bestellt 0 ausgeliefert Hersteller: Alstom, Bombardier Achsformel: Bo (Bo )(2 )(Bo )Bo Spurweite: 1435 mm (Normalspur) Länge über Kupplung: 68.302 mm Höhe …   Deutsch Wikipedia

  • Hashfunktion — Beispiel einer Hashfunktion (hier SHA 1), links drei unterschiedliche Eingabewerte, rechts die entsprechenden Hashcodes Auf den meisten unixartigen Systemen lassen sich diese Beispiele mit echo n Fox | sha1sum etc. nachvollziehen Eine… …   Deutsch Wikipedia

  • Kollision — Kollision, (v. lat. kollisio), dt. Zusammenstoß, Zusammenprall, bezeichnet: den Zusammenprall zweier Meinungen, siehe Konflikt im Rechtswesen die gleichzeitige Gültigkeit verschiedener Rechtsnormen für denselben Sachverhalt, siehe Kollisionsregel …   Deutsch Wikipedia

  • Kollisionsangriff — Ein Kollisionsangriff ist ein Angriff auf eine kryptologische Hashfunktion mit dem Ziel, zwei verschiedene Dokumente zu finden, die auf einen identischen Hashwert führen. Im Gegensatz zu Preimage Angriffen sind dabei beide Dokumente (und damit… …   Deutsch Wikipedia

  • Merkles Meta-Verfahren — (auch Merkle Damgård Konstruktion) ist eine Methode zur Konstruktion von kryptographischen Hash Funktionen. Gegeben ist eine Kompressionsfunktion , die kollisionssicher ist, d. h. es ist nicht mit realistischem Aufwand möglich, zwei… …   Deutsch Wikipedia

  • Secure Hash Algorithm — Der Begriff secure hash algorithm (engl. für sicherer Hash Algorithmus), kurz SHA, bezeichnet eine Gruppe standardisierter kryptologischer Hashfunktionen. Diese dienen zur Berechnung eines eindeutigen Prüfwerts für beliebige elektronische Daten.… …   Deutsch Wikipedia

  • Projekt Safetrain — Das Projekt Safetrain (oder auch Safetrain Projekt) war der Name eines Forschungsprojekts für Verkehrssicherheit und wurde vom 1. August 1997 bis Juli 2001[1] vom in Warschau ansässigen Centrum Naukowo Techniczne Kolejnictwa (CNTK)[2] koordiniert …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”