Re: Hashes,File protection,etc

[Bob Mathews <bobmath () earthlink net>]

-----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-----