[Standards] MD5 is weak...?
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
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
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
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 Cridland - mailto:dave at cridland.net - xmpp:dwd at jabber.org
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade
More information about the Standards