Papers in Computer Science

Discussion of computer science publications

Random Oracles are Practical: A Paradigm for Designing Efficient Protocols

Posted by dcoetzee on May 3rd, 2009

Citation: Bellare, M. and Rogaway, P. Random oracles are practical: a paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security (Fairfax, Virginia, United States, November 3-5, 1993). CCS 1993. ACM, New York, NY, 62-73. (PDF)

Abstract: We argue that the random oracle model — where all parties have access to a public random oracle — provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol P is produced by first devising and proving correct a protocol PR for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function h. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.

Discussion: This influential 1993 paper introduced the random oracle model, designed to enable a methodology for the design of efficient formally sound cryptographic protocols such as encryption and authentication, and is one of the milestones in the philosophy of cryptographic protocol design.

The holy grail of cryptography is cryptographic protocols – algorithms for tasks like encryption and signing – that are provably secure against attack. However, in the study of algorithms, negative results such as “no efficient algorithm exists to break this scheme” are notoriously difficult to prove; this is one reason why major problems like whether P=NP defy solution.

Like complexity theorists, cryptographers turned to conditional results: they assume that some cryptographic primitive is available – a very simple building block such as one-way functions, or one-way trapdoor functions – and then build more complex primitives, including complete protocols, using them. In “The Random Oracle Metholodgy, Revisited,” discussed later, Ran Canetti defended this practice:

One of the great contributions of complexity-based modern cryptography, developed in the past quarter of a century, is the ability to base the security of many varied protocols on a small number of well-defined and well-studied complexity assumptions. Furthermore, typically the proof of security of a protocol provides us with a method for transforming [an] adversary that breaks the security of said protocol into an adversary that refutes one of the well-studied assumptions. The Random Oracle Methodology does away with these advantages.

One may draw an analogy with the P=NP problem: why do we suppose that NP-hard problems are difficult to solve? Because if we could solve any one of them in polynomial time, it would resolve the longstanding P=NP problem and provide fast algorithms for a variety of well-studied problems. Likewise, if we could show that a protocol relying on a particular cryptographic primitive is insecure, it would solve a longstanding open problem (e.g. do one way functions exist?) and simultaneously break many other protocols relying on that primitive.

However, unlike the case of P=NP, systems proven conditionally secure by reduction to cryptographic primitives are rarely implemented. Indeed, until the publication of “Random Oracles are Practical,” most cryptographic systems used in practice had no formal justification whatsoever. This is because conditionally secure formal systems are much too inefficient for practical use. Yet there were ad hoc efficient cryptographic protocols in use in practice that clearly were good at withstanding concerted attack – without any formal backing, what was it that gave them their strength? Bellare and Rogaway write:

Theorists view certain primitives (e.g. one-way functions) as “basic” and build more powerful primitivees (e.g. pseudorandom functions) out of them in inefficient ways; but in practice, powerful primitives are readily available and the so-called basic ones seem to be no easier to implement. In fact theorists deny themselves the capabilities of practical primitives which satisfy not only the strongest kinds of assumptions they like to make, but even have strengths which have not been defined or formalized.

To facilitate the design of more efficient protocols,  the authors advance the following methodology: suppose that all parties in a cryptographic protocol, including the attacker, have access to a random oracle. A random oracle is like an ideal pseudorandom number generator: you seed it with a particular initial value, and then it gives you an arbitrarily long sequence of random bits. The sequence depends on the seed, but has no other predictable patterns (and in particular, does not cycle).

In real life, random oracles cannot be implemented; deterministic programs cannot produce arbitrarily-long random outputs. But this paper asserts the following thesis: if a protocol can be proven secure in the presence of a random oracle, and we then replace calls to the random oracle with calls to a good cryptographically secure pseudorandom number generator, a process called instantiation, the resulting protocol is expected to be secure in practice. Moreover, schemes designed using this method are expected to be more efficient than conditionally secure schemes.

It’s not hard to see that this methodology is not perfectly sound in theory. For example, one can design a cryptographic protocol that passes zero to the oracle, and if the result is f(0), it reveals its secret key. In the random oracle model, this is very unlikely to occur, so the system remains secure; but if the system is instantiated with f, then it always occurs, and the system is completely insecure. Part of the thesis is that “an appropriate instantiation for a random oracle ought to work for any protocol which did not intentionally frustrate our method by anticipating the exact mechanism which would instantiate its oracles” (section 6, Instantiation).

