97
$\begingroup$

What is the "Random Oracle Model"? Is it an "assumption" akin to the hardness of factoring and discrete log? Or something else?

And why do some researchers have a strong distrust of this model?

$\endgroup$
1

2 Answers 2

165
$\begingroup$

A random oracle is described by the following model:

  • There is a black box. In the box lives a gnome, with a big book and some dice.
  • We can input some data into the box (an arbitrary sequence of bits).
  • Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
  • If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message $m$, until we actually try $m$. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really "random" oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Indeed, see SHA-256 (or SHA-512 if you wish). It suffers from something called the "length extension attack". This is an artefact from the Merkle–Damgård construction: to hash a message $m$, the message is first split into fixed-size blocks (64 bytes for SHA-256), the last block being padded with some bits which include the length of $m$, and some ones and zeros such that we end up with a full block. Each block is then processed over a running state, the hash output being the last block value.

So suppose that there is a message $m$, that I do not know, but I know the length of $m$ and its hash $h(m)$. With that information, I can rebuild the padding bits which were added (let's call them $\pi$). Then, I can envision the message $m'$: $$ m' = m || \pi || x $$ for some value $x$ that I choose arbitrarily. I then know that the computation of $h(m')$ will begin by splitting $m || \pi$ into blocks and processing them, and after having processed the last bit of $\pi$, the current "running state" will be exactly $h(m)$. So, if I know $h(m)$, I can finish the computation of $h(m')$ by taking it from there, and I can do that without knowing $m$. In particular, I end up with $h(m')$ while not having presented $m'$ to the gnome.

This property proves that SHA-256 is not a random oracle. Yet, it does not endanger in any way the resistance of SHA-256 to collisions or preimages. Therefore, being a random oracle seems to be strictly harder than being a secure hash function.

It has actually been shown (by Canetti, Goldreich and Halevi) that random oracles cannot exist "in all generality" in the following sense: it is possible to build pathological signature and asymmetric encryption schemes, which are secure when they internally use a random oracle, but which are insecure whenever an actual computable function is used instead of the mythical gnome-in-the-box.

Summary: proofs in the random oracle model are fine, but are never complete enough to cover a practical implementation: we know that any function we will use in lieu of the random oracle will not be a random oracle; so security relies on the fervent hope that the parts where the actual function is not a random oracle do not impact security. This justifies a bit of mistrust. Still, a proof in the random oracle model is much better than no proof at all.

$\endgroup$
11
  • 57
    $\begingroup$ +1 for "There is a black box. In the box lives a gnome, with a big book and some dice." $\endgroup$ Sep 30, 2011 at 17:04
  • 11
    $\begingroup$ The answer above is pretty good. If you want a slightly longer answer, you can see this post: practicalcrypto.blogspot.com/2011/09/… $\endgroup$
    – user925
    Oct 8, 2011 at 19:22
  • 1
    $\begingroup$ @MatthewGreen: Just reading your blog article, it is a good one. Thanks for the link! $\endgroup$ Oct 8, 2011 at 21:03
  • 3
    $\begingroup$ @MatthewGreen I read the post and ended up reading your entire blog. Great writing! $\endgroup$
    – PulpSpy
    Oct 11, 2011 at 14:52
  • 1
    $\begingroup$ The question nicely explains a random oracle, but could give a wrong idea of what security in the Random Oracle Model is. Especially, invoking the length-extension property to "prove that SHA-256 is not a random oracle" can be misleading. Fact is: no public hash function can be a random oracle, because its public definition allows a near-perfect distinguisher from a random oracle; that's true including for hashes believed secure in the Random Oracle Model, like SHA-3. $\endgroup$ Nov 1, 2016 at 15:07
16
$\begingroup$

The bear describes a process for choosing and computing a uniform random function involving gnomes in boxes, but this doesn't really explain what the random oracle model is in the context of proving security reductions. There are three parts: uniform random functions, cryptosystems built out of hash functions, and random oracle proofs.


Uniform random functions. A die roll has a probability distribution on the possible outcomes {1, 2, 3, 4, 5, 6}. The outcomes all have equal probability 1/6 when it is a fair die roll, in which case we call the distribution uniform. We can also have a uniform distribution on coin tosses {heads, tails}, and a uniform distribution on sock colors {red, blue, green, teal-with-mauve-trim, …}, and so on, for any finite set of possible outcomes.

We can also have a uniform distribution on $t$-bit-to-$h$-bit functions $H\colon \{0,1\}^t \to \{0,1\}^h$. This space of functions is a finite set: you can write down a finite truth table for every bit of the $h$-bit output in terms of the $t$ bits of input, so there are exactly $(2^h)^{2^t}$ such functions; in the uniform distribution, each one has equal probability $1/(2^h)^{2^t}$.

