-
Notifications
You must be signed in to change notification settings - Fork 143
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
SECURITY: MD4 collision/preimage attacks (CVE-2014-8242) #5
Comments
Thanks for raising this. The attack is a little harder than you describe because there's also a hash Possibly for this situation, or maybe even by default, we should switch to |
It's really nice idea but what about blake-2b? This is really brand new very strong and fast function. |
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:
The delta file format doesn't need changing. |
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! |
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? |
A patch would be appreciated On Mon, Aug 4, 2014, 9:49 PM Michael Samuel notifications@github.com
|
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 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. |
Thanks for the patch. It seems like the big question is how to manage the |
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. |
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. |
Not yet, I've had a lot on, but I should be able to this weekend.
|
Any news folks? :) There are bunch of tools which used librsync and ignore security issues like DropBox: |
I've been moving countries and changing jobs so time has been short. The |
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 |
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. |
sourcefrog/librsync@therealmik:blake2...blake2 has the incremental changes to add an option to select and to get the tests passing again. |
Hello Martin, I see that the patches to fix this issue have been merged in your branch, not upstream yet. Could a new release 1.0.0 be expected in the near future? Thank you. |
Yes, I think all that's needed now is [ ] add some tests covering this mode |
Hi librsync fans, https://github.com/librsync/librsync now has the BLAKE2 algorithm by default, with options in the API and command line to go back to md4 for compatibility. Please give it a shake, and if no problems are found I'll make a 1.0 release. |
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.
The text was updated successfully, but these errors were encountered: