# Random Oracle to prove an Authenticated DH protocol

I am trying to understand how they use the random oracle to solve the CDH. For example, in the security proof on page 7 of the following paper; A Lightweight Message Authentication Scheme for Smart Grid Communications, Fouda et al. 2001. The authors used a random oracle to break the security of an authenticated DH protocol. They assumed an adversary who can break the semantic security of the shared key and used this adversary along with a random oracle to solve CDH.

1. to my understanding a random oracle is like a hash function where the input is a random string and the output also is another random string, so how can we use to solve the CDH;
2. in the paper, they gave the adversary a tuple $$(g, g^a, g^b)$$ and allowed him to make a query to the random oracle. Then, they tracked the queries to the random oracle to monitor of $$g^{ab}$$ was queried. But Why would the adversary query g^ab to the random oracle? Is it part of the game?
• Sorry, @Mona. I was unable to open the paper on the link. – McFly Apr 27 at 14:21
• how can I attach it? – Mona Apr 27 at 18:19
• dropbox.com/s/ogzmbtawqg81cdl/… – Mona Apr 27 at 18:27

## 2 Answers

Answers to your questions:

1) Random oracle - is a replacement for hash-function. Its input is any bitstring, and output - random string. In some sense - it's an ideal hash-function. But in order to evaluate it, you (attacker) need to explicitly ask the oracle.

2) "Why would the adversary query g^ab to the random oracle. Is it part of the game?" - no, adversary of course isn't obligated anything for you, and it isn't obligated to ask ROM for $$g^{ab}$$. But, easy to see, that if the attacker didn't ask oracle for $$g^{ab}$$, he has only a negligible probability of success. In the article it's simply expressed as "has no idea on the session key"; it's indeed true - recall that oracle will return some random string for this input, regardless of all previous actions/queries of the attacker. While it's not a rigorous mathematical statement, it still correctly describes what happens.

In addition, I would try to explain why this ROM model good for modeling hash function. In this proof we essentially use the fact that any attacker will explicitly ask the oracle for hash-values, and we can track all these queries. While in real life, for real hash function, we can't track attacker actions. But, if hash-function is good (ideal), to get hash-value everyone needs to honestly calculate it by applying hash-function to some input (e.g., you can't derive hash-value of some input from hash-values of other, even somehow related, inputs). So, if hash function is good enough, any successful attacker at some point should calculate hash from $$g^{ab}$$, i.e. this attacker should know $$g^{ab}$$ at some step. So, this attacker is able to solve CDH. This is a meaning of this proof in ROM. It doesn't mean that for any hash-function it's true - it's only true for good hash functions, which are really unpredictable and behave like random oracles.

• Thank you for your explanation. I understand your explanation very well, but why in the paper, the authors said, they will give the attacker a random number instead of the output of ROM. I am quoting this sentence from the paper. "When the adversary makes a query on the session key, we flip a coin B belong {0,1} , and return a random value ." – Mona Apr 27 at 18:40
• @Mona, they give random number as output of random oracle - because output of random oracle must be a random number (this is how ROM defined). Another words - for attacker, this behavior of random oracle is totally fine, it's what attacker expects from random oracle. – Mikhail Koipish Apr 28 at 11:37
• Thank you very much for your help. This is very clear now. – Mona Apr 28 at 18:14

First of all, the random oracle is a proof model, and it can not be confused with hash functions, because these last (probably) aren't random; anyway, can be easily distinguished from such: see this Yehuda Lindell's answer.

In the proof paradigm in the Random Oracle Model, a protocol $$\mathcal{P}$$ is first proved to be secure doing access to an oracle function $$\mathcal{O}$$, this is denoted by $$\mathcal{P}^{\mathcal{O}}$$, and then replacing the oracle access by the computation of an oracle candidate function $$h$$.

In order to figure out the proof, the model considers two entities: the challenger and the adversary. The proof is constructed by letting the challenger defy the adversary to make her questions and guess if the answer comes from $$\mathcal{P}^{\mathcal{O}}$$ or from $$\mathcal{P}^{\mathcal{h}}$$. Here is where takes role the flipping coin: the challenger draws a coin and chooses the first or the second accordingly. If you want details, an excellent reference is the Boneh and Shoup book, Section 8.10 - Key derivation and the random oracle model

Look, in the paper, the constructed random oracle is not used to break the CDH. In fact, that is a proof by contradiction: if we assume the adversary can take advantage to win the challenge in the proof, so she could also have some advantage to solve the assumed CDH.

So, as we believe she cannot solve the CDH, the protocol must be secure.

• Thank you very much for your help. So p^h is the key? The challenger flips a coin and if coin=0 , he picks the key, p^h, if coin=1 he picks the random number, p^o. We record all queries to the ROM, then if key occurs then we assume that the adversary has an advantage more than 1/2. – Mona Apr 28 at 18:12
• PS: I downloaded the Boneh book. Is it section 2.3.2 Definition of semantic security ? – Mona Apr 28 at 18:29
• @Mona, the proof idea is based on the fact that if no feasible adversary cannot make a distinction between two sources of bits, these two sources will be similar to him/her, even if the 2 sources, in fact, have distinct distribution. Therefore, if by doing such a game, no adversary can make a distinction between a function output and a "good random" source of bits, so we can exchange them. BTW: is the Section 8.10 - Key derivation and the random oracle model, page 320. – McFly Apr 28 at 20:01
• I understand, thank you very much... – Mona Apr 29 at 17:16