CertainKey To Pay $10,000 For MD5 Collision 14
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."
Re:the reward is just like a bonus (Score:3, Informative)
I think by "nondeterministic", you mean a relation which maps multiple inputs to a single output, don't you? The output of any hashing algorithm is deterministic: that is, you always get the same hash out when you put the same input string in. And I'll think you'll find when you look at the algorithm that it's not so simple to reverse, nor to find collisions.
Take the whole algorithm, reverse the order,
Well, to start with, reversing the algorithm properly might be hard. A lot of block ciphers do different steps at each stage, depending on what the input is. It might not be very straightforward to produce an algorithm in reverse order, in the same way it could be awkward to parse a program in reverse order. For example, which stage is "the end"? Where you stop depends on your input string!
and replace each step with a step that can produce multiple possible outputs for a given input. (such as, sqrt(4)).
I'm not exactly sure what you mean here, but it appears to involve computing an inverse function. (In your example, you seem to be noting that inverse of the x-squared function can be +x, or can be -x). Hash functions are designed to be difficult to reverse: computing the inverse function is not always easy. Considering how hard factoring a large number can be.
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.
Well, you'ld just said that you replaced each step of the old algorithm with a step that will produce multiple values. So your "search" will always stop at the first step, will it not?
I'm not sure exactly what you're proposing, but it really sounds like you're assuming that some of the steps involved are much easier than they probably are.
No need to brute-force it.
Well, there probably was, actually. For example, I've known one professional cryptographer for over fourteen years, and he was, of course, interested in analysing MD5 and SHA back when we were both students. If it were as easy to break as you suggest, he probably would have solved it then. He's not dumb: he had the highest entrance marks in the faculty of math the year he applied, entered with a full scholarship, graduaded Dean's Honours list with an average in the high 90% range, did his PhD in cryptography at Berkley... the whole bit. The man's quite literally a genius, and yet he didn't break SHA or MD5. To anyone who's met him, they know that means it's a hard problem.
Futhermore, he's not the only cryptographer who would have been interested: just about anyone who did work in crypto was interested in the strengths and failings of SHA and MD5. The fact that they both withstood analysis for so many years attests to the difficulty involved.
The Chinese team has really done some good work to find these collisions, and they deserve congradulations for their well-earned reward.
It certainly wasn't as easy as it may look.
--
AC
Re:what is safe now ? (Score:1, Informative)