CertainKey To Pay $10,000 For MD5 Collision

jlcooke writes "CertainKey Inc. (the folks who put a $10,000 bounty on finding a collision in MD5) will award the prize Friday to Xuejia Lai, Xaioyun Wang, and Hongbo Yu of the Dept. of Computer Science and Engineering at Shanghai Jiaotong University in Shanghai, China. These are the same people who Broke SHA-1."

Comments

Re:the reward is just like a bonus

[Short Circuit]

I'm no crypto expert, but isn't it just a matter of finding a nondeterministic operation in the algorithm, giving it a resulting value, and proceeding backwards with two values that collide in that operation?

Take the whole algorithm, reverse the order, and replace each step with a step that can produce multiple possible outputs for a given input. (such as, sqrt(4)) Start at the end of your "new" algorithm, and search for the first step that will produce multiple values as an output for a single value as an input. This single input value, when run through the the true algorithm forward from the appropriate point, will give you your collided key result. Run through your new algorithm forward from the step that it was deduced from, and it will give you the colliding values.

No need to brute-force it.