Alex Rivera | Logout

Create your own MD5 collisions

Asked 2009-06-01T03:50:03.163
52

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?

algorithm language-agnostic hash
Edit
Report

2 Answers

1

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.

answered 2009-06-01T04:47:58.823
-5

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!

answered 2009-06-02T03:41:57.407

Your Answer