Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does md5 have any uniqueness guarantee for short strings (finite number of strings)?

So I understand that there is proof that MD5 can not guarantee uniqueness as there are more strings in the universe than there are MD5 hash strings, but is there any inverse proof for a finite number of strings?

Basically, if I have strings of maximum length of X, is there an X for which MD5 is guaranteed to be unique? if yes, then what is that X? and if there are more than one values for X, what is the maximum value of X?

or is there such an X for any other hashing algorithm, SHA-1, etc.?

like image 236
xtrahelp.com Avatar asked May 15 '12 03:05

xtrahelp.com


1 Answers

Summarizing the excellent answers here: What's the shortest pair of strings that causes an MD5 collision?

The shortest known attack on MD5 requires 2 input blocks, that is, 128 bytes or 1024 bits.

For any hash algorithm that outputs N bits, assuming it distributes inputs approximately randomly, you can assume a collision is more than 50% likely in about sqrt(2^N) inputs. For example, MD5 hashes to 128 bits, so you can expect a collision among all 64 bit inputs. This assumes a uniformly random hash. Any weaknesses would reduce the number of inputs before a collision can be expected to occur.

like image 164
Clueless Avatar answered Sep 21 '22 12:09

Clueless