Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

It the corresponding statement true for SHA-2?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
Assuming processing power doesn't skyrocket... –  hexafraction Jun 5 '12 at 20:00
    
Not even then. I won't detail the math in a comment, but if we were to construct the most energy-efficient computer theoretically possible, it would require all of the output from a supernova in order to cycle a 219-bit counter. And that's an almost imperceptible fraction of the energy necessary to run a counter through 256 bits. –  Stephen Touset Feb 28 '13 at 18:02
    
@StephenTouset And even then, SHA-512 is more expensive to compute than iterating a counter, so you can add a few more bits of required computational work to that. –  Thomas Mar 1 '13 at 10:00
    
It still astonishes me to consider that given the hundreds of zetabytes of data our species has ever stored digitally, we haven't even made perceptible progress in representing all the values capable of being stored in 32 bytes of the tiniest chip of RAM ever created. –  Stephen Touset Mar 1 '13 at 18:33
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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