6 ms·

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

• tveita 14y ago
  > 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 http://www.strchr.com/hash_functions has examples of collision rates for different hashes, all non-cryptographic.
  • wisty 14y ago
    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.
    • kibwen 14y ago
      Hash randomization was actually enabled by default in Python 3.3. http://docs.python.org/3/whatsnew/3.3.html#summary-release-highlights http://docs.python.org/3/whatsnew/3.3.html#summary-release-h...
      • slurgfest 14y ago
        Which means this is not available in PyPy? :(
        • wisty 14y ago
          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 http://doc.pypy.org/en/latest/cpython_differences.html).
• floody-berry 14y ago
  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.
  • pjscott 14y ago
    You have a practical way to generate collisions in, say, SHA-256?
    • floody-berry 14y ago
      You only need to generate collisions for the keyspace used. Brute forcing 20-30 bit collisions in any hash function is trivial.
• pjscott 14y ago
  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.
• zond 14y ago
  [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 :)