MD4 bug in rsync for lengths = 64 * n
craig at atheros.com
Sun Aug 4 13:22:02 EST 2002
I am the author of BackupPC (http://backuppc.sourceforge.net) and
I am working on adding rsync support to BackupPC.
I am implementing the server-side in perl, and the client will
run vanilla rsync. (BTW, is there the protocol documented? I've
answered all my questions by looking at the source, but it would
be great to check against any docs.)
I started with librsync 0.9.3 and the Intermezzo perl interface to
librsync written by Shirish Phatak. However, as I'm sure is well-known,
the Adler crc32 and MD4 computed by librsync don't match those in
After swapping the crc32 endianess, changing RS_CHAR_OFFSET from 31 to
0, and adding rsync's checksum_seed to librsync's MD4 they now agree,
except in one case: when the total data length (including the 4 byte
checksum_seed) is a multiple of 64, the MD4 checksums in librsync and
rsync don't agree. After reviewing the code in librsync, rsync and the
original RSA implementation, I believe the bug is in rsync. It doesn't
call mdfour_tail() when the last fragment is empty. Unfortunately
this happens in the particularly common case of 700 + 4 = 64 * 11.
The same bug occurs in both the block MD4s and the entire-file MD4.
The bug is benign in the sense that it is on both sides so rsync works
correctly. But it is possible (I am certainly not a crypto expert) that
missing the trailing block (that includes the bit length) substantially
weakens the computed MD4.
The fix is easy: a couple of ">" checks should be ">=". I can send
diffs if you want. But of course this can't be rolled in unless it
is coupled with a bump in the protocol version. I saw some earlier
email about fixing MD4 to handle files >= 512MB (I presume this
relates to the 64-bit bit count in the final block). Perhaps this
change can be made at the same time?
More information about the rsync