Neue Ansätze für die Sicherheit der Random-Oracle-Methodik

Thumbnail Image

Files

FayBjoern-2009-01-30.pdf (842.07 KB)

Date

2008

Authors

Advisors/Reviewers

Further Contributors

Contributing Institutions

Publisher

Journal Title

Journal ISSN

Volume Title

Publisher

License

In Copyright
In Copyright

Quotable link

DOI:
http://dx.doi.org/10.22029/jlupub-9580

Abstract

In vielen gängigen kryptographischen Protokollen, wie z. B. "Hash and Sign" oder "nicht-interaktiven Zero-Knowledge-Protokollen", kommen Hashfunktionen zum Einsatz. Um die Sicherheit dieser Protokolle zu beweisen bedient man sich häufig der sogenannten Random-Oracle-Methodik. Dabei wird eine Hashfunktion während des Beweises (im Random-Oracle-Modell) so behandelt als würde sie sich wie eine echte Zufallsfunktion verhalten, ein sogenanntes Random-Oracle. Da eine Implementierung (im Standard-Modell) eines solchen Protokolls wieder mit einer Hashfunktion erfolgt, statt eines Random-Oracles, kann es sein, dass der Beweis seine Gültigkeit verliert. Dies wurde anhand eines Beispielprotokolls von Canetti, Goldreich und Halevi 1998 verdeutlicht, welches im Random-Oracle-Modell sicher ist, sich aber mit keiner Hashfunktion sicher implementieren lässt. Es ist daher von wesentlicher Bedeutung zu erkennen, wann die Random-Oracle-Methodik zu sicheren Protokollen führt. Wie das oben genannte Beispiel zeigt, reicht es dazu nicht, nur die Hashfunktionen zu untersuchen und geeignete Bedingungen an diese zu stellen. Vielmehr muss das vollständige Protokoll untersucht werden. Um aber nicht jedes Protokoll einzeln zu behandeln, ist es hilfreich, die Protokolle so allgemein wie möglich zu halten, und dann Bedingungen sowohl an die Protokolle als auch an die Hashfunktionen zu stellen. Genau dieses Vorgehen wird in der vorliegenden Arbeit angewendet und führt letztendlich zu einer besseren Absicherung der Random-Oracle-Methodik. Die vorliegende Arbeit gliedert sich wie folgt: Zunächst werden in Kapitel 2 einige Grundlagen zusammenfassend dargestellt und Notationen angegeben. Außerdem wird neben dem bekannten Begriff der "rechnerischen Ununterscheidbarkeit" noch der neue Begriff der "rechnerischen Unabhängigkeit" eingeführt und dadurch die genauere Betrachtung von Verteilungen ermöglicht. Im Kapitel 3 wird definiert, was formal unter einem Random-Oracle zu verstehen ist und es wird verglichen, inwieweit sich unterschiedliche Arten von Random-Oracles (wie sie von verschiedenen Autoren benutzt werden) effizient gegenseitig simulieren lassen. Es hat sich herausgestellt, dass sich hier durchaus theoretisch Probleme ergeben können, diese aber für die Praxis eher von untergeordneter Bedeutung sind. Im Kapitel 4 werden dann die zur Implementierung benötigten Hashfunktionen behandelt, wobei zuerst bereits bekannte Hashfunktionen dargestellt und anschließend neue definiert werden, nämlich unvorhersehbare und zufallerhaltende, welche zur besseren Absicherung der Random-Oracle-Methodik benötigt werden. Für eine Einordnung der neuen Hashfunktionen in das bereits bestehende Gefüge von Hashfunktionen werden die in dieser Arbeit vorgestellten Hashfunktionen noch miteinander verglichen, so dass sie sich am Ende in etwa der "Stärke" nach anordnen lassen. Da wir die Sicherheit von Protokollen betrachten, muss geklärt werden, was genau unter einem solchen Protokoll zu verstehen ist. Dies wird in Kapitel 5 behandelt. Dabei wird die Struktur der Protokolle soweit angegeben, dass sie zwar eine sehr spezielle Form haben, aber immer noch so allgemein sind, dass sich viele Anwendungen damit realisieren lassen. Außerdem werden die möglichen Angriffe auf diese Protokolle spezifiziert sowie die möglichen Erfolge, die ein solcher Angriff haben kann. In Kapitel 6 wird schließlich die Random-Oracle-Methodik noch einmal genauer dargestellt und mit ähnlichen Verfahren verglichen sowie deren Unsicherheit aufgezeigt. Anschließend wird mit Hilfe der hier entwickelten neuen Ansätze gezeigt, wie sich die Random-Oracle-Methodik besser absichern lässt. Dabei wird im Wesentlichen eine Transformation der Protokolle durchgeführt und die Verteilung der an den Protokollen beteiligten Variablen im Random-Oracle-Modell und im Standard-Modell verglichen. Für zwei Vermutungen ließen sich leider keine streng formalen Beweise finden. Allerdings liefern die in dieser Arbeit entwickelten Methoden trotzdem gute und plausible Argumente für die Gültigkeit dieser Vermutungen. Abschließend werden in Kapitel 7 die wichtigsten Ergebnisse zusammengefasst und die sich aus dieser Arbeit ergebenden offenen Fragen diskutiert.

Link to publications or other datasets

Description

Notes

Original publication in

Original publication in

Anthology

Collections

Dissertationen/Habilitationen

URI of original publication

Forschungsdaten

Series

Citation