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-
 
Search WWH ::




Custom Search