Cryptography Reference
In-Depth Information
jeder Nachricht speichert der Server maximal einen Hashwert. Am Anfang ist die Liste
der Nachricht-Hashwert-Paare leer. Wird nun eine Anfrage
x ∈ D
an den Server gestellt,
so schaut er zunächst nach, ob bereits ein Paar
(
x, h
)
, für irgendeinen Hashwert
h
∈
B
, gespeichert ist. Falls ja, gibt er
h
zurück. Ansonsten wählt der Server zufällig und
gleichverteilt einen neuen Hashwert
h
aus
B
, speichert das Paar
(
x, h
)
und liefert
h
als
Antwort zurück. Der Vollständigkeit halber legen wir fest, dass, falls
x
∈
D
gilt, das
zurückgegeben wird.
Wir bezeichnen das gerade beschriebene Zufallsorakel mit H oder auch H
B
, H
D
oder
H
B
, je nachdem, ob der Definitions- oder der Bildbereich des Zufallsorakels eine Rolle
spielt bzw. aus dem Kontext hervorgeht.
Ein Zufallsorakel modelliert also, dass man einen Hashwert zu einer Anfrage
x
nicht
vorhersagen kann, wenn das Zufallsorakel noch nicht zu
x
befragt wurde, da ein solcher
Hashwert erst bei der ersten Anfrage zufällig gewählt wird. Ohne das Zufallsorakel zu be-
fragen, kann man den Hashwert zu
x
höchstens raten, was bei ausreichend großem Bildbe-
reich allerdings wenig erfolgversprechend ist. In diesem Sinne modelliert ein Zufallsorakel
eine
ideale Hashfunktion
. In der Tat erfüllt ein Zufallsorakel alle Anforderungen, die man
von einer Hashfunktion erwarten würde - neben den in Abschnitt 8.2 kennengelernten
auch viele weitere.
Insbesondere sieht man leicht, dass ein Zufallsorakel bestmögliche Kollisionsresistenz
bietet: mehr als ein Geburtstagsangriff ist selbst für einen unbeschränkten Kollisionsfin-
der nicht möglich. Um dies einzusehen, sei
A
ein Kollisionsfinder gemäß Definition 8.2.1,
wobei wir nun annehmen, dass
A
Zugriff auf das Zufallsorakel H hat. Dann bezeichne
adv
Coll
(
A,
H
)
den Vorteil von
A
bezüglich H analog zu Definition 8.2.2. Man beachte,
dass im zugehörigen Experiment
Fehlersymbol
⊥
E
A
die Indexwahl nun weggelassen werden kann. Um-
gekehrt umfasst der Wahrscheinlichkeitsraum zu
E
A
die vom Zufallsorakel verwendeten
Zufallsbits.
Im Folgenden bezeichnen wir einen Angreifer/Kollisionsfinder
A
für H als
q
-beschränkt
,
falls in jedem Lauf des zugehörigen Experimentes
E
A
höchstens
q
Anfragen an H gestellt
werden. Dabei zählen die zwei Anfragen an H, die nötig sind, um zu testen, ob das von
A
ausgegebene Nachrichtenpaar eine Kollision darstellt, mit;
A
selbst darf im Experiment
E
A
2
Anfragen an H stellen.
Nun erhalten wir folgendes Lemma.
also lediglich
q
−
Lemma 10.4.1.
Es sei
q
≥
2
und
A
ein
q
-beschränkter Kollisionsfinder. Dann gilt:
q
(
q
−
1)
adv
Coll
(
A,
)
≤
,
mit
N
=
|
B
|
.
H
2
N
Beweis.
Der Beweis dieser Aussage folgt leicht aus der Eigenschaft des Zufallsorakels
und Lemma 3.3.4 (Geburtstagsphänomen): Nach Annahme werden im Experiment
E
A
insgesamt maximal
q
Hashwerte vom Zufallsorakel gewählt. Diese Hashwerte werden
nach Definition des Zufallsorakels zufällig und unabhängig voneinander gewählt. Die
Wahrscheinlichkeit, dass unter diesen eine Kollision auftritt, ist gemäß Lemma 3.3.4 dur
ch
q
(
q
−
1)
2
N
nach oben beschränkt.
Aus der Kollisionsresistenz können wir zudem schließen, dass ein Zufallsorakel zweites-