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.

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.

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.

I'm not a "hash guy" by any means - what impact would that have on its performance?

None for large strings and you'd have to benchmark small strings.

Negligible, a few tens of cycles of extra overhead.

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

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).

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?

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.

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.

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/

[1]: http://openjdk.java.net/jeps/180

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.

If you trigger this fallback (e.g. someone is colliding all your hashes), your entire collection is probably stuffed into one bucket.

Degrading only individual buckets is of course a nice middle ground that avoids harsh discontinuities in performance for slightly bad inputs.

See also http://perl11.org/blog/seed.html "The dangerous SipHash myth"

It's technically impossible to declare a hash function used in hash table secure, a countermeasure against DoS attacks. djb made a bad mistake here. You always get seed exposure somehow. It is independent on the hash function. You can always brute-force it.

So java is right. The only countermeasure against collision attacks are fixes in the collision resolution. Adding stronger hash functions only makes the table slower, but not secure. And lot's of prominent hash tables are insecure, since they drank djb's cool aid.