On Tue, 15 Oct 2002 15:39:50 BST, Roland Postle <mailblazde.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

-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) Comment: Exmh version 2.5 07/13/2001

iD8DBQE9rEH7cC3lWbTT17ARAk6UAJ9J7vhvFlvFbuJmaeXYWMCReerJ7ACfRTnN IOytrhLP51kOKFIEEn5t4KM= =2MIR -----END PGP SIGNATURE-----

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]