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

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. In many popular cryptographic protocols like "hash and sign" or "non-interactive zero-knowledge protocols" hash functions are used. To prove the security of such protocols the so called random oracle methodology is often used. For the proof (in the random oracle model) the hash function is treated like a real random function, a so called random oracle. Since for an implementation (in the standard model) of such a protocol a hash function is used, it could be that the proof does not hold. This has been clarified by Canetti, Goldreich, and Halevi 1998 by an example protocol, which is secure in the random oracle model, but could not be securely implemented with any hash function. Therefore it is vitally important to know, when the random oracle methodology yields secure protocols. The example above shows, that is not sufficient to study only the hash functions and formulate conditions for them. In fact the whole protocol has to be studied. Since we do not want to deal with every protocol on its own, it is useful to treat them as generic as possible, and formulate conditions for the protocols and the hash functions. This approach is used in this thesis and leads to a better security of the random oracle methodology. The thesis is organized as follows: In chapter 2 first some basics and notations are given. Furthermore the new notion of "computational independence" is introduced, which is a pendant to "computational indistinguishability" and provides an exacter treatment of probability distributions. In chapter 3 random oracles are defined and examined if different kinds of random oracles could be simulated efficiently, if one is given but another one is needed. It is shown that there could be theoretical problems, but that they are of small importance in practice. In chapter 4 the hash functions for implementation are studied, first some that are already known and then some new one, namely unpredictable and random-preserving hash functions. For classification the new hash functions are compared with already known ones, so that they could be sorted by "strength". Because we study the security of protocols we have to clarify, what exactly a protocol and its security is. This is done in chapter 5. Therefore the structure of a protocol is given, which is as generic as possible and as special as necessary. Moreover attacks and their possible success are defined. In chapter 6 the random oracle methodology is illustrated in more detail and some similar techniques and the weakness of the random oracle methodology are described. Then the new approaches are used to show how to make the random oracle methodology more secure. Therefore basically the protocols are transformed and the distribution of the used variables is compared between the random oracle model and the standard model. For two conjectures no formal proof could be given, but there are some well founded arguments for their validity. At the end the results are recapitulated and there is a discussion of open questions in chapter 7.