is SHA-512 collision resistant?

Question

According to the books that i have read, it says that S.H.A(Secure Hash Algorithm) is collision resistant.But if the input space is a 1024 bit number and the output space is a 512 bit message digest then shouldn't it be colliding for (2^1024)/(2^512) times? As the range is lesser than the domain being mapped there should have been collisions. please explain where i am going wrong.

Drudgery

Related: Pigeonhole principle and Collision resistance – Slayton

I'm voting to close this question as off-topic because this is purely about cryptography without involving programming. – Boonie

Yes, it will collide by definition. However, it should be impossible to calculate or guess which value collide. You cannot just iterate over possible values until you find a collision of course, you'd have run out of time (any time - pick your period) before you'd find a collision. – Boonie

(2^1024)/(2^512) = 2^512 which is close to 10^155 (which is bigger than a googol but less than a googolplex). – Requisite

What does "the input space is a 1024 bit number" mean? The only thing that counts is the number of unique inputs and in turn the number of unique outputs. Perhaps see Hash collision probability calculator. – Requisite

Answer 1

Maybe your book has also mentioned the definition of collision resistance? It does not mean that no collisions are created (which is clearly not the case), but that given a hash you are not able to create a message easily that produces this hash.

a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b

From Wikipedia

Nianiabi

Not quite, Cryptographic hashes such as SHA256 are also frequently used to identify items such as file contents from one another. There is always a change of a collision but in practice this is extremely rare, rare enough to be ignored in most cases. Git for example uses hashes to uniquely identify commits. – Requisite

Not quite what? I don't get your point with regard to the OP question "what is collision resistance". – Nianiabi

@Requisite Git uses SHA-1 and is therefore not a brilliant example :P Maybe try ZFS or similar. – Boonie

@MaartenBodewes Note there is no claim that Git uses SHA-256. In fact if SHA-1 suffices one should assume that SHA-256 is even better at resisting collisions. – Requisite

Answer 2

The chance for a collision does not depend on the input size. The chance to a 512-bit hash collision is 1.4×10^77, see Probability table

Requisite

Answer 3

As you describe: Since the input space (arbitrary size) is larger than the output space (e.g. 512bit for sha512), there always exist collisions.

"Collision resistant" means, it is adequately unlikely for a collision to be found.

Your confusion is answered when considering how large the output space "512 bits" really is:

2^512 (the number of possible configurations of a 512 bit array) is of the order 10^154.

For comparison: The number of atoms in the visible universe is somewhere in the range of 10^80. A million is 10^6. So a million universes like ours are 10^86 atoms. A million times a million universes are 10^92 atoms.

If you could store a single 512 bit value on a single atom, how many universes would you need to have all possible 512 bit hash values stored?

Starting with a specific 512bit number (and assuming the has function is not broken), the probability p to obtain a collision is assuming you can produce new hashes with a rate R and have the total time of t to do this is:

p = R*t/(2^(512/2))

(The exponent is halved (google "birthday attack") because: The expected search space for a success is to find a collision in n bits is n/2.) Let's plugin in some example numbers:

The has rate of the bitcoin network is currently about R = 200*10^15 / s (200 million terrahashes per second).

Consider the situation that since the beginning of the universe the bitcoin network's current hashing capacity would have been available for the sole purpose of finding a collision for a specific hash value, i.e. for an available time of t=13.787*10^9 years,

then the probability that a collision would have been found by now is about 7 × 10^-41 %

Again, it is hard to appreciate how small this number is.

Edit: A similar question with a good answer is found here: https://crypto.stackexchange.com/questions/89558/are-sha-256-and-sha-512-collision-resistant

Capacitance