librsync signature collisions/preimages

[mik]

Note: this vulnerability is already public: https://github.com/librsync/librsync/issues/5

Sending a copy to duplicity, because I found this when auditing duplicity.

The signatures generated by librsync for duplicity are md4 sums truncated to 64 bits.

Collision attacks:
  An attacker could try to get two different entries into a signature file, in case the first one to be seen will be the only one replicated in delta files.
  This has almost no complexity for md4, and even for a strong hash truncated to 8 bytes would only require approximately 2^32 hashes to be generated (birthday collision).

Second-Preimage attacks:
  An attacker could compute a hash for existing (but known) data that they want replicated elsewhere, and generate a different block that will later be replaced with the original.

The main precondition for these attacks is that attacker-controlled data needs to be written to a file then taken out of context after restore. This is probably not an issue for a majority of users, but this could have security ramifications for people backing up databases, VM images or even log files.

Replacing md4 in librsync with a 256-bit hash (blake2b is fast, sha256 is standard) would be the best option, obviously requiring a change in the signature file format (but not the delta file format - so backups could still be restored using older versions).

[mik (therealmik)]

I made an experimental branch of librsync that addresses the problems here: https://github.com/therealmik/librsync/ (branch: blake2)

Signature files created by this branch will have a different magic, but old signatures will still be readable.

I also have a pure-python (but slow) reimplementation here:
https://github.com/therealmik/pyrdiff (only the "python2" branch has blake2 support so far)

Feedback from the Duplicity project would be appreciated, as Duplicity seems to be the biggest user of librsync.