5
$\begingroup$

What I'm wondering is whether the codomain and image of common hash functions are strictly equal… or whether there are any known values which have no possible preimage.

For example, SHA-1 outputs a 160-bit digest. Can it be proved that every possible sequence of 160 bits is a possible output of SHA-1 (even though corresponding preimages cannot be easily computed, by design), or are there certain outputs which can be demonstrated to be impossible based on the construction of the hash function?

This question about uniformity of hash function output seems related, though what I'm interested in has less to do with overall uniformity, and more with provable existence/non-existence of any preimage for specific outputs.

$\endgroup$
2
  • 1
    $\begingroup$ There are two separate aspects to this question. One is whether there might be an impossible output due to some flaw in, or the structure of, the has function -- there's one or more special output(s) that due to structure cannot be produced. The other is whether it's likely/possible to have an impossible output by just pure bad luck -- there just happens to be one or more random-looking output(s) that it just so happens no input can produce. $\endgroup$ Commented Jan 21, 2018 at 18:41
  • $\begingroup$ Right, that's why I asked about provable non-existence of any pre-image for certain outputs. Given that preimage resistance is an important property of hash functions, it'd be impossible to identify random-bad-luck gaps. I'm thinking about something analogous to the DES weak keys, where the behavior of those keys is straightforwardly demonstrated in terms of the structure of the cipher. $\endgroup$
    – Dan Lenski
    Commented Jan 21, 2018 at 18:53

1 Answer 1

7
$\begingroup$

No, it is not known that any cryptographic hash in common use has impossible output values (that is a bitstring of the appropriate size to be an output, but that is not reached by any input message). That's at least for MD5, the SHA(-1/-2) family of FIPS 180-4, SHA-3 of FIPS 202, RIPEMD-xxx, Blake/2, Tiger/2, Whirlpool.

In fact, it would be surprising that such impossible output value exists, and even more that it could be exhibited:

  • For a hash modeled as a random function, the probability that there is such value is lower than $1/2$ for a $n$-bit hash when there are more than $n\,2^n$ inputs; and that probability lowers with larger message input sets. See this for details.
  • For a Merkle-Damgård hash with Davies-Meier round function, the message block at most twice as large as the output, and the length padding at most about a quarter of the block size (like MD5 and direct larger successors are), under the assumption that the underlying block cipher is a Pseudo Random Permutation, and by an adaptation of the above reasoning, it is very probable that all outputs are reached with a single message block; and even more probable that they all are reached with two message blocks. Anything else seems to require a severe defect of the underlying block cipher, and any known such defect seems considerably lesser.
  • For the sponge construction of SHA-3, a similar argument can be made that a severe defect of the sponge function would be required to have some output values unreachable.

Update (Feb 2024): it's possible to construct secure hashes that demonstrably reach all their output values, using a one-way bijection. Thanks to this (new?) technique using certain elliptic curves, they can be just the width required for collision-resistance, and reasonably fast (though not as fast as symmetric crypto allows).

$\endgroup$
3
  • $\begingroup$ In that formula in the linked answer, what exactly does $o(1)$ mean? What is it equal to? $\endgroup$ Commented Jan 21, 2018 at 11:45
  • 3
    $\begingroup$ @lyrically wicked: In the formula $2^n\cdot(n\cdot\ln(2)+\gamma)+1/2+o(1)$ giving the expected (average) number of inputs to reach all $n$-bit value under the assumption that the hash is a random function, $o(1)$ designates a quantity that converges to $0$ when $n$ increases to infinity. We can safely say that for large $n$, this quantity is much less than $1$ (in absolute value). See little-o notation. $\endgroup$
    – fgrieu
    Commented Jan 21, 2018 at 14:21
  • $\begingroup$ This answer is obsolete, especially it's update. It won't be maintained (since the question is a duplicate and any change would bring the Q into the hot Q, which is objectionable). See this answer instead. $\endgroup$
    – fgrieu
    Commented Feb 6 at 17:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.