Up to what string length is it possible to use MD5 as a hash without having to worry about the possibility of a collision?
This would presumably be calculated by generating an MD5 hash for every possible string in a particular character set, in increasing length, until a hash appears for a second time (a collision). The maximum possible length of a string without a collision would then be one character less than the longest of the colliding pair.
Has this already been tested for MD5, SHA1, etc?
The mathematics of the birthday paradox make the inflection point of probability of collision roughly around sqrt(N), where N is the number of distinct bins in the hash function, so for a 128-bit hash, as you get around 64 bits you are moderately likely to have 1 collision. So my guess is for the complete set of 8 byte strings it's somewhat likely to have a collision, and for 9 byte strings it's extremely likely.
edit: this assumes that the MD5 hash algorithm causes a mapping from input bytestring to output hash that is close to "random". (vs. one that distributes strings more evenly among the set of possible hashes, in which case it would be more close to 16 bytes.)
Also for a more specific numerical answer, if you look at one of the approximations for calculating collision probability, you get
p(k) ≈ 1 - e-k(k-1)/(2*2128) where k = the size of the space of possible inputs = 2m where the input bytestring is m bits long.
the set of 8 byte strings: p(264) ≈ 1 - e-0.5 ≈ 0.3935
the set of 9 byte strings: p(272) ≈ 1 - e-2144/(2*2128) = 1 - e-215 = 1 - e-32768 ≈ 1
Also note that these assume the complete set of m/8 byte strings. If you only use alphanumeric characters, you'd need more bytes to get a probable collision.
I doubt if there is any useful length where you're not going to have possible collisions. Those algorithms are not really used for that purpose. It's meant to try to be unique for slight changes in the data (like corrupted files) rather than unique over all possible sets of data.
