MD4 checksum_seed

[Eran Tromer]

Hi,

On 2004/03/15 03:49, Donovan Baarda wrote:
>>Note that, above, block hash collisions are very easy to find if you
>>know checksum_seed. The rolling Fletcher checksum1 is trivially
>>defeated. To defeat the k-bit truncated MD4 checksum2, just keep
>>generate random blocks having the same checksum1 until you find two with
>>the same checksum2; by the birthday paradox it will take about 2^(k/2)
>>attempts, where usually k=16 or k=24 with J.W. Schultz's code.
> 
> I haven't really thought much about carefully crafted data to bust
> things. I didn't think the Fletcher checksum was that bad. Although I
> can see that it would be fairly trivial to craft data for collisions,
> wouldn't it be harder to craft data for a Fletcher collision _and_
> attempt to produce a checksum2 collision? 

For blocks larger than about 270 bytes, the strength added by the
Fletcher sum is close to zero -- you can obtain any Fletcher sum of your
choice, with plenty of easily manipulated degrees of freedom remaining.
Smaller blocks are a bit messier (e.g., for blocksize<=256 you can't
obtain all possibilities of the lower 16 bit of the Fletcher sum), but
still doable. So you can sample "sufficiently random" blocks all having
the same Fletcher sum (say, zero), and then the birthday paradox applies
to strong sum without any special trickery.

Just to be sure, I wrote a quick&dirty collision search code for the
rsync and librsync hashes. I used a generic collision-finding algorithm
(namely Gabriel Nivasch's multistack variant of the generalized Rho
method) to search for a truncated MD4 collision among the blocks whose
Fletcher sum is zero. It took 13ms to find a collision for the default
parameters of rsync version<2.6.0, with either checksum_seed=0
(disabled) or checksum_seed=32761 (the value fixed for batch mode). With
a 4 byte strong hash, which is the most you're likely to see with
Schultz's code, the above took 1.4 seconds. For librsync with default
parameters (8-byte strong hash), finding a collision took a couple of
hours. Here are examples of colliding pairs for each of the above case:
  http://dl.tromer.org/misc/rsync-collisions.tgz

I should stress that if you manage to insert such a pair into someone's
file, his rsyncs will become slow and his rdiffs will silently fail.
Such poisoning is very practical in many settings -- consider website
databases and user mailboxes (yes, a pure-ASCII collision can be easily
generated with a bit of extra effort). Of course, the attacker will need
some knowledge about the file format, and some care in regard to
alignment and timing. Still, not a pretty prospect.


> The 2^(k/2) attempts assumes random attempts... how does this compare
> to "crafted to bust fletcher" attempts?

Very favorably. My code performs just as one would expect for a random
function.

As you mentioned, MD4 has known weaknesses [1]; I'm not sure it's easy
to exploit them in our context, but the Fletcher checksum may indeed
make it somewhat harder to do so. Anyway, I didn't take advantage of them.


> Does checksum_seed really need to be random for the checksum2 to be
> random? I know md4 is considered vulnerable compared to md5, but does it
> have a poor distribution for a fixed seed? If it does, would it make
> sense to switch to md5 rather than randomise the seed?

checksum_seed must be random for the checksum2 to be random -- simply,
because there is no other source of randomness in the hash calculation,
and if everything is deterministic then you can find collisions in
advance and put them in the data. This doesn't have anything to do with
the cryptographic strength of MD4. But if the attacks of [1] can be
adapted to our scenario then things will become even *worse* than the
above, and this is a good reason to switch to MD5.


>>For the purpose of evaluating the
>>probability of retransmission, rsync uses s2length bytes of good hash
>>plus 4 bytes of wishful thinking, and Baarda's analysis doesn't really
>>apply.
> 
> You can still use the same formula, just don't count checksum1 in the
> "checksum size" part of it. Or depending on how much you think it's
> worth you could count it as x<32 bits worth of checksum, not the full 32
> bits.

In adversarial setting the Fletcher checksum is worthless. So to obtain
the intended 2^-10 failure probability, rsync should increase its strong
checksum by 4 bytes.

That's for rsync in normal mode, where checksum_seed is randomized. For
fixed checksum_seed (i.e., rsync in batch mode and librsync) the failure
probability in adversarial setting is 1, as demonstrated above.


A couple of related notes:

librsync really ought to include a whole-file hash, like rsync. Maybe
also an option of retransmitting the file in case of failure (where
possible). Either way, failure must be reliably detected. Beside
increasing reliability, in many cases it would allow use of smaller
block checksums. You can't just entrust integrity checking to a
subsequent invocation of md5sum or such; re-reading the files is
expensive and not always possible.

The use of CHAR_OFFSET is a pure waste of CPU cycles. It merely amounts
to adding constants to s1 and s2 (blocklen*CHAR_OFFSET and
blocklen*(blocklen+1)/2*CHAR_OFFSET, respectively). These depend only on
the block length, which you know anyway. Indeed rsync mercifully sets
CHAR_OFFSET=0 which is optimized away, but it still obfuscates the code
and the relevant comment (rsync.h lines 38-39) is wrong.

And speaking of the latter, gcc -O3 vs. -O2 gets a speedup by a factor
of 8 to 10 in rsync's get_checksum1() and librsync's rs_calc_weak_sum().
Tested with gcc 3.3.2 on i686 Xeon and Katmai. You may want to make -O3
the default.


Regards,
  Eran


[1] http://citeseer.ist.psu.edu/68442.html
    ftp://ftp.rsa.com/pub/pdfs/bulletn4.pdf
    http://www.cacr.math.uwaterloo.ca/hac/about/chap9.pdf Remark 9.50