Hash functions part 2 – security

In part 1, we built a phone directory using a hash table. We used a deliberately weak hash function, resolved collisions by comparing names, and saw why a matching hash does not prove equality.

Now suppose anyone can submit names to our directory over the network. An attacker can choose names specifically to make the table slow. The directory might still return the correct phone number, but spend so much time searching that it cannot serve other users.

This is hash flooding. Understanding it requires separating two kinds of collision and asking what the attacker can predict.

01Hash collisions and bucket collisions#

A hash collision occurs when two distinct inputs produce the same hash value:

a != b
h(a) == h(b)

For arbitrary-length inputs and a fixed-size output, collisions are unavoidable. There are more possible inputs than outputs. A cryptographic hash aims to make finding collisions computationally infeasible; it does not eliminate them.

A bucket collision occurs when two inputs map to the same bucket. Their full hash values can be different. With eight buckets, our directory uses:

bucket(name) = h(name) % 8

Using SumCodeUnits from part 1, which adds the UTF-16 code units into an unsigned 32-bit value:

Bob and Dan collide in both their hash values and their buckets. Eve and Ian only collide in their buckets. Hash flooding can exploit either: the attacker needs many entries to follow the same expensive search path, not necessarily to have identical full hashes.

Collisions are therefore not automatically vulnerabilities. A correctly implemented table handles them. The security problem is allowing an attacker to concentrate enough of them to exhaust the application's resources.

02How hash flooding becomes expensive#

Consider a table that resolves bucket collisions with a linked list. If an attacker submits n distinct names that all land in one bucket, looking for a missing name in that bucket can require checking all n entries. That lookup costs O(n), rather than the expected O(1) under well-distributed input and a controlled load factor.

Insertion depends on what the table does. Adding an entry at the head of a list can be constant time, but a dictionary normally needs to check whether the key already exists. If each insertion searches the growing chain, building it requires roughly:

0 + 1 + 2 + ... + (n - 1) = n * (n - 1) / 2

That is O(n²) total work. Cached full hashes may avoid some key comparisons, but the chain still has to be traversed. Other table designs use different collision strategies, so these particular costs describe this chained-table example rather than every hash table.

The danger is amplified when a server automatically builds dictionaries from request parameters or other user-controlled fields. The attacker supplies data; the server pays the insertion cost. Python's PEP 456 documents why predictable hashing and earlier randomization attempts were insufficient protection against this class of attack. Microsoft's December 2011 ASP.NET vulnerability write-up describes how specially crafted form submissions could trigger expensive hash-table insertions and cause a denial of service.

03Predictable hashing lets attackers prepare offline#

Our sum function is particularly easy to manipulate: rearranging the letters of a name always preserves its hash. An attacker can generate many distinct permutations without searching for collisions at all.

Even without such a shortcut, a public deterministic hash lets an attacker calculate bucket indices locally. For a fixed table with m buckets and uniform output, about one candidate in m lands in a chosen bucket. The attacker can keep those candidates and submit only the ones that collide. Resizing can change bucket placement, but it does not separate inputs with identical full hashes.

Replacing the sum with a public, unkeyed cryptographic hash does not remove this opportunity. The attacker can still evaluate the hash and filter candidates by bucket.

04A seed is not necessarily a secret key#

A seeded function takes an extra parameter that changes its output. This can help vary bucket placement, but the existence of a seed parameter says little about resistance to an attacker. A fixed public seed can be included in an offline search. A secret seed may still be too small to resist guessing, recoverable from observations, or mixed in a way that preserves collisions.

For example, adding a seed after hashing cannot separate an existing full-hash collision:

h(a) == h(b)
(h(a) + seed) mod 2^32 == (h(b) + seed) mod 2^32

Mixing a seed throughout the computation can avoid that particular weakness, but does not by itself establish cryptographic security. The distinction matters in practice: the HighwayHash authors' discussion of hash flooding links attacks that construct collisions independent of the seed for particular CityHash and MurmurHash variants. Those findings concern specific algorithms and variants, not every function with a seed parameter.

05Keyed hashing makes placement unpredictable#

A pseudorandom function (PRF) takes a secret key and an input. For someone who does not know the key, its outputs should be computationally indistinguishable from those of a random function. The same key and input still produce the same output, so the table can repeat its calculations.

SipHash was designed for short inputs and uses a secret key. In the standard SipHash-2-4 variant, the key is 128 bits and the output is 64 bits. The Linux kernel's SipHash documentation shows generating a key from a cryptographically secure random source and using the result to select a hash-table bucket. Keep the key secret and stable for the table's lifetime; changing it requires rebuilding the table's placement.

06Why reducing the hash to a bucket still works#

A table must reduce the hash to its bucket range. Conceptually, using a SipHash implementation that returns an unsigned 64-bit value:

// Conceptual API: secretKey is generated once for this table.
ulong hash = SipHash24(secretKey, nameBytes);
int bucketIndex = (int)(hash % (ulong)buckets.Length);

With four buckets, the index is between 0 and 3. Collisions are common, regardless of the hash's width. That does not make the secret key useless.

With a public hash, an attacker can predict which names share a bucket before sending them. With a suitable keyed function and an unknown random key, the same offline calculation is unavailable. A collision set prepared for one independently keyed table does not reliably concentrate entries in another.

The benefit is unpredictable placement, not collision-free placement. If the attacker cannot observe which bucket a candidate reaches, submitting more random names normally spreads them across the table instead of selecting only the troublesome ones.

There are limits. Keyed hashing raises the cost of preparing an attack; it does not guarantee constant-time operations or prevent every denial of service. The HighwayHash discussion also examines why the data structure and information exposed to the attacker matter.

07Protecting the whole operation#

For our networked directory, the hash function is one part of the defense:

• Use a table implementation with documented protection for attacker-controlled keys. Any custom hash or equality implementation must preserve the assumptions that protection relies on.
• When keyed hashing is used, generate its key securely and keep it secret. A predictable seed or a public unkeyed digest does not provide the same protection.
• Bound the work a request can trigger: the number and length of names, the total input size, and the amount of memory the directory can consume.
• Consider the collision strategy. A balanced tree within an overloaded bucket can bound search costs when keys support a suitable ordering; resizing alone cannot fix identical full hashes.

Our table still needs to compare keys for equality, just as it did in part 1. Security adds a further requirement: handling attacker-chosen inputs without allowing a small request to trigger an unreasonable amount of work.