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?
A random oracle is described by the following model:
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.
|show 2 more comments|