Bill Sommerfeld's Weblog

Tuesday August 17, 2004

Hash crash Interesting times for cryptographic hash functions..

On Perry Metzger's Cryptography mailing list, we find first a report of a collision found in the original (never widely used) SHA function, and then the bigger report that four researchers in China have apparently come up with a general method for attacking MD4-like hash functions. Most impressively, they say about MD4:

There are also rumors of an impending announcment of a collision in SHA-1. No word yet on whether/how these methods can be extended to SHA-256/384/512; it looks doubtful that they'll be useful against HMAC-based constructions but other uses of hash functions need closer examination.

The attacks find pairs of messages which hash to the same value -- but nobody has yet revealed the algorithms in use; this is likely a much easier problem than finding a message which hashes to a fixed value. The MD4/MD5 message pairs differ only in a few bits, while the SHA1 pairs (produced by a different research group) differ by quite a bit more -- this is likely an artifact of the more complex message schedule found in the SHA series. SHA-256 and up use an even more complex message schedule.