Cryptography Reference
In-Depth Information
Urbild- sowie Urbild-resistent ist (siehe Aufgabe 8.6.1 und Aufgabe 10.7.2). Daneben gilt
auch, dass der von einem Zufallsorakel gelieferte Hashwert keinerlei Information über die
Eingabe in sich birgt, da im Zufallsorakel der Hashwert unabhängig von der Eingabe
gewählt wird; eine Eigenschaft, die man von »normalen« Hashfunktionen nicht verlangt
und die insbesondere durch die Kollisionsresistenz nicht impliziert ist: eine Hashfunktion
kann auch dann kollisionsresistent sein, wenn sie, zum Beispiel, immer das erste Bit der
gegebenen Nachricht mit ausgibt (siehe Aufgabe 8.6.2).
Zufallsorakel lassen sich nutzen, um einfache, aber dennoch sehr eziente Konstruk-
tionen für kryptographische Primitive zu erhalten, die sicher sind, sofern man idealisierte,
durch Zufallsorakel modellierte Hashfunktionen voraussetzt. Neben digitalen Signaturen
(siehe unten) gilt dies für Verschlüsselungsverfahren (siehe die Bemerkungen am Ende
von Abschnitt 6.4.3 sowie Aufgabe 10.7.4) und MACs, um nur einige Beispiele zu nen-
nen. Wie in Aufgabe 10.7.3 näher untersucht werden soll, erhält man etwa einen sicheren
MAC wie folgt: Die Etikettierfunktion
T
sei durch
l
T
(
x, k
)=
H
(
k
·
x
)
für alle
x
∈
D
und
k
∈{
0
,
1
}
(10.4.1)
definiert, wobei
k · x
die Konkatenation von
k
und
x
bezeichnet. Wie bereits in Auf-
gabe 9.8.8 gezeigt, wäre diese Konstruktion unsicher, falls das Zufallsorakel durch eine
Familie iterierter Hashfunktionen ersetzt werden würde.
Leider kann man ein Zufallsorakel (wohl) nicht realisieren, zumindest nicht, ohne wei-
tere unrealistische Annahmen zu machen. Insbesondere ist die obige »Implementierung«
eines Zufallsorakels als Server unrealistisch: Der Server wäre ein Flaschenhals und würde
unter den zahlreichen Anfragen und zu speichernden Nachricht-Hashwert-Paaren schnell
zusammenbrechen. Schlimmer noch, der Server müsste völlig vertrauenswürdig, robust
und fehlerfrei sein. Im Bereich der digitalen Signaturen zum Beispiel könnte ein bös-
williger Server Hashwerte in Abhängigkeit der Nachrichten wählen, um so absichtlich
Kollisionen herbeizuführen. Im Hash-then-Sign-Ansatz könnten sich dadurch leicht Si-
gnaturen fälschen lassen. Zudem lernt ein solcher Server natürlich alle zu signierenden
Nachrichten. Würden Nachricht-Hashwert-Paare verloren gehen, so würden Signaturen
nutzlos oder ungültig werden. Ein weiteres schwerwiegendes Problem ist die Frage, wie
man erreicht, dass beliebige Parteien »unbehelligt« mit dem Server kommunizieren kön-
nen. Die Liste der Probleme ließe sich beliebig fortsetzen (siehe auch Aufgabe 10.7.5).
Aus den genannten Gründen spricht man bei kryptographischen Konstruktionen, die
ein Zufallsorakel als Hashfunktion verwenden, oder anders ausgedrückt, in deren Sicher-
heitsbeweis eine Hashfunktion als Zufallsorakel modelliert wird, von Konstruktionen bzw.
Sicherheitsbeweisen im »
Zufallsorakel-Modell
«(
random oracle model (ROM)
). Das Mo-
dell, in dem wir bisher gearbeitet haben, wird zur Abgrenzung »
Standardmodell
«ge-
nannt.
In der Praxis wird ein Zufallsorakel meist durch eine konkrete Hashfunktion, z. B.,
eine Hashfunktion aus der SHA-Familie, ersetzt. Damit stellt sich natürlich die Frage, ob
dies gerechtfertigt ist, d. h., ob beim Übergang vom Zufallsorakel zu einer konkreten Hash-
funktion die bewiesenen Sicherheitseigenschaften der betrachteten Konstruktion erhalten
bleiben.
