TU Darmstadt

ULB

TUprints

Random Oracles in the Standard Model

Mittelbach, Arno Andreas (2016)
Random Oracles in the Standard Model.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Preview

Text
16-01-11-prefinal.pdf
Copyright Information: CC BY-NC-ND 3.0 Unported - Creative Commons, Attribution, NonCommercial, NoDerivs.
Download (2MB) | Preview

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

Random Oracles in the Standard Model

Language:

English

Referees:

Fischlin, Prof. Dr. Marc ; Ran, Prof. Dr. Canetti

Date:

December 2016

Place of Publication:

Darmstadt

Date of oral examination:

7 December 2015

Abstract:

Provable security is a fundamental concept of modern cryptography (see, e.g., Katz and Lindell; Introduction to Modern Cryptography, Chapter 1, 2007). In order to argue about security, we first require a precise and rigorous definition of what security means (e.g., a definition of secure encryption). Such a security definition, in particular, contains a description of the capabilities of an adversary, i.e., a model of the adversary which tries to come as close to reality as possible. Given a security model, the provable security approach is to provide a mathematical proof that a given construction achieves the desired level of security. In other words, we prove that no (efficient) adversary can break the security with good probability given that it behaves as defined within the security model. Typically, proofs reduce the security of a construction to an unproven cryptographic hardness-assumption---we show that the existence of an adversary violates an assumption---which, preferably, is as simple as possible. Furthermore, any assumption needs to be stated precisely. Examples of cryptographic hardness assumptions can be complexity-theoretic assumptions, such as, P vs. NP, the assumed existence of objects, such as, one-way functions, or long standing open problems from number theory, such as, factoring large integers or computing the discrete log in certain groups.

A widely used technique for the construction of cryptographic schemes is the so-called random oracle methodology, introduced in 1993 by Bellare and Rogaway (CCS, 1993). As before, we start with a precise model of security which is extended to include a uniformly random function which may be evaluated by any party (including the construction and adversary). As a random function has a huge, if not infinite description, parties cannot be given its code but, instead, are provided with black-box access to an oracle which evaluates the function for them. This oracle is called the random oracle. Then, as before, a mathematical proof is given that a construction is secure as per definition relative to the random oracle. Finally, to implement the scheme in practice, the random oracle is replaced by a cryptographic hash function (such as SHA-3).

No mathematical model can fully capture reality and, thus, cast in the framework of provable security, we may consider a random oracle security model as being somewhat further away from reality than a standard security model: in addition to the abstractions of the standard security model it is assumed that adversaries do not make any use of the code of a hash function; it is assumed that they do not even evaluate the hash function on their own but use an external device for the evaluation (i.e., black-box access). Now, if we trust schemes that are designed according to the provable security approach, should we then also trust schemes devised via the random oracle methodology?

This question has lead to a huge debate within the cryptographic community and has been discussed for more than two decades. The discussion is fueled by results showing that the extension of security models to include a random oracle may produce provably secure schemes that cannot be securely implemented. In 1998, Canetti, Goldreich, and Halevi (STOC, 1998) showed that schemes exist that are inherently insecure but which should be secure according to the random oracle methodology. In more detail, they present a public-key encryption scheme which an adversary can trivially attack when given the code of the hash function that was used to replace the random oracle. Note that this differs from, e.g., side-channel attacks: while here also the attack is successful because it is outside the model, implementations can, potentially, protect against these attacks and, thus, secure implementations may exist. With the scheme presented by Canetti et al., on the other hand, there is, provably, no secure implementation although the scheme is secure in the random oracle model.

Despite these negative results, many of the schemes that we trust on a daily basis---examples include the standardized public-key encryption scheme RSA-OAEP as well as the standardized signature schemes RSA-PSS and DSA---only have proofs in the random oracle model. Similarly, for many advanced cryptographic concepts, including IND-secure deterministic public-key encryption, correlated-input secure hash functions, universal hardcore functions, and many others, we (so far) only have constructions in the random oracle model. One reason for the success of random oracles is that they allow to design very efficient and natural schemes. Furthermore, the power of random oracles enables us to realize concepts which we would not know how to implement without random oracles. A third, and very compelling argument in favor of the random oracle methodology is that the random oracle heuristic seems to be a good one: no random oracle scheme which was not designed to portrait inconsistencies of the random oracle model has been attacked due to the use of random oracles. However, if a scheme is, indeed, secure, should we then not be able to understand and pinpoint the underlying source of hardness?

