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.