Every hash function has a worst enemy

Hash functions are fundamental in computer science. They’re used in foundational data structures like sets, hash tables and Bloom filters, and in more exotic ones like HyperLogLog and cuckoo filters; they’re also used in cryptography to conceal private information.

So, what are hash functions? Well… they’re functions that map an arbitrarily large input space to a fixed size output space. That’s it.

Typically, the output space indexes an array in memory. For example, if the output space of a hash function is the integers between $0$ and $7$, then we’re dealing with an array of size $8$. More explicitly, hashing relies on two core properties:

1. Output space must have fixed size - as mentioned above, this is the key property.
2. Determinism - a given input must map to the same output, every time.

with irreversibility (unable to easily go backwards from output to input) an optional third property in the case of cryptographic hash functions. We won’t worry about irreversibility.

Sets: Under The Hood

The simplest hash based data structure is a set. A set is used for storing an unordered collection of distinct items (or “keys”). The most common set operations are inserts and lookups.

The process of inserting a key into a set goes like:

1. Map the key to a positive integer (e.g. via ASCII or UTF-8), $x$
2. Compute the hash of the integer, $h(x)$
3. The computed hash value provides the memory address to store the key.

The process of looking up a specific key goes like:

1. Map the key to a positive integer, $x$
2. Compute the hash to get the memory address, $h(x)$
3. Check if memory address contains any values

"cat", "dog", "fox" stored in slots 4, 7, 0

"dog" is in the set; "emu" is not in the set

These two operations are the core of all hash based data structures - not just sets. For instance, hash tables (aka dictionaries) work the same way except they store a value alongside each key.

Collisions & Linked Lists

Since hash functions map a large space to a smaller space, you’d be correct in thinking that there often exist multiple inputs that get mapped to the same output value. When this happens in a set, it’s called a collision - and it complicates the lookup process.

We can’t store multiple items at a single memory address because that defeats the purpose of having an address. So, what to do? Well… we can store the first item at the address, $h(x)$, and keep with it a pointer to the location of the next item. At this second address we can keep the second item and also a pointer to the third item… and so on. Does this sound familiar? It’s just a linked list which starts at address $h(x)$. Fig 3 shows two examples of a set using different hash functions. The first example only has one collision which results in a linked list of length two; the second example shows a set with a high number of collisions resulting in two long linked lists.

Ready to hash 7 keys into 8 slots

Ready to hash 7 keys into 2 slots

Long linked lists in a set are problematic because they slow inserts and lookups down significantly. Performing an insert without a collision is an $O(1)$ operation. But if the insert maps to a location with $n$ items already living there, then it will take $n$ steps to traverse the list before appending the latest item to the end. This makes inserts with a collision an $O(n)$ operation; similarly, lookups on a linked list are $O(n)$ 😬.

So what we’d like from a good hash function is one that spreads keys out evenly across the buckets (each position in the array is often called a bucket), so that collisions are rare, linked lists stay short and set operations remain $O(1)$ on average.

When collisions became an attack: HashDoS, 2011

At the 28th Chaos Communication Congress in December 2011, Alexander Klink and Julian Wälde showed that the web platforms most of the internet ran on could be tied up by a single HTTP request. The talk is Effective Denial of Service attacks against web application platforms.

The attack is the slow lookup above, made deliberate. Web frameworks load a request’s parameters into a hash table before the code ever runs. Their hash functions were fixed and public, so an attacker could work out thousands of parameter names that all land in the same bucket, and send them in one POST request. Each insert then scans the whole chain built so far: $n$ keys cost about $n^2/2$ comparisons instead of about $n$. One request could keep a server’s CPU busy for minutes, and a handful of them could take it down.

PHP, ASP.NET, Java, Python and Ruby were all affected. The weakness had been described in 2003 by Crosby and Wallach, and Perl fixed it then; most other languages hadn’t. The fix that stuck was to stop using a fixed hash function: Python, for example, has picked a random hash seed for strings every time it starts since version 3.3.

If $h$ maps a universe of keys $U$ into $m$ buckets, then some bucket must receive at least $|U|/m$ keys. Since $U$ is typically much larger than $m$, that bucket holds an enormous number of keys, and an adversary who knows the definition of $h$ can pick $n$ of them and force every operation down one $O(n)$ linked list. And this is true of every fixed $h$! No matter how well it is designed… it has a worst enemy.

Being Lucky on Purpose

We could hope real inputs are spread out uniformly 🤞. But in the real world, data is clumpy, full of patterns and even adversarial. Hence, if our implementation is to be useful, we cannot make any assumptions about the input keys. And, as we’ve just seen, no fixed $h$ can save us either.

Instead of assuming random inputs, perhaps we can make our choice of $h$ random? This is the idea behind Universal Hashing: it relocates the randomness from an area we don’t control (inputs) to an area we do (choice of $h$). Universal Hashing says that if we put together an appropriate family of hash functions then we can pick $h$ at random from this family and have mathematical guarantees about the collision rate, regardless of the input distribution (hence “universal”). This element of randomness when selecting $h$ protects us against potential adversaries who might otherwise deliberately pass in colliding keys to slow down lookups. But what makes a family of hash functions “appropriate”, and how can a hash function be random and deterministic at the same time? That’s the subject of the next post.