Re: Hashes,File protection,etc

[Valdis.Kletnieks () vt edu]

On Tue, 15 Oct 2002 15:39:50 BST, Roland Postle <mail () blazde co uk>  said:

>    MD5 has an output of 128 bits, which I think is too small for
>  good security.  A collision can be found by brute force in 2**64
>  operations.

Assuming 10,000 trials a second, this will take 58,494,242 cpu *years*.
(an 'md5sum' of a 17M file on my laptop takes 0.110 seconds on a 1.6G Pentium4,
so 10K/sec trials of 17K texts is "in the ballpark" - even assuming a processor
that's 10x faster gets you down only to 5M cpu-years).

And notice that this is "a collision".  At that point, you have 2 essentially
random plaintexts that happen to have the same MD5 hash, and said hash is
unrelated to anything else.  Most likely, neither one resembles *in the
slightest* something "reasonable" (for instance, if you're expecting a 1.8M
source tarball, it should be in tar format and somewhere near 1.8M in size).
Forcing a collision to *a specific known hash* is a lot harder - and at that
point you'll probably still have an essentially random file.  And unlike
beating a CRC-32, there's probably no efficient way to take a *given* file, and
find a way to *modify* that file and still maintain the SAME md5sum.

And remember that 58 million CPU years is *per collision*.  Are there *any*
targets who's threat model *really* includes this?  Probably not for private
individuals - there's cheaper ways to do it (Marcus Ranum's "rubber hose
cryptography" and related methods).  Inter-bank encryption codes?  If they
change them once per year, you'll need a 50 million CPU machine for it to
do you any good.  I suspect even nuclear launch codes can be obtained with
less investment of resources....

So - do *YOU* have anything secured by an md5sum that's worth 58 million
cpu-years to break?  If you don't, then md5 is 'secure enough'.  If you do,
I hope you have all the physical security issues and personnel security
issues dealt with... :)
-- 
                                Valdis Kletnieks
                                Computer Systems Senior Engineer
                                Virginia Tech

Attachment: _bin
Description: