Hash Flooding

October 10, 2026

This week, I spent some time making performance optimizations for Serverpod CLI's code generator. The framework allows you to define models in YAML, and define endpoints and future calls in Dart classes. The CLI takes those definitions and generates type safe Dart interfaces that you can use in your client and server code.

In the case of an endpoint defined like so:

import 'package:serverpod/serverpod.dart';

class ExampleEndpoint extends Endpoint {
  Future<String> hello(Session session, String name) async {
    return 'Hello $name';
  }
}

running serverpod generate spits out a type safe interface that allows you to send requests to your server through a method call.

var result = await client.example.hello('World');

The generator does this by:

analyzing your project's source files,
creating definitions for objects we need to generate,
collecting information like class name, methods, parameters, annotations, comments, etc,
and then generating typed interfaces that you can call safely.

As your project grows, the generator can spend more time making unnecessary rounds of analysis and code generation on file saves/deletions. So it needs to be smart with file change events and decide early (and correctly) to proceed to generation or not, for all of the changed files or for a subset.

One way it achieves this is with fingerprinting and stamping after generation runs so that it can detect when the filesystem is unchanged for an early exit.

But you can also change your definitions in a lot of interesting ways. If you define a type alias in a separate file, import that in your endpoint file and use it as a parameter, the generator needs to know to regenerate your endpoint interface when that alias definition is modified even though it comes from a different file than the one containing the actual endpoint definition. Same thing goes for documentation comments defined using @template and @macro markers.

In this case, the generator needs to only regenerate the file that has changed and not your entire project.

I reached for FNV1a hash functions for this problem set. The analyzer builds a rich definition of objects we care about. Taking a cheap hash on that allows the generator to make quick comparisons between different runs and decide to bail or generate code.

While I was researching about FNV1a, I learnt about its susceptibility to hash flooding. This note details my attempt at simulating hash flooding with my own hash table implementation.

Hash flooding attacks exploit hash collisions to get your server to perform severely slow lookups causing denial of service. You typically reach for hash tables (or hash maps) for lookup speed. This attack turns what is supposed to be fast into a resource depleter.

I have implemented hash tables with open and closed addressing strategies for handling collisions so I have a prime environment to simulate this. My implementations use a very terrible hash function. For this exercise, I will introduce FNV1a hash function to confirm what I read. And then attempt to prevent this attack with a slightly modified version of the same function.

The FNV1a hash algorithm iteratively XORs the input with a base offset and multiplies with a large prime number.

int fnv1aHash(Object input) {
  const _prime = 0x00000100000001b3;
  int value = 0xcbf29ce484222325;

  for (final unit in input.toString().codeUnits) {
    value = (value ^ unit) * _prime;
  }

  return value;
}

I will not dump the hash table implementation code here. You can find it through the link at the end of this note. I am using an implementation with closed addressing.

For the server, I set up a simple one that speaks JSON-RPC. Server starts on a port, client connects and sends JSON messages. The messages are either a POST to cache users or a GET to retrieve users.

final server = Server(port: 8080);
await server.start();

final client = Client(port: 8080);
await client.connect();

The user model is simple:

{"name": String, "age": int}

POST carries a body containing all of the users to be cached. The cache is keyed by the user name. GET carries a body containing all of the user names to look up.

The simulation begins by finding 100000 keys that will generate the same hash value when passed to the FNV1a function. Brute force is employed here. The idea is to pick a hash value, then iteratively call the hash function with random inputs and collect the ones that produce that hash value.

List<String> findCollisions(
  int bucketSize,
  int numberOfCollisions,
  int Function(Object) hashFunction,
) {
  final collisions = <String>[];
  int i = 0;

  while (collisions.length < numberOfCollisions) {
    final hashValue = hashFunction(i) % bucketSize;
    if (hashValue == 0) {
      collisions.add(i.toString());
    }
    i++;
  }

  return collisions;
}

The hash function used for collision finding is the same as the one used in the hash table.

Then I fill the cache with those keys and lookup a subset.

await client.sendRequest(
    Packet(
      request: 'POST',
      body: jsonEncode(
        collisions.map((e) => User(name: e, age: random.nextInt(100))).toList(),
      ),
    ),
);

await client.sendRequest(
    Packet(request: 'GET', body: jsonEncode(collisions.take(1000).toList())),
);

I then setup a small benchmark harness that runs the simulation against the FNV1a hash function a number of times. The server response time is measured for both requests. The final output is the median time for all of the runs.

Sample size: 3
Average run time for fnv1a hash: 0:00:19.057000

19 seconds to cache 100000 records and lookup 1000 is quite slow. This shouldn't even take up to a second to complete using the default hash table implementation in Dart.

I'm running this on a Mac from 2022 with 8 processor cores and 24GB RAM running macOS Tahoe.

I have effectively simulated the attack. Now how do I avoid it? The reason this can be exploited is that your server's hash function can be made public or figured out. If you introduce a control value that only you know without changing the algorithm, you can get things under, well, control. Attackers will have to determine that value to cause a denial of service.

So I can modify the FVN1a function to take a seed. This may be rotated. An attacker with the same seed will be able to exploit the system. But with an incorrect seed, the attacker is unable to reliably find keys that will cause collisions in the first place.

int fnv1aSeededHash(int seed, Object input) {
  const _prime = 0x00000100000001b3;
  int value = 0xcbf29ce484222325;

  /// Add the seed to the mix.
  for (int i = 0; i < seed; i++) {
    value = (value ^ i) * _prime;
  }

  for (final unit in input.toString().codeUnits) {
    value = (value ^ unit) * _prime;
  }

  return value;
}

Rerunning the benchmark harness with the new seeded hash function used by the collision finder and the hash table, the results are not so different. Because in this case, the attacker knows the seed.

Sample size: 3
Average run time for seeded fnv1a hash: 0:00:18.843000

Using a different seed in the hash table than the collision finder produces the fastest result.

Sample size: 3
Average run time for seeded fnv1a hash with different seeds: 0:00:05.001000

I believe I can even get more gains by increasing the bucket size for the hash table and using a better hash function. The hash table implementation could be even more efficient. But I will stop here as I have accomplished what I set out to validate.

The Takeaway

Collisions in a hash table using closed addressing (chaining) mean that a lookup goes from O(1) to O(n), where n is the number of keys that produce the same hash. In my simulation, n is 100000. There are other approaches to handling this. Java uses a red-black tree to get O(logn) lookups through binary search.

The full benchmark code and hash table implementation used can be found here.