Do you hash data <24 bytes a lot? Annoyed that it's hard to do well and fast? Well if you don't need adversarial resistance, then do I have a 64-bit CRC for you: 0x(1)E691A23E28619DF3
Conversation
With this CRC, you can take ANY random non-zero data <192 bits and every change <17 bits will always result in a different hash value. This may not sound impressive so consider this: That's >2^76 combinations of changes that never yield the same 64b hash value! And for any input!
1
14
More so, you can take ANY random non-zero data <192 bits and every combination of changes <9 bits will generate a COLLISION-FREE set of hash values. That's >2^45 hash values. And again, this guarantee is input independent! Try that with your favorite hash function!
1
11
Finally, because this is a CRC, small changes between inputs guarantee bigger changes in the resulting hash value, which is a great property for real-world data and real-world hash tables.
1
9
So what's the catch? There are three:
1) the 191 bit limit on the guarantees made above
2) no adversarial resistance which may or may not matter to you
3) not every CPU supports carry-less multiplication to optimize CRC computation
2
10
If it amuses people, I'm trying to use my GPU to find a solution to the 191 bit limit but the 64-bit CRC space is, um, "very large".
1
14
I also believe that the adversarial resistance problem could easily be solved by randomly permuting the input data, thus preserving the CRC strengths but defeating the attacker's ability to predict how bits feed into the CRC but I haven't tested the practicality of this theory.
2
6
Replying to
Rather than inventing an insecure PRF, you're far better off designing the hash table to avoid degrading to O(n). For example, buckets could become a hash table based on SipHash if they end up with too many collisions or an approach based on another data structure can be used.