[Standards] MD5 is weak...?

Dave Cridland dave at cridland.net
Wed Sep 12 10:21:03 UTC 2007


Yes, folks, it's time for the "MD5 is weak" show. Join in if you know  
the words, and don't worry if you miss it, it'll be repeated very  
soon.

All this is my limited understanding only. Not a qualified or  
licensed cryptographer. Please consult your own cryptographic expert.  
The value of hashes may go down as well as up. Etc.

On Wed Sep 12 07:57:31 2007, Jonathan Chayce Dickinson wrote:
> Oh, and MD5 has been heavily criticized, is it not time somebody  
> used SHA?
> 
> 
MD5 has several known weaknesses. It's also one of the most carefully  
examined cryptographic hash functions, which is why. SHA-1 is now  
also showing weaknesses, although it's not yet reached the point  
where they're useful. SHA-2 (including SHA-256) is effectively just  
SHA-1 "but more so", so most experts seem to think there's a  
possibility that a severe flaw in SHA-1 would yield flaws in SHA-2 as  
well.

There are several key exploitable weaknesses in MD5, in particular,  
if the attacker knows X and H(X), it's possible (ie, slightly easier  
than it should be) for them to construct Y, such that H(Y)==H(X).  
It's actually trivial if they can choose both X and Y. This means in  
particular that MD5 is worthless as a signature - so if you see a  
software package which is apparently "signed" with MD5, this is not a  
useful guide that the software package is authentic. This is harder  
(in both cases) for the attacker if X and Y must fit a particular  
tight syntax, since there's then less room to wiggle.

Luckily, this doesn't affect CRAM-MD5, or DIGEST-MD5, or SCRAM/HEXA  
when used with MD5. It doesn't even affect many uses of HMAC-MD5,  
which is also used for signatures. This is because the X is  
(partially or completely) unknown.

MD5 is not susceptible to a second preimage attack, that is, given  
only H(X), an attacker cannot determine what X might be, nor can they  
find Y such that H(Y)==H(X) - you need to know X first. (As an aside,  
this is also harder to do even with an entirely unbroken hash, thanks  
to the Birthday Paradox).

There is one reason pushing change, which is that with modern  
hardware, it's simply too quick to do, making dictionary attacks more  
feasable. (Actually, there's the reputation of MD5, too, but there's  
only one *technical* reason).

CRAM-MD5 and DIGEST-MD5 are not hash agile, whereas SCRAM and YAP  
(and HEXA) are, so the answer to your question is that somebody is  
using SHA (in particular, SHA-256 is popular), and moreover, somebody  
is expecting the entire SHA family of cryptographic hashes to be  
broken utterly one day.

In the case of HEXA, I elected to continue using MD5 as the mandatory  
hash, but used several rounds of it, increasing the computational  
cost trivially, but leveraging the vast deployed base of MD5-capable  
software.

Most people disagreed with this decision, not because MD5 was weak in  
this respect, but because they pointed out that SHA-256 was a lot  
better deployed than I thought. This means that - assuming MD5 second  
preimage attacks are likely to become viable before SHA-256 second  
preimage attacks, which seems a reasonable asusmption - deploying  
SHA-256 to begin with will extend the life of the mechanism at little  
cost to initial deployments.

(To be fair, a lot of people agreed that use of MD5 in HEXA was safe,  
but said that they felt uncomfortable with it nonetheless).

Dave.
-- 
Dave Cridland - mailto:dave at cridland.net - xmpp:dwd at jabber.org
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade



More information about the Standards mailing list