# Hash values that are impossible to reach

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.

• Yes it's possible. For example the code int GetHashValue(){ return 1; } does not return any value other than 1. Is that what you mean? No? Then you need to ask a specific question about a specific hash function. – Dour High Arch Dec 12 '14 at 23:43
• It's possible, but unlikely, unless by design. It depends on the individual algorithm. – Yuval Filmus Dec 14 '14 at 18:06

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.
• I do not believe this. I believe each 256 bit string has exactly $2^{256}$ sha-256 prehashes of length 512. – Albert Hendriks May 20 '16 at 18:13