(Go: >> BACK << -|- >> HOME <<)

Skip to content
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

Very low compression speed of optimal mode on repetitive data #12

Open
KirillKryukov opened this issue Jun 7, 2020 · 1 comment
Open

Comments

@KirillKryukov
Copy link

blzpack's "optimal" mode slows down ~ 1000 times when used for compressing repetitive data.

Posted as separate issue, because:

  1. I found how to trigger the slowdown. Just use repetitive data, e.g., a long sequence of the same byte.

  2. This can be used to construct denial-of-service attack on a system that uses BriefLZ's "optimal" mode.

Previous issue #11 was about unpredictable slowdown, this issue is about predictable and reliable slowdown on repetitive data, which can be used to attack systems depending on BriefLZ.

This chart shows compression speed of different modes of blzpack, using repetitive (mainly single byte repeat) data of varying sizes (data size shown on the x-axis):

brieflz-compression-speed

The one dropping to the bottom is the "optimal" mode.

The main issues is a combination of these factors:

  1. A user using blzpack may have no idea that this slowdown is possible.
  2. There is a tendency among compressor users to use the strongest level available, in this case "optimal".
  3. Slowdown is an order of 1000 times compared to expected speed, which is indistinguishable from being frozen (on sufficiently large data, within realistic waiting time). Hence the potential to use it as DOS attack.
  4. Slowdown happens on particularly constructed data, which is different from normally used data. Therefore the user may be unaware of the issue after testing blzpack on his data.

Some of the the possible solutions:

  1. Remove the "optimal" mode entirely.
  2. Fix the "optimal" mode to remove slowdown (though it might become not optimal anymore).
  3. Document the potential DOS-attack in the readme. (a half-measure, because users may still miss this warning).

This is not meant in any negative way, and otherwise I enjoy blzpack, so just I want to help making it safer for potential users. Thanks!

@jibsen
Copy link
Owner
jibsen commented Jun 12, 2020

Sorry about the delay.

I largely agree with your concerns about the worst-case behavior of the optimal level. But I feel it provides both an interesting data point and a useful option for off-line compression, so I would like to keep it available.

In retrospect I could have made it a separate function in the API to distinguish it more.

Fix the "optimal" mode to remove slowdown (though it might become not optimal anymore).

This is essentially what level 9 does; it is the same algorithm, but limited to avoid the worst-case behavior.

This is not meant in any negative way, and otherwise I enjoy blzpack, so just I want to help making it safer for potential users. Thanks!

I am happy you raised the issue and welcome the discussion!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants