12 ms·
This is a good looking hash, just from the construction I can see that it should be extremely fast for bulk hashing of large objects and with strong statistical
by jandrewrogers 8y ago
This is a good looking hash, just from the construction I can see that it should be extremely fast for bulk hashing of large objects and with strong statistical properties.
I do want to comment for the wider audience why the details of this construction does not lend itself to small keys, and how you would fix that. I have an (unpublished, I'm lazy) AES-based hash function that is very fast for both bulk hashing and small keys, which required a mostly performance neutral (likely fits in an unused ALU execution port) tweak to the bulk hashing loop.
Large key performance is entirely in the bulk loop algorithm (an AES round in this case) and small key performance is entirely in the mixer/finalizer algorithm. If you have a very wide bulk loops with no mixing of the individual lanes then it usually requires a deep mixing stage that makes small keys very expensive since that is a fixed overhead. The question then becomes, how do you cheaply "bank" dispersal of bits across lanes in the bulk loop to shorten the mixing stage without creating an operation dependency between lanes that will massively reduce throughput.
As an important observation, vectorizing the AES lanes makes it difficult to disperse bits because there are no good, cheap operations that move bits between lanes. However, the CPU will happily run multiple AES operations and other 128-bit operations concurrently across ALU ports if they are in independent registers. This allows you to trivially create a "mixing" lane that solely exists to aid bit dispersal because you no longer are trying to do sideways operations on a vector. So what does a mixing lane look like that doesn't create dependencies on your hashing lanes? It is so simple it is embarrassing: XOR the input data lanes. The mixing lane is worthless as a hash but it only exists to represent all the bits from all the lanes.
At the mixing stage, you simply fold the mixing lane into each of the hashing lanes by running it through a round of AES -- one concurrent operation. This allows you to avoid the deep mixing stage altogether, which means small keys can be hashed very quickly since almost all of the computation is in the finalizer. Using this technique, I've been able to hash small keys in <30 cycles with concurrent AES lanes.
- jandrewrogers 8y agoAs one more comment, because I've made the same mistake in the past, it is often a bad idea to use the length in the initialization vector of a general purpose hash because it means you can't make an incremental version of the hashing algorithm e.g. a stream of data of unknown size. This is a trivial change but it has side effects in how you pad partial blocks. If the length is not part of the initialization vector, then the padding vector for partial blocks should vary as a function of partial data length. Otherwise it is trivial to create collisions by having partial blocks of different sizes that mimic the padding vector. Fixing this can be as easy as using _mm_set1_epi8(partial_length) as your padding vector.
- 0xb100db1ade 8y agoOn the other hand, https://en.wikipedia.org/wiki/Length_extension_attack https://en.wikipedia.org/wiki/Length_extension_attack Although Meow Hash is described as non-cryptographic, so the described attack is likely not applicable
- DrJosiah 8y agoI'm a fan of your work; I've personally mangled your Metrohash64 in some of my own work for incremental updates. Any chance you're thinking about releasing the program for generating new (good) Metrohash constants + shifts?
- jandrewrogers 8y agoI have a completely new algorithm construction I have been using for a while that I am releasing any day now -- I was literally working on the documentation this weekend. It is a substantial improvement on the original algorithms in almost every regard and also easier to customize.
- DrJosiah 8y agoI look forward to the release, and I know the feeling (writing docs, cleaning up comments, etc.). I've been perpetually ~2 weeks from commercial release of my own product since July or so.
- presscast 8y ago>Large key performance is entirely in the bulk loop algorithm (an AES round in this case) and small key performance is entirely in the mixer/finalizer algorithm. If you have a very wide bulk loops with no mixing of the individual lanes then it usually requires a deep mixing stage that makes small keys very expensive since that is a fixed overhead. The question then becomes, how do you cheaply "bank" dispersal of bits across lanes in the bulk loop to shorten the mixing stage without creating an operation dependency between lanes that will massively reduce throughput. This sounds deeply fascinating, but I'm way out of my depth. Can you suggest any reading that would help me appreciate the "architecture" of hash functions?
- TimTheTinker 8y agoAny clue why this hash isn’t cryptographically secure (beyond the designers’ stated intent)?