0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 should be able to get away with something lighter weight like H(key||message).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, but if they simply add a bunch of random data, then that is a normal condition that most hash tables are designed to deal with. I want to know if there’s a way to prevent them from knowing that two values they upload will hash into the same bucket. I was thinking you’d use the same key for everything, which obviously has the property that you described for exact collisions, but I’m unsure whether partial collisions (just in some low-order or high-order bits) of the original hash would translate to collisions in the HMAC. $\endgroup$ – Dan May 23 at 19:27
  • $\begingroup$ Right, of course. Hash collisions aren't the issue. Hash collisions mod N are the issue. HMAC should be sufficient for that. If an HMAC is too expensive, you can probably get away with something like H(key||message). I don't enough about the BLAKE algorithms to comment on them specifically. $\endgroup$ – Aman Grewal May 23 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.