-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tuesday 15 October 2002 09:27, Valdis.Kletnieksat_private wrote: > 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). You're ignoring the block structure of MD5. An clever attacker isn't going to hash 17K of data over and over again, changing a few bytes each time. He's going to calculate the hash of (17K-64bytes) of data, save the chaining variable outputs, and then calculate the hash of the last 64 byte block repeatedly with different data. I have a not-terribly-well-optimized C implementation that hashes 700,000 - 800,000 blocks per second on an old PentiumII-350Mhz, so your estimate is several orders of magnitude too slow. > 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. Maybe the plaintexts are only partially random. An attacker could generate documents A and B, then search for x and y such that MD5(A,x) = MD5(B,y). You're not going to be happy if you digitally sign this document: I agree to sell my car to Bob for US$10,000.00 cPRo7eH9Lk++Z5Q/fb+tS And then I drag you into court claiming that you've signed this one (which has the same MD5 hash) instead: I agree to sell my car to Bob for US$1.00 2DUn0TIEgI+/XkPNYG6Nm Obviously, that bit of random junk at the end is going to raise your suspicions, but maybe I can hide it away somewhere (as in a hidden part of a Word document) you won't notice it. (Incidentally, this is why experts recommend you don't digitally sign a document you didn't generate, unless you make some small change to it first. That would mess up my correcting block attempt.) Other attacks are possible, too. Hash functions are supposed to be collision resistant, and cryptographic protocols assume they are. If the hash function turns out to be not so good, all kinds of mischief can happen. -bob mathews -----BEGIN PGP SIGNATURE----- iD8DBQE9rKa4PgDecCrBEpcRApTWAJ4lWLPinDtz1tRAzvCLOlUrqZp0bQCfWrTx DQ7e49FTtlVHQyYjtpdnbnE= =CF+G -----END PGP SIGNATURE-----
This archive was generated by hypermail 2b30 : Wed Oct 16 2002 - 11:45:07 PDT