SECURITY: MD4 collision/preimage attacks (CVE-2014-8242)

[therealmik]

If you are syncing a mix of trusted and untrusted data (such as VM images or databases), an attacker could corrupt synced data.

The easier attack is to generate collisions of the combined MD4/rolling sum in order to corrupt the file. This attack has almost no complexity for MD4, and in general for a 64-bit hash there's a birthday attack of 2^32 complexity.

With some effort a preimage could be generated (with any 64-bit hash, this has 2^64 complexity - maybe a better attack is possible with MD4). This would allow for malicious changes in synced files.

[sourcefrog]

Thanks for raising this.

The attack is a little harder than you describe because there's also a hash
across the whole synced file. However for MD4 it may still be tractable.

Possibly for this situation, or maybe even by default, we should switch to
SHA-256.

[pavel-odintsov]

It's really nice idea but what about blake-2b? This is really brand new very strong and fast function.

[therealmik]

I did a compatible re-implementation in python before logging this ticket (mostly to make sure I wasn't FoS) - the whole file hash isn't there in librsync, and even if it had the same one as the rsync utility it would only change the attack.

SHA256 is fine - it will increase the signature size from 12 bytes to 36 bytes per block, but the trade-off is that you get very high assurance that the data you're syncing is correct. Or to put it another way - 36 bytes is the minimum size a signature needs to be to work correctly with the rsync algorithm.

With the current 64-bit hash, the birthday collisions are very likely to hit people by accident - just backing up VM images or databases.

I think what could be done is:

• Change the signature magic on new signature files, which will simply use the new hash without truncation.
• Old signatures will still be read when creating deltas, but never created. This ensures current systems (such as duplicity) using librdiff won't break, but hopefully will phase themselves out relatively fast.

The delta file format doesn't need changing.

[pavel-odintsov]

Hello!

I do some performance tests for different popular hash functions from OpenSSL (http://www.stableit.ru/2014/07/openssl-101e-fips-11-feb-2013-centos-6.html#comment-form) and I'm vote against another hash functions for default configuration because another functions very slow even on powerful Intel e5 2670v2 processors:

md4
real    0m19.018s
user    0m16.216s
sys    0m11.192s

md5
real    0m28.764s
user    0m25.793s
sys    0m12.040s

sha1
real    0m31.177s
user    0m28.992s
sys    0m11.336s

sha256
real    1m10.431s
user    1m8.714s
sys    0m10.995s

sha512
real    0m48.131s
user    0m45.186s
sys    0m12.097s

But I suggest ability to calculate hash functions in multiple threads because hashing can eat whole CPU core but there are alot of CPU on other threads. If you add ability to use multiple cores for hashing you can got X times speedup.

Thank you!

[therealmik]

I created a collision using a generic birthday attack against rdiff. This attack didn't take any special advantage of MD4, but let me more or less completely control the data I fed in.

This is a direct result of the truncated hash - 8 bytes = 64 bits. So 32 bits of space + ~32 bits of time = collision. A 256 bit hash would make this out of reach for mankind (given a strong hash function).

I'll hold off for a little while before releasing the code that does this, but probably not more than a week since others will likely be able to reproduce it in that time if they wish.

Is help required getting a patch out?

[sourcefrog]

A patch would be appreciated

On Mon, Aug 4, 2014, 9:49 PM Michael Samuel notifications@github.com
wrote:

I created a collision using a generic birthday attack against rdiff. This
attack didn't take any special advantage of MD4, but let me more or less
completely control the data I fed in.

This is a direct result of the truncated hash - 8 bytes = 64 bits. So 32
bits of space + ~32 bits of time = collision. A 256 bit hash would make
this out of reach for mankind (given a strong hash function).

I'll hold off for a little while before releasing the code that does this,
but probably not more than a week since others will likely be able to
reproduce it in that time if they wish.

Is help required getting a patch out?

—
Reply to this email directly or view it on GitHub
#5 (comment).

[therealmik]

Sorry for the delay with this. I have a branch at https://github.com/therealmik/librsync/tree/blake2 that is an initial attempt to replace md4 with blake2.

This almost certainly breaks binary compatability, but that is required anyway because of
#define RS_DEFAULT_STRONG_SUM_LEN 8 -- a birthday attack is trivial.

I have done a small amount of testing, and it seems to work - it will always create signature files with the new magic (but I've left code paths there to add legacy signature file creation), but it will read either type of signature and use it properly.

There appears to be a fair amount of dead objects in some structs - for example rs_job_t has an md4 context that isn't used AFAICT.

A review would be appreciated, but in the mean time I'll try a few tests myself before sending a PR.

[sourcefrog]

Thanks for the patch. It seems like the big question is how to manage the
migration. Perhaps if it just can't be easily accommodated in the same
format there needs to be a bump and applications must handle it
themselves.

[therealmik]

I think the best way to manage might be a library version bump. Then users of the software (eg. duplicity) will need to recompile (but probably not change any code).

My patch changes the signature file magic number - so it can read old signatures, but will always write new signatures. Delta files are unchanged.

I think this will work well enough, at-least for duplicity. I'm not sure about other librsync users.

[therealmik]

Have you had a chance to review this yet? I'd like to release more details soon, as I've been sitting on this for an uncomfortably long time.

[sourcefrog]

Not yet, I've had a lot on, but I should be able to this weekend.
On Sep 18, 2014 6:24 PM, "Michael Samuel" notifications@github.com wrote:

Have you had a chance to review this yet? I'd like to release more details
soon, as I've been sitting on this for an uncomfortably long time.

—
Reply to this email directly or view it on GitHub
#5 (comment).

[vps2fast]

Any news folks? :) There are bunch of tools which used librsync and ignore security issues like DropBox:
/Applications/Dropbox.app/Contents/Frameworks/librsync.1.0.2.dylib

[sourcefrog]

I've been moving countries and changing jobs so time has been short. The
merge seems to fail, I haven't investigated yet.

[sourcefrog]

I'm working on merging the blake2 branch, in https://github.com/sourcefrog/librsync/commits/blake2. It breaks some tests that check the signature format, which is probably just as well, because it's changing the default format.

There probably needs to be an rdiff command-line option to choose the format.

[sourcefrog]

I made some more progress towards this in https://github.com/sourcefrog/librsync/commits/blake2, to get the tests to work again and have an option for back-compatibility.