Hacker News new | past | comments | ask | show | jobs | submit login

When SipHash was presented at CCC, it was alongside the proof of concept attacks against MurmurHash and CityHash. See the "Attacks" section of [0].

Murmur was notable at the time for its use in Java and Ruby. Ruby has since moved to SipHash-2-4, while Java (OpenJDK) has thrown up its hands in disgust at the problem and created a binary tree fallback mode for its HashMaps[1]. Which at this point I'm pretty confident is the only rigorously correct solution.

[0]: https://131002.net/siphash/

[1]: http://openjdk.java.net/jeps/180




It's a bit disingenuous to say java has given up and created a binary tree fallback mode. It doesn't actually switch the whole hash table into a binary tree, but rather it switches the linked list inside each bucket into a binary tree, and only when a certain threshold is passed.


If you trigger this fallback (e.g. someone is colliding all your hashes), your entire collection is probably stuffed into one bucket.

Degrading only individual buckets is of course a nice middle ground that avoids harsh discontinuities in performance for slightly bad inputs.


See also http://perl11.org/blog/seed.html "The dangerous SipHash myth"

It's technically impossible to declare a hash function used in hash table secure, a countermeasure against DoS attacks. djb made a bad mistake here. You always get seed exposure somehow. It is independent on the hash function. You can always brute-force it.

So java is right. The only countermeasure against collision attacks are fixes in the collision resolution. Adding stronger hash functions only makes the table slower, but not secure. And lot's of prominent hash tables are insecure, since they drank djb's cool aid.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: