Create your own MD5 collisions

Question

I'm doing a presentation on MD5 collisions and I'd like to give people any idea how likely a collision is.

It would be good to have two blocks of text which hash to the same thing, and explain how many combinations of [a-zA-Z ] were needed before I hit a collision.

The obvious answer is hash every possible combination until hit two hashes the same. So how would you go about coding this. As a quick experiment I tried hashing every combination of 5 columns of [A-Z], storing this in a .net hashtable and catching the collision exception. Two problems with this - the hashtable eventually times out, and I'm pretty sure I'm going to need A LOT more characters.

Obviously this data structure is too big to handle in memory, so now I'll have to get a database involved. Also sounds like a good project to test out azure - a bit like these guys.

Can anyone point me in the direction of an efficient way of doing this?

Answer 1

Check out this paper about hash function tunneling.

Answer 2

I would take a look at Hashcash. With an effective hash algorithm, like md5, the time to calculate a collision to exponential with the number of bits. What Hashcash does is calculates partial collisions. That is, a match of say the lower 16 bits of the hash. To get the lower 16 bits to match, one would have to try hashing 2^15 different combinations on average. If you know how long it takes to come up with a 16, 24, or 32 bit collision, then you can easily calculate out the time for higher numbers of bits.

Answer 3

If you're talking about how likely a straightforward collision is - one where there is no deliberate attempt to cause one - then you're going to be disappointed: You'd need to generate on average 2^64 plaintexts before you can expect to see a collision, and that's substantially more than you're going to be able to do in a reasonable (or really, even an _un_reasonable) time.

If you're looking to demonstrate the difficulty of deliberately crafting a collision, other answers have already demonstrated that. The extra constraint of requiring the strings to be entirely textual makes even those approaches largely impractical, though.

Answer 4

The whole point of such hashes is that collisions are extremely unlikely. You're not going to generate one by chance--your machine will almost certainly die of old age before you succeed. The whole point of using a hash would go away if you could reasonably generate collisions!

Answer 5

It's hard to do it with just text files, AFAIK. You can get some collisions, but having them also be from just [a-zA-Z] is not easy (yet).

On the other hand, if you just want two "meaningful"-looking files with the same hash, you can do it with something like, say, PostScript: have different binary blobs causing the collision, and use a conditional expression to display different output accordingly.

See e.g. this problem (the H2 part) and solution. For example, this PS file and this one have the same MD5sum.