Does md5 guarantee uniqueness for short lines (finite number of lines)?

Question

So, I understand that there is evidence that MD5 cannot guarantee uniqueness, since there are more lines in the universe than there are MD5 hash lines, but is there any backward proof for a finite number of lines?

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

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

Answer 1

To summarize the excellent answers here: What is the shortest pair of lines causing MD5 collision?

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

For any hash algorithm that outputs N bits, assuming it allocates inputs approximately randomly, you can assume that a collision is more than 50% more likely in approximately sqrt(2^N) inputs. For example, MD5 hashes up to 128 bits, so you can expect a collision between all 64-bit inputs. This assumes a uniform random hash. Any flaws will reduce the number of entries before a collision occurs.

Answer 2

The answer to your question is yes. For any hash function, there is a maximum length X for which you will get unique strings. However, finding X could be very difficult. The idea is to run this program:

 X= 0; For i = 0 onward For all strings of length i Compute the hash code of that string. If a collision is found, return X. X = i 

The idea is to simply list long and long lines until you find a hash collision. In the end, you will have to, because in the end you will create more lines than there are possible hash outputs.

While waiting, assuming the hash function is actually quite random, you need to generate O (& radic; U) different lines before you find a collision, where U is the size of the space to which the hash functions are attached. For 256- bit hashes is 2 ²⁵⁶ . This means that in practice the aforementioned program would never have stopped if the hash function had not been violated, but in theory this means that your number X exists.

Hope this helps!