Cheap and Secure Web Hosting Provider : See Now

[Solved]: Hash values that are impossible to reach

, ,
Problem Detail:

I was just curious as to if there are (or could by) any hash values that are impossible to compute due to the implementation of the algorithm. For example, SHA-256 produces a value that is 256-bits long. Technically, there are $2^{256}$ possible hash values that can be computed. Is it possible that a specific sequence of 256-bits cannot be generated using the SHA-256 algorithm?

This question is not specific to SHA-256 itself, but any hashing algorithm that follows a uniform distirbution pattern.

Regarding common cryptographic hash functions such as the SHA-2 family, it is highly likely that they are surjective (i.e. all potential $2^{256}$ values of SHA2-256 have a preimage). However, given $y$, finding $x$ such that $\text{SHA2-256}(x) = y$ is believed to be a computationally infeasible problem — that's preimage resistance, one of the defining properties of cryptographic hash functions. It's possible that there's a non-constructive way to provide that SHA2-256, but no such way is known, and as far as I know cryptographers tend to think the only way these functions might be proven surjective is by providing a way to compute inverses, which would mean that the functions would be broken.

To summarize, given $y$, it is probably (in the we-believe-it-but-we-could-be-wrong sense) theoretically possible to find $x$ such that $\text{SHA2-256}(x) = y$, but probably (in the chance-for-a-random-$y$ sense) practically impossible.

Hash functions for applications such as hash tables are a different matter. The point of such functions is to spread the input as wide as possible onto a finite-size output, so it is beneficial to cover as much output range as possible. It's often easy to find preimages for these hash functions, but that isn't guaranteed. A given hash function may or may not cover its whole potential $2^N$ output set.