| |||||||||||||
A hash-based DOS attack on BtrfsA hash-based DOS attack on BtrfsPosted Dec 14, 2012 2:06 UTC (Fri) by masoncl (subscriber, #47138)In reply to: A hash-based DOS attack on Btrfs by wahern Parent article: A hash-based DoS attack on Btrfs
Going back to the original example, which programs include all three of my conditions? The one example listed here already has a collision scheme included, so the program in theory can get around it.
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.
-chris
(Log in to post comments)
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 2:21 UTC (Fri) by therealmik (subscriber, #87720) [Link]
So the obvious (although contrived) example, would be a CMS where the username is prefixed to the filename (rather than put in a subdirectory).
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.
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 3:30 UTC (Fri) by davidescott (guest, #58580) [Link]
I don't think Chris Mason really needs to be reminded how hash tables work. I'll trust he is up on the theory.
Chris (if you are still monitoring the thread),
Given the current on disk layout where would the introduction of protections against this kind of attack introduce btrfs2?
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 12:35 UTC (Fri) by masoncl (subscriber, #47138) [Link]
We can easily add a different hash to the directory format. There are 64 bits available for the hash, although you're limited to 32 bits on 32 bit userland thanks to the readdir/seekdir/telldir interfaces.
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 ;)
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 16:09 UTC (Fri) by cesarb (subscriber, #6266) [Link]
I believe the ext* family uses salting (the "Directory Hash Seed" field you can see in dumpe2fs). This should be enough to make the hash unpredictable as long as the attacker does not know the seed, and the only way to know the seed should be having raw block access to the partition and reading the superblock.
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.
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 17:01 UTC (Fri) by davidescott (guest, #58580) [Link]
It might not be a bad idea to salt, even if the salt can be determined through telldir. As you pointed out anyone running local code has much more obvious methods of attack (touch "filename" instead of touch "hash_collision_with_filename"), and a per directory salt would prevent most of the remote attacks suggested in the comments.
Hopefully nobody exports a "tell/read/seekdir" interface over php.
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 17:35 UTC (Fri) by dakas (guest, #88146) [Link]
Uh, with a CRC salting a whole directory with the same salt will cause exactly the same collisions as without salt. The salt will just cause the final CRC to be XORed with a constant.
A CRC is not a cryptographic hash. Salting is useless, and identical prefixes have identical impact on the result.
A hash-based DOS attack on Btrfs Posted Dec 14, 2012 21:56 UTC (Fri) by masoncl (subscriber, #47138) [Link]
I should have made it clear that salting only makes a difference if we add an optional second hash.
|
|||||||||||||