Are common cryptographic hashes bijective when hashing a single block of the same size as the output?

Question

It's been said that CRC-64 is bijective for a 64-bit block.

It the corresponding statement true for typical cryptographic hashes, like MD5, SHA-1, SHA-2 or SHA-3?

For example, would SHA-512 be bijective when hashing a single 512 bit block?

Answer 1

It would be very freakish if it turned out to be true. It is not an expected property of SHA-512 to have such bijectivity. It would be worrisome, even, because that's a kind of structure that should not appear in a proper cryptographic hash function.

Actually proving that SHA-512, for 512-bit blocks, is not bijective, would already be a kind of a problem. We do not expect to be able to prove such things without breaking the function.

One "simple" way to prove this would be a single collision (on short inputs), which in theory could be found by chance. But for finding such, we expect to have to calculate about $2^{256}$ hashes (and store/compare them to the other values) to have a non-neglible probability to find a collision.

For example, if I have one zettabyte of fast accessible storage (which would be more than half of humanity's currently stored data), I can store about $2^{62}$ SHA-512 hashes. The probability that between these is at least one duplicate would be about $2^{-389} \approx 10^{-117}$. If every human (around $2^{33}$ in some years) repeats this experiment about once a week (i.e. $2^6$ times a year) with $2^{62}$ new hashes, humanity each year has a chance of $2^{-351}$ of finding a collision. Assuming that humanity will work on this for 10 times as long as the universe already existed (i.e. 130 billions of years), we get a chance of $2^{-314} \approx 10^{-94}$. For comparison, the probability that a ticket wins the main prize in the German weekly lottery (6/49) is around $2^{-27}$, so the probability that humanity will ever find a collision (in the scenario outlined above) is lower than the probability of me winning the main prize each week, for 11 weeks in sequence (with one ticket per week).

So we can expect collisions to stay hidden until the end of times.

Answer 2

No. Cryptographic hash functions model a random function, not a random permutation. A significant fraction of output hash values are expected to be unreachable and another fraction have multiple preimages.

While bijectivity in general does not mean that the inverse is easy to calculate, for the types of constructs which are used in hash functions in practice, if it were bijective, it could be easily inverted and would thus not make a very good hash function.

There are other known bijective (candidates for) one-way functions, like the ones used for asymmetrical cryptography, but these constructs tend to be a lot slower, and are different from the ones used in hash functions.

Answer 3

No.

Proof :

Let A be an object represented by a string of bits of length N "10001010110101100 ..."

Let H be the Hash of A , SHA256(A) = H ,H is of 256 bits length

How many possibilities of H are there ? the answer is 2 to the power of 256

And how many possible values of A we got ? the answer is 2 to th power of N

So if N>256 than our hashs are impossible to be unique , in that case , there would be too much possible values to assign hashs to. therefore , we will certainly have duplicated hash, at least 2 to the power of N-256 duplicated hashs

if SHA256 was bijective , than why dont we just use it as a perfect compression algorithm , that can put gigabytes in 256 bits ? ;) you can find answers for such questions in the information science .

( SHA256 hashs are unique for objects of size <= 256 bits )