Hash-Funktionen: Kollisionen und preimage-attack

06.01.2016, 11:04

MrWoodpecker

Hash-Funktionen: Kollisionen und preimage-attack

Erstmal noch ein frohes neues Jahr, an alle die das hier lesen smile

Hey,
ich sitze schon seit etwas längerer Zeit an einer bzw. an zwei Fragen, mit denen ich noch nicht so richtig umzugehen weiß.

Ich darf noch keine URLs posten, deswegen habe ich im Text alle Links gekennzeichnet und ganz unten eine Übersicht erstellt - sorry dafür, aber eine andere Lösung ist mir dazu nicht eingefallen...

Es geht um folgende Aufgaben:

Geben Sie an, wie die Wahrscheinlichkeiten,
- zu einem gegebenen Hash-Wert einen passenden Text zu finden (Teilaufgabe 1)
- zwei Texte mit gleichem Hash-Wert zu finden (Teilaufgabe 2)
von der Länge $\begin{eqnarray*} $L$ \end{eqnarray*}$ des Hash-Wertes anhängt.

---

Zu Hash-Funktionen habe ich mittlerweile eine ganze Menge gelesen und verstanden:
Wir haben eine Hash-Funktion $\begin{eqnarray*} $H$ \end{eqnarray*}$ mit $\begin{eqnarray*} H(x) = h \end{eqnarray*}$ , wobei $\begin{eqnarray*} $x$ \end{eqnarray*}$ die Eingabegröße und $\begin{eqnarray*} $h$ \end{eqnarray*}$ der Hash-Wert von $\begin{eqnarray*} $x$ \end{eqnarray*}$ ist.

zu Teilaufgabe 1:
Hier bin ich immerhin schonmal soweit, dass ich sagen kann, dass es sich um eine ( Link 1 ) preimage-attack handelt.
Also:
Wir haben ein $\begin{eqnarray*} $h$ \end{eqnarray*}$ und suchen ein $\begin{eqnarray*} $y$ \end{eqnarray*}$ für das gilt $\begin{eqnarray*} $h = H(y)$ \end{eqnarray*}$ .
Hier habe ich mich noch gar nicht weiter mit beschäftigt. Vielleicht könnten wir uns erstmal Teilaufaufgabe 2 anschauen. smile

zu Teilaufgabe 2:
Das habe ich erstmal als Kollision ausgelegt. Also quasi $\begin{eqnarray*} $H(x) = H(y)$ \end{eqnarray*}$ mit $\begin{eqnarray*} $x \neq y$ \end{eqnarray*}$ . Was bedeuten würde, dass zwei völlig verschiedene Dateien die gleiche Signatur bekommen würden.
Also habe ich mich dazu etwas belesen und bin dann relativ schnell zum "( Link 2 ) Geburtstagsparadoxon" gedrängt worden. Dazu bin ich auf einen ( Link 3 ) Foliensatz der Uni Potsdam (ab PDF-Seite 9) gestoßen, der mir auch weitergeholfen hat.

Auf Seite 10 sind dann Beispiele für die Kollisionen mehrere Hash-Werte innerhalb einer Hash-Funktion.

Beispiel 1:
Das Alphabet: $\begin{eqnarray*} $\sum := \{0,1\}$ \end{eqnarray*}$
$\begin{eqnarray*} $N = 2^{32}$ \end{eqnarray*}$ Anzahl aller Möglichkeiten für eine 32-Bit Hash-Funktion
$\begin{eqnarray*} $r = 2$ \end{eqnarray*}$ Anzahl der zu finden Kollisionen

Dann wäre meine Formel:
$\begin{eqnarray*} $C(N;r) = 1 - \prod_{i = 1}^{2} (1-\frac{i}{2^{32}}) \approx 6.98492 \cdot 10^{-10}$ \end{eqnarray*}$ für $\begin{eqnarray*} $L=32$ \end{eqnarray*}$

Das würde zu einer allgemeinen Formel
$\begin{eqnarray*} $P(L = \dots) = C(2^L;2) = 1 - \prod_{i = 1}^{2} (1-\frac{i}{2^{L}})$ \end{eqnarray*}$

Beispiel 2:
$\begin{eqnarray*} $P(L = 64) = C(2^{64};2) = 1 - \prod_{i = 1}^{2} (1-\frac{i}{2^{64}}) \approx 1.6263 \cdot 10^{-19}$ \end{eqnarray*}$
$\begin{eqnarray*} $P(L = 128) = C(2^{128};2) = 1 - \prod_{i = 1}^{2} (1-\frac{i}{2^{128}}) \approx 8.81621 \cdot 10^{-39}$ \end{eqnarray*}$
...

Dazu wäre meine Frage, ob ich mich damit auf dem richtigen Weg befinde, oder ist das kompletter Blödsinn, den ich hier fabriziert habe?
Ich bin ehrlich gesagt noch nicht 100%ig von meinem Vorgehen überzeugt.

Danke für die Mühe - ich hoffe mir kann jemand helfen. smile

06.01.2016, 11:06

MrWoodpecker

Auf diesen Beitrag antworten »

Die Links
Das mit den Links funktioniert leider auch so nicht Big Laugh

...

code:
1: 2: 3: 4:	Link 1 - Wikipedia -> Preimage-Angriff Link 2 - Wikipedia -> Geburtstagsparadoxon Link 3 - cs.uni-potsdam. de/ti/lehre/05-Kryptographie/slides/bremser_crypt-hashpdf.pdf

06.01.2016, 11:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MrWoodpecker
Geben Sie an, wie die Wahrscheinlichkeiten,
- zu einem gegebenen Hash-Wert einen passenden Text zu finden (Teilaufgabe 1)
- zwei Texte mit gleichem Hash-Wert zu finden (Teilaufgabe 2)
von der Länge $\begin{eqnarray*} $L$ \end{eqnarray*}$ des Hash-Wertes anhängt.

Irgendwie fehlt mir da noch eine Information: Es sollte doch zumindest auch noch die Anzahl der hier betrachteten Texte bekannt sein, vielleicht auch als Parameter für die Lösungsangabe? verwirrt

Und ich gehe mal davon aus, dass die Hash-Werte unterschiedlicher Texte als unabhängig, identisch gleichverteilt in der Menge der $\begin{align*} 2^L \end{align*}$ möglichen Werte angenommen wird.

06.01.2016, 12:16

MrWoodpecker

Auf diesen Beitrag antworten »

Hey,

die Aufgabenstellung oben ist alles, was ich zu dem Thema bekommen habe. Keine zusätzlichen Informationen. Der Dozent meinte nur "Sie kriegen das schon hin"..

Zitat:

Und ich gehe mal davon aus, dass die Hash-Werte unterschiedlicher Texte als unabhängig, identisch gleichverteilt in der Menge der 2L möglichen Werte angenommen wird.

Das denke ich auch..

06.01.2016, 13:00

HAL 9000

Auf diesen Beitrag antworten »

Naja gut, in dem Fall würde ich diese Anzahl $\begin{align*} n \end{align*}$ an Texten als Parameter aufnehmen, von dem das Ergebnis dann abhängig ist - ist einfach notwendig!

Zu Teilaufgabe 1: Betrachte das Gegenereignis, d.h. dass alle $\begin{align*} n \end{align*}$ Texte nicht den vorgegebenen Hashwert haben. Wegen der angenommenen Unabhängigkeit ist die Wahrscheinlichkeit dieses Gegenereignisses gleich $\begin{align*} \left(1-\frac{1}{2^L}\right)^n \end{align*}$ .

Bei der an sich schwierigerenTeilaufgabe 2 hast du ja schon den richtigen Ansatz ("Geburtstagsproblem"), allerdings betrachtest du in deiner Formel nur den Fall $\begin{align*} n=3 \end{align*}$ , warum auch immer. Allgemein wäre mit der Wahrscheinlichkeit $\begin{align*} 1-\prod_{i=1}^{n-1}\left(1-\frac{i}{2^L}\right) \end{align*}$ zu arbeiten.

07.01.2016, 16:50

MrWoodpecker

Auf diesen Beitrag antworten »

Hey,

danke schonmal für die Hilfe smile

Ich habe jetzt mal ein bisschen was zusammengebastelt:

zu Teilaufgabe 1:

zur Erinnerung: zu einem gegebenen Hash-Wert einen passenden Text finden

Wir haben nun also festgelegt, dass

$\begin{eqnarray*} $P = 1 - (1 - \frac{1}{2^L})^n$ \end{eqnarray*}$

ist.

Ich habe erstes eine Art allgemeine Aussage formuliert:

$\begin{eqnarray*} $A =$ \end{eqnarray*}$ Die Wahrscheinlichkeit, dass zu einem gegeben Hash-Wert der Hash-Funktion $\begin{eqnarray*} $H$ \end{eqnarray*}$ mit der Länge $\begin{eqnarray*} $ L $ \end{eqnarray*}$ ein passender Text aus $\begin{eqnarray*} $ n $ \end{eqnarray*}$ Texten gefunden wird.

---

$\begin{eqnarray*} $n$ \end{eqnarray*}$ ist die Anzahl der Texte
$\begin{eqnarray*} $L$ \end{eqnarray*}$ ist die Länge der Hash-Werte in Bit

Beispiel 1:

$\begin{eqnarray*} $L = 32$ \end{eqnarray*}$ (32-Bit-Hash-Funktion)

$\begin{eqnarray*} $n = 1000000$ \end{eqnarray*}$

$\begin{eqnarray*} P(A) = 1 - (1 - \frac{1}{2^{32}})^{1000000} \approx 0.0002328029 \end{eqnarray*}$

$\begin{eqnarray*} n = 8000000000 \end{eqnarray*}$

$\begin{eqnarray*} $P(A) = 1 - (1 - \frac{1}{2^{32}})^{8000000000} \approx 0.8447378$ \end{eqnarray*}$

$\begin{eqnarray*} $L = 128$ \end{eqnarray*}$ (128-Bit-Hash-Funktion)

$\begin{eqnarray*} $n = 1000000$ \end{eqnarray*}$

