Why are protocols often proven secure under the random oracle model instead of a hash assumption? Is this true that whenever you design a protocol using a hash function, you must prove its security under the random oracle? 

I mean, is it possible to devise a protocol $P$ using a function $H$, and then prove a theorem saying that $P$ is secure in a model $M$ given that $H$ is a collision-resistant function? What I most often see is some thing like: given a random oracle $H$, $P$ is secure in the model $M$. 

Is this because it's more difficult or even impossible to prove security without the random oracles?
A random oracle is an idealization of a hash function $H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1]

That being said it is still possible to prove things using different, weaker, assumptions about the hash function or even the compression function in the case of a MD hash function (collision resistance for example). Those are "proofs in the standard model"

Is it possible to go from one to the other? Not always since there are separations: there exists schemes that can be proven secure in the RO model that will become insecure as soon as you instanciate the RO by a real world hash function. [2]

Is it the end of the world? Not really, since we also have strong results that use the notion of Indifferentiability from RO: simply put, if your hash function is indifferentiable from a RO then you can replace your RO by your hash function and the scheme will remain secure. [3]

There are (as always) subtleties and what I've just said is not always true but this is good enough to make us feel more comfortable with our assumptions. [4]

Is this RO-indifferentiability just theoretical crypto stuff? No! I haven't checked for all of them but I know that Skein and Keccak 2 of the SHA-3 finalist come with proofs regarding that very property. I believe all of the finalist do. [5] [6]


[1] Random Oracle
[2] Impossibility result
[3] Indifferentiability framework
[4] Indifferentiability revisited
[5] Skein Proofs
[6] Sponge Proofs (keccak)


If you want you can start by reading the following:


http://en.wikipedia.org/wiki/Standard_model_%28cryptography%29
http://en.wikipedia.org/wiki/Random_oracle
http://blog.cryptographyengineering.com/2011/09/what-is-random-oracle-model-and-why.html