Zufallsorakel

Ein Zufallsorakel (englisch random oracle) wird in der Kryptologie verwendet, um eine ideale kryptologische Hashfunktion zu modellieren. Die Hashfunktion wird dabei durch Zugriff auf ein Orakel ausgewertet. Das Zufallsorakel gibt zu jeder Eingabe einen zufälligen Ausgabewert zurück, falls diese Eingabe zum ersten Mal abgefragt wird, ansonsten die gleiche Ausgabe wie bei der letzten Abfrage. Aufgrund der Konstruktion des Zufallsorakels erfüllt es die klassischen Eigenschaften einer kryptologischen Hashfunktion, starke Kollisionsresistenz und Einwegfunktion, in perfekter Weise.

Das Random-Oracle-Modell

Von einem Sicherheitsbeweis, der ein Zufallsorakel verwendet, sagt man, er sei im Random-Oracle-Modell geführt worden. Entwickelt wurde das Random-Oracle-Modell von Mihir Bellare und Phillip Rogaway.[1] Protokolle, deren Sicherheit im Random-Oracle-Modell bewiesen wurde, sind im Allgemeinen effizienter als solche mit einem Sicherheitsbeweis im kryptologischen Standardmodell ohne Zufallsorakel.

Dieser Effizienzgewinn erfolgt allerdings auf Kosten der Sicherheit, da es gemäß der Church-Turing-These unmöglich ist, einen endlichen Algorithmus anzugeben, der ein Zufallsorakel implementiert. Es gibt (speziell für diesen Beweis konstruierte) Protokolle, die im Random-Oracle-Modell beweisbar sicher sind, jedoch für jede konkrete Instanziierung des Zufallsorakels durch eine Hashfunktion unsicher sind.[2]

So kann beispielsweise eine Hashfunktion Teilbits der Eingabe verraten, ohne gegen die Kollisionsresistenz zu verstoßen, was bei Commitment-Verfahren zu Problemen führen kann. Des Weiteren können Hashfunktionen basierend auf der Merkle-Damgård-Konstruktion von Erweiterungsangriffen betroffen sein, was diese unterscheidbar von echtem Zufall macht.

Literatur

  • Douglas R. Stinson: Cryptography. Theory and Practice. 3. Auflage. Chapman & Hall/CRC, 2005, ISBN 1-58488-508-4, Seiten 122–123
  • Jonathan Katz, Yehuda Lindell: Introduction to Modern Cryptography: Principles and Protocols, S. 457, Chapman & Hall/CRC, 2007

Einzelnachweise

  1. ↑ Mihir Bellare and Phillip Rogaway: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security. 1993, S. 62–73 (ucsd.edu).
  2. ↑ Ran Canetti, Oded Goldreich, and Shai Halevi: The Random Oracle Methodology, Revisited. In: STOC. 1998, S. 209–218 (weizmann.ac.il).