Let $X$ be the set of 256-bit strings and $x \rightarrow H(x)$ a map on this set, where $H$ is SHA-256. How often is $H^-1(y)$ empty?

Question

It cannot be "frequent" because that implies $H$ is not really 256-bit. Are there statistical or mathematical bounds on this? Finding the inverse is computationally difficult, but what matters here is existence.

Answer 1

If we model SHA-256 as a random function, then we would expect $H^{-1}(x)$ to be empty with probability about $e^{-1} = 0.36787944.$. To put it another way, we would expect that about $2^{256}/e$ of the 256 bit values $x$ not to have preimages.

Now, we don't know if modeling SHA-256 in this way is accurate; we have no indication that it is not...

Answer 2

To generalize this, pick a given $x$. Model the action of SHA-256 as picking a random output $y_o\in\{0,1\}^{256}$ uniformly and independently for each $y_i\in\{0,1\}^{256}$. The probability that $y_o=x$ is $p:=\frac{1}{2^{256}}$. This means we can compute the probability that $x$ has $k$ pre-images as a binomial distribution:

$$\text{Pr}[\vert H^{-1}(x)\vert=k] = \binom{2^{256}}{k}p^k(1-p)^{256}$$

With a size of $2^{256}$, we're better off approximating a binomial distribution by a Poisson distribution, with $\lambda = p\cdot 2^{256}=1$, giving

$$\text{Pr}[\vert H^{-1}(x)\vert=k] = \frac{e^{-1}}{k!}$$

(you can also generalize this to the case where we have inputs of more or less than 256 bits, or to the case when we know that $x$ has at least one pre-image).

The analysis gets tricky if we take two values $x_0$ and $x_1$ and ask for the probability that both have a certain size of pre-image, since any element in the pre-image of $x_0$ cannot be in the pre-image of $x_1$, and vice versa. But actually, if we're thinking about small sizes of pre-images, then the probabilities change so little that we can treat the pre-image sizes as independent.

And as @poncho says, SHA-256 could have some undiscovered structure that invalidates this model of it.