Is it known to what message size are standard hash functions injective?

Question

This simple Python script verifies that all messages of length 1 have different SHA-1 hashes:

import hashlib
s = set()
for i in range(256):
    s.add(hashlib.sha1(chr(i)).hexdigest())
print len(s)

Is it known up to which message sizes are cryptographic hash functions such as SHA-1, SHA-2 or MD5 injective? In other words (for each hash function):

1. What are the shortest two messages with the same hash?
2. What's the smallest n such that there exist two messages of length n with the same hash?

Answer 1

(edit) This assumes "ideal" hash function design (a one-way function with no internal structure). Actual implementations approximate this, and may have flaws which make them more predictable than they should be.

According to Wikipedia (summary bar on the RHS), "No actual collisions have yet been produced" for SHA-1. The best we've done is find algorithms that "should" find collisions eventually. SHA-1 has predictable collisions (SHAttered), but these collisions are definitely not the shortest, because they involve a prefix longer than the hash itself.

Since the point of a hash function is that any change (even a single bit) should change the whole result in a basically pseudorandom way, you're essentially looking at the birthday problem.

The table on this Wikipedia page lists the tradeoff between how many inputs you have and how worried you should be about a collision. This other table here lists the "security" of each hash (in bits).

An example calculation: for SHA-512, with 256 bits of security, you have to be looking at 10^32 before you start to get problems. log2(10^32) is about 106 bits, which means you should start worrying about collisions after about 13 bytes. However, if you're picking them randomly, you might have other issues at that point, like your electricity bill and the death of the Sun.

Answer 2

This is something I've spent some time trying to figure out too. The answer is a lot harder then it appears, but quite consistently seems to be "We have no clue".

This might seem strange but it's actually quite reasonable when you consider what you are looking for. Essentially you're asking someone to find a collision in a hash function. That is supposed to be VERY hard. Both SHA-1 and SHA-2 and to a lesser extent MD-5 (which is broken) were designed not only so that find preimages and collisions would be hard, but even more then that. A good hash function should be indistinguishable from a random oracle.

If we were able to figure out things like the ones you are asking we would know way more about the functions then what we should be able to tell.

Obviously you can be sure that there are two messages of length <= n+1 which collide, where n is the block length of the hash function. I would expect the length of the smallest collisions to be close to maximal but to be honest I can't really back that up with math.