A hash-based DOS attack on Btrfs

Posted Dec 14, 2012 2:13 UTC (Fri) by cyanit (guest, #86671)
In reply to: A hash-based DOS attack on Btrfs by wahern
Parent article: A hash-based DoS attack on Btrfs

But the key setup only needs to be done at filesystem mount time; that said, I have no idea how AES-NI accelerated AES-CBC compares to SipHash in practice.

A hash-based DOS attack on Btrfs

Posted Dec 14, 2012 2:54 UTC (Fri) by cyanit (guest, #86671) [Link] (6 responses)

So, AES-128 takes 80 cycles of latency on Sandy Bridge with AES-NI for each 16 byte block vs SipHash's claim of 134 cycles per 16 bytes on the best 64-bit CPU they give data for.

However, if other instructions can be scheduled by the out-of-order CPU in the meantime, then AES should be much faster, since the reciprocal throughput is actually 10 cycles on Sandy Bridge and should only take up one execution unit.

Without AES instructions things are most likely reversed.

A hash-based DOS attack on Btrfs

Posted Dec 14, 2012 11:23 UTC (Fri) by daniel (guest, #3181) [Link] (4 responses)

A few tens of nanoseconds in either case. That is spectacularly good performance. I'll take a hash designed by a hash expert any day over a cheap hack or something I rolled myself that seems to pass my tests. Been there, wish I'd had Siphash then. Using CRC for the hash was just a bad idea, Chris must have been having a bad day that day. Best time to fix it is now, it only gets harder later.

A hash-based DOS attack on Btrfs

Posted Dec 14, 2012 15:27 UTC (Fri) by drag (guest, #31333) [Link] (3 responses)

BTRFS folks responded that supporting other hashing algorithms is on their list of patches to apply.

A hash-based DOS attack on Btrfs

Posted Dec 15, 2012 2:11 UTC (Sat) by daniel (guest, #3181) [Link] (2 responses)

Anyway, it is apparent that issue is not merely a linear increase in directory operation time, but a for-real bug that looks like some kind of live-lock. The hash can and should be fixed, because although the attack in question turned out to achieve something other than its original intent, there is no question that trivially being able to force hash collisions is a vulnerability.

The most important result here is not the inappropriateness of CRC as a hash, but that Btrfs is a complex beast, still in development, a critical bug was just exposed, and likely a few more remain. Given wide enough testing and continued developer commitment it will become stable, but today it is not. From where I sit, it looks like Ext4 will be wearing its standard Linux filesystem crown for some time yet.

A hash-based DOS attack on Btrfs

Posted Dec 15, 2012 6:17 UTC (Sat) by SEJeff (guest, #51588) [Link]

Unless tux3 matured first *poke*

A hash-based DOS attack on Btrfs

Posted Dec 15, 2012 13:18 UTC (Sat) by vonbrand (subscriber, #4458) [Link]

From a cursory look over, I'd say 220 *minutes* isn't just a bad hash degenerating to a linear search...

A hash-based DOS attack on Btrfs

Posted Dec 15, 2012 2:46 UTC (Sat) by wahern (subscriber, #37304) [Link]

But AES-NI isn't the complete algorithm. Siphash numbers are for the complete operation, including compression and output. You could probably cobble something basic together with the internal AES mixer (what AES-NI optimizes), but then you've just invented your own algorithm with unknown characteristics, all in an attempt to gain negligible performance improvements. That sort of premature optimization is what causes these sorts of bugs in the first place.