1
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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...

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.