1
$\begingroup$

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

  1. Is my formula correct?
  2. How could I estimate this assuming a given bias in the hash function? (i.e. some values are more likely than other)

$\endgroup$
1
$\begingroup$

I'm not following your argument (why "construct" a mapping, when you want random mappings?)

I'm going to start from scratch.

If $b=|B|$ and $a=|A|$ there are at most $b(b-1)^a$ maps that miss an element - we pick an element $\beta \in B$ in $b$ ways, then pick a map from $A$ to $B\setminus \{\beta\}$ in $(b-1)^a$ ways. This over-counts maps by counting multiple times any maps that miss multiple elements, but that will tend to be a relatively tiny amount, and we have at least an upper bound for the number of such maps.

So an upper bound for our probability is: $$p<\frac{b(b-1)^a}{b^a} = b\left(1-\frac{1}{b}\right)^a$$

(This isn't a great upper bound when $a,b$ are close, since $(1-1/b)^b\approx 1/e$. But when $a$ is much larger than $b$, this is actually a useful upper bound. The value $b(1-1/b)^a$ is actually the expected number of missed elements of $B$.)

Taking the log, we get $$\log p<\log b + a\log(1-1/b)<\log b - \frac{a}{b},$$

because $\log(1-x)<-x$ for $x\in[0,1)$.

So this means the probability is less than $be^{-a/b}$, which is indeed very tiny when $a=2^{2^{64}}, b=2^{256}$ - it is bounded above by $e^{-2^{63}}$.

If the probabilities are uneven, then let $p(\beta)$ be the probability of getting $\beta\in B$, and let $p_{min}=\min_{\beta\in B} p(b)$.

Then the above argument, refactored, will show that:

$$p<b(1-p_{min})^a \leq be^{-ap_{min}}$$

Depending on how badly varied to probabilities are, this might not be a great estimate, but the $p_{min}$ value would have to be very tiny to give a significant value to $a=2^{2^{64}}$ and $b=2^{256}$.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. I detailed my reasoning a bit more. My mapping is explicit in the first part, and implicit in the second -- I changed the wording a bit to make it clearer. $\endgroup$ – Symeof Dec 3 '15 at 16:07
  • $\begingroup$ By the way, do you really have $a=2^{2^{64}}$? That seems extreme - that means your message can be $2^{64}$ bits, or $2^{21}$ terabyes. $\endgroup$ – Thomas Andrews Dec 3 '15 at 16:18
  • $\begingroup$ Yes, the maximal size of input of SHA256 is specified here: csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf. Thomas Pornin cites it in stackoverflow.com/questions/2658601/… and says it is "2^64 - 1 bits" $\endgroup$ – Symeof Dec 3 '15 at 16:22

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.