Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

CertainKey To Pay $10,000 For MD5 Collision

timothy posted more than 8 years ago | from the wham dept.

Encryption 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."

cancel ×

14 comments

Sorry! There are no comments related to the filter you selected.

Gives a whole new meaning to... (2, Funny)

vasqzr (619165) | more than 8 years ago | (#11703737)


HACKED BY CHINESE!

Re:Gives a whole new meaning to... (0)

Anonymous Coward | more than 8 years ago | (#11703987)

That's gold Jerry...gold!

Now make them find the substitute! (1)

solafide (845228) | more than 8 years ago | (#11703816)

That would benefit them. Now I think I will offer a prize of a few hundred thousand for another common crypto method and the condition is you have to find the substitute, plus everything you do is my property. Makes it quite profitable to offer the reward! Billy

Unfortunately... (3, Funny)

jd (1658) | more than 8 years ago | (#11704057)

The serial numbers of the dollar bills used to pay the winners had a hashing collision in the bank machine, which therefore only registered the first note.

watch out! (1, Funny)

Anonymous Coward | more than 8 years ago | (#11704313)

Don't show up, guys! They're waiting to arrest you under the DMCA!

Re:watch out! (1)

jlcooke (50413) | more than 8 years ago | (#11704374)

CertainKey Inc. is in Canada. And the funds are being wired to China.

Re:watch out! (1)

tomstdenis (446163) | more than 8 years ago | (#11704801)

Does this mean no patties for a few weeks?

Tom

the reward is just like a bonus (1)

coolcold (805170) | more than 8 years ago | (#11704339)

consider the amount of effort to break the algorithm when compared to the reward, it appears the reward won't be attractive enough for hackers to break it.

It would server great as a bonus in research though

Re:the reward is just like a bonus (0, Redundant)

Short Circuit (52384) | more than 8 years ago | (#11704674)

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.

Re:the reward is just like a bonus (3, Informative)

Anonymous Coward | more than 9 years ago | (#11706509)

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?

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:the reward is just like a bonus (1)

bedessen (411686) | more than 9 years ago | (#11719433)

I'm no crypto expert...

You could have stopped right there, honestly...

Hashing functions are designed to explicitly prevent or make exceedingly difficult that sort of thing, so you can't just "work backwards" in that way. Maybe you'd like to review the algorithm... [wikipedia.org]

Does this mean... (1)

codehead (14804) | more than 8 years ago | (#11705367)

...that these same guys found cost-effective means to crack not just one, but *two* widely-used hash algorithms?

what is safe now ? (1)

free2 (851653) | more than 8 years ago | (#11705874)

which algorithms are safe now ?

Re:what is safe now ? (1, Informative)

Anonymous Coward | more than 9 years ago | (#11718126)

"Broken" SHA-1 is still safer (2^69 operations) than MD5 (2^64) was ever supposed to be.
Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>