Hacker News Reader

Comment by Whitespace | Hacker News Reader

I haven't read the article, but the claim of MurmurHash3 having low collision rates is false: you can generate an arbitrary quantity of collisions according to [0].

When this was released last year, ruby[1], jruby[2] and rubinius[3] all switched to siphash[4]. Looking at [5] mentions tomcat, .NET, PHP, etc. all switching away from MurmurHash.

(I'm not saying one would HashDoS one's own database, I'm merely pointing out that MurmurHash3 wasn't _designed_ with low collision rates in mind [siphash is, though])

[0] http://emboss.github.com/blog/2012/12/14/breaking-murmur-has...

[1] http://www.ruby-lang.org/en/news/2012/11/09/ruby19-hashdos-c...

[2] http://jruby.org/2012/12/03/jruby-1-7-1.html

[3] https://github.com/rubinius/rubinius/commit/a9a40fc6a1256bcf...

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

[5] http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2011-481...

[edit: formatting]

View on HN

> MurmurHash3 wasn't _designed_ with low collision rates in mind

There is a difference between "low collision rate" and "collision resistance".

Real-world data often contain regular patterns that can cause "bad" hash functions to give very non-random output, e.g. numbers at fixed intervals, pointers all aligned to 4k boundaries, or long strings that differ only by a short suffix.

For instance, early versions of Java would sample only a few of the characters in a long string to calculate the hash code, which caused horrendous performance if you stored a bunch of related file paths in a hash map.

Most hash functions try to avoid bad behaviour on this kind of good-natured input, but some are better at it than others, due to careful design for random-like distribution, and low collision rates.

http://www.strchr.com/hash_functions has examples of collision rates for different hashes, all non-cryptographic.

Python's hash, for example, will generate lower collisions than a "good" hash function. 'file1', 'file2', and 'file3' will not collide, but end up in sequential boxes, which is very efficient. Of course, you can send python web apps a "cookie of death", in which all cookies collide. There's a patch, but I think it's disabled by default.

Hash randomization was actually enabled by default in Python 3.3.

http://docs.python.org/3/whatsnew/3.3.html#summary-release-h...

Which means this is not available in PyPy? :(

python -R should enable it in 2.X (in the patched version, 2.7.3 is fine). PyPy does not include hash randomization (see http://doc.pypy.org/en/latest/cpython_differences.html).

To clarify: with MurmurHash{2,3} or CityHash, it's easy to generate arbitrary numbers of reasonably small keys which all hash to the same value regardless of what seed is used. This is much worse than most people initially assume when they hear that "collisions in murmurhash have been found".

That said, it's a fine hash function if you're not worried about malicious keys.

[disclaimer]I wrote god[/disclaimer]

As someone in the thread below wrote, Murmur is good if you don't worry about malicious keys (it is not cryptographic, and doesn't claim to be).

I don't worry about malicious keys :)

Murmurs main issue (in an attacker controlled context) is how it incorporates the seed in to the hash, not unexpected collisions on non-malicious data.

Further, _any_ hash, even cryptographic, will not protect you if it is not used with a random seed unknown & unpredictable to the attacker.

You have a practical way to generate collisions in, say, SHA-256?

You only need to generate collisions for the keyspace used. Brute forcing 20-30 bit collisions in any hash function is trivial.

Reply on news.ycombinator.com