Re: MD5 status

On Sunday, December 1, 2002, at 11:32 PM, Oscar Batyrbaev wrote:

> Hi folk,
>
> I am briefly back just to post this short follow up post backed up by
> a very solid
> (albeit published in 96) tech report by M.J.B. Robshaw attached:
> http://islab.oregonstate.edu/koc/ece575/rsalabs/bulletn4.pdf
>
> "... Another
> property that might well be largely unaffected by
> work on collisions is that of being one-way. When
> a hash function is being used purely as a one-way
> function, perhaps to store a table of hashes of computer
> passwords, then work on collisions might well
> have little relevance..."

This is right. Being able to find a collision does not _necessarily_ mean that you can recover anything about the original message.

>
> 2. However, I am very interested to see that new said to be
> unpublished work by
> Dobbertin as he is of course one of the biggest authorities on this.
> Why is he not
> making it public - if it is to do with "responsible disclosure" -
> please feel free
> to send me this in private - I can even sign an NDA. I also could not
> find his
> most up-to-date web site - a pointer will be cool.

My understanding is that Dobbertin has worked for German intelligence since about '96, and is not permitted to discuss anything he may or may not have broken. I doubt that anyone who has a definitive answer for you would be willing to discuss it.

Cryptographers have been saying ever since Dobbertin found full collisions in the MD5 compression function that you shouldn't use it. That's sound advice, considering how many of the people who are willing to put forth the effort to find a practical break instead of a theoretical one are never going to publish their work (the intelligence world). Whether Dobbertin himself has fully broken MD5 by now is beside the point.

  I don't know anyone who works on trying to turn MD5's problems into practical breaks. Part of the reason is that people are more interested in working on problems whose solutions offer utility... MD5 is already considered broken, so why not work on breaking something people might be recommending? Plus, while MD5's problems lend cryptographers to believe that better attacks against it likely exist, they may not be easy to find. Everybody knows that academic researchers go for low hanging fruit :-)

Do you need help?

In addition to our free technical library, Pantek provides professional IT services to companies who utilize Open Source software: Learn more about Pantek's Technical Support offerings Place an order for 24/7/365 Technical Support here Learn more about Pantek, who we are, and what we do Chat with a Live Operator Related securityfocus.com Links bugtraq certification focus-bsd focus-ids focus-ih focus-linux focus-ms focus-sun focus-unix-other focus-virus forensics incidents libnet linux-secnews ms-secnews pen-test secpapers secprog sectools secureshell security-basics securityjobs sf-news vuln-dev webappsec Request more information about Pantek

So then, if you're not worried about protecting yourself against governments, then why should you worry, particularly if no one else appears to be looking at the problem? Just because no one is actively working on this doesn't mean that a very smart person (possibly an attacker) couldn't find a full break. Perhaps a break will be found in the near future, and you may or may not find out about it. If you do find out about it, you'll have to change all your systems, which can be a royal pain. If you don't find out about it, then you could be hosed.   Wouldn't you like to ensure that your systems are safe against any potential problems, especially considering that it doesn't look very good for MD5?

> 3. (this might be an obvious question): for full MD5 - how can they
> "un-one-way"
> it in general - with all the various bit shifting, etc. going on - if
> you loose
> bits during bit shifting in one direction - how can you "find" them in
> reverse?

Statistical attacks. It's hard to say exactly how it would work before a problem is found. But, let's say that you know the first block of the message (common headers, etc... usually a good assumption) and the final block of the MD5 internal state. Perhaps you might be able to take the last state and figure out a handful of prior states that are far more likely than others. If you're trying to break an ASCII stream, discard anything that couldn't have caused the current state because it isn't ASCII. Take any candidate states and repeat, until you get to the end, and see if you match the known starting block. There's definitely a lot of significant work involved in such an attack, even if you have a full MD5 break, but that doesn't mean it isn't practical given the right computational resources.

As the quote above notes, though, the more immediate concern is collisions. Collisions allow for message forgery, whether or not you can find anything out about the original message. Let's say you have a way to cause a collision on a 128-bit MD5 digest that effectively reduces its strength to 40 bits. If you can find a collision after 2^40 operations, and you're smart about it, you should be able to find a collision based on a starting message that you'd like to forge. Basically, you would take the bits that don't matter, and vary those when looking for your collision. The end result would be a real-looking forged message. Plus, even if you can't come up with a valid-looking message, most applications will die horribly if a message does validate and yet is actually garbage.

How exactly you'd go about modifying the bits that don't matter on an attack is dependent on the attack that you have against the algorithm. Needless to say, this is also a matter of smart statistics :-)

John Received on Mon Dec 2 15:03:09 2002