$\begin{eqnarray*} $P(A) = 1 - (1 - \frac{1}{2^{128}})^{1000000} \approx 2.350988702 \cdot 10^{-32}$ \end{eqnarray*}$

$\begin{eqnarray*} $n = 8000000000$ \end{eqnarray*}$

$\begin{eqnarray*} $P(A) = 1 - (1 - \frac{1}{2^{128}})^{8000000000} \approx 1.8807909613\cdot 10^{-28}$ \end{eqnarray*}$

...

Das kann man natürlich dann unendlich weiter spinnen. Aber es zeigt eben, dass umso länger ein Hash-Wert ist, desto geringer wird die Wahrscheinlichkeit eine Kollision zwischen $\begin{eqnarray*} $n$ \end{eqnarray*}$ Texten.

---

Man könnte die Formel ja auch noch umbauen um zu errechnen, wie viele Texte man generieren müsste um mit sehr großer Wahrscheinlichkeit auf den gesuchten Hash-Wert zu treffen.

Beispiel 2:

$\begin{eqnarray*} $L = 32$ \end{eqnarray*}$

$\begin{eqnarray*} $1 - (1 - \frac{1}{2^{32}})^x = 0.99$ \end{eqnarray*}$

$\begin{eqnarray*} $0.01 = (1 - \frac{1}{2^{32}})^x$ \end{eqnarray*}$

$\begin{eqnarray*} $ln(0.01) = ln(1 - \frac{1}{2^{32}}) \cdot x$ \end{eqnarray*}$

$\begin{eqnarray*} $\frac{ln(0.01)}{ln(1 - \frac{1}{2^{32}})} = x$ \end{eqnarray*}$

$\begin{eqnarray*} $x \approx 1.977911002 \cdot 10^{10}$ \end{eqnarray*}$

Also kann man allgmein sagen:

Um zu einen gegeben Hash-Wert mit hoher Wahrscheinlichkeit einen passenden Text zu finden, kann man $\begin{eqnarray*} $x$ \end{eqnarray*}$ mit Hilfe von

$\begin{eqnarray*} $\frac{ln(0.01)}{ln(1 - \frac{1}{2^L})} = x$ \end{eqnarray*}$

errechnen.

Das müsste doch so der Aufgabe entsprechen, oder?

zu Teilaufgabe 2:

zur Erinnerung: zwei Texte mit gleichem Hash-Wert finden (Kollision)

Wir haben nun also festgelegt, dass

$\begin{eqnarray*} $P = 1 - \prod_{i = 1}^{n-1} (1 - \frac{i}{2^L})$ \end{eqnarray*}$

ist.

Beispiel 3:

Für $\begin{eqnarray*} $L = 32$ \end{eqnarray*}$ und $\begin{eqnarray*} $n = 100$ \end{eqnarray*}$ würde es also wie folgt aussehen:

$\begin{eqnarray*} $P = 1 - \prod_{i = 1}^{99} (1 - \frac{i}{2^32}) \approx 1.152511023 \cdot 10^{-6}$ \end{eqnarray*}$

Das entspricht also der Wahrscheinlichkeit bei 100 generierten 32-Bit-Hash-Werten mindestens eine Kollision zu finden.

---

Das lässt sich dann natürlich auch alles in größeren Dimensionen berechnen - z.B. für 128-Bit-Hash-Funktionen mit mehr Texten usw.

Auch hier wird sicherlich zu erkennen sein, dass mit größerer Länge eines Hash-Wertes auch die Kollisionswahrscheinlichkeit sinken wird.

Mit der auf Seite 11 vorgestellten Formel (cs.uni-potsdam) lässt sich dann noch berechnen wie viele Zeichenketten es braucht um zwei gleiche Zeichenketten in zu finden (mit einer Wahrscheinlichkeit von 50%, wobei man hier auch variieren könnte um wieder eine möglichst hohe Wahrscheinlichkeit zu erreichen)

$\begin{eqnarray*} $1.18 \cdot \sqrt{N}$ \end{eqnarray*}$

Beispiel 4:

$\begin{eqnarray*} $L = 32$ \end{eqnarray*}$

$\begin{eqnarray*} $1.18 \cdot \sqrt{2^{32}} \approx 77333$ \end{eqnarray*}$

Das würde doch bedeuten, dass man 77333 Hash-Werte erzeugen müsste um mit 50% Wahrscheinlichkeit eine Kollision dabei zu haben.
Aber die Wahrscheinlichkeit auf Teilaufgabe 1 (also zu einem gegebenen Hash-Wert einen Text zu finden) liegt bei:

$\begin{eqnarray*} $1-(1 - \frac{1}{2^32})^{77333} \approx 1.80052803 \cdot 10^{-5}$ \end{eqnarray*}$

Mehr fällt mir nun zu Teilaufgabe 2 nicht ein...

Ich wäre dankbar, wenn sich nochmal jemand meine Gedanken dazu anschauen und mir seine Meinung dazu schreiben könnte.
Danke für die Mühe smile

Neue Frage »

Antworten »

Hash-Funktionen: Kollisionen und preimage-attack

Verwandte Themen