On Wed, Apr 26, 2000 at 07:05:18PM -0000, [EMAIL PROTECTED] wrote: > > Hi! > > 26 Apr 00 12:45, Alexander Hvostov wrote to UUCP: > > AH> Yeah, yeah, you just try and break an MD5 checksum anytime this > AH> year. *cough* > It'll take some time, but it's possible. A simple brute-force attack will do > the job. And "some time" depends VERY much on the hardware the cracker owns. > It > may be enough to be secure against your friends, but not against a "real" > cracker.
It still only scales linearly with the speed of hardware available. You would have to have more funding than the NSA to get that much hardware! Is there any reason to believe it could be done in less than the age of the universe (~1e10 years) for 128bit MD5? Read RFC 1321 and tell me what you think then. :) (http://www.faqs.org/rfcs/) You have to make on the order of 2^128 guesses to come up with a message that has the same hash as the file you're trying to spoof. (you don't get the advantage of the "birthday paradox" (29 people in a room -> 50% chance at least one pair has the same birthday) because the other member of the pair is already picked: it is the md5 hash of the original file. $ bc -l 2^128 / 10000000000 / 365 / 24 / 60 /60 1079028307080601418897.0529154990 l(.)/l(10) 21.0330328388 so, you'd have to perform 10^21 md5 hashes per second to get as many hashes as there are possible hashes. (you wouldn't exactly "exhaust the key space", since the "key" is the message you are hashing, and it is _much_ longer than 128 bits.) Since MD5 works on chunks of 64 bytes, you could mess with the last few bytes only and not have to run MD5 on the whole file every time, just the last 64-padlength bytes and the pad bytes. (You would pre-compute the first bit of the file.) This lowers the time required to check a variation of each computation a lot (especially for long files), but not enough. Also, if you try to exhaust the (effectively 64byte) keyspace, you won't have any luck at all! That's 2^512 different possibilities!) On my P200MMX, md5sum takes at best 0.85sec on a 12724349 byte MP3 file. To md5 transform one 64byte chunk takes scale=0 12724349 / 64 + 1 198818 scale=10 0.85 / . .0000042752 i.e. 4 microseconds = 4*10^-6 ~= 2^(-18) (10^3 ~= 2^10, coincidentally) Thus, on my computer, assuming you could generate a test m5dsum in the time it takes to do a single md5 block, it would take 2^(128-18)=2^110 seconds to have a pretty good chance of stumbling upon a bit pattern that worked. That's a long time: 2^110 / 365 / 24/ 60 / 60 41161663325523430591470829.6012501268 10^25 years is a damn long time. The universe is only on the order of 10 billion years old! RC5 is a similar algorithm to MD5 (designed by the same guys, RSA), consisting of rotates and bit shifts, so, given that I get 430 kkeys/s on my computer, and that www.distributed.net reports 147 Gkeys/s for RC5, if we had every computer that's running RC5 trying to find a hash collision for a given hash, 41161663325523430591470829.6012501268 * 430/147 / 1000000 120404865510034524859.4044675410 That's still 10^20 years, which is a damn long time. You would be hard pressed to find enough computing power to do this, no matter who you are. (even the NSA couldn't do it in a year. I'm sure they don't have 20 orders of magnitude more computing power than d.net. Also, MD5 is somewhat complicated, so you would have a hard time building dedicated hardware much faster than a general purpose CPU.) (BTW, if you don't know about distributed computing, check out www.distributed.net, and www.dcypher.net. dcypher's got a real-world useful project: simulating gamma rays to help figure out how to build better nuclear waste containers. Too bad they only run on x86: linux, *bsd, or windoze.) Even if you did find a way to change a file and preserve its MD5 digest, you might have a hard time making use of that. Assume you've made some changes to a file, and then you want to adjust it back to the original MD5 digest. You would have to find a block of data that you could set arbitrarily, otherwise changing the bytes to make the digest right would make the file invalid. If you did this with a shell script, you could mess with a comment longer than 64 bytes (as long as the bytes didn't turn out to include \n, which would end the comment, wasting the billions of universe-ages of CPU time you spent calculating it.) For a binary file, you would have to make the whole rest of the file smaller so you could add 64 bytes somewhere that got ignored. (if you change the length of the file, that will get noticed along with the md5sum, most likely!) Some people have made some progress in cryptanalysis of md5sum, but I haven't heard about this affecting the likelyhood of finding collisions for a given hash value. If this is not the case, (i.e. collisions are a lot more likely than 1 in 2^128, or for some other reasone it takes orders of magnitude less than 2^128 guesses before you find a message with the same digest as some other _already specified_ message), I would really like to hear about it. BTW, what makes you think "real crackers" have super fast hardware at their disposal? Do you think they cracked into NASA or the NSA or something? AFAIK, most crackers are just badasses with an internet connection and a PC. (almost always x86, but I suppose some have the sense to get a Mac and run some kind of Unix on it.) (I think _mostly_ only script kiddies try "hack" from non-Unix machines. Sillies :) Besides, I'm almost certain that no system cracker would bother to get the md5 digests the same on all the files they changed, since most people don't check. I'd say you would be able to find changed files > 99% of the time, and either you wouldn't find any changed, which would mean a _very_ sophisticated cracker, or you would find every file she changed. (the chance of one changed file randomly staying unchanged is 1/(2^128)) Happy hacking :) -- #define X(x,y) x##y Peter Cordes ; e-mail: X([EMAIL PROTECTED] , ns.ca) "The gods confound the man who first found out how to distinguish the hours! Confound him, too, who in this place set up a sundial, to cut and hack my day so wretchedly into small pieces!" -- Plautus, 200 BCE
