MD4 second-preimage attack

Hi,

A year ago we discussed the strength of the MD4 hash used by rsync and
librsync, and one of the points mentioned was that only collision
attacks are known on MD4. Well, a recent paper by Wang et al [1] shows a
several second preimage attacks. First, there's an algorithm which,
given a random message and its MD4 hash, finds another message having
the same hash with probability 2^-56. Second, if the attacker can also
alter the original message (and thus its hash) slightly, he can find a
second message having the same hash with just 2^27 MD4 invocations.

Doubtless, even stronger attacks will soon be found.

MD4 (with known seed) is thus completely broken, making rsync batch mode
and librsync unsafe to use in malicious environments. Please do consider
phasing out MD4.

The fastest hash function with no interesting known attacks is SHA-256,
which is still somewhat expensive (though this can be partially
addressed by the meta-hash idea discussed on the librsync list last
July, "Re: more info on 25gig files"). SHA-1 may also be OK for a while
despite the known collision attacks, and has acceptable speed.

Also, as discussed in detail earlier: to thwart some attacks, rsync
batch mode and librsync should be fixed to use a random seed.

  Eran

[1]
http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3810&spage=1




-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=103432&bid=230486&dat=121642