2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dour High Arch Dec 12 '14 at 23:43
  • $\begingroup$ It's possible, but unlikely, unless by design. It depends on the individual algorithm. $\endgroup$ – Yuval Filmus Dec 14 '14 at 18:06
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I do not believe this. I believe each 256 bit string has exactly $2^{256}$ sha-256 prehashes of length 512. $\endgroup$ – Albert Hendriks May 20 '16 at 18:13
  • $\begingroup$ @AlbertHendriks I'm confused. Which part of my answer don't you believe? And what justifies this belief? $\endgroup$ – Gilles 'SO- stop being evil' May 20 '16 at 19:03
  • $\begingroup$ Good question. The part I don't believe is "cryptographers tend to think the only way these functions might be proven surjective is by providing a way to compute inverses". I've written a CSP solver that prehashes 8 (out of 64) steps of SHA-256. Note that 8 steps use only the first 256 (of 512) bits of the input (prehash). Now what my program finds, is that it never has to branch for the strings that I did, meaning there's exactly one prehash for each such string. This suggests that 8 rounds of sha-256 is a perfect hash (regarding 256 bits). That's indirect evidence for my statement above. $\endgroup$ – Albert Hendriks May 20 '16 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy