The Pointlessness of the MD5 "attacks"

David Wagner daw at cs.berkeley.edu
Wed Dec 15 12:12:49 EST 2004


Ben Laurie writes:
>Indeed, but what's the point? If you control the binary, just distribute 
>the malicious version in the first place.

Where this argument breaks down is that someone might have partial
but not total control over the binary.  This partial control might
not be enough for them to distribute a malicious version straightforwardly,
but just enough to exploit a MD5 collision.  It is hard to be confident
that such an attack scenario is impossible.

To give one contrived example, imagine that the Windows 2010 binary
comes with an image file that is displayed as part of the splash start
screen.  Imagine that the graphic designer is allowed to supply that
image, but the graphic designer has no other authorized access to the
source or binary of Windows.  Now a disgruntled graphic designer might
be able to arrange to find a MD5 collision MD5(img1) = MD5(img2) so that
img1 looks like an entirely reasonable Windows splash screen, but img2
contains some scrawled epithet ("Tired of Windows crashing all the time?
Try Linux!").  Or, even more contrived, imagine that img1.jpg looks
like a completely normal JPG file, but img2.jpg exploits some buffer
overrun in the startup screen's JPG decoder to overwrite the program's
image with some other malicious code.

Sure, these scenarios are contrived and unlikely.  But how do you
know that there is not some other (possibly more complex but less
contrived) scenario that you would consider more troubling?

>People seem to be having a hard time grasping what I'm trying to say, so 
>perhaps I should phrase it as a challenge: find me a scenario where you 
>can use an MD5 collision to mount an attack in which I could not mount 
>an equally effective attack without using an MD5 collision.

I've got a better challenge: show me a convincing argument that no such
scenario exists.

What I'm trying to get at is that you've got the burden of proof
backwards.  Implicit in your challenge is the idea that we should
keep trusting MD5 until someone finds a convincing argument that it is
insecure in practice.  My argument is that this is much too trusting.
I believe that, given the theoretical results on MD5, we should not have
any trust whatsoever in the security of MD5 as a collision-resistant
hash until someone is able to offer a convincing argument that MD5 is
secure enough in practice despite its known weaknesses.

I could try to answer your challenge.  I might even be able to devise
some solution to your challenge that would satisfy you.  For instance,
maybe the image file attack above qualifies as a solution.  Or maybe
the S-box table attack in my previous email is good enough.  But I don't
really want to argue about whether I have found a valid answer to your
challenge.  I shouldn't be required to meet that burden -- the burden
of proof should be on whoever wants to believe that MD5 is secure.

Why should the burden be on MD5 defenders?  Not just because I said so.
Part of the reason is that there are just too many complex scenarios
to consider.  Suppose I conceded that I couldn't find a scenario you'd
accept.  What would that prove?  Very little.  Even if I can't think of
a suitable scenario for you off the top of my head, that doesn't mean
that with more thought I wouldn't find one.  Even if I spent a month
trying and still couldn't find one, that doesn't mean that others can't.

My experience is that if it is possible to find a theoretical attack with
one day's work, it is often possible to extend this to a more practical
attack with, say, one week's work.  Bruce Schneier puts this concisely:
"Attacks always get better."  Trusting in MD5's collision-resistance
amounts to assuming that "cryptanalysts of MD5 will get this far, but
no farther", and that seems like a pretty questionable assumption to me.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list