On Tue, 2006-02-21 at 14:58 -0800, [EMAIL PROTECTED] wrote: > 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.
For the record, here it is in the SF mailarchive. http://sourceforge.net/mailarchive/forum.php?forum_id=29760&max_rows=25&style=flat&viewmonth=200404&viewday=5 If I understand correctly, provided we add random seeds for blocksums, these weaknesses would only make attack case 4) easier. > 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. Remember we only use a small part of the md4sum for the "strong blocksum", and hence are already using less than the full md4sum. We don't really need that many bits of hash for the blocksum. The important thing for the blocksum is speed. I think md4 + random seed is pretty much the best "useful hash bits per second" for blocksums. We can adjust the blocksum size to use more bits to compensate for the fact that ~20% of the bits are insecure if we want. If someone can provide detailed evidence that some other algorithm provides more useful-hash-bits/sec, taking into account the random seed, I'll be convinced :-) In any case, the first thing that will be tackled is changing to use the libmd/openssl API for hashes, which will make switching what hash we want to use painless... a configure option? > 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. The whole file checksum is the real protection against attacks, and for this I think we should use something strong, which means "enough useful hash bits to protect against attack". Remember we only calculate this once over the whole file, not once for every potential block match. > Also, as discussed in detail earlier: to thwart some attacks, rsync > batch mode and librsync should be fixed to use a random seed. [...] There are a few things I'm proposing to add to the TODO; 1) Add whole filesum checksums in the signature and delta. The signature will have the oldfile filesum, the delta will have the oldfile and newfile filesums. Applications will optionally be able to verify the oldfile filesum against the delta before applying patches, and patch will evaluate the newfile filesum and return an error if it doesn't match. 2) Add a blocksum/filesum seed in the signature and delta. This will be used as the seed for both filesums and blocksums. It will default to random when generating signatures, but can optionally be specified on the command-line. The delta and patch operations will use the seed from the corresponding signature. 3) Add variable blocksum size in the signature. An optimal blocksum size can be calculated from the filesize, blocksize, and failure probability. The blocksize can be specified on the commandline, but will default to sqrt(filesize). The blocksum size will be calculated the same as rsync. Note that for this to work with streams, the truncated md4 blocksums will not be emitted when generating the signature until the oldfile input is completely read (to get the filesize). This ties in with feature 4) 4) Add blocksum collision detection when generating the signature. This will involve keeping the whole md4 blocksums and checking that the truncated strongsum doesn't match against an existing block that has a different whole md4sum. If a collision is detected, an error will be returned. It is up to the application to do things like re-try with another seed (Note you can't retry for piped input). I'm not entirely sure about using the seed for the filesums too. It may be sufficient and convenient to use an unseeded SHA-1 or something, and the delta would not need to include the seed. However, it is a no-overhead addition that should help. -- Donovan Baarda <[EMAIL PROTECTED]> http://minkirri.apana.org.au/~abo/ -- To unsubscribe or change options: https://lists.samba.org/mailman/listinfo/rsync Before posting, read: http://www.catb.org/~esr/faqs/smart-questions.html
