2
$\begingroup$

ROM is considered to be collision resistant. Does ROM assume there is an infinite set of outputs, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM is guaranteed a collision given a large enough set of input, even when the output is generated randomly.

$\endgroup$
  • 4
    $\begingroup$ "Collision resistance" does not mean "Collision free", necessarily. Maybe that is a contributor as to the confusion? Being hard to find to find isn't the same thing as non-existence. $\endgroup$ – Ella Rose Jun 25 '16 at 16:25
-3
$\begingroup$

That is the point of ROM. You assume 'somehow' the existence of a truly random function with no collisions. You do not care how this is constructed and designed because there is no real truly random hash function. But you assume it exists in an ideal world. Of course this has implications in real world because such a function does not exist. But ROM supporters will tell you that they provide a nice modular approach for security proofs in a way that we do not care about this function in real world: if you instantiated with a problematic hash function then you just change it. But the model, the random oracle model is sound and complete and it is focused on other attacks as well that do not change with the choice of the hash function

$\endgroup$
  • 1
    $\begingroup$ No, there is no such function that has no collisions, since the range is finite. That is certainly not what's assumed in ROM. You assume that the function has uniform distribution on its finite size output set [256 bitlength strings, for example]. Then, the best case happens, i.e., collisions don't become likely until you have $\sqrt{2^{256}}$ or so input queries, due to the birthday paradox. $\endgroup$ – kodlu May 14 '19 at 0:17
2
$\begingroup$

As Ella Rose points out in a comment, it is not that there are no collisions; rather, one can prove that the probability of encountering a collision is small in the random oracle model.

The random oracle model posits a finite domain and a finite codomain; otherwise the space of functions would be infinite and there could not be a uniform distribution on them. If $f\colon A \to S$ is a uniform random function into a set $S$ of $n$ elements (e.g., $S$ is the set of $t$-bit strings, so that $n = 2^t$), then $f(x)$ is independent for each distinct $x$, and $\Pr[f(x) = h] = 1/n$ for each $x$ and $h$.

When we combine these two properties—$x \ne x'$ implies $f(x)$ and $f(x')$ are independent, and $\Pr[f(x) = h] = 1/n$—we can conclude from a standard birthday argument that any algorithm making $q$ queries to a random oracle has probability at most $q^2/n$ encountering a collision. Following Ramanujan, Knuth, etc., the expected number of queries before a collision is $$1 + \sum_{k=0}^{n - 1} \prod_{i=1}^k \biggl(1 - \frac i n \biggr) = 1 + \sum_{k=1}^n \frac{n!}{(n - k)! \, n^k} \approx \sqrt{n \pi/2}.$$ Consequently, the expected query cost of any algorithm to break a cryptosystem like RSASSA-PSS signature by finding a collision in a $t$-bit random oracle is about $2^{t/2}$—which for typical values of $t$ like 256 is far beyond the capacity of humanity to carry out.

Of course, it is possible that we will learn something about SHA-256 that enables finding collisions more cheaply than generic collision searches, like we did with MD5 and SHA-1. But this is how the random oracle model works.

$\endgroup$

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.