Slashdot Mirror

← Back to Stories (view on slashdot.org)

CertainKey To Pay $10,000 For MD5 Collision

Posted by timothy on from the wham dept.

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

14 comments

  1. Gives a whole new meaning to... by vasqzr · · Score: 2, Funny


    HACKED BY CHINESE!

    1. Re:Gives a whole new meaning to... by Anonymous Coward · · Score: 0

      That's gold Jerry...gold!

  2. Now make them find the substitute! by solafide · · Score: 1

    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

  3. Unfortunately... by jd · · Score: 3, Funny

    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.

    --
    It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
  4. watch out! by Anonymous Coward · · Score: 1, Funny

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

    1. Re:watch out! by jlcooke · · Score: 1

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

    2. Re:watch out! by tomstdenis · · Score: 1

      Does this mean no patties for a few weeks?

      Tom

      --
      Someday, I'll have a real sig.
  5. the reward is just like a bonus by coolcold · · Score: 1

    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

    --
    I am harvesting funny/good quotes. Please help by putting them in your sigs :)
    1. Re:the reward is just like a bonus by Short+Circuit · · Score: 0, Redundant

      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.

      --
      tasks(723) drafts(105) languages(484) examples(29106)
    2. Re:the reward is just like a bonus by Anonymous Coward · · Score: 3, Informative

      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

    3. Re:the reward is just like a bonus by bedessen · · Score: 1

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

  6. Does this mean... by codehead · · Score: 1

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

    --
    -- Estoy feliz, feliz de que no sea cierto.
  7. what is safe now ? by free2 · · Score: 1

    which algorithms are safe now ?

    1. Re:what is safe now ? by Anonymous Coward · · Score: 1, Informative

      "Broken" SHA-1 is still safer (2^69 operations) than MD5 (2^64) was ever supposed to be.