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

[Donovan Baarda]

On Thu, 2004-04-08 at 12:36, Martin Pool wrote:
> On  5 Apr 2004, Donovan Baarda <abo at minkirri.apana.org.au> wrote:
> 
> > librsync needs a whole file checksum. Without it, it silently fails for
> > case 1), 3), and 4).
> 
> Yes, a whole-file checksum should be used with it.  Presumably
> something stronger than md4 like SHA-1.

md4 is probably good enough for most applications. I know it's not as
secure as others, but when you take into account the requirement that
the signature match as well, compromising it becomes much more
complicated.

> I think the only question is whether this should be done internally in
> librsync, or as a separate process.  I can see arguments either way.  
>
> In some cases you might prefer to actually store an signed signature
> using something like GPG.

Yeah... good point. The rdiff program should probably use a whole file
md4sum though.
 
> > librsync could benefit from a random checksum_seed. It would need to be
> > included in the signature. Without it librsync is vulnerable to cases 1)
> > and 3).
> 
> Random with respect to what?  I think it would be nice if repeatedly
> summing identicaly files gave identical signatures.  Maybe it can vary
> depending on only the input data...

The problem is repeatability is what makes it vulnerable. If the content
fully determines the signature, the content can be crafted to produce a
particular signature. It is relatively easy to calculate two different
blocks with the same blocksum if the checksum_seed is known.

librsync could be modified to detect when two blocks had the same
blocksum in a signature, and permutate the checksum seed in a
deterministic way to try repeatedly until a signature without collisions
is found. This would give repeatable signatures and protect against case
1), but not case 3). It would also allow crafted files that force m/2
recalculations of the signature.

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. You can't manipulate individual
blocks without it affecting every other blocksum, but the signature for
the same file is always the same. Nice :-)

This would fit in nicely with adding a whole-file checksum to the
signature... generate the wholefile md4sum, and use that as the starting
"seed" for the individual blocksums. The wholefile sum becomes the seed.

This doesn't allow for "permutating" the seed if it happens to result in
blocksum clashes. However, given that the probability if this happening
is pretty astronomical (when using the wholefile sum seed) and will be
caught by a whole-file checksum miss-match, do we care? It is far more
likely to get false block matches when calculating the delta (because
sums are calculated at every byte boundary, not just at block
boundaries).

More thoughts on using the wholefile sum as the seed; at first I thought
this would still be vulnerable to case 3). Using a any single block as
the original file and trying to find any block that matches means you
still have "birthday algorithm" numbers of blocks to check (ie 2^(n/2)).
However, each block "comparison" requires the recalculation of the
"target" blocksum using the "original" blocksum as the seed, resulting
in non-birthday algorithm number of checksum calculations (ie, 2^n).

I've Cc'd this to the rsync list because they might get some ideas from
it.

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