Cryptography Reference
In-Depth Information
Bevor wir diese Frage beantworten, könnte man sich zunächst die Frage stellen, wel-
che Eigenschaften eine Hashfunktion, wenn sie ein Zufallsorakel ersetzen soll, überhaupt
haben sollte. Kollisionsresistenz alleine reicht im Allgemeinen sicherlich nicht; wie oben
bereits angedeutet, bietet ein Zufallsorakel viel mehr als das (zum Beispiel, dass ein Hash-
wert keine direkte Information über die Eingabe liefert). Es gibt intensive Anstrengungen
in der Kryptographie, Eigenschaften von Familien von Hashfunktionen zu definieren und
entsprechende Familien zu konstruieren, die wenigstens einige relevante Eigenschaften
des Zufallsorakels fassen (siehe auch Abschnitt 10.8).
Unabhängig von der Präzisierung der Eigenschaften lautet die Antwort auf die obige
Frage aber: Nein! Es ist formal nicht gerechtfertigt ein Zufallsorakel durch eine konkrete
Hashfunktion zu ersetzen. Jede konkrete Hashfunktion ist weit davon entfernt, sich wie ein
Zufallsorakel zu verhalten. Zunächst ist klar, dass bei einer konkreten Hashfunktion die
Hashwerte zu allen Eingaben von Anfang an festliegen, nicht erst nachdem eine Anfrage
gestellt wurde. Der Begriff der Anfrage macht für Hashfunktionen auch keinen Sinn. Jeder
kann den Hashwert zu einer Nachricht auf seine Weise bestimmen, solange das Ergebnis
mit der Spezifikation der Hashfunktion übereinstimmt. Es ist insbesondere nicht nötig,
explizit ein Orakel aufzurufen.
Außerdem gibt es viele konkrete Konstruktionen, die deutlich machen, dass es kei-
ne allgemeine, formale Rechtfertigung für das Ersetzen eines Zufallsorakels durch eine
konkrete Hashfunktion gibt. Wir nennen nur einige Beispiele:
- Wir haben gesehen, dass ein Zufallsorakel kollisionsresistent ist. Eine konkrete Hash-
funktion kann dies aus den in Abschnitt 8.2 beschriebenen Gründen niemals sein,
höchstens eine Familie von Hashfunktionen. Zudem gilt die Kollisionsresistenz für
Zufallsorakel sogar für berechenbar unbeschränkte Kollisionsfinder, was für Familien
von Hashfunktionen nicht möglich wäre, da sich ein solcher Kollisionsfinder für jedes
Mitglied der Familie eine Kollision merken könnte.
- Während, wie oben besprochen, man mit Hilfe eines Zufallsorakels leicht einen si-
cheren MAC konstruieren kann, ist die dort angegebene Konstruktion unsicher, falls
das Zufallsorakel durch eine Familie iterierter MD-Hashfunktionen ersetzt wird (sie-
he Aufgabe 10.7.3).
- In der Literatur finden sich (etwas künstliche) kryptographische Konstruktionen, die
man im ROM als sicher nachweisen kann, die aber für
jede
konkrete Familie von
Hashfunktionen unsicher sind (siehe auch Abschnitt 10.8).
Insgesamt stehen Sicherheitsbeweise im ROM auf recht wackligen Beinen, weshalb das
ROM für viel Diskussion in der Kryptographie sorgt und man insgesamt bestrebt ist,
Sicherheitsbeweise möglichst im Standardmodell zu führen.
Trotzdem wird das ROM in der Kryptographie häufig verwendet. Dies hat vor allem
die folgenden zwei Gründe:
- Kryptographische Konstruktionen, deren Sicherheit auf dem ROM basieren, sind
häufig deutlich e
zienter als solche, die ohne das ROM auskommen.
- Viele in der Praxis eingesetzte kryptographische Verfahren konnten bisher nur im
ROM als sicher nachgewiesen werden.
Ein Sicherheitsbeweis im ROM ist immerhin besser als überhaupt kein Beweis. Ein Beweis
im ROM deutet zumindest darauf hin, dass die betrachtete kryptographische Konstruk-
tion im Prinzip in Ordnung ist. Die Konstruktion kann »lediglich« durch das »Brechen«
der konkreten Hashfunktion - die das Zufallsorakel ersetzt - unsicher werden.
