5
$\begingroup$

I am testing a theoretical hash function, $f()$, which produces n-bits of output.

By the pigeon hole principle, if I run $f(x)$ over a search space of $1+2^n$ values, I will get at least one collision. According to the birthday problem I should get many more collisions than that.

Is there a similar principle that I can determine how many values of $x$ will be needed to ensure with high probability that I have produced all possible $2^n$ values of $f(x)$?

I'm relatively certain that there is no 100% guarantee of obtaining all values, but at least an approximation within a degree of confidence should be possible. Are these approximations only practical when considering specific hashing algorithms?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Belongs on Crypto SE? $\endgroup$ Commented Nov 21, 2016 at 15:29
  • 1
    $\begingroup$ Uhm, why are you testing a theoretical hash function? Are you a security researcher? If not, it might be prudent to stick to existing hash functions. $\endgroup$ Commented Nov 21, 2016 at 15:29
  • $\begingroup$ Related: security.stackexchange.com/questions/107081/… $\endgroup$ Commented Nov 21, 2016 at 16:45
  • $\begingroup$ en.wikipedia.org/wiki/… ​ ​ $\endgroup$ Commented Nov 21, 2016 at 16:58

1 Answer 1

Reset to default
6
$\begingroup$

If $f()$ can be modeled as a random function (that is, if each output for a distinct input is independent of all other outputs), then this is a well studied problem in probability theory, known as the Coupon Collector's Problem.

The link I gave you gives more details; the bottom line is that you start getting good probability of seeing all possible sequences after around $C n 2^n$, for a constant $C$ not too far from 1 (and whose actual value depends on what "good probability" actually is).

Of course, if your theoretical hash function doesn't act randomly (for example, there are pairs of inputs $A \ne B$ where we're guarranteed that $f(A) \ne f(B)$), this analysis does not apply.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Isn't it $\Theta(n\log(n))$-time since this is expected? $\endgroup$ Commented Oct 16, 2021 at 20:19
  • $\begingroup$ @kelalaka: when I wrote $Cn2^n$, $n$ is the number of bits (just as micker used it). $\theta(n \log n)$ is what you get when $n$ is the size of the sample space (and so there are $\log_2 n$ bits...) $\endgroup$ Commented Oct 17, 2021 at 2:27
  • $\begingroup$ @kelalaka: he specifies that $n$ is the number of bits within the output of $f$; hence using that same notation in the answer makes sense (rather than changing the meaning of $n$) $\endgroup$ Commented Oct 17, 2021 at 11:26