3 ms·

I've seen FNV have some unfortunate properties around symmetric keys. I'd at least use Jenkins instead. If not Murmur, this, or Spooky Hash.

by cbsmith 15y ago

tripzilch 15y ago
Symmetric keys?? Which part of "not suitable for cryptographic purposes" did you not understand? Neither FNV, Jenkins, Murmur nor this new City Hash are supposed to be used for cryptography. Besides, the way one generally requires hash functions in cryptography, performance is the least of your worries (unless you're trying to crack), so there's no reason whatsoever not to go with a proper cryptographically strong hash such as SHA256. That said, Jenkins has worse avalanche behaviour than FNV--though I'm sure with a few tweaks that could be fixed, non-crypto hash functions aren't exactly rocket science (check out where FNV's constants came from)--but as it is, Jenkins is more of an academic example. Spooky (also developed by Bob Jenkins) seems better. Oddly enough Spooky claims 3 bytes per cycle, but the author cannot confirm CityHash's 6 bytes per cycle ( http://burtleburtle.net/bob/hash/spooky.html http://burtleburtle.net/bob/hash/spooky.html ). Though whatever it is, both are obviously blazingly fast, picking one over the other because of performance reasons should only be done once you've established that the speed of the hashing function is indeed a bottleneck, and you can compare the performance on the specific hardware it's supposed to run on.
- cbsmith 15y ago
  > Symmetric keys?? Which part of "not suitable for cryptographic purposes" did you not understand? I don't mean symmetric in the cryptographic sense. I mean as in "ABBA" mapping to the same hash value as "YZZY". I can't remember the specific case, but I think it was with 8 byte keys, and it might be like the above or it might be more like "ABAB" and "YZYZ". Either way, it caused some pretty catastrophic failures in one case due to the unusually high probability of such keys existing in our dataset. I've done tests with pretty huge dictionaries on both Jenkins & FNV, and despite FNV's enviable characteristics, empirically Jenkins did much better at avoiding collisions. Sometimes the stuff that looks good on paper has unfortunate characteristics with real world data sets (which typically aren't that random).

I've seen FNV have some unfortunate properties around symmetric keys. I'd at least use Jenkins instead. If not Murmur, this, or Spooky Hash.

by cbsmith 15y ago

I've seen FNV have some unfortunate properties around symmetric keys. I'd at least use Jenkins instead. If not Murmur, this, or Spooky Hash.

tripzilch 15y ago

Symmetric keys?? Which part of "not suitable for cryptographic purposes" did you not understand? Neither FNV, Jenkins, Murmur nor this new City Hash are supposed to be used for cryptography. Besides, the way one generally requires hash functions in cryptography, performance is the least of your worries (unless you're trying to crack), so there's no reason whatsoever not to go with a proper cryptographically strong hash such as SHA256. That said, Jenkins has worse avalanche behaviour than FNV--though I'm sure with a few tweaks that could be fixed, non-crypto hash functions aren't exactly rocket science (check out where FNV's constants came from)--but as it is, Jenkins is more of an academic example. Spooky (also developed by Bob Jenkins) seems better. Oddly enough Spooky claims 3 bytes per cycle, but the author cannot confirm CityHash's 6 bytes per cycle ( http://burtleburtle.net/bob/hash/spooky.html http://burtleburtle.net/bob/hash/spooky.html ). Though whatever it is, both are obviously blazingly fast, picking one over the other because of performance reasons should only be done once you've established that the speed of the hashing function is indeed a bottleneck, and you can compare the performance on the specific hardware it's supposed to run on.

cbsmith 15y ago
> Symmetric keys?? Which part of "not suitable for cryptographic purposes" did you not understand? I don't mean symmetric in the cryptographic sense. I mean as in "ABBA" mapping to the same hash value as "YZZY". I can't remember the specific case, but I think it was with 8 byte keys, and it might be like the above or it might be more like "ABAB" and "YZYZ". Either way, it caused some pretty catastrophic failures in one case due to the unusually high probability of such keys existing in our dataset. I've done tests with pretty huge dictionaries on both Jenkins & FNV, and despite FNV's enviable characteristics, empirically Jenkins did much better at avoiding collisions. Sometimes the stuff that looks good on paper has unfortunate characteristics with real world data sets (which typically aren't that random).