On Fri, 23 Dec 2005 21:07:57 -0800, Paul Rubin wrote: > Steven D'Aprano <[EMAIL PROTECTED]> writes: >> http://www.iusmentis.com/technology/encryption/pgp/pgpattackfaq/hash/ >> >> the expected number of random unique files you would need to compare >> before finding a single collision in the MD5 hashes is (very roughly) >> 10**70, or ten billion trillion trillion trillion trillion trillion. > > That's not right, the right number is around 2**64 or 2e19. See the > section of that page about the birthday attack. It's still an awful lot.
Oh poot, a stupid typo! I entered 1e60 in my calculation instead of 1e6, which is doubly embarrassing because the correct number to use is 1e9: [quote] In MD5's case, 2**64 messages need to be tried. This is not a feasible attack given today's technology. If you could try 1,000,000 messages per second, it would take 584,942 years to find a collision. A machine that could try 1,000,000,000 messages per second would take 585 years, on average. [end quote] So the expected number of files (messages) needed to check to find a collision is: 585*365*24*60*60*1e9 = 1.8e19 or more than ten million million million, which of course equals 2**64. > There are also known ways of deliberately constructing md5 collisions > (i.e. md5 is broken). Whether the OP should care about that depends > on the application. Sure, but I don't he is deliberately trying to sabotage his own files :-) -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
