Not logged in
Log in now
Create an account
Subscribe to LWN
LWN.net Weekly Edition for December 5, 2013
Deadline scheduling: coming soon?
LWN.net Weekly Edition for November 27, 2013
ACPI for ARM?
LWN.net Weekly Edition for November 21, 2013
This isn't a new issue, reiserfs had a similar hashing scheme. Other hashes are different, but crc32c is implemented in hardware on newer CPUs, so there is a real performance benefit here.
A hash-based DOS attack on Btrfs
Posted Dec 14, 2012 2:21 UTC (Fri) by therealmik (subscriber, #87720)
Another example would be somebody just wanting to hog a lot of in-kernel CPU time, and causing conflicts with their own filename, even though they're rate-limited by higher-level schemes (eg. server-level rate-limits).
Creating a conflict with a lock file created in the same directory is probably another example.
As a previous poster alluded, crc32c is good for detecting random corruption, not for hash tables or malicious corruption.
The CPU implementation of crc32c argument is also deeply flawed - extra tree walks are not worth the few cycles saved, as tree walks are vastly more expensive.
Remember that hash tables are only O(1) in a "perfect hash" scenario, so the hash table performance approaches what you'd expect from O(n) as the hash gets worse.
Posted Dec 14, 2012 3:30 UTC (Fri) by davidescott (guest, #58580)
Chris (if you are still monitoring the thread),
How would one go about strengthening the FS and making it more resistant to these kinds of attacks? I gather that BTRFS is capable of supporting other hashes -- what are the various options down the road? It it an option at filesystem creation time to use a more collision resistant hash? How big a hash can one use? If one had a hardware SHA-512 and wanted to waste the disk space could they? Are there ways to salt hashes using something secret in the directory structure? Could the Hash be replaced with red-black trees etc?
Given the current on disk layout where would the introduction of protections against this kind of attack introduce btrfs2?
Posted Dec 14, 2012 12:35 UTC (Fri) by masoncl (subscriber, #47138)
Salting etc are also more than possible. I personally don't think the hash makes the shared directories in any way secure, but I've been wrong many times before ;)
Posted Dec 14, 2012 16:09 UTC (Fri) by cesarb (subscriber, #6266)
But if the hash output is visible via telldir, the attacker can still find out the salt unless you are using strong crypto, which would not be very good for performance. I think the hash output is not visible via telldir on the ext* family.
You could play games like having a per-directory randomly chosen salt, but if you are getting to that point IMHO it is better to work on making the algorithms robust against degenerate edge cases.
Posted Dec 14, 2012 17:01 UTC (Fri) by davidescott (guest, #58580)
Hopefully nobody exports a "tell/read/seekdir" interface over php.
Posted Dec 14, 2012 17:35 UTC (Fri) by dakas (guest, #88146)
A CRC is not a cryptographic hash. Salting is useless, and identical prefixes have identical impact on the result.
Posted Dec 14, 2012 21:56 UTC (Fri) by masoncl (subscriber, #47138)
Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds