does using an HMAC protect against hash table DoS attacks?

Question

For a hash set where the values are supplied by a third party, one concern is that an attacker can run a denial of service attack by creating many values that all fall into one bucket of the hash table, causing accesses to take linear time instead of amortized constant time and overloading the system. (Since it’s a set, let’s assume that exact data matches are not stored, so you can’t fill the bucket just by writing the same value many times.) What’s the best defense against this type of attack?

Using a cryptographic hash helps because it makes it hard to generate values that have specific hashes — but if there are N buckets and N is not super large, simply generating random data will still produce a hit approximately once every N tries. So if an attacker knows (or can guess) your hash function, they could still attack your system fairly easily by precomputing a bunch of colliding values and then uploading just those values.

It seems like an HMAC / some other kind of keyed hash would be a good way to prevent an attacker from knowing what bucket their data will end up in, but will it also cause values which hashed to the same bucket using the original hash function to be distributed evenly (seemingly randomly) across buckets?

Also, if that works, I was wondering if an HMAC is necessary, or if using some other hash method that uses a secret (for instance using the keyed versions of the BLAKE2/3 hash family) would work just as well.

Answer 1

but if there are N buckets and N is not super large, simply generating random data will still produce a hit approximately once every N tries.

Changing the hash function won't change this fact. There should be other mitigations to a user adding a bunch of random data, such as rate limiting or changing your data structure.

How do you plan on obtaining the key for the HMAC? If it's the same for everything, then hash collisions in the underlying hash function translate to hmac collisions. If it's derived from the data, then the attacker's job is just marginally more difficult; they have to effectively compute three hashes per calculation (one for the key derivation, two for the hmac) instead of one. If it's random, how will you be able to retrieve data from the table?

As you mention in the comments, we don't care about hash collisions but rather hash collisions mod N. In this scenario, an HMAC would sufficiently stop an attacker from being able to calculate data that would hash to the same bucket. If the HMAC construction is too expensive for your application, you can use something like SipHash.