For any hash value, is there an infinite number of inputs that hash to it?

Question

Bruce Schneier writes (back in 2005) in a post on cryptanalysis of SHA-1:

SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions.

How do we know that there is an infinite number of messages that hash to each possible value? Is this known to be true for other hash algorithms than SHA-1?

Answer 1

As rightly pointed by Henrick Hellström and Otus, FIPS 186-4 defines SHA-1 with a maximum message length of $2^{64}-1$ bits, hence it is certain that no 160-bit value is the hash of an infinite number of messages. In the following, unless otherwise stated, I assume that we modify the definition of SHA-1 to allow for an infinite number of messages, by removing the length limitation and taking the message length modulo $2^{64}$.

It is not known, in the mathematical sense of that, that there is an infinite number of messages that hash to each possible value; that's both if we define possible value as one of the $2^{160}$ bitstrings of size 160 bits; or even if we define it as one of the (conceivably less than) $2^{160}$ bitstrings such that there exists a message that hashes to that value.

However, we expect that each of the $2^{160}$ bitstrings is the result of hashing an infinite number of messages.

Given the structure of SHA-1 (a Merkle-Damgård hash), this would follow from the plausible conjecture that modifying two consecutive message blocks except for the last 72 bits (of padding and length) is enough to reach any desired value. Or more precisely: that for any $I$ and $K$ of 160 bits, and any suffix $S$ of 72 bits, there exists $A$ of 512 bits and $B$ of 440 bits, such that $\mathcal F(\mathcal F(I,A),B\|S)=K$, where $\mathcal F$ is the compression function of SHA-1 (with first argument the 160-bit hash state, and second argument the 512-bit block input). This conjecture allows to explicitly construct $2^{160n}$ messages of $1024n+952$ bits hashing to any value $K$ (for $n=0$ we set $I$ to the initialization constants of SHA-1, and $S$ to $\text{0x80}$ followed by the length $952$ over 64 bits; we proceed by induction, postfixing previous messages with the former $S$, and setting the new $S$ to $\text{0x80}$ followed by $(1024n+952)\bmod2^{128}$ over 64 bits).

That conjecture seems extremely plausible is we model $\mathcal F$ as a random function of its inputs; or if we model the cipher that it uses internally as an ideal cipher, followed by addition modulo $2^{32}$ of each of the 5 words of input and output (an even better model of what SHA-1 is). The argument goes like: it is likely that for any 160-bit intermediary $J$ we can find $B$ allowing to reach any $K$ as $\mathcal F(J,B\|L)$, for we have $2^{440}$ choices of $B$ and only $2^{160}$ values of $K$ to cover, with the square of the later number much larger than the former. Even if there was some exceptions because $\mathcal F$ or its internal cipher is too regular, we have a large (arguably full or next to full) choice of $J$ by varying $A$, and that will help fully covering the possible $K$. Note: I fell more confident about this argument with belt and suspenders than I would be with a single round of $\mathcal F$.

Back to the actual definition of SHA-1 with limited input length, the above plausible conjecture would imply that more than $2^{(2^{61})}$ messages hash to any given value. That's practically infinite for all but a mathematician.

Answer 2

According to the version of FIPS 180 available back in 2005, SHA-1 has an input length limitation, which means there are not an infinite number of messages that are valid SHA-1 inputs to begin with. The reason for this constraint is the padding contains a fixed length input bit length field.

Older algorithm of a similar design, such as MD5, also have fixed length input bit length fields in their padding, but no input length limitations. These hashes consequently have a theoretically infinite number of valid inputs.

Some newer algorithms, such as SHA-3, do not have fixed length input bit length fields in their padding, and consequently do not have any input length limitation.

Answer 3

A hash function as described in wiki is "A hash function is any function that can be used to map data of arbitrary size to data of fixed size".

Hence what given inputs of a varying length there can be an infinite number of messages.

Now following the Pigeon Hole Principle where given a set of messages M that a hash function maps to a set of hash values S where M > S there will be inevitably collisions.

Hence given this properties we can say there will be X number of messages that results in multiple occurrence of hash value Y. And finally yes this holds true for all hash algorithms to a certain degree (There are other set of hash algorithms such as perfect hash algorithms that are designed where X = Y)