7
$\begingroup$

Aumasson, Bernstein and Bosslet did an excellent job demonstrating fatal weaknesses in MurmurHash and CityHash, but what about SpookyHash?

My first uneducated guess is that it would be much harder to create collisions, but not impossible.

My second uneducated guess is that it would be impossible to create the massive kind of multi-collisions required for a HashDoS. That is, an attacker could possibly create two or three messages that hash to the same value regardless of the seed, but not hundreds or thousands. And since a moderate amount of collisions are expected anyway in any hash table and cared for, the attack would fail.

Am I correct about that? If not, would it help to mix the seed repeatedly into the state, like here?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ The creator says it would be possible to create a second preimage (thus collisions, and perhaps many): "When NOT to use (SpookyHash): if you have an opponent. This is not cryptographic. Given a message, a resourceful opponent could write a tool that would produce a modified message with the same hash as the original message". In general, to guard against DoS attacks in a hash table application, it can help to use a secret, random seed or prefix chosen at initialization of the table; it is not perfect, though: there might be e.g. timing attacks able to detect collisions, and then find new ones. $\endgroup$ – fgrieu♦ Mar 27 '13 at 8:13
  • 1
    $\begingroup$ @fgrieu: Yes, the DoS attack is explained nicely here. If one can create second preimages with a probability of one regardless of the secret seed, like shown for MurmurHash, then, indeed, it is easy to break the hash table - and if it is with a probability less than one but still high, an attack might still succeed. But I cannot see how one could find such preimages for Spooky with a high enough probability to make attacks more efficient than simply flooding with requests. $\endgroup$ – jbaagoe Mar 27 '13 at 12:01
  • 1
    $\begingroup$ To clarify: a similar question has been asked here. But Spooky is very different from Murmur-derived hashes like xxHash: instead of repeated multiplications and rotations on the same word, it uses Additions-Rotations-Xors on 12. The promoters of SipHash never mention Spooky which is faster than Murmur and presumably one of the functions that SipHash aims to replace. $\endgroup$ – jbaagoe Mar 27 '13 at 13:28
  • $\begingroup$ The creators of SipHash actually do mention Spooky in this paper: 131002.net/siphash/siphash.pdf $\endgroup$ – GBleaney Jul 3 '14 at 20:56
5
$\begingroup$

Jean-Philippe Aumasson (the principal author of SipHash) has kindly answered my question by email and acknowledges that he is unaware of an efficient HashDoS attack against SpookyHash. This does not imply that no such attack exists, only that he was unable to find one rapidly.

Improve this answer
$\endgroup$

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.