-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Tuesday 15 October 2002 09:27, Valdis.Kletnieks_at_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-----
Received on Oct 16 2002
Intro
