How to explain Hash DoS to your parents by using cats

[Nytro]

How to explain Hash DoS to your parents by using cats

Published December 20th, 2012 by Barney Desmond 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:

Assume, for the sake of argument, that you moved into larger premises very quickly.

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:

Phew, it’s a good thing you invested in a rapidly reconfigurable walling system!

Meltdown

Real mayhem arrives in the afternoon: evil employees from Kitty Kare return and ask to pick up ALL the cats. One by one.

Placing a cat in the room takes a roughly-fixed amount of time, called constant time when dealing with algorithms, mathematically written as O(1).

Finding a particular cat means going to the room and checking all the cats there. The more cats there are, the longer it takes. This is called linear time, written as O(n).

On average, your staff have to search about 4,500 cats (half of all the cats in the room) before they happen to find the right one. Things get better as some of the cats are returned to their (evil) owners, but it’s a bad situation for a long time. Your genuine customers are quite angry and upset, and it’s well past midnight by the time you knock off and go home.

You get home that night and have dreams. Bad dreams, about being overwhelmed by cats.

You’ve just been Hash DoS’d, with cats.

Fixing those felines

In short, the answer to this problem is to use a hash function that isn’t vulnerable to this sort of attack. A cryptographic hash function is a special type of hash function that makes it difficult to create specifically-chosen collisions like the one shown here.

This won’t completely prevent the evil attacker from hammering away and trying to produce cat-names that happen to cause collisions, but it makes life a lot harder for them.

A full-blown cryptographic hash function like SHA-1 would probably be overkill for your kitty daycare centre, but it’s the right line of thinking. So long as your hash function can evenly distribute cats into rooms, all you need to worry about is having enough staff to look after them all.

Purrfect!

Sursa: How to explain Hash DoS to your parents by using cats | Anchor Web Hosting Blog