In this thesis we study random oracles with the help of program obfuscation (in particular indistinguishability obfuscation and point-function obfuscation). The study of obfuscation has a long tradition in computer science, and specifically in cryptography, but only recent advancements gave rise to the first candidate constructions of provably secure general-purpose indistinguishability obfuscators (Garg et al.; FOCS, 2013). Intuitively, a program obfuscator takes as input a program and produces a functionally equivalent but unintelligible program, i.e., the obfuscated program hides how it operates. Conceptually, this is very close to one of the fundamental abstractions made within the random oracle model where hash functions do not have an explicit and efficient description but can be evaluated only via black-box access to the random oracle. While an obfuscated hash function still has an explicit and efficient description, the description should hide the way the function works and, thus, intuitively, should be of no help to any adversary.

Using obfuscation-based techniques we show how to instantiate the random oracle in various cryptographic constructions. Amongst others, we obtain the first standard model (i.e., without random oracles) candidate construction for a universal hardcore function with long output, a q-query correlated-input secure hash function, and q-query IND-secure deterministic public-key encryption. We obtain our positive results by instantiating various forms of universal computational extractors. The universal computational extractor (UCE) framework was introduced by Bellare, Hoang, and Keelveedhi (CRYPTO, 2013) to provide (very strong) standard-model notions of hash functions that allow instantiating random oracles in a wide range of applications. Intriguingly, even though obfuscation allows us to show how to replace random oracles in certain situations, it also allows us to show limitations of the random oracle methodology as well as of UCEs. Using obfuscation-based techniques, we prove that several concrete UCE assumptions (including all originally proposed assumptions) cannot hold in case indistinguishability obfuscation exists. (We note that these negative results inspired the weaker UCE notions that lay at the core of our positive constructions.) Assuming the existence of indistinguishability obfuscation also allows us to extend the uninstantiability techniques of Canetti et al. (STOC, 1998) and show that a large class of random-oracle transformations are not sound. This affects the Encrypt-with-Hash transformation (Bellare et al.; CRYPTO, 2007) to construct deterministic public-key encryption, as well as the widely used Fujisaki--Okamoto transformation (Fujisaki, Okamoto; CRYPTO, 1999) which transforms weak public-key encryption schemes into strong public-key encryption schemes.

An often repeated criticism of random-oracle uninstantiability results is that the schemes only fail to be secure because they are designed to do so and, furthermore, their artificial design conflicts good cryptographic practice (see, for example, Koblitz and Menezes; Journal of Cryptology, 2007). Similar criticism can be voiced also for our counterexamples to the general applicability of the above mentioned random-oracle transformations. While this does not refute the mathematical validity of such uninstantiability results, we do, however, also present a very different counterexample to the soundness of the random oracle methodology: we show that if indistinguishability obfuscation exists, then a strong variant of point-function obfuscation (which can be similarly interpreted as a strong form of symmetric encryption) cannot be achieved without the help of random oracles while at the same time there are simple and elegant constructions in the random oracle model. We note that the same holds also for our negative results for UCEs.

In summary, we develop techniques to work with obfuscation which allow us to show that the existence of indistinguishability obfuscation implies that various random oracle techniques may lead to insecure schemes. Our results suggest, once again, that we should be careful with random oracle proofs and we hope that they spark further research to overcome the necessity to use random oracles in the first place. Concerning the latter, we make first steps by proposing new and widely applicable UCE notions together with standard-model candidate constructions showing that UCEs may, indeed, be a viable alternative to the use of random oracles.

Alternative Abstract:

Alternative Abstract

Language

