1.
Introduction
2.
Random Oracle
3.
Random Oracle Model
4.
Algorithms in the Random Oracle Model
5.
Attacks on Random Oracle Model
5.1.
Preimage Attack
5.2.
Second Preimage Attack
5.3.
Collision Attack
6.
6.1.
What is an Oracle in cryptography?
6.2.
Do Random Oracle modes really exist?
6.3.
Can Random Oracle be executed by a finite algorithm?
6.4.
Is the Random Oracle model collision resistant?
6.5.
How to know if a hash function is collision resistant?
7.
Conclusion
Last Updated: Mar 27, 2024

The Random Oracle Model and its Algorithms in Cryptography

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Do you often wonder what the random oracle model in Cryptography is? A random oracle in cryptography responds to each distinct query with a random answer selected uniformly from its output domain. Repeated questions receive the same response each time they are sent in. In this blog, we will be looking at random oracle modes in cryptography.

Random Oracle

Cryptography describes proven security as an essential concept. Although, in some functions, security is sacrificed for effectiveness. RSA (Ron, Adi, and Leonard) methods, too, are effective but need to be more secure. In such cases, encryption methods such as ElGamal are used. But, there is a need for more effective and safe models. One such model is a Random Oracle.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Random Oracle Model

A random oracle is a mathematical model and a hypothetical black box (can contain any query and doesnâ€™t exist as far as we know). It maps every possible query to a random response from its output domain. Each random response is selected uniformly, and the same queries are responded to with the same output. These models are used as ideal cryptography hash functions.

In this model, a hash function h: X â†’ Y is chosen randomly from FX, Y, and we are only permitted oracle access to the function h.

A true random oracle might not exist in real life. But, it is believed that a hash function that is well-designed would behave like a random oracle. That is why it is useful to study the random oracle model.

Algorithms in the Random Oracle Model

An algorithm in the random oracle model can be applied to any hash function since the algorithm needs to know nothing about the hash function. In Random Oracle Model, the algorithm/formula of function h(x) is unknown. The only way to compute the h(x) is to query the oracle.

• Suppose that h is a random oracle and h(x) is computed for all x Îµ X0 âŠ‚ X, then for all x Îµ X\ X0 and any y Îµ Y, we have

Pr[h(x)=y] = 1/M.
(i.e, For all possible values of x and y, the probability of x and y such that h(x) = h(y) is = 1/M.)

• Computing any amount of h(x1), h(x2), â€¦not helpful to find other values of h(x).

• Las Vegas Algorithm: a randomized algorithm that either returns a correct answer or fails to give an answer.

• A randomized algorithm has worst-case success probability Îµ, if for all instances that Pr[ return correct answer] â‰Ą Îµ

• A randomized algorithm has average-case success probability Îµ, if Average(Pr[return correct answer]) â‰Ą Îµ.

Attacks on Random Oracle Model

The Radom Oracle Model, however useful, is not without its flaws. It is susceptible to different types of attacks which can be used to calculate the hash of an unknown message. Three types of attacks can be performed on the Random Oracle Model. These attacks must be considered while determining the possible security measures for the Model. The attacks are named as follows:

• Preimage Attack
• Second Preimage Attack
• Collision Attack

Preimage Attack

A Preimage is data entered into the hash function to calculate the hash value. A hash function is a one-way function. Due to this property, the hash can not be used to calculate the Preimage.

In a Preimage Attack, an attack is launched on the hash function to determine the preimage of the hash value. This attack is faster than that of the brute force method. In this attack, the algorithm tries to find a message with a specific hash value.

Thus for a system to resist these types of attacks, the hash function should be a one-way one. For a one-way hash function, it is difficult to compute the original message from the given hash value, whereas the calculation of the hash is easy.

Second Preimage Attack

In a Second Preimage Attack, an attacker is given a specific input. Then the attacker can find a different input that results in the same hash value as the given input.

A Second Preimage attack occurs when the attacker can find another input that results in the same hash value as the given input. These types of attacks are extremely harmful to a model. For example, if Adam sends a message to Bert, Tom intercepts it. If Tom launches a Second Preimage attack on the message and determines a text that hashes to the same hash value, then Tom can substitute the message Adam sent and attach the digital signature to it. This would result in Bert thinking that the message has been sent from Adam, but in reality, the message was altered by Tom.

Collision Attack

In a Collision Attack, rather than determining a message that produces the same hash as the given one, the attacker tries to find two messages that produce the same hash value. This results in a hash collision.

What is an Oracle in cryptography?

Blockchain oracles allow smart contracts to operate depending on inputs and outputs from external systems by connecting blockchains to those systems.

Do Random Oracle modes really exist?

Random Oracle modes are ideal hash functions and do not exist. If they do exist, it may be really hard to find one.

Can Random Oracle be executed by a finite algorithm?

A random oracle can execute no function implemented by a finite algorithm. It is because the random oracle model has infinitely many inputs and each output is independent of the other.

Is the Random Oracle model collision resistant?

The random oracle model is collision-resistant because it is given a large set of inputs even if the output is generated randomly.

How to know if a hash function is collision resistant?

The hash function is defined as collision resistant if it is difficult to discover two inputs that hash to the same output.

Conclusion

In this article, we discussed what a Random Oracle Model is. We also covered the algorithms in the random oracle modes.