DDOS on Hash Tables (Self Balancing Hash Tables)

Hash Tables are widely used in server software. A malicious user can easily forge keys in the communication with the server that will result in hashes from the keys so that they will end up in the same bucket. This will force the hashtable to grow each time this bucket is filled.

In a worst case implementation, this will result in an enormous amount of empty buckets and only one full bucket. Even if the implementation is smart and will therefore only will grow the targetted bucket, the hash table will fail its use. The hash table is meant to make lookups for a key fast by distributing the pairs in buckets, this effect is gone when all pairs are located in one bucket, which will cause linear time look-ups.

One malicious user won’t be able to crash a server, but a DDOS attack with several users would be tremendously more efficient when targeting this weakness in hash tables.

A simple solution would be to randomly pick a salt for the hash function on each new instance of a hash table. Basically we prefix each key with a random salt before we hash it. The malicious user might know the hash function, but he has to guess the salt, which neglects the effect.

Additionally logic could be added to detect an unbalanced hash table and switch the salt on when the table is unbalanced.

This could also be usefull to balance hash tables when there is no malicious user, but the keys are possibly unfortunate.

Leave a Reply

Your email address will not be published.