Comment by antirez | Hacker News Reader

Comment by antirez | Hacker News Reader

It is worth adding that if your goal using an hash function is sharding across different servers the CRC function can be good, especially the CRC16 function, that has a smaller output than the CRC32, tends to perform very well with many common "key name" patterns.

It's also worth to note that the CRC16 (and CRC32) function will map every possible input of 16 (or 32) bits to a different output, without collisions, similarly to a block cipher.

EDIT: I would take this web site with a bit of salt, the description of the "One Way" concept in the home page is, as far as I can tell, not correct:

"Another important goal is that "similar" input vectors produce very different output vectors. For the case of table lookup, table keys are usually either human language strings, index numbers, or other data that exhibit non-randomness. For the case of message digest functions, the goal is to make it as difficult as possible to find two different messages that result in the same hash. A hash function with this property is called a one-way hash function."

It's sort of almost correct. He's fumbling his way towards the avalanche property: for a perfect cryptographic hash if you flip a single bit in the input, on average half the bits in the output will change.

http://en.wikipedia.org/wiki/Avalanche_effect

Yes, but the Avalanche effect does not mean it is not invertible. It is possible to design a one way hash function with remarkable avalanche (50% of flipped bits on average after 1 bit change in input) effect but that is easily invertible.

The simplest would be an hash function that outputs an N-bit hash where M bits are a pseudo-random sequence of bits (depending on the input, let's say SHA1(input)) that are used to key a stream cipher, and the rest N-M bits are the XOR between the stream cipher output and part of the input of the hash function.

Perfect Avalanche effect, but the function is invertible.

Only in that special case where the input <= the output of the hash function, as in your example earlier in the thread.

An hash function is invertible enough if it will leak the first three bytes of the input. Does not need to be invertible as F^-1 in mathematical notation.

You should not use a simple hash like a CRC for sharding if you need to remain robust against hostile users. Otherwise the users can bypass the sharding and execute a denial of service.

To give an example, the Linux kernel's network stack uses cryptographically secure hash functions in its hash tables, to ensure that a hostile network cannot cause the kernel's hash tables to devolve into linked lists and thus break the O(1) performance expectations of the kernel.

This can only be fixed with a crypto hash function, that IMHO would be a premature optimization here. Users having this potential problem (key names are result of external user inputs) can simply prefix the key with HMAC(key,secret) truncated to a few bytes.

At that point why not just use the HMAC and drop the weak hash entirely?

antirez, can you recommend some good hashing resources?

I use the well know resources: wikipedia, a few web sites with many hash functions benchmarked that will show up if you google "hash functions".

However this is very interesting IMHO if you want to understand the inner working of CRC: http://www.ross.net/crc/crcpaper.html

If you are interested in cryptographic hash functions a good introduction is "Applied Cryptography" that can be integrated with "Handbook of Applied Cryptography" (all chapters free here: http://www.cacr.math.uwaterloo.ca/hac/).

Would you recommend this source as well?

http://burtleburtle.net/bob/hash/

He did muddle around the definition of one way functions, but the information provided is useful.

http://home.comcast.net/~bretm/hash/8.html This seems to indicate that CRC is not a good fit for hashing.

I have used http://burtleburtle.net/bob/hash/ before and it has worked very well for all the use cases I have thrown at it.

Reply on news.ycombinator.com