Return to Answer

You can easily tell it's not an invertible function because the size of the domain (possible number of inputs) is greater than the size of the range (possible number of outputs).

That is not correct, too. Take modulo 2^256 as hash then it is non-invertible. One, however, given a hash value can calculate a pre-images easily, given x, a;; x+k 2^265 are pre-images. In other words, we inverted the map. The correct definition is a function which is computationally infeasible to invert

The errors in the topmost answer

The range is 2^256 (possible output states) and the size of the input space is infinite (technically 2^(2^64) apparently, but much larger than 2^256). And that's precisely what permits the collisions (by the pigeon hole principle, there must be more than one possible input for each output - at least for one of the inputs).

SHA256 input space is limited due to the padding standard of NIST. One can hash at most 2^64 bits therefore there are at most 2^(2^64) different messages since the size of the message is encoded at the end of the padding in 64 bits.

The pigeonhole principle only says that there is at least one pigeonhole that has more than one pigeon. It doesn't talk about others that can be empty or not. With this, we can say that at least there must be one collision. Interestingly, we don't know that a SHA256 restricted to 64 bits attains all 64-bit values. What we expect from SHA256 is it is indistinguishable from uniformly random.

• If we only consider this it is pre-image attack and the cost is O(2^256) for SHA-256. Note that the aim of the pre-image attack is not finding the original input, it is rather finding an input that has the same hash value. If there is no external test for the input, one cannot decide that the found pre-image is the pre-image. And, the actual search space for the pre-image can be much larger than the pre-image attack handles.

• If we only consider this it is pre-image attack and the cost is O(2^256) for SHA-256. Note that the aim of the pre-image attack is not finding the original input, it is rather finding an input that has the same hash value. If there is no external test for the input, one cannot decide that the found pre-image is the pre-image. And, the actual search space for the pre-image can be much larger than the pre-image attack handles.

  There is a variant of pre-image attack, that occurs when the message space is short, like hashing the phone numbers. In this case, it may very easy to find the pre-image.