Blog

We came across this interesting article recently, it’s about how an attacker can perform a denial-of-service attack by feeding perverse input to a system that uses weak hashing algorithms. This is referred to as a Hash DoS, and the specific target mentioned in the article is btrfs.

btrfs is a next-gen filesystem that’s expected to replace ext3/4 in Linux. It’s still considered experimental but is quite usable and maturing fast. This article piqued our interest because we’re using btrfs “for reals” here at Anchor.

It’s well and good to say that, but the article isn’t very exciting unless you have a background in computer science. How would you explain Hash DoS to your parents, who probably don’t have a CompSci background? This is the internet, so the answer is cats.

Welcome to Purrfect Kitty Daycare =-^_^-=

Let’s pretend that you run a daycare centre for pampered pusses. Doting owners drop their kitty off on the way to work each morning, and pick them up in the afternoon. You look after the pussies fantastically, so business is growing by leaps and bounds with more moggies every week. You can’t look after all the cats, so you hire some enthusiastic helpers.

Fast forward a few months, you now have 26 cat-minders working for you while you manage the business. Each minder has their own space to work in. To divide the work, you assign them to minders based on the cat’s name: all cats whose name begins with the letter ‘A’ go to minder no. 1, the cats whose name starts with the letter ‘B’ goes to minder no. 2, and so on.

When owners arrive to drop off or pick up their furry bundle of joy, they know exactly which room to go to! It’s super simple and does the job nicely. Your offices look something like this:

What you’ve implemented is called a hash function. It’s really basic but it does the job. As long as a cat has a name, there’s a room for it, and you always know exactly where to find a cat. When you use a hash function to distribute objects like this, each object (cat) goes into a bucket (room).

Kitty Kollisions

Your rooms don’t fill up evenly, this is to be expected. You might have a few cats in Room A (Alice, Alison, Amanda), and only one in Room X (Xerxes). Room A has what’s called a hash collision.

Finding Xerxes in the afternoon is easy, he has the whole room to himself. When Alice’s owner comes to pick her up, the attendant at the front desk has to ask what she looks like (or remember from previous visits). No big deal, we just have to check all the cats in Room A until we find Alice. It takes a couple of seconds.

Sometimes you’ll get a lot of cats in one room, maybe a dozen, but you can still work out which one you’re looking for with a little effort. You’ve got ninety-nine problems but cats ain’t one.

Moggy Mischief

A rival appears! Kitty Kare has opened up across town and is looking to put you out of business. They’ve seen how your hashing function in action and know how it works. They’re going to use it against you, because they’re evil.

First, they need cats. Lots of cats. Maybe they pick up strays off the street, or just get kittens from the internet. It doesn’t matter how, but they’ve got over nine-thousand cats.

Now they give them all names starting with “Mr” – Mr Bigglesworth, Mr Fluffles, Mr Mac, Mr Pete, Mr Lincoln, Mr MoonUnit, etc. The list is practically infinite. Each cat gets a little engraved nametag on its collar and goes on its catty way.

They bring all the cats to Purrfect Kitty Daycare. Your staff are very smart people, and manage to handle the tsunami of tabbies by moving a few walls around to make enough room. It slows them down a bit, and your customers get irate that they have to wait to drop off their cat, but they get there in the end.

Your offices now look something like this:

---

The kitty photo belongs to FoundAnimals and is licensed under Creative Commons CC-BY.