One way to choose such a function uniformly at random is to wander through the Library of Babel and pick a book with $2^t$ pages, each of which has an $h$-bit string on it, so that the content of page $x$ is $H(x)$. Another way is to trap a gnome in a box with a coin and an empty book of $2^t$ pages; enslaved thus, when you ask the gnome for an input $x$, the gnome consults page $x$ in the book, and if it's empty, flips the coin $h$ times and writes down the result. Another way is to just flip a coin yourself $h 2^t$ times and write down a gigantic truth table.

However you choose a function $H$ uniformly at random—whether by randomly browsing a library like a civilized being, or by enslaving a gnome like a savage bear—for any particular function $f\colon \{0,1\}^t \to \{0,1\}^h$, the probability $\Pr[H = f]$ of getting that function is $1/(2^h)^{2^t}$. Another way to put this is that for any particular input $x$ and output $y$, $\Pr[H(x) = y] = 1/2^h$—and the value at each distinct input is independent, so $\Pr[H(x_1) = y_1, \dots, H(x_\ell) = y_\ell] = 1/2^{h\ell}$ if $(x_1, \dots, x_\ell)$ are all distinct. This property makes the model of uniform random functions easy to reason about.


Cryptosystems built out of hash functions. Some cryptosystems are defined in terms of a hash function. For example, RSA-FDH—Full Domain Hash—uses a hash function $H$ for public-key signatures:

  • A public key is a large integer $n$.
  • A signature on a message $m$ is an integer $s$ such that $$s^3 \equiv H(m) \pmod n.$$
  • To make a signature, the signer, who knows the secret solution $d$ to the equation $$3 d \equiv 1 \pmod{\lambda(n)},$$ computes $$s := H(m)^d \bmod n.$$

The use of a hash in signatures is crucial for security, as Rabin first observed in 1979[1]: if we instead used the signature equation $s^3 \equiv m \pmod n$, then anyone could immediately forge the signature 0 on the message 0, or take two message/signature pairs $(m_0, s_0)$ and $(m_1, s_1)$ to forge a third $(m_0 m_1 \bmod n, s_0 s_1 \bmod n)$, or forge a signature $\sqrt[3]{m}$ on any integer cube $m$, etc.

The formulas are written in terms of $H$, so you can write a procedure that computes the various parts of the cryptosystem with $H$ as a parameter alongside all the others:

def sign(H, n, d, m):
    s = modexp(H(m), d, n)
    return s
def verify(H, n, m, s):
    return modexp(s, 3, n) == H(m)

What properties do we require of $H$? Typically some combination of preimage resistance, collision resistance, etc. For a uniform random function, the expected cost of finding a preimage or finding a collision is high. We could imagine enslaving a gnome in a box, and using sign(gnomebox, n, d, m) and verify(gnomebox, n, m, s):

book = {}
def gnomebox(m):
    if m not in book:
        book[m] = random(2**h)
    return book[m]

However, for this cryptosystem to be useful, we need everyone to agree on the same function, so we need everyone to share the same gnome. Sharing gnomes is not a scalable way to do commerce over the internet, which is the only reason capitalism doesn't choose to rely on this particular type of slavery to concentrate wealth.

Instead, when we actually use this cryptosystem, we agree to pass, say, SHAKE128-2047 as $H$, when we choose $n$ to be 2048 bits long: s = sign(shake128_2047, n, d, m), verify(shake128_2047, n, m, s).

When we use a particular hash function like SHAKE128 together with particular fancy math like $s^e \equiv H(m) \pmod n$, the hash function could in principle interact with the fancy math in a way that destroys security, but the hash function we choose has been studied for many years to get confidence that it has no useful properties other than being cheap to evaluate, and even if it did turn out to have bad interaction or bad properties—say because we used SHAKE128 but the fancy math internally uses the inverse of the Keccak permutation for some reason, or because we used MD5 as $H$—we could swap in a different hash function.

If we make a bad choice of hash function, there might be easy attacks that depend on the choice of hash function, like a way to compute $H(m \mathbin\| m')$ given $H(m)$ but not $m$ and thereby forging hashes of messages with unknown prefixes, or like finding MD5 collisions and thereby disrupting Iran's nuclear program. But there might also be attacks that don't depend on the choice of hash function. Can we say anything in general about the rest of the cryptosystem?


Random oracle proofs. To get confidence that forging signatures is hard, we show that a forger can be used as a subroutine to solve the RSA problem and invert $x \mapsto x^3 \bmod n$ for uniform random $x$. We suppose that solving the RSA problem is hard; consequently, if a forger can be used to solve the RSA problem, forgery can't be much easier than solving the RSA problem.

Specifically, we give the forger access to $H$, the public key, and a signing oracle which returns the signature on any message of the forger's choice:

def forge(H, n, S):
   ... S(m0) ... S(m1) ...
   return (m, s)

Here we would obviously pass lambda m: sign(H, n, d, m) as $S$; the point is that the forger is only allowed to call the signing oracle $S$, but is not allowed to inspect it or to see what the secret key $d$ is.

The forger is successful if, given (m, s) = forge(H, n, S), the resulting message and signature pair pass verify(H, n, m, s), subject to the restriction that $m$ was not passed to the signing oracle $S$. (Otherwise, the forger could win by asking $S$ for a signature on a message and returning that, which would not impress anyone as a method of forgery.) Obviously, a forger might win by guessing a signature at random, which has a very small but nonzero probability of success.

Given such a forger, we will show how to compute cube roots modulo $n$ with comparable success probability: specifically, a cube root function cbrt that uses forge as a subroutine and wins if modexp(cbrt(n, y), 3, n) == y. Let's assume that the forger makes at most $q$ queries to the hashing oracle $H$ or the signing oracle $S$.

We will make our own specially crafted hashing and signing oracles for the forger to use: they will be specially crafted to let us extract an RSA problem solution, but the hashing oracle we construct still has uniform distribution, and the signing oracle we construct still produces valid signatures for the cryptosystem instantiated with the specially crafted hashing oracle.

def cbrt(n, y):
    j = random(q)    # Guess at which one the forger will invert.
    i = [0]          # Mutable counter.
    ms = {}          # Maps message we have seen to index i.
    ys = {}          # Maps image we have given out to index i.
    xs = {}          # Maps index to preimage of H0.
    def H0(m):
        ms[m] = i[0]
        if i[0] == j:
            xi = m
            yi = y
        else:
            xi = random(n)
            yi = modexp(xi, 3, n)
        xs[i] = xi
        ys[yi] = i[0]
        i[0] += 1
        return yi
    def S0(H, m):
        if m not in ms:
            if modexp(H0(m), 3, n) == y):
                # We accidentally won without the forger.
                raise Exception
        return xs[ms[m]]
    try:
        (m, s) = forge(H0, n, S0)
        return s
    except Exception:
        return xs[ys[y]]

(This procedure is the standard proof of RSA-FDH security by Mihir Bellare and Phil Rogaway[2], Theorem 3.1.)

When the forger returns an attempted forgery $(m, s)$, there's a high probability that it passed $m$ to the hash; there's a $1/q$ probability that it was the $j^{\mathit{th}}$ query to the hash, in which case we returned $y$ from our carefully crafted hash; then if the forger was successful, $s^3 \equiv y \pmod n$, as we hoped.

Of course, there's also a tiny chance that the forger stumbled upon a successful forgery by chance for another message it fed to the hashing oracle, but that happens with probability $1/n$ which is very very very very very small. There's also a chance that our cube root procedure stumbles upon a successful cube root without the forger's help, but again, with probability $1/n$ for each query from the forger, which is very very very very very small.

Thus, if the forger has success probability $\varepsilon$, our cube root procedure has success probability approximately $\varepsilon/q$, with a little extra computation for some more calls to modexp. This suggests that if there's a cheap algorithm to compute forgeries using $q$ oracle queries, then there's an algorithm to solve the RSA problem costing only $q$ times as much—provided the forgery algorithm is generic in terms of $H$.

This was a particularly simple ROM proof; others use more elaborate techniques like the forking lemma, where we rerun the adversary's algorithm with the same random choices inside the algorithm, but a different oracle[3].


Why is this model controversial? In practical terms, it's not controversial: only academic cryptographers in an ivory tower worry about it, while practitioners have used ROM-based cryptosystems for decades largely without trouble. Hash functions like MD5 have gone bad, admitting collisions, and the Merkle–Damgåard structure admits length extension, but these cause problems just as well in non-RO proofs. So what is their objection?

It is tempting to draw the following inference:

If a scheme is secure in the random oracle model, then it is secure if we instantiate it with a particular hash function like SHAKE128 as long as the hash function isn't too badly broken.

Obviously, as above, we could devise a cryptosystem that is broken if you instantiate it with SHAKE128, but works fine if you instantiate it with pretty much any other hash function. Ran Canetti, Oded Goldreich, and Shai Halevi proved an academically very cute result: there exists a signature scheme which is secure in the random oracle model—meaning there's a random oracle proof like above showing how to turn a forger into an algorithm to solve some hard problem—but which is insecure with any practical instantiation[4].

It can be built out of any secure signature scheme $(S, V)$ you like, and it works roughly as follows:

  • To sign a message $m$ with secret key $\mathit{sk}$,

    • If $m$ is of the form $(i, \pi)$ where $\pi$ is a proof that $(i, H(i))$ is in the graph of the $i^{\mathit{th}}$ polynomial-time function in some enumeration of them,* then the signature is $(\mathit{sk}, S_\mathit{sk}(m))$. (Such a proof can be verified in polynomial time.)
    • Otherwise, the signature is $(\bot, S_{\mathit{sk}}(m))$.
  • To verify a signature $(z, s)$ on a message $m$ under public key $\mathit{pk}$, compute $V_{\mathit{pk}}(s, m)$. (We ignore $z$, which serves only as a back door.)

This signature scheme can be proven secure in the random oracle model, because the probability that $(i, H(i))$ is actually in the graph of the $i^{\mathit{th}}$ polynomial-time function in any particular enumeration of them is negligible for uniform random $H$, but if you choose any particular family of functions for $H$ then it is easy to construct a back door message that dumps out the private key by simply using its index in the enumeration.

This is a complexity-theoretic trick to devise a pathological signature scheme that throws a temper tantrum if you try to instantiate it in the real world. What the Canetti–Goldreich–Halevi scheme shows, by counterexample, is that the inference we would like to draw is not formally valid.

One might infer that there is some technical criterion distinguishing pathological counterexamples like this from the multitude of ROM-based protocols actually devised for practical use like RSA-FDH, RSA-KEM, RSA-OAEP, RSA-PSS, DH key agreement, etc.

Some academics choose instead to leave the random oracle model in the dustbin on the basis of this counterexample, and focus on finding ways to convert attacks on (e.g.) a signature scheme into preimage or collision attacks on the hash function, or find systems that through extreme contortions avoid hash functions altogether—a setting which is dubbed the ‘standard model’ in passive-aggressive phraseology to cast shade on the random oracle model and its practitioners. This comes at considerable cost to the complexity of proof techniques and the efficiency of the resulting cryptosystems, which seldom if ever appear outside academic journals and conference proceedings, no matter how strongly they express feelings there[5][6][7][8].

On the other hand, this doesn't mean that random oracle proofs are useless in practice. Protocols with random oracles have been wildly successful in the real world, to the point that nearly every public-key cryptosystem used in practice takes advantage of them—as a design principle they are highly effective at thwarting attacks from the first secure signature scheme in history[1] to modern Diffie–Hellman security[9].

Indeed, not only have we had no reason to doubt the security of (e.g.) RSA-FDH in practice in the quarter century of its existence, but it is hard to imagine that a $q$-query forger could actually be a factor of $q$ cheaper than an algorithm to solve the RSA problem, since the distribution on message hashes and signatures from the signing oracle, $(h_i, {h_i}^d \bmod n)$, is exactly the same as the distribution on quantities anyone could have computed without a signing oracle, $({s_i}^e \bmod n, s_i)$; and since the hash oracle is independent of the secret key. This suggests that there may be something awry in our attempts at formalization.

It would not be the first thing awry with formalization of cryptographic attacks in the literature. For example:

  • There is no formalization of collision resistance of a fixed hash function like SHA3-256[10][11]. On 257-bit outputs, there is guaranteed to be some collision $x_0 \ne x_1$, so there is a very cheap algorithm that prints collisions: it simply prints $(x_0, x_1)$ with no effort. But we have no idea how to find it without spending energy to compute an expected $2^{128}$ evaluations of SHA3-256.
  • There is almost certainly a 128-bit string $s$ such that the first bit of $E \mapsto \operatorname{MD5}(s \mathbin\| E(0) \mathbin\| E(1))$ is a high-advantage distinguisher for $E = \operatorname{AES}_k$ under uniform random key $k$ from a uniform random permutation $E$[12], which violates the premises of most inferences drawn about bounds on the PRP advantage of AES, e.g. those justifying the use of AES-GCM in practice. But we have no idea how to find $s$ without spending an obscene amount of energy.

None of these technical issues of formalization prevent the widespread and highly successful use of collision-resistant hashes or of AES. Nor should they prevent the use of random oracles as a design principle or justify the summary rejection of essentially all public-key cryptography in practice.


* There are more technical details: actually we work in the asymptotic setting where everything is parametrized by an input size, and we consider families of functions keyed by a seed and indexed by the input size, and enumerating functions bounded by some superpolynomial cost, etc. See the paper for details if you're interested.

$\endgroup$
2
  • 3
    $\begingroup$ I found this bit particularly helpful: "If we make a bad choice of hash function, there might be easy attacks that depend on the choice of hash function [...] but there might also be attacks that don't depend on the choice of hash function. Can we say anything in general about the rest of the cryptosystem?" $\endgroup$ May 17, 2019 at 21:42
  • 1
    $\begingroup$ Very helpful answer! I would also suggest the "UCE" paper by Bellare and al. And also the "Context restricted indifferentiability" by Jost and Maurer. They are nice resources discussing the bridge between the impossibility results and the apparent security of "real world" construction based on the ROM. $\endgroup$ May 18, 2019 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.