• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Kollisionsresistente Hashfunktionen und Einwegfunktionen

Contents

  • Definitionen
  • Satz

Definitionen

Sei $f:X \rightarrow Y$ eine Funktion. $f$ heißt eine Einwegfunktion, genau dann wenn für alle $x \in X$ gilt:
  • $y := f(x)$ kann in Polynomialzeit berechnet werden
  • Für die Berechnung eines Urbildes $x$ aus $y$ existiert kein randomisierter Algorithmus, der in Polynomialzeit läuft.
Eine Funktion $H:\{0,1\}^* \rightarrow \{0,1\}^k$ heißt kollisionsresistente Hashfunktion, wenn gilt: Jeder effiziente Algorithmus findet nur mit kleiner Wahrscheinlichkeit eine Kollision.

Was heißt „kleine Wahrscheinlichkeit“? Nach dem Auswerten der Funktion $H$ für $x_1, x_2, \dots x_n$ sollte die Wahrscheinlichkeit nicht signifikant höher sein als $\displaystyle 1-\frac{n!\cdot{{2^k} \choose n}}{{2^k}^n}$ Diese Wahrscheinlichkeit kommt von dem Geburtstagsparadoxon bzw. dem Schubfachprinzip. Wir haben $2^k$ Schubfächer (Funktionswerte) in die wir die $x_i$ (Urbilder) einordnen können.

Satz

Behauptung: Jede kollisionsresistente Hashfunktion ist eine Einwegfunktion. Beweis: durch Widerspruch Sei $f$ eine kollisionsresistente Hashfunktion Annahme: $f$ ist keine Einwegfunktion

Dann existiert ein Angreifer $\mathcal{A}$, der für eine Bild $f(x)$ ein $x'$ findet, sodass $f(x) = f(x')$ gilt.

Der Angreifer $\mathcal{B}$ macht nichts anderes, als zufällig Werte $x \in {0,1}^{2k}$ zu wählen, $f(x)$ zu berechnen, den Angreifer $\mathcal{A}$ auf $f(x)$ anzuwenden und zu überprüfen, ob das von $\mathcal{A}$ gelieferte $x' \neq x$ ist. Sobald das ein mal der Fall ist, hat der Angreifer gewonnen.

Nun wenden wir $f$ auf $x \in {0,1}^{2k}$ an. Es gilt:

$Pr_x[\underbrace{|f^{-1}(f(x))|}_{\substack{\text{Anzahl der Urbilder}\\text{zum Hashwert} f(x)} } = 1] \leq \frac{2^k}{2^{2k}} = \frac{1}{2^k}$.

Die $2^k$ im Zähler stehen für die Funktionswerte und die $2^{2k}$ für die Urbilder.

Nun ist $\frac{1}{2^k}$ eine vernachlässigbare Funktion.

$\Rightarrow$ Die Wahrscheinlichkeit, dass wir keine Kollsion finden ist vernachlässigbar.

$\Rightarrow$ Mit signifikanter Wahrscheinlichkeit hat $f(x)$ $k \geq 2$ Urbilder.

$\Rightarrow$ Die Wahrscheinlichkeit, dass $\mathcal{B}$ Kollisionen findet ist etwa $(1-\frac{1}{k}) \cdot m$, wobei $m$ die Anzahl der Widerholungen ist.

Published

Jul 23, 2013
by Martin Thoma

Category

German posts

Tags

  • IT-Security 12

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor