4
$\begingroup$

This is in reference to this answer on Stackoverflow. If you read the first paragraph of the answer, you'll find this line:

It's always a many:1 mapping (meaning there will always be collisions) since every function produces a smaller output than it's capable of inputting (If you feed every possible 1mb file into MD5, you'll get a ton of collisions).

What is this many:1 and what are collisions? Does many:1 mean two different inputs would have the same hash outputs?

$\endgroup$

1 Answer 1

4
$\begingroup$

Does many:1 mean two different inputs would have the same hash outputs?

Yes. This is a consequence of the pidgeonhole principle: as MD5 has a much larger number of potential inputs ($2^{2^{64}}$ or so) than outputs ($2^{128}$), some inputs must lead to the same output, i.e. collide.

Cryptographic hashes all have this "limitation", because they have a constant output size and allow much larger inputs. However, with good cryptographic hashes (MD5 is very broken in this sense), you have no way of finding those collisions. This is called collision resistance and is one of the properties we require of hashes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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