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?

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.

  • Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Jun 25 '17 at 11:11

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.

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 )

New contributor
Hassen Dhia is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 2
    This proof doesn't work, as the question is restricting the inputs to N=256 – poncho Dec 6 at 16:08
  • 2
    And we do not know SHA256 is unique for <=256-bit inputs as you state without explanation -- or even consider it likely, as the previous answers correctly say. If you could prove that, you would be famous among cryptographers. – dave_thompson_085 Dec 7 at 3:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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