Is there necessarily an infinite number of inputs to any given output in a crypto hash function?

Question

This might be a very easy question. Let's consider cryptographic hash functions with the usual properties, weak and strong collision resistance and preimage resistance.

For any given output, obviously there are multiple inputs. But is that necessarily an infinite number of preimages, for any given hash value?

How would I go about giving a formal proof that there exists no crypto hash function $h$ such that there is a given value $v = h(m)$ for which the possible set of inputs $m^*$ is finite? Would this necessarily break collision resistance?

Answer 1

For any given output, obviously there are multiple inputs.

This is not true. Namely, for any is not true. There are outputs such that multiple inputs produce them - this is consequence of pigeonhole principle. But we cannot claim that this holds for any output for any hash function. This can be true for some specific hash function only.

... proof that there exists no crypto hash function ...

There is no proof because this statement is simply false. Here is a simple example of a hash function that has many hashes that have finite number of preimages.

function hash(x){
    if (x.length <= 64) {
        return 
            '1' ||
            '0000000000000000000000000000000000000000000000000000000000000000' ||
            sha3(x);
    } else {
        return
            '0' ||
            sha3(x) ||
            '0000000000000000000000000000000000000000000000000000000000000000';
    }
}

The number of inputs that produce hashes starting with '1' is finite.

Answer 2

We expect the cryptographic hash functions look sort of random (completely undefined). We expect them to have relatively well-distributed output. If a cryptographic hash function has finite or no output on any value on the range, I'll be surprised.

The basic requirement for hashing is the collision resistance and this requires nothing beyond that.

• Collision-resistance implies second-preimage resistance, and
• second-preimage resistance implies preimage resistance, this one a bit tricky to prove sine relying on how much hash function compresses the message space. See, Cryptographic Hash-Function Basics by P. Rogaway and T. Shrimpton, 2004 for details.

One, however, can design one by using any secure existing cryptographic hash function that doesn't produce some outputs. Consider the SHA256 that has classical generic 256-bit pre-image and secondary pre-image resistances and 128-bit classical generic collision resistances. Now consider a new hash function SHA256x defined as:

$$\operatorname{SHA256x}(m) = 1\mathbin\| \operatorname{SHA256}(m)$$

The SHA256x has 257-bit output, however, the values $0\mathbin\|\{0,1\}^{256}$, i.e. values starting with zero, never occur. It has the same resistance as SHA256. Of course, such construction has no value at all, other than pedagogically.