5
$\begingroup$

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?

|improve this question
$\endgroup$
7
$\begingroup$

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]

If you want you can start by reading the following:

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I find Bellare&Rogaway's Random oracles are practical a good read. At least this is how I was introduced to Random Oracles. $\endgroup$ – fgrieu Dec 7 '12 at 11:42
  • $\begingroup$ Also: beware that the length-extension property of many hashes, including SHA-2 (but not SHA-3), makes them easily distinguishable from a random oracle. $\endgroup$ – fgrieu Dec 7 '12 at 11:45
  • 2
    $\begingroup$ Interestingly enough while a construction $H^2:x\to H(H(x))$ does not have this length extension property it is still distinguishable from a RO H^2 & HMAC $\endgroup$ – Alexandre Yamajako Dec 7 '12 at 13:34
  • 1
    $\begingroup$ I was veering more towards the proof technique in the random oracles. It is not by simply replacing the random oracle with a perfect random function we can arrive at the same proof in the standard model. But what seems troubling to me is the fact that security proof in the random oracle allows the simulator to see the oracle queries made by the adversary. Is there any justification for this? Or is this simply that we cannot do without this assumption? $\endgroup$ – Anh Dec 10 '12 at 2:48
  • $\begingroup$ @Anh See this paper, which discusses precisely your concern. They call observability to this ability of the simulator. $\endgroup$ – cygnusv Jun 24 '15 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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