[librsync-users] MD4 second-preimage attack

[Donovan Baarda]

On Tue, 2006-02-21 at 14:58 -0800, rsync2eran at tromer.org 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 <abo at minkirri.apana.org.au>
http://minkirri.apana.org.au/~abo/