At lunch today, I told Eric about Hash Attacks: for many hash functions, it’s possible to construct a large set of keys that collide. This can be used to cause a Denial of Service as hashtable operations can be induced to take O(n) time instead of O(1).

Crosby and Wallach suc­cess­ful­ly demon­strat­ed this against a number of ap­pli­ca­tions.

Andrew has a good writeup of Hash Algorithm Attacks.

There are various mit­i­ga­tions suggested. The one that I used when I first became aware of this problem is to use a salt to the hash function.

In other words, change:

unsigned hash(const char* s)
{
    unsigned h = 0;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

to:

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

where salt is chosen randomly when the hash table is created or when the process starts. This should be enough to vary the order in which keys are dis­trib­uted to buckets from run to run.