3
$\begingroup$

I'm currently building an implementation of the dynamo paper, yottastore. Imagine it as a huge, distributed, hash map.

To find the node holding a key, I use rendezvous hashing (an improvement over consistent hashing), which requires 4 hashes. In order to avoid hash flooding attacks I'm using a keyed hash function, using a key unknown to the client.

My goal would be to have the client perform the hashes instead of the server. Is there an alternative to keyed hash, so that I can defend against hash flooding attacks, but so that the client itself can perform the hashes?

If instead of a non-crypto hash like xxhash I were to use a cryptographic one, like blake, could I drop the secret key while still defending against hash flooding?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The point of using a keyed hash with a secret key (known only to the server) is to avoid the client being able to know the output of the hash for any particular input. How can you preserve that property if the client is able to determine the output of the hash itself? And, given how exceptionally fast xxhash is, why would you want to offload that to a client? $\endgroup$
    – knaccc
    Aug 30, 2022 at 18:16
  • 1
    $\begingroup$ I would say that the real goal is to avoid that a malicious user could generate arbitrary collision. But with a crypto hash, even without a key, it's very hard to generate collisions, isn't it? Even xxhash, when done 4 times in a row, can become slow. I would say that the real problem here is: how could I trust a user generated hash? I would need to verify it by rehashing. $\endgroup$
    – Mascarpone
    Aug 31, 2022 at 7:49
  • $\begingroup$ A quick web search shows that you should be able to do hundreds of millions of xxhash operations per second - are you sure you're going to have speed issues? I assume you're using the output of the hash to evenly spread files across nodes/disks. This makes finding collisions incredibly easy for the purpose of overloading one particular node/resource. $\endgroup$
    – knaccc
    Aug 31, 2022 at 23:18
  • $\begingroup$ @knaccc sorry I missed your reply. I'm also using io_uring, which allows me to do 6 million ops/s per thread on my nvme device, so hashing starts becoming expensive. But it seems there's no way around it :) $\endgroup$
    – Mascarpone
    Nov 24, 2022 at 11:00

1 Answer 1

Reset to default
1
$\begingroup$

As you mention in one of your comments, if you cannot trust the client to not make a hash flooding attempt, then you cannot trust the client to give proper hashes. The hash would have to be recomputed on the server to verify it thereby defeating the purpose of having the client compute the hash. Otherwise, the client could simply assign incorrect hashes to cause hash flooding.

Furthermore, as discussed in the Wikipedia article about SipHash:

An unkeyed hash function such as SHA is only collision-resistant if the entire output is used. If used to generate a small output, such as an index into a hash table of practical size, then no algorithm can prevent collisions; an attacker need only make as many attempts as there are possible outputs.

This is trying to say that even if you use a cryptographically secure hash function, when you reduce the set of values by taking only some of the bits or by computing a hash bucket by taking the hash modulo the number of buckets you have increased the collision probability. Thus if the attacker knows both the hash algorithm and the reduction algorithm, they need only generate random values, hash, and reduce them until a collision is found in the reduced space. This will be much easier than attempting to find a collision of the original hash function. Thus, the only way to protect against hash flooding is with a proper keyed hash function where the key is unknown to the attacker.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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