3 ms·

Looks like a pretty straightforward 64-bit block hash unrolled 4 times. I'd prefer a bit more assymetry in the diffuse() method, but since it passes SMHasher it

Looks like a pretty straightforward 64-bit block hash unrolled 4 times. I'd prefer a bit more assymetry in the diffuse() method, but since it passes SMHasher it's probably OK. I wonder how the Rust version compares with plain-jane C. -Austin (murmurhash guy).

aappleby 10y ago
Actually, just noticed a minor issue - since there's no intermixing between the four lanes and the diffuse() function is the same for all of them, if any of the IVs match then I can swap all the blocks in those lanes and get the same hash out. For example, if IV1 and IV2 match and the block pattern is ABCDABCDABCD, then BACDBACDBACD will produce the same hash value. A minor finalizer change would fix it for any IV (pseudocode as I don't actually know Rust) - vec[0] ^= diffuse(vec[1]); vec[1] ^= diffuse(vec[0]); vec[2] ^= diffuse(vec[3]); vec[3] ^= diffuse(vec[2]); u64 result = diffuse(vec[1] ^ diffuse(vec[3])); that's probably overkill but should work.
- alekratz 10y ago
  I'm not a "hash guy" by any means - what impact would that have on its performance?
  - loeg 10y ago
    None for large strings and you'd have to benchmark small strings.
  - aappleby 10y ago
    Negligible, a few tens of cycles of extra overhead.
- pbsd 10y ago
  That won't help much; you can zero the entire final state easily, e.g., with the message IV0 IV1 IV2 IV3 (or by xoring the latest diffuse() output back into the state), in which case you get diffuse(0) = 0 and with your finalization function you still get easy collisions. The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.
  - Ajedi32 10y ago
    Not sure what you mean by "secure". The linked page flat-out says: > Warning! This is not a cryptographic function, and it certainly should not be used as one. So the focus here is speed, not resistance to malicious actors attempting to generate collisions.
thomasahle 10y ago
Since you clearly pit a lot of thought into these kinds of hash functions, I wonder what you thoughts are about the kind of hash functions used in theory? That is theoretically proven "k-independent" functions, such as polynomial hashing, multiply shift or tabulation hashing?
- aappleby 10y ago
  Making a fast, good hash function isn't too hard now, so some sort of "provable key-independent collision resistance" is definitely the next thing that needs to be worked on. That said, I haven't really looked into the theory much.
  - throwbsidbdk 10y ago
    Have you looked at Siphash? I remember reading recently that murmur has been found to have some predictable hashes independent of salts but a lot of big names still use it since it's fast and has good properties.
    - Gankro 10y ago
      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/ https://131002.net/siphash/ [1]: http://openjdk.java.net/jeps/180 http://openjdk.java.net/jeps/180
      - kccqzy 10y ago
        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.
warmwaffles 10y ago
I love working with murmurhash, but where the hell do I even start learning about hashing and the current theories around it?
- aappleby 10y ago
  Take a look at the tests in SMHasher, they indirectly spell out a lot of what makes a hash "good" (though not all the tests are particularly readable).

aappleby 10y ago

Actually, just noticed a minor issue - since there's no intermixing between the four lanes and the diffuse() function is the same for all of them, if any of the IVs match then I can swap all the blocks in those lanes and get the same hash out. For example, if IV1 and IV2 match and the block pattern is ABCDABCDABCD, then BACDBACDBACD will produce the same hash value. A minor finalizer change would fix it for any IV (pseudocode as I don't actually know Rust) - vec[0] ^= diffuse(vec[1]); vec[1] ^= diffuse(vec[0]); vec[2] ^= diffuse(vec[3]); vec[3] ^= diffuse(vec[2]); u64 result = diffuse(vec[1] ^ diffuse(vec[3])); that's probably overkill but should work.

alekratz 10y ago
I'm not a "hash guy" by any means - what impact would that have on its performance?
- loeg 10y ago
  None for large strings and you'd have to benchmark small strings.
- aappleby 10y ago
  Negligible, a few tens of cycles of extra overhead.
pbsd 10y ago
That won't help much; you can zero the entire final state easily, e.g., with the message IV0 IV1 IV2 IV3 (or by xoring the latest diffuse() output back into the state), in which case you get diffuse(0) = 0 and with your finalization function you still get easy collisions. The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.
- Ajedi32 10y ago
  Not sure what you mean by "secure". The linked page flat-out says: > Warning! This is not a cryptographic function, and it certainly should not be used as one. So the focus here is speed, not resistance to malicious actors attempting to generate collisions.

thomasahle 10y ago

Since you clearly pit a lot of thought into these kinds of hash functions, I wonder what you thoughts are about the kind of hash functions used in theory? That is theoretically proven "k-independent" functions, such as polynomial hashing, multiply shift or tabulation hashing?

aappleby 10y ago
Making a fast, good hash function isn't too hard now, so some sort of "provable key-independent collision resistance" is definitely the next thing that needs to be worked on. That said, I haven't really looked into the theory much.
- throwbsidbdk 10y ago
  Have you looked at Siphash? I remember reading recently that murmur has been found to have some predictable hashes independent of salts but a lot of big names still use it since it's fast and has good properties.
  - Gankro 10y ago
    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/ https://131002.net/siphash/ [1]: http://openjdk.java.net/jeps/180 http://openjdk.java.net/jeps/180
    - kccqzy 10y ago
      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.

warmwaffles 10y ago

I love working with murmurhash, but where the hell do I even start learning about hashing and the current theories around it?

aappleby 10y ago
Take a look at the tests in SMHasher, they indirectly spell out a lot of what makes a hash "good" (though not all the tests are particularly readable).