Comments (20)
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.
from librsync.
It's really nice idea but what about blake-2b? This is really brand new very strong and fast function.
from librsync.
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.
from librsync.
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!
from librsync.
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?
from librsync.
A patch would be appreciated
On Mon, Aug 4, 2014, 9:49 PM Michael Samuel [email protected]
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).
from librsync.
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.
from librsync.
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.
from librsync.
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.
from librsync.
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.
from librsync.
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" [email protected] 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).
from librsync.
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
from librsync.
I've been moving countries and changing jobs so time has been short. The
merge seems to fail, I haven't investigated yet.
from librsync.
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.
from librsync.
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.
from librsync.
sourcefrog/librsync@therealmik:blake2...blake2 has the incremental changes to add an option to select and to get the tests passing again.
from librsync.
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.
from librsync.
Yes, I think all that's needed now is
[ ] add some tests covering this mode
[ ] check the compiler warnings are harmless
[ ] update docs
[ ] release
from librsync.
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.
from librsync.
Released! https://github.com/librsync/librsync/releases/tag/v1.0.0
from librsync.
Related Issues (20)
- Migrate from Travis to GitHub Actions. HOT 1
- Supplying rdiff Base File Using Pipe Results in Illegal Seek Error in librsync HOT 8
- Generate signature from empty basis HOT 2
- Replace popt with something better supported. HOT 3
- Improve GitHub and Doxygen docs. HOT 2
- popt not found on Pop_OS Hirsute
- rsync vs network speed HOT 9
- rs_patch_file old <-> new file HOT 1
- 1) sig file -> size 0 ? 2) static/dynamic lib Windows ? HOT 6
- Runtime error when linking to rsync MSVC compiled with MT or MTd ? HOT 2
- Determine delta size before generation (streaming api) HOT 2
- build 2.3.2 with msvs 2019 failed HOT 2
- [Feature Request] Implement FastCDC? HOT 7
- Request: Add windows build to stable release HOT 2
- v2.3.3 tests are failing only on s390x HOT 4
- rdiff v2.3.4 I/O error on Linux Mint HOT 6
- rdiff v2.3.4 popt.dll error on Windows HOT 10
- Suggestion: have static binary for windows users HOT 2
- Migration to GitHub is not complete HOT 1
- Support for MacOS universal2 architecture ? HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from librsync.