Hash tables: attack and defense

The calculator from the last chapter needed named variables, and the chapter ended with a question: how does a dictionary find a name among a million in a single operation? That it can, we saw in Chapter 13: a lookup in a set of a million elements takes as long as in a set of ten thousand, a few hundredths of a microsecond. But here is an experiment that doesn’t fit that picture. Two lists of distinct integers, both the same length. We build a set from each and time it.

The numbers in the second list are distinct too, there are as many of them, the operation is the same, and yet that set takes thousands of times longer to build. Twice as many numbers cost four times as much time, which is how the quadratic programs of Chapter 13 behave. So “one operation” is not guaranteed. To see when it holds and when it doesn’t, we need to know how a set finds an element.

There is a hint in Chapter 14. An array hands over a cell by its number in a single step: the address is the start plus the number times eight, and the millionth cell is as close as the first. If we could turn the key itself (a name, a word, a number, a tuple) into a cell number, a lookup by key would be as fast as reading by index.

The chapter is set up as a match. First the defense builds such a card index. Then the attack looks for a weak spot in it and finds one: this is how, in December 2011, speakers on a stage in Berlin showed that a single request could tie up a server for tens of minutes. Then the defense patches the hole. Three rounds, and by the end of the second we will have solved the puzzle of the two sets.

IBM, January 1953. Luhn’s memo

Round 1. Defense: numbered drawers

Luhn’s idea goes like this. Set up $m$ drawers numbered from $0$ to $m - 1$: an ordinary list, where a cell is found by its number instantly. Come up with a function that makes an integer out of a key, and put the record in the drawer numbered “that integer modulo $m$.” To find the record, compute the same number and look in that one drawer only.

A function that turns a key into a number is called a hash function, and the number itself is the key’s hash. The list of drawers together with the rule for filling them is a hash table, and the drawers themselves are usually called buckets. Here is our first card index. Its hash function is the simplest one imaginable for a word: the sum of the codes of its letters. A letter’s code comes from the function ord: for “a” it is 97, for “b” 98.

Six heroes went into eight buckets, but not one to a bucket: Natasha shares bucket 0 with Kutuzov. Two different keys that land in the same bucket make a collision. Our card index copes with it the way Luhn proposed: a bucket holds a list of records, and get goes through it, comparing keys. This method is called chaining. Going through the list does no harm while the chains are short. Trouble starts if one of them grows long.

In the last loop, enumerate(buckets) hands out “number, item” pairs, so we don’t have to keep a counter by hand. Play with the card index yourself: type in keys, switch hash functions and see where the keys fall.

Round 1. Attack: namesakes

The attack doesn’t even have to try: the weak spot is visible in the card index itself. Type “listen”, “silent” and “enlist” into it. The sum of codes doesn’t depend on the order of the letters, so all anagrams (we collected them for a crossword in Chapter 8) land in the same bucket. What that means for a whole novel we can check like this: spread the vocabulary of War and Peace, 20,478 distinct words, over 65,536 buckets with five different hash functions, and count how many buckets are used, how long the longest chain is, and how many comparisons a word lookup costs on average.

The table reads like the report of a rout. Word length uses 26 buckets out of sixty-five thousand: the book has no other lengths. The longest chain holds 3,069 words, and a lookup costs more than a thousand comparisons on average, worse than a sorted list. The first letter does little better: nearly six hundred comparisons. The sum of codes looks more respectable but fails as well. A word of five to eight lowercase letters has a sum between 5 × 97 = 485 and 8 × 122 = 976, a narrow strip, and anagrams coincide outright, so only 2,415 buckets are in use. Chains reach 78 words, and a lookup costs fifteen comparisons.

The last two lines are another world. The poly31 function multiplies the running hash by 31 and adds the code of the next letter, which is how Java computes the hash of a string. The multiplications spread the letters over different “digits,” so “listen” and “silent” get different hashes, and neighboring words get distant ones. It is the same Horner’s method that evaluates a polynomial: the hash is the value of a polynomial whose coefficients are the letters, at the point 31. Taking the remainder modulo $2^{32}$ keeps the number within 32 bits, as in Java. Python’s built-in hash does no worse, though it works differently; we will come back to it in the third round.

What a lookup costs

What does “scatter as if drawn by lot” mean, and why does it make lookups fast? Let the table have $m$ buckets and $n$ keys. The ratio $\alpha = n/m$ is called the load factor: it is the average number of keys per bucket. In the table above, $\alpha = 20\,478 / 65\,536 \approx 0.31$.

For War and Peace the theorem promises $1 + 0.31/2 \approx 1.2$ comparisons, and that is what poly31 and hash got. The theorem also names the condition for speed: the time of a lookup is set by $\alpha$, not by $n$. Keep $\alpha$ bounded, and a lookup costs $O(1)$ however many records there are. So when the keys multiply, the buckets must multiply too.

Round 1. Defense: moving day

A card index with eight buckets will serve six heroes forever and is hopeless for a million phone subscribers: at $\alpha = 125\,000$ a lookup turns into a search through everything. The cure is familiar from Chapter 14: when it gets crowded, move somewhere bigger, twice as big, say. But a hash table has a harder time moving than a list does. The bucket number is the hash modulo $m$, and when $m$ changes, the numbers change too. A record that sat in bucket 3 of eight may end up in bucket 11 of sixteen. So in a move every record is placed anew. We will wrap the card index in a class and set it against eight buckets forever.

Eight buckets forever is the square again: four times the keys, and each key about four times slower. With moving, the price of a key stays nearly level: 256 times more keys, and each costs only a few times as much. That growth toward the end comes from memory: a big table no longer fits in the processor’s fast cache, which is the subject of Chapter 34. In Chapter 14 we proved with coins why the rare moves don’t spoil the average price: when the table doubles, every insertion sets aside a couple of coins in advance for the next re-placement, and an insertion costs $O(1)$ amortized. Tick the “grow” box in the card index above and keep adding keys: at every move you will see the records scatter into new buckets.

No chains: open addressing

Python’s dictionary and set work differently: they follow Amdahl’s idea. They have no chains: each cell of the table holds at most one record. If its cell is taken, a record looks for another one along a fixed route, and a lookup follows the same route until it finds the key or an empty cell. This is called open addressing. We will take the microscope from Chapter 14 and watch how Python lays numbers out in the table of a set. The hash of a small integer is the number itself, so the number $x$ in a table of eight cells wants cell $x \bmod 8$.

The three and the five took their own places. Eleven wants cell 3 too, but it is taken, and 11 ended up in cell 0. Nineteen found both 3 and 0 taken and settled in 1. The route here goes from cell $i$ to cell $5i + 1$ modulo the size of the table, adjusted by the high bits of the hash (for small numbers these are zeros; in big tables the set also checks a few neighboring cells first). From three you get $16 \bmod 8 = 0$, from zero 1, and then 6, 7, 4, 5, 2: the route visits all eight cells before it repeats. In the card index above, the “open addressing” switch shows Amdahl’s simplest route: the next cell, then the one after that.

Open addressing has a price of its own: in an almost full table the routes grow long, since free places are few. That is why Python’s dictionary moves sooner than our card index, as soon as two thirds of the cells are taken. A table of 8 cells holds five records, one of 16 holds ten, one of 32 holds twenty-one. The order of the records, which a dictionary remembers (we saw this in Chapter 8), is kept separately: the records themselves lie in an ordinary array in order of insertion, and the hash table holds only their positions in that array.

Between rounds: birthdays

While the teams swap sides, a little problem. Suppose the hash function is perfect and keys fly into buckets as if by lot. Could we make the table so big that collisions practically never happen and chains are no longer needed?

Any pair of keys can collide, and there are a lot of pairs. Among $k$ keys there are $\frac{k(k-1)}{2}$ of them, and each pair lands in the same bucket with probability $\frac1m$. So the expected number of collisions is $\frac{k(k-1)}{2m}$, and it reaches one half when $k$ is of the order of $\sqrt{m}$. The exact calculation for 365 days is done in the math course; the same formula for any $m$ shows that a collision becomes more likely than not at $k \approx 1.18\sqrt{m}$ keys. For 365 days that is 23 people; for a million buckets, 1,178 keys. Check it by experiment.

The lesson of the break is a sober one: collisions are unavoidable, and they come early. Even if the hash is a 32-bit number, with four billion possible values, among 77 thousand keys two equal hashes turn up with a probability above one half. A table has to be able to live with collisions, by chains or by routes. Its speed rests on something else: collisions are few and spread evenly. Remember that word: “evenly.” In the second round the attack will strike right at it.

Why a key can’t be a list

But first, an old debt. In Chapter 8 a dictionary refused to take a list as a key, with the error unhashable type: 'list', and in Chapter 12 a set refused the cells of the island. Now the word makes sense: “unhashable” means there is no hash to be had from it, and so no bucket to choose. Here is what the built-in function hash can do.

The hash of a small integer is the number itself. There is one exception: hash(-1) is −2, because inside CPython, which is written in C, the number −1 is reserved as a signal that “something went wrong while computing the hash.” Big numbers are taken modulo $2^{61} - 1$, so the hash of $2^{61} - 1$ is zero. The hashes of $1$, $1.0$ and True are the same: a law requires it, and without that law a dictionary couldn’t work.

It must hold because a dictionary looks for a key only in the bucket of its hash. If equal keys had different hashes, d[1.0] would look in one bucket while the record with the key 1 lay in another, and the dictionary wouldn’t find it, even though the keys are equal. That is why Python treats 1, 1.0 and True as one key: the third line of the output is a dictionary with a single entry, where the first key stayed and the value was overwritten twice. The hash of a tuple is built from the hashes of its items. The hash of a list, though, Python refuses to compute at all. It wouldn’t be hard to compute, the same way as for a tuple, say. The danger lies elsewhere, and a class of our own can show it.

Take the island cell from Chapter 12. Its equality goes by coordinates, and for dictionaries and sets to accept it, it also needs a __hash__ method. By the hash contract, that method must rely on the same fields that __eq__ compares, the pair of coordinates. The easiest way is to take the hash of a tuple of those fields.

The first lookup is good news: Cell(3, 5) inside the square brackets is a new object, but it equals the key, its hash is the same, and the dictionary finds the burrow. The second is alarming. Snowy’s burrow was stored under the cell (10, 10), and then the cell was moved. The record is still in the dictionary (the last line prints it), yet there is no way to find it. With the new key, (11, 10), the dictionary looks in a different bucket. With the old one, (10, 10), it comes to the right bucket, but the key lying there is no longer equal to it. The record is lost, though nobody deleted it.

The same would happen to a list used as a key: one append through a second label, and the record is gone. That is why the only built-in types Python makes hashable are the immutable ones: numbers, strings, tuples of hashable items, and frozenset, the frozen set. For your own classes the rule is this: if you write __eq__, write __hash__ from the same fields, and don’t change those fields while the object is sitting in a dictionary or a set. Incidentally, if you write __eq__ without __hash__, Python takes the hash away from the class on its own, and that is why the cell in Chapter 12 turned out to be unhashable.

Round 2. Attack: Berlin, 2011

The defense has built a card index where a lookup costs $1 + \alpha/2$ comparisons. But the theorem had a condition: the keys scatter over the buckets as if by lot. Keys are written by people, and some of those people are adversaries.

For poly31, the Java hash, finding keys with equal hashes is almost a school exercise. The hash of a two-letter string is $31 \cdot c_1 + c_2$, where $c_1$ and $c_2$ are the codes of the letters. Move the first letter one step forward and the second 31 steps back, and the sum stays the same. The code of “A” is 65, of “a” 97, of “B” 66:

From there Horner’s method does the work: the hash of a longer string depends on its beginning only through the hash of that beginning. So “Aa” can be swapped for “BB” anywhere in a string, and the hash won’t change. From $k$ blocks, each of them “Aa” or “BB”, you get $2^k$ different strings with one hash: eight blocks give 256 strings, twenty give more than a million. For Java, the speakers in Berlin used another pair of the same kind, “Ey” and “FZ”. Try to find a pair yourself in the forge.

Now for the attack on our card index. It is the same class as in the section on moving, only with poly31 as the hash function. We put $n$ random strings into it, and then $n$ crafted ones of the same length.

The function itertools.product runs through all the combinations: product(["Aa", "BB"], repeat=3) gives eight triples, from ("Aa", "Aa", "Aa") to ("BB", "BB", "BB"), and "".join glues each of them into a string. Ordinary keys get roughly twice as expensive with every doubling, crafted ones three to four times: they all sit in one bucket, and the $i$-th insertion looks through its $i - 1$ predecessors. This is the sum $0 + 1 + \ldots + (n-1) = \frac{n(n-1)}{2}$ from Chapter 13, the square that cost GTA Online a minute and a half of loading. Only here it was summoned on purpose. The last line estimates how long 200 thousand keys would take, as in the talk: minutes for a single request.

A running Python program has thousands of hash tables: every dictionary, every set, even the names of a module’s variables are kept in a dictionary. The lab below finds out which of them can be knocked down: the course server fills tables with ordinary and crafted keys and times them.

The built-in set can’t be taken with “Aa” and “BB”: its string hash works differently, which is the business of the third round. But now we can solve the puzzle from the start of the chapter. Python doesn’t scramble the hash of an integer: it is the remainder after division by $p = 2^{61} - 1$. That is simpler and faster, and it makes the hash contract easy to keep for 1 and 1.0. The second list in the puzzle is the numbers $0, p, 2p, 3p, \ldots$

Every number in the second list has the hash zero. All sixteen thousand want the same cell and look for a free one along the same route: the $i$-th number walks past all $i - 1$ predecessors. It is the same square as in our card index, only inside the built-in set. That is no reason to be afraid of sets, but it is worth remembering: if a program puts into a dictionary or a set whatever a stranger has sent it (numbers from a request, names of form fields, words from an email), then the stranger decides how long it runs. The simplest defense is the one PHP shipped two weeks after the talk: limit the count. Since version 5.3.9, PHP by default accepts at most a thousand fields in one request.

Round 3. Defense: salt

The attack rests on one thing: the attacker knows the hash function in advance and works out the collisions at home. So the hash function has to depend on a secret the attacker doesn’t have. Such a secret is called salt: a random number that the program picks when it starts and shows to no one. The first idea is to mix the salt in at the beginning, that is, to start the computation from the secret number instead of zero.

Salt at the start didn’t help at all: all eight crafted strings are still in one bucket, whatever the salt. And it is clear why: “Aa” and “BB” add the same amount to the hash, whatever has piled up before them. A salt that only shifts all the hashes mixes nothing. The second attempt makes a secret of the base we multiply by: instead of 31, a random number from a huge range, with the arithmetic done modulo a big prime $p$. Now “Aa” and “BB” coincide only if $65 \cdot b + 97 = 66 \cdot b + 66$, that is, if the base $b$ equals 31. With a random $b$ the eight strings have scattered into eight buckets. It can be proved that this holds for any two strings, whichever ones the attacker chooses.

For strings of 24 letters and $p = 2^{61} - 1$ that is about one chance in $10^{17}$. The attacker can send any keys at all, but without knowing the base cannot guess which of them will collide. This defense does have a gap: the adversary sees how the table behaves (in what order the server returns keys, how long it takes to answer), and from such observations it is sometimes possible to work out the secret. So in the hash functions used in practice the salt is hidden inside a function considered cryptographically strong: its outputs don’t give the secret away, even to someone who sees millions of hashes. And that is how the story of Python went.

See for yourself. Run the cell twice and compare the hashes.

The first line changes from run to run: the salt is chosen anew every time the interpreter starts. The second confirms that the sandbox runs SipHash-1-3 with 128 bits of salt. Then the cell starts four separate Python interpreters, giving each one the environment variable PYTHONHASHSEED: the subprocess module runs another program and collects its output, and sys.executable is the path to the interpreter itself. With random every run gets its own salt, so a different hash and a different order in the set. With 0 the salt is off, and the hash is the same each time. People do this when they need to reproduce a bug that depends on order.

Salt isn’t the only answer. Java took another road: in Java 8 (2014) a chain that grows too long (more than eight records) turns into a balanced search tree. Then even in the bucket where the attacker has gathered all the keys, a lookup costs about $\log n$ comparisons instead of $n$. What these trees are and why they don’t degenerate is a story for the next chapter. All in all, the defense has three lines: salt, so the adversary can’t prepare collisions; a limit, so nobody can send a million keys; and a structure whose worst case is no disaster.

Tasks

Four tasks: build a card index, break someone else’s, and twice use a ready-made one without falling into a trap. Every task has big inputs with a time limit, so checking every pair won’t pass.

What next

Time to tally the score. A hash table finds a record in $O(1)$ on average, given a decent hash function, a sensible load and salt against an adversary. But that speed was paid for with the one quality we demanded of a good hash: it scatters keys every which way. Neighboring words land in distant buckets, and the table has no order at all. A dictionary remembers only the order of insertion. Ask it something that has to do with the order of the keys themselves.

To find the words from “war” to “warm”, or the word that comes right after “napoleon” in the alphabet, the dictionary had to go through all twenty thousand keys: the hash of “war” says nothing about where “warm” is. A thousand such pairs of questions already take more than a second. A sorted list would answer quickly, but every new word would have to be inserted into its middle, shifting the tail, and that is the $O(n)$ of Chapter 14. A hash table can’t do “all the names from A to C” or “the next one in alphabetical order.” We need a structure that keeps its keys in order, searches almost as fast as a hash table, and still takes in new keys cheaply. It was invented in Moscow in 1962 by two mathematicians. It grows like a tree, and like a tree it has to be pruned. It is the subject of the next chapter.