4 ms·

Breaking CityHash64, MurmurHash2/3, wyhash, and more

50 points by fanf2 2y ago

aappleby 2y ago
Nooooo my hash functions! :D -Austin (author of MurmurHash)
TacticalCoder 2y ago
> I will quickly explain some of the basics of hash function security and then show how easy it is to break this security for some commonly used non-cryptographic hash functions. OK so non-cryptographic hashes pretend to have security now? > A lot of problems don’t necessarily require secure hash functions, and people would much prefer a faster hash speed. Ah wait: no you're saying that instead of using a cryptographic hash, one may not require a secure hash so may pick a non-cryptographic hash. So now you're saying that non-cryptographic hashes aren't secure. So which one is it? Are non-cryptographic hashes secure or not? Because if they're not secure, I don't see which security there is to be broken there. I was there when all the Java and PHP webservers could be DoS due to collisions. I don't dispute it's doable to find collision in a non-cryptographic hash. But I'm not sure I'd define finding collisions in a non-cryptographic hash as "breaking its security".
- rcxdude 2y ago
  I think the point is "here's the desired properties for a cryptographic hash, and here's a practical demonstration of how non-cryptographic hashes don't have them". I don't think this is meant to be a surprising outcome if you know about the definition of cryptographic hashes, more just an interesting demonstration of how specifically non-cryptographic hashes are non-cryptographic.
- jnwatson 2y ago
  I think you have to give the author a little credit. Sometimes developers pick a non-cryptographic hash and they don't realize they actually need collision resistance, e.g. because an attacker-controlled input can cause an O(1) hash table operation to go O(n). These kinds of articles are great for red teams, since they actually have to demonstrate the problem instead of just switching out the algorithm.
gnabgib 2y ago
None of these hashes are cryptographic. They're designed to be /fast/ and so therefore easier to break. They're mostly only used in developer-controlled situations (hash maps etc) where you probably control the keys (if you don't.. well you're at risk). The risk/cost of a collision (the break) is decreased performance, not a security failure. Crypto hashes don't have a problem of being slow.. they are designed to be slow. The conclusion tries to tie weak/fast hashes to crypto/secure hashes (the https mention), but they're worlds apart.
- rcxdude 2y ago
  Slowness isn't always a desireable property of cryptographic hashing. Generally you only want that property when you are trying to do some kind of key derivation from a human-generated password. In plenty of circumstances you want them to be fast, but hashes that have the desired security properties are all slower than the hashes designed to be fast and work well enough with non-adversarial input.
- fanf2 2y ago
  The point of this post is to demonstrate how easy it is to generate collisions for HashDoS attacks. Cryptographic hash functions are usually designed to be fast since they are on the hot path for cryptographic signatures and for hash-based message authentication codes. Password hashes are designed to be slow, but they are an entirely different beast. The point about https in the conclusion is that the author’s PolyMur hash uses a polynomial construction related to GCM and poly1305, which makes it much harder to invert.
- tedunangst 2y ago
  Crypto hashes are not designed to be slow.
  - rurban 2y ago
    It's relative. They are about 1000x slower than fast, good enough hash functions. Dirt slow. Nobody is talking about password hashes here.
MattPalmer1086 2y ago
A lot of the comments here are getting really hung up on cracking non cryptographic hashes, because they're not supposed to be secure. It's just a nice demonstration of the properties we want in a cryptographic hash function, by showing how easy it can be to abuse hashes that are not designed with those properties.
tommiegannert 2y ago
Thanks! Bookmarked. This could be a really useful resource when testing for e.g. thundering herd issues in data structures, while not being in control of the hash function.

50 points by fanf2 2y ago

Nooooo my hash functions! :D -Austin (author of MurmurHash)

> I will quickly explain some of the basics of hash function security and then show how easy it is to break this security for some commonly used non-cryptographic hash functions. OK so non-cryptographic hashes pretend to have security now? > A lot of problems don’t necessarily require secure hash functions, and people would much prefer a faster hash speed. Ah wait: no you're saying that instead of using a cryptographic hash, one may not require a secure hash so may pick a non-cryptographic hash. So now you're saying that non-cryptographic hashes aren't secure. So which one is it? Are non-cryptographic hashes secure or not? Because if they're not secure, I don't see which security there is to be broken there. I was there when all the Java and PHP webservers could be DoS due to collisions. I don't dispute it's doable to find collision in a non-cryptographic hash. But I'm not sure I'd define finding collisions in a non-cryptographic hash as "breaking its security".

rcxdude 2y ago
I think the point is "here's the desired properties for a cryptographic hash, and here's a practical demonstration of how non-cryptographic hashes don't have them". I don't think this is meant to be a surprising outcome if you know about the definition of cryptographic hashes, more just an interesting demonstration of how specifically non-cryptographic hashes are non-cryptographic.
jnwatson 2y ago
I think you have to give the author a little credit. Sometimes developers pick a non-cryptographic hash and they don't realize they actually need collision resistance, e.g. because an attacker-controlled input can cause an O(1) hash table operation to go O(n). These kinds of articles are great for red teams, since they actually have to demonstrate the problem instead of just switching out the algorithm.

gnabgib 2y ago

None of these hashes are cryptographic. They're designed to be /fast/ and so therefore easier to break. They're mostly only used in developer-controlled situations (hash maps etc) where you probably control the keys (if you don't.. well you're at risk). The risk/cost of a collision (the break) is decreased performance, not a security failure. Crypto hashes don't have a problem of being slow.. they are designed to be slow. The conclusion tries to tie weak/fast hashes to crypto/secure hashes (the https mention), but they're worlds apart.

rcxdude 2y ago
Slowness isn't always a desireable property of cryptographic hashing. Generally you only want that property when you are trying to do some kind of key derivation from a human-generated password. In plenty of circumstances you want them to be fast, but hashes that have the desired security properties are all slower than the hashes designed to be fast and work well enough with non-adversarial input.
fanf2 2y ago
The point of this post is to demonstrate how easy it is to generate collisions for HashDoS attacks. Cryptographic hash functions are usually designed to be fast since they are on the hot path for cryptographic signatures and for hash-based message authentication codes. Password hashes are designed to be slow, but they are an entirely different beast. The point about https in the conclusion is that the author’s PolyMur hash uses a polynomial construction related to GCM and poly1305, which makes it much harder to invert.
tedunangst 2y ago
Crypto hashes are not designed to be slow.
- rurban 2y ago
  It's relative. They are about 1000x slower than fast, good enough hash functions. Dirt slow. Nobody is talking about password hashes here.

MattPalmer1086 2y ago

A lot of the comments here are getting really hung up on cracking non cryptographic hashes, because they're not supposed to be secure. It's just a nice demonstration of the properties we want in a cryptographic hash function, by showing how easy it can be to abuse hashes that are not designed with those properties.

tommiegannert 2y ago

Thanks! Bookmarked. This could be a really useful resource when testing for e.g. thundering herd issues in data structures, while not being in control of the hash function.