Let us define a hash function $$\begin{align*} H \colon A &\to B\\ a &\mapsto b \end{align*}$$
$$|A| \geq |B|$$ Assuming it is perfectly random (Hyp 1), we estimate the probability that it is not surjective. We construct a mapping $$ H(a_{i}) = \left\{\def\arraystretch{1.2}% \begin{array}{@{}c@{\quad}l@{}} b_{i} & \text{for } i \in \{1,...,|B|-1\} \\ \text{any value except }\beta & \text{for } i \in \{|B|, ..., |A|\} \\ \end{array}\right. $$
where all but one element in B have a pre-image in A (the second part of the mapping is not explicit).
The probability that we don't hit beta after one try is $$1 - 2^{-|B|}$$
We assume that events are independent (Hyp 2). The number of possible tries left is given by: $$|A|-|B|+1$$
We then derive the following expression:
$$P(\text{"there exists }\beta \in B \text{ with no pre-image"}) = (1-2^{-|B|})^{|A|-|B| + 1}$$
In the case of SHA256, we have
$$ |A| = 2^{2^{64}} \approx 2^{18446744073709551615}; |B| = 2^{256} $$
This gives us: $$(1-2^{-256})^{2^{18446744073709551615}-2^{256} + 1} \leq 10^{-5000000} \approx 0$$ where the upper-bound was computed here
- Is my formula correct?
- How could I estimate this assuming a given bias in the hash function? (i.e. some values are more likely than other)