Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I suppose this question addresses surjectivity and injectivity. We talk about collisions but did we prove yet rigidly that this function is not reversible?
EDIT: Accepting the answer based on Dirichlet Box Principle (if domain is bigger than codomain innevitably there will be collisions). I agree that for mappings $h:\{0,1\}^*\rightarrow \{0,1\}^{256}$ the function is not injective and therefore not bijective
Background
Terminology
Pigeonhole-Principle
The pigeonhole principle goes back to 1624. We can state it as; if there are $m$ pigeons and $n$ holes with $m>n$ then when the pigeons are placed into the holes, there is at least one box that has more than one pigeon.
We can look at the traditional example; 101 pigeons and 100 holes. Place each hole one pigeon, and you will get 1 pigeon not placed into a hole so one must put this pigeon into a hole that has already one pigeon. Therefore there is one hole more than one pigeon.
The pigeonhole principle doesn't state that each hole must be filled. It is possible that 101 pigeons are places into one hole (a big one). This still applies to the pigeonhole principle.
With a small note: although the pigeonhole principle is a very simple argument it forms the basis of the combinatorics.
Cryptographic Hash Functions (CHF): CHF maps arbitrary data into a small fixed hash space $$H:\{0,1\}^*\to \{0,1\}^\ell$$ where $\ell$ is the fixed output size and it is 256 for SHA256 and $\space{}^*$ is the kleene star and in short here it forms a set that includes empty string and all finite binary strings.
There are XOF hash functions (e.g. SHAKE of SHA3 series) that the output size is determined during the digest request. In any case, one can see that the input space is larger in practice!
There are 5 main properties we want from CHF's
The 3. and 4. have formal definitions that we consider on the security and the below definitions comes from Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.
Collisions
With the pigeonhole principle there exist at least two input $m_1$ and $m_2$, $m_1 \neq m_2$ such that $\operatorname{SHA256}(m_1) = \operatorname{SHA256}(m_2)$. This implies that collisions are inevitable!
The collision security is bounded by the birthday paradox and roughly for a hash function with $\ell$-bit output, it has $\mathcal{O}(2^{\ell/2})$ cost with 50% probability.
No Injective
Once you have a collision this implies that a function (SHA256 here) cannot be a bijective function, since is not injective. Therefore we cannot talk about an inverse.
Surjective?
Even we don't know that SHA256 is surjective. To see that SHA256 is surjective, one has to find or show that the $2^{256}$ outputs occur.
Finding out this is impossible, since, one at least must try $2^{256}$ distinct inputs and this is infeasible.
On the other hand, showing SHA256 is surjective is problematic since it will indicate that SHA256 is not secure!
If we model SHA256 as pseudo-random function as Meir Moar did and limit the input space equal to output space then a hash value doesn't occur with probability $(1-1/n)^n$ and that is $1/e$ when $n \to \infty$. This is also the portion of the output hash value is not occurs. For the modeled SHA256 this makes $~2^{254.56}$ has values empty.
However, the input space is not limited to 256-bit. In this case, the probability of being empty becomes smaller and smaller $(1/e)^\frac{input-space}{output-space}$. And for both cases, we are still don't know until we look for all values.
If reversible
Assume that SHA256 is reversible then this means that it doesn't have the pre-image security at all. Given the has value one can find the pre-image using the reversible. This is not simple news, you would have heard that immediately.
There is no proof that SHA256 has 256-bit preimage security, however, any attack that has less than 256-bit search will still require substantial work to achieve to break the pre-image resistance. All of the current attacks are on the reduced rounds.
A good example from history is this; MD5 has imminent collisions, however, it has still pre-image resistance ( the best non-brute-force pre-image attack is still slower than brute-force in practice). So, even any collision attack better than the generic collision attack ( the birthday attack), we don't expect that the pre-image resistance will be broken.
The cost of MD5 pre-image attack by 2009 by Yu Sasaki and Kazumaro Aoki.
This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5. The memory complexity of the attack is $2^{45} \cdot 11$ words.