To provide some practical justification for its thesis, “Random Oracles are Practical” presents a very simple, efficient encryption algorithm for long messages that is secure against a variety of attacks in the random oracle model. We begin by assuming (as in the conditionally secure model) that we have access to two primitives:

  • a trapdoor permutation f, which is a function that, like RSA, can encrypt or decrypt a short k-bit value;
  • a random hash function H that inputs arbitrarily long strings and outputs k-bit results.

Now suppose we want to encrypt the message x. We choose a k-bit random value s which will be used as the seed for the random oracle. We XOR the output of the oracle with the message x to generate the encrypted message. Finally, we append the encryption f(s) of the seed with the trapdoor permutation, so that the receiver can determine s, and the hash H(sx) of the seed together with the message to protect against tampering. This scheme is secure against three types of attacks in the random oracle model:

  • In a chosen-plaintext attack, the polynomial-time adversary supplies two strings, one of them is encrypted, and the adversary must determine by examining the ciphertext which one was encrypted. They don’t have to do this perfectly, just significantly more than 50% of the time.
  • In a chosen-ciphertext attack, the adversary is additionally given access to the decryption function, and they can ask it to decrypt any string except the encrypted string they’re given.
  • Finally, a malleability adversary is one that, given the encryption of one string, can determine the encryption of a related string, such as an extension of the original string or one where some characters are replaced by other characters.

Sure enough, when the random oracle is replaced by a cryptographically secure pseudorandom number generator, the result is a system that is secure in practice, in the sense that no practical attack against the system has ever been found. The authors go on to describe similar efficient systems for signing and non-interactive zero-knowledge proofs that are sound in the random oracle model.

Over the years, many researchers took the advice of this paper and designed new efficient protocols based on the random oracle model. Encouragingly, these systems withstood the test of the time and have not been broken. This seems to say that the methodology is sound. But in 2002, a strong result by Canetti, Goldreich, and Halevi cast doubt upon the thesis (“The Random Oracle Methodology, Revisited.” J. ACM 51, 4 (Jul. 2004), 557-594. PDF). Their main result is as follows:

There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. [...] Moreover, each of these schemes has a “generic adversary”, that when given as input the description of an implementation of the oracle, breaks the scheme that uses this implementation.

In other words, not only can these encryption schemes be broken for any possible instantiation, but they supply a constructive method to do so fully automatically.

The proof method is similar to the example cited earlier of an encryption protocol revealing secret information if the oracle returns f(0) when given zero for the seed, where f is the cryptographically secure pseudorandom number generator used to instantiate the protocol. The difference is that instead of modifying the protocol to always fail for one particular f, it causes it to fail on a different f for each input. The input that causes failure under instantiation with f is simply the description of f (i.e., the machine code for f). Because the attacker has access to this information, they know just how to break the system. Fundamentally, this attack relies on a sort of “white box” reverse engineering – not only can the attacker execute the function f, but they can examine its code as well.

This does not say that the practical schemes designed to be secure in the random oracle model are insecure — to the contrary, they have stood the test of time quite robustly — but it does call the theoretical advantages of the paradigm into doubt. The authors of “The Random Oracle Methodology, Revisited” disagree sharply about the philosophical implications of this result for protocol design. Ran concludes that “the Random Oracle model is a bad abstraction of protocols for the purpose of analyzing security,” and strongly prefers the older approach of reductions to hard problems. Oded sees the random oracle model as an effective “sanity check” for rapidly ruling out insecure designs. Shai speculates on two possible reasons why existing protocols based on the random oracle model have defied attack:

  1. The systems are more difficult to break because a proof of security in the random oracle model rules out a large class of attacks – those that work in the random oracle model. Methods of attack that overcome this will take longer to develop.
  2. Existing protocols have some as-yet-unidentified feature that makes them more resilient than the contrived protocols described in this work.

Shai’s view of the utility of the model is more optimistic: he sees it as an “engineering tool” that is better than having no formal proof of security at all, and makes finding attacks more difficult.

What’s the future of the random oracle model? Perhaps we will identify some class of protocols for which instantiation is a sound procedure, or at least for which the generic attacks in this paper are inapplicable. Or perhaps we will adopt a new model that provides stronger guarantees. For now, formalizing and justifying the design of cryptographic protocols remains a difficult problem and a contentious philosophical debate.

The author releases all rights to all content herein and grants this work into the public domain, with the exception of works owned by others such as abstracts, quotations, and WordPress theme content.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>