Cryptography Reference
In-Depth Information
Das Ergebnis entspricht der bekannten Beobachtung, dass bei 6 Würfen mit einem Würfel im
Mittel eine „Sechs“ auftritt, wenn der Würfel symmetrisch ist und jede Augenzahl mit der
Wahrscheinlichkeit 1/6 gewürfelt wird.
Für das Finden einer Kollision bei einem Hashwert von z.B. n = 160 Bit bedeutet das Ergeb-
nis, dass bei 2
160
Versuchen im Mittel eine Kollision gefunden wird. Diese Zahl von Versu-
chen ist praktisch undurchführbar, es würde für die heute verfügbare Rechenleistung bereits
ein kürzerer Hashwert von z.B. n = 80 ausreichen (vgl. 2
80
ns 38 Mio. Jahre).
3.1.2.2
Angriff auf starke Kollisionsresistenz
Bei starker Kollisionsresistenz genügt es, dass ein Angreifer zwei beliebige Nachrichten m
1
und m
2
mit gleichen Hashwerten h(m
1
) = h(m
2
) findet. Er kann dazu beliebige Nachrichten m
i
auswählen und ihre Hashwerte h(m
i
) in einer geordneten Liste speichern. Sobald ein gleicher
Hashwert auftritt, ist dies beim Speichern in der Liste zu bemerken und der Angriff war erfolg-
reich. Neben der Zeit für die Versuche ist für jeden Versuch entsprechender Speicherplatz
erforderlich.
Es wird wieder angenommen, dass die Hashwerte eine Länge von n Bit haben. Die Nachrich-
ten dürfen beliebig lang sein. Es wird weiter angenommen, dass es sich um gute Hashfunktio-
nen handelt, d.h. die Hashwerte der Nachrichten sich gleichmäßig und quasi-zufällig auf alle
2
n
möglichen Hashwerte verteilen.
Beim 1. Versuch ist die Wahrscheinlichkeit für eine Kollision gleich 0, weil die Liste noch leer
ist. Beim 2. Versuch ist die Wahrscheinlichkeit für eine Kollision gleich 2
-n
, weil eine Kollisi-
on mit einem von 2
n
möglichen Hashwerten auftreten kann. Beim j-ten Versuch kann eine
Kollision mit jedem der j-1 vorhandenen Hashwerte in der Liste auftreten. Die Wahrschein-
lichkeit dafür ist (j-1)·2
-n
. Bei jedem Versuch kann nur eine Kollision auftreten. Die Wahr-
scheinlichkeit für eine Kollision ist deshalb gleich dem Erwartungswert an Kollisionen. Die
Erwartungswerte für die Versuche 1 bis j kann man addieren. Der Erwartungswert E
K
für die
Summe der Kollisionen ist damit:
n
n
E
2
[ 0
1
2
...( j
1)]
2
( j
1)
j / 2
(3.1-2)
K ( j Versuche)
Die Zahl der Versuche j, die im Mittel E
K(j Versuche)
= 1 Kollision verursachen, ergibt sich, in-
dem (3.1-2) gleich 1 gesetzt und nach j aufgelöst wird.
n
n
n
j (j
1)
2 2
bzw.
j
1/ 2
2 2
1
1/8 2
(3.1-3)
n/2
bzw. für große n :
j
)
2
2
Als wesentliches Ergebnis zeigt sich, dass ein Angriff auf starke Kollisionsresistenz viel weni-
ger Versuche erfordert. Die Zahl der Versuche für eine zu erwartende Kollision reduziert sich
etwa auf die Wurzel der Versuche, die bei einem Angriff auf schwache Kollisionsresistenz
erforderlich sind. Oder anders ausgedrückt, bei Angriff auf starke Kollisionsresistenz muss der
Hashwert die doppelte Länge in Bit aufweisen wie bei einem Angriff auf schwache Kollisions-
resistenz, damit ein Angriff vergleichbar schwer ist.