Ein grundlegendes Prinzip moderner Kryptographie ist die sogenannte Beweisbare Sicherheit (siehe z.B. Katz und Lindell; Introduction to Modern Cryptography, Kapitel 1, 2007). Um die Sicherheit eines Verfahrens mathematisch zu zeigen wird zunächst eine präzise mathematische Definition davon benötigt, was Sicherheit bedeutet (z.B. eine Definition von sicherer Verschlüsselung). Eine solche Definition beinhaltet insbesondere eine Beschreibung der Fähigkeiten eines Angreifers, das heißt, ein Angreifermodell, welches so genau wie möglich die realen Gegebenheiten abbilden sollte. Gegeben eine Sicherheitsdefinition wird anschließend bewiesen, dass ein bestimmtes Verfahren die Definition erfüllt. Hierfür zeigen wir typischerweise, dass die Existenz eines (effizienten) Angreifers eine oder mehrere (meist unbewiesene) kryptographische Annahmen verletzt. Diese können beispielsweise aus der Komplexitätstheorie (z.B. P vs. NP) oder Zahlentheorie (z.B. Faktorisieren großer Zahlen oder die Berechnung des diskreten Logarithmus in bestimmten Gruppen) stammen oder es kann die Existenz kryptographischer Primitive gefordert werden (z.B. die Existenz von One-way Funktionen). Verwendete Annahmen müssen ebenfalls präzise definiert und sollten möglichst einfach und allgemein gehalten werden.

Eine weitverbreitete Methode für die Konstruktion von kryptographischen Primitiven ist die 1993 von Bellare und Rogaway eingeführte Random-Oracle-Methodik} (CCS, 1993). Wie zuvor ist der Ausgangspunkt auch hier eine präzise Sicherheitsdefinition. Diese wird zudem um die Existenz einer zufälligen Funktion erweitert, auf die jede Partei (insbesondere auch Konstruktion und Angreifer) Zugriff haben. Da eine zufällige Funktion eine sehr große, wenn nicht sogar unendlich große Beschreibung hat, kann diese den Parteien nicht direkt gegeben werden. Um die Funktion dennoch ausführen zu können erhalten sie daher Black-Box-Zugriff auf ein Orakel, das die Funktion für sie ausführt. Dieses Orakel wird auch Random Oracle genannt. Anschließend wird wie zuvor ein mathematischer Beweis geführt, um die Sicherheit der Konstruktion relativ zu der Existenz eines Random Oracles zu zeigen. Um eine solche Konstruktion in der Praxis verwenden zu können wird das Random Oracle für die Implementierung durch eine kryptographische Hashfunktion (z.B. SHA-3) instanziiert.

Ein mathematisches Modell kann die Realität niemals in Gänze abbilden. Ein um ein Random Oracle erweitertes Sicherheitsmodell kann daher als etwas weiter von der Realität entfernt angesehen werden: Neben den Abstraktionen eines Standard-Sicherheitsmodells wird zusätzlich angenommen, dass Angreifer die Beschreibung der Hashfunktion ignorieren und diese nur über eine externe Instanz (per Black-Box-Zugriff) auswerten. Wenn wir nun kryptographischen Verfahren vertrauen, die beweisbar sicher sind, sollten wir dann auch Verfahren vertrauen, die relativ zu einem Random Oracle beweisbar sicher sind?

Über die Einordnung von Random-Oracle-Verfahren wird seit über zwei Jahrzehnten in der kryptographischen Gemeinschaft gestritten. So zeigen diverse Resultate, dass die Erweiterung von Sicherheitsmodellen um Random Oracles problematische Konstruktionen zur Folge haben können, Konstruktionen die zwar im Random-Oracle-Modell sicher, jedoch in der Praxis immer unsicher sind, unabhängig davon wie sie implementiert werden. Canetti, Goldreich und Halevi (STOC, 1998) zeigen die Existenz von im Random-Oracle-Modell sicheren Public-key Verschlüsselungsverfahren, die jedoch trivial angreifbar sind sobald ein Angreifer Zugriff auf die Beschreibung der verwendeten Hashfunktion erhält. Ein solches Resultat ist insbesondere von z.B. Seitenkanalangriffen zu unterscheiden: Obwohl in beiden Fällen Angriffe erfolgreich sind, die durch das Sicherheitsmodell nicht abgedeckt werden, können Implementierungen potentiell gegen Seitenkanalangriffe gesichert werden; sichere Implementierungen können existieren. Im Falle des Public-key Verfahrens von Canetti et al. kann hingegen keine sichere Implementierung existieren obwohl das Verfahren im Random Oracle Modell als sicher bewiesen ist.

Trotz negativer Resultate sind viele Verfahren die wir tagtäglich einsetzen nur im Random Oracle Modell als sicher bewiesen. Beispiel hierfür sind das standardisierte Verschlüsselungsverfahren RSA-OAEP sowie die standardisierten Signaturverfahren RSA-PSS und DSA genannt. Darüber hinaus kennen wir für viele komplexeren kryptographischen Primitive lediglich Konstruktionen im Random Oracle Modell. Beispiele hierfür sind IND-sichere deterministische Public-key Verschlüsselung, Correlated-input sichere Hashfunktionen oder universelle Hardcorefunktionen.

Gründe für den Erfolg von Random Oracles sind vielfältig. Zum einen sind Random-Oracle-Verfahren häufig sehr effizient und natürlich. Darüber hinaus ermöglichen Random Oracles die Konstruktion starker kryptographischer Primitive, die wir ohne den Einsatz von Random Oracles derzeit nicht konstruieren können. Ein weiteres Argument für den Einsatz von Random Oracles ist das die Random-Oracle-Heuristik zu funktionieren scheint: Kein Random Oracle Verfahren, das nicht mit dem Ziel konstruiert worden ist Schwächen des Random Oracle Modells aufzuzeigen konnte bislang aufgrund der Nutzung von Random Oracles angegriffen werden. Aber sollten wir, wenn ein Verfahren in der Tat sicher ist, nicht in der Lage sein den Grund der Sicherheit, bzw. das zugrundeliegende schwere Problem zu identifizieren?

In dieser Dissertation untersuchen wir Random Oracles mit Hilfe von Code Obfuscation (insbesondere betrachten wir Indistinguishability Obfuscation sowie Point-function Obfuscation). Code Obfuscation hat eine lange Tradition in der Informatik (insbesondere der Software Entwicklung) wurde jedoch meist als Heuristik betrachtet. Ein wissenschaftlicher Durchbruch in kryptographischer Obfuscation (einer beweisbar sicheren Form von Obfuscation) gelang erst kürzlich Garg et al. (FOCS, 2013), die eine Konstruktion eines Indistinguishability Obfuscators vorschlagen. Ein Code Obfuscator ist vereinfacht gesagt ein Programm, welches als Eingabe den Code eines Programms erwartet und einen funktional äquivalenten, jedoch nicht mehr verständlichen, Programmcode erzeugt: Aus dem obfuszierten Programmcode kann die Art und Weise, wie das Programm Berechnungen durchführt nicht mehr rekonstruiert werden. Konzeptionell ist dies ähnlich zu den Abstraktionen des Random-Oracle-Modells bei denen davon ausgegangen wird, dass kein Programmcode der Hashfunktion existiert und diese nur mittels Black-Box-Zugriff auf das Random Oracle ausgewertet werden kann. Bei einer obfuszierten Hashfunktion liegt zwar Code vor, jedoch versteckt die Beschreibung jegliche Informationen über die Funktion und sollte daher einem Angreifer, so die Idee, nicht nützlich sein.

In der vorliegenden Arbeit zeigen wir, wie mittels Obfuscation, Random Oracles in verschiedenen Konstruktionen ersetzt werden können. Unter anderem geben wir die ersten Standardmodell-Konstruktionen (d.h. Konstruktionen ohne die Verwendung von Random Oracles) für universelle Hardcorefunktionen mit langer Ausgabe, für q-query Correlated-input sichere Hashfunktionen sowie für q-query IND-sichere deterministische Verschlüsselung an. Hierfür zeigen wir, wie verschiedene sogenannte Universal Computational Extractors mittels Obfuscation instanziiert werden können. Das Universal Computational Extractor (UCE) Framework wurde von Bellare, Hoang und Keelveedhi (CRYPTO, 2013) vorgeschlagen, um ausreichend starke Eigenschaften von Hashfunktionen im Standardmodell abbilden zu können, die es erlauben Random Oracles in unterschiedlichen Anwendungen zu instanziieren. Obfuscation erlaubt hingegen nicht nur Random Oracles in verschiedenen Kontexten zu ersetzen, sondern kann auch zur Auslotung der Grenzen von Random Oracles und UCEs verwendet werden. So zeigen wir, dass verschiedene UCE-Annahmen (dies beinhaltet insbesondere alle Originalannahmen von Bellare et al.) nicht haltbar sind, sollte Indistinguishability Obfuscation existieren. (Es sei angemerkt, dass diese negativen Resultate die schwächeren UCE Annahmen inspiriert haben, welche die Basis unserer positiven Konstruktionen bilden.) Unter der Annahme, dass Indistinguishability Obfuscation existiert, können wir darüber hinaus die Uninstanziierbarkeitsresultate von Canetti et al. (STOC, 1998) erweitern: Wir zeigen, dass diverse Random-Oracle-Transformationen uninstanziierbare Konstruktionen hervorbringen können. Dies betrifft unter anderem die Encrypt-with-Hash Transformation (Bellare et al.; CRYPTO, 2007) für die Erzeugung deterministischer Public-key Verschlüsselungssysteme sowie die weitverbreitete Fujisaki--Okamoto Transformation (Fujisaki, Okamoto; CRYPTO, 1999), die schwache Public-key Verschlüsselungsverfahren in sehr starke Verfahren transformiert.

Eine häufig vorgebrachte Kritik an Uninstanziierbarkeitsresultaten für Random Oracles ist, dass die aufgezeigten Verfahren nur deswegen unsicher werden, da diese explizit so konstruiert worden sind und dass dies nur deswegen möglich ist weil ihr künstlicher Aufbau gute kryptographischer Praxis ignoriert (siehe z.B. Koblitz und Menezes; Journal of Cryptology, 2007). Diese Kritik kann ebenso gegen unsere Gegenbeispiele für die allgemeine Anwendbarkeit der oben genannten Random-Oracle-Transformationen vorgebracht werden. Obwohl dies die mathematische Gültigkeit der Ergebnisse nicht mindert, zeigen wir dennoch weitere Gegenbeispiele für die diese Kritik nicht gilt. Unter der Annahme, dass Indistinguishability Obfuscation existiert zeigen wir, dass starke Varianten von Point-function Obfuscation (diese können auch als starke symmetrische Verschlüsselungsverfahren angesehen werden) nicht existieren können, obwohl im Random-Oracle-Modell effiziente und einfache Konstruktionen existieren.

Zusammenfassung: Wir entwickeln Techniken zur Arbeit mit Obfsucation, die uns erlauben zu zeigen, dass diverse Random-Oracle-Techniken zu unsicheren Verfahren führen können unter der Annahme, dass Indistinguishability Obfuscation existiert. Unsere Ergebnisse legen nahe, Random-Oracle-Beweisen mit einer gewissen Skepsis zu begegnen und dass die Forschung an Techniken zur Überwindung von Random Oracles ein lohnenswertes Unterfangen ist. In diesem Sinne zeigen wir neue und schwächere UCE Definitionen auf (mit zugehörigen Standardmodell-Konstruktionen), die es erlauben Random Oracles in vielfältigen Kontexten zu umgehen.

German

URN:

urn:nbn:de:tuda-tuprints-52224

Classification DDC:

000 Generalities, computers, information > 004 Computer science

Divisions:

20 Department of Computer Science > Cryptography and Complexity Theory

Date Deposited:

21 Jan 2016 07:46

Last Modified:

09 Jul 2020 01:12

URI: