[librsync-devel] librsync and rsync vulnerability to maliciously crafted data. was Re: MD4 checksum_seed

[Donovan Baarda]

G'day,
From: "Wayne Davison" <wayned at samba.org>
> On Thu, Apr 08, 2004 at 03:50:48PM +1000, Donovan Baarda wrote:
> > I think I've just realised what you were getting at; if the
> > checksum_seed is based on something like the whole file md4sum, it
> > becomes repeatable, but unpredictable.
>
> Not so.  Copy the file once, and you'd get all the data you'd need to
> create a new local file using a known-signature attack (as long as the
> input file didn't change, and that's easy to predict for many files).

I think between Eran Tromer and myself we have shown that for an md4
blocksum with 'n' bits and a file with 2^m blocks, you will have to try
2^(n-m) blocks to find a match to a known signature. For librsync's 64 bit
strong_sum, even a 4G file will need 2^43 attempts, which is sufficiently
hard. Sure, you have all the data you need, but that doesn't make it easy
:-)

Assuming no md4sum exploits are used...

> I also don't like the doubling of the I/O-cost on the sending side, so
> I don't think this is a good way to go.

I agree... a random seed gives as good or better protection without the
"double parse" for the signature.

However, it does mean you don't get the same signature for the same data.
Perhaps there are some other ways to make the signature repeatable without
requiring a double parse?

Is using the md4sum of the first block only as a seed secure enough? I don't
think it is. I think any non-random signature seed needs to take into
account the whole file for it to be secure, otherwise it reduces to the
birthday algorithm for crafting clashes.

----------------------------------------------------------------
Donovan Baarda                http://minkirri.apana.org.au/~abo/
----------------------------------------------------------------