Are cryptographic hash functions perfect hash functions?

Question

For a cryptographic hash function and input values of shorter length than the hash function output, it's pretty obvious that there should be as few collisions as possible. But are there guaranteed to be none?

In other words, for a cryptographic hash function $H: x\to y, x \in \mathbb{N}, y \in [0,y_{max}]$, are there any $x_i \ne x_j$ with $x_i,x_j \le y_{max}$ so that $H(x_i) = H(x_j)$?

This seems to be a special case of Is every output of a hash function possible?, with the additional limitation of inputs to the space of possible outputs.

If there are any such collisions, wouldn't that mean that, due to the pigeonhole principle, there exists some possible output of the hash function that can never be reached by hashing another output, i.e.

$\exists y:H(x) \ne y$ for all $x, y \in [0,y_{max}]$?

Are common cryptographic hashes bijective when hashing a single block of the same size as the output? even mentions that some hash values are expected to be unreachable by all possible inputs, which would of course also imply the limited input range given above.

Are there any practical consequences of that property of hash functions? I'm thinking about things like the Bitcoin proof-of-work system that require collisions (or "close collisions", differing only by some amount from the target hash value) to be found. Any chance that finding such a collision (range) would be not only practically, but theoretically impossible?

Answer 1

If a hash function is a random oracle, which is about as perfect as can be expected for a hash function, then we actually expect a lot of collisions. If the hash function output is in a space of size $N$ (e.g. $N = 2^n$ for a "$n$-bit output") then collisions are expected, on average, when about $\sqrt{N}$ distinct inputs are hashed (see the birthday problem for more details).

If you want to feed the $2^n$ possible sequences of $n$ bits to a hash function $h$, which produces $n$-bit outputs, and such that no collision occurs at all, then $h$ must severely depart from the normal hash function model -- in a way, it must be quite imperfect. This calls for a pseudo-random permutation. Think of it as a block cipher which you can compute in the "encrypt" direction but not the "decrypt" direction.

I am not aware of good constructions for that. Some attempts include RSA: let $N$ be a RSA modulus of unknown factorization, and $e$ the public exponent; then $m \mapsto m^e \pmod N$ is a one-way permutation of the set of integers modulo $N$. But it is not completely "random looking" (it is one-way on average) and requires a big $N$. Other constructions can use elliptic curves, but still with some drawbacks and caveats.

Answer 2

I wouldn't even go so far as to say that a good hash function must have "as few collisions as possible" as you state in your question. The identity function has no collisions if we restrict the domain to be the inputs having the same size as the digest. But it's clearly a lousy hash function.

To be "good" as a hash function is hard to define (which is discussed in other questions on crypto.SE in fact).

We don't know if there are (say) no collisions in 100-bit inputs to SHA-1. A reasonable (but not rigorous) thing to do would be to assume SHA-1 is a random function and then compute the probability that there is a collision among the 100-bit inputs. Given that there are $2^{100}$ such inputs the probability is close to 1 that there are collisions, by the birthday bound.

But your question seems to ask if SHA-1 is designed away from this property. I would say "no", that SHA-1 is designed to be as "close to random" as possible and likely has birthday properties.

An interesting question would be this: What is the smallest $n$ such that there exists a collision among the $2^n$ inputs of length $n$? The expected value of $n$ is about 80, but it will almost certainly not be exactly 80. And finding it via brute force is going to be really difficult (after all, we don't know ANY collisions in SHA-1).