Vulnerability Development mailing list archives
Re: Hashes,File protection,etc
From: Bob Mathews <bobmath () earthlink net>
Date: Tue, 15 Oct 2002 16:37:25 -0700
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tuesday 15 October 2002 09:27, Valdis.Kletnieks () vt edu 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-----
Current thread:
- RE: /instmsg/alias/annoying_web_logs ;), (continued)
- RE: /instmsg/alias/annoying_web_logs ;) Elan Hasson (Oct 15)
- RE: /instmsg/alias/annoying_web_logs ;) Dave Aitel (Oct 16)
- Re: /instmsg/alias/annoying_web_logs ;) zeno (Oct 16)
- Re: /instmsg/alias/annoying_web_logs ;) Chip McClure (Oct 15)
- RE: /instmsg/alias/annoying_web_logs ;) Shawn K. Hall (RA/Security) (Oct 20)
- Re: Hashes,File protection,etc Tony (Oct 15)
- Re: Hashes,File protection,etc Roland Postle (Oct 15)
- Re: Hashes,File protection,etc Valdis . Kletnieks (Oct 15)
- Re: Hashes,File protection,etc Roland Postle (Oct 16)
- Re: Hashes,File protection,etc Valdis . Kletnieks (Oct 16)
- Re: Hashes,File protection,etc Bob Mathews (Oct 16)
- Re: Hashes,File protection,etc Jose Nazario (Oct 15)
- Re: Hashes,File protection,etc Valdis . Kletnieks (Oct 15)
- RE: Hashes,File protection,etc Rich Cower (Oct 15)
- Re: Hashes,File protection,etc Eric Fritzges (Oct 15)
- Re: CROSS SITE-SCRIPTING Protection with PHP Sverre H. Huseby (Oct 14)
- Re: CROSS SITE-SCRIPTING Protection with PHP Valdis . Kletnieks (Oct 14)
- RE: CROSS SITE-SCRIPTING Protection with PHP Chris Field (Oct 12)
- Re: CROSS SITE-SCRIPTING Protection with PHP RoMaNSoFt (Oct 12)
- RE: CROSS SITE-SCRIPTING Protection with PHP Rohan Amin (Oct 12)