1

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?
4

(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.

  • 1
    An actual collision in SHA-1 was found in 2017. The Wikipedia has been updated to eflect that. – Eugene Ryabtsev Jul 11 at 8:41
  • The SHAttered attack doesn't affect the actual answer to the question, because the chosen prefix is longer than one internal block, but I've clarified at the top. – cloudfeet Jul 11 at 12:19
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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