Universal hashing and attacks

The O(1) average in lessons 2 and 3 assumed the keys spread out. When the keys come from strangers, someone can choose them to collide. Then a hash table becomes very slow. This lesson shows the attack and the defence: choose the hash function at random.

Keys chosen against you

Any fixed hash function has bad sets of keys. With m buckets and many possible keys, some bucket receives at least a share 1/m of all possible keys. Anyone who knows the function can pick n keys from that bucket. Then all n keys share one chain, and inserting them costs 1 + 2 + … + n steps, which is O(n²).

This is a real attack, called hash flooding. A web server stores the fields of each request in a hash table. In 2011, researchers showed that one request with about 100,000 carefully chosen field names could keep a server busy for minutes. PHP, Java, Ruby and Python were all affected. An attack that makes a program slow, rather than wrong, is called a denial of service: real users cannot get served.

Choosing the function at random

The attacker needs to know the hash function in advance. So the table picks its function at random when it is created, from a large family of functions. The attacker can still see the code, and so the family, but not which member was picked. Compare a fixed function with a random one on the attacker’s keys:

A family of hash functions is called universal if, for any two different keys x and y, a function picked at random from the family makes them collide with chance at most 1/m. That is the same chance as if each key were thrown into a random bucket.

The family in the figure is a classic one, found by Carter and Wegman in 1979. Pick a prime number p bigger than every key. Then pick two random whole numbers: a from 1 to p − 1, and b from 0 to p − 1. The function is

h(k) = ((a * k + b) % p) % m

Why does universality help? Take any key x. Each of the other n − 1 keys collides with x with chance at most 1/m. Adding up these chances, x’s chain is expected to hold at most 1 + (n − 1)/m keys, which is less than 1 + α. This holds for every set of keys, even keys chosen by an attacker. The average is now over the table’s random choice, which the attacker cannot control.

Why collisions stay rare

Here is why the Carter and Wegman family is universal. Take two different keys x and y, both less than p. Before the final % m, they become

r = (a*x + b) % p
s = (a*y + b) % p

The argument has three steps.

1. r and s are different. Their difference is a·(x − y), taken % p. Neither a nor x − y is a multiple of the prime p, so their product is not a multiple of p either. (This is where p being prime matters.) So r ≠ s.
2. Every pair (r, s) with r ≠ s is equally likely. There are p(p − 1) choices of (a, b), and exactly p(p − 1) pairs (r, s) with r ≠ s. Given r and s, the two lines above can be solved for exactly one a and one b. So each choice of (a, b) gives a different pair, and each pair comes from exactly one choice. Picking (a, b) at random therefore picks (r, s) at random.
3. Few pairs collide after % m. Fix r. The keys collide when s % m = r % m. Among the p − 1 values s can take, at most (p − 1)/m share r’s remainder. So the chance is at most ((p − 1)/m) / (p − 1) = 1/m.

Hashing a key now costs one multiplication, one addition and two remainders: still O(1). Strings and other long keys use related families that read the key once, in O(L) for length L.

What Python does

Python took this path after the 2011 attack. For str and bytes, the hash uses a function called SipHash with a secret random key chosen each time Python starts. That is why hash('cat') differs between runs (lesson 1). The environment variable PYTHONHASHSEED can fix the key, for example to make a test repeatable.

Whole numbers are not protected. On a 64-bit computer, hash(k) is the remainder of k after dividing by 2⁶¹ − 1 (61 twos multiplied together, minus 1), with no randomness at all:

import sys
sys.hash_info.modulus           # 2305843009213693951, that is 2**61 - 1
hash(2**61 - 1)                 # 0
hash(2 * (2**61 - 1))           # 0 as well

(The practice pages run Python inside the browser as a 32-bit program. There the number is 2³¹ − 1 instead.)

So a dict filled with many multiples of 2⁶¹ − 1 puts every key on the same probe sequence, and each insert costs O(n). If a program builds a dict from whole numbers sent by strangers, it should limit how many it accepts, or turn them into strings first.