4 ms·

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, th

by antirez 15y ago

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

pja 15y ago
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 http://en.wikipedia.org/wiki/Avalanche_effect
- antirez 15y ago
  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.
  - jacquesm 15y ago
    Only in that special case where the input <= the output of the hash function, as in your example earlier in the thread.
    - antirez 15y ago
      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.
thinkbohemian 15y ago
antirez, can you recommend some good hashing resources?
- antirez 15y ago
  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 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/ http://www.cacr.math.uwaterloo.ca/hac/).
  - xtacy 15y ago
    Would you recommend this source as well? http://burtleburtle.net/bob/hash/ http://burtleburtle.net/bob/hash/
  - zohebv 15y ago
    He did muddle around the definition of one way functions, but the information provided is useful. http://home.comcast.net/~bretm/hash/8.html 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/ http://burtleburtle.net/bob/hash/ before and it has worked very well for all the use cases I have thrown at it.
JoshTriplett 15y ago
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.
- antirez 15y ago
  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.
  - JoshTriplett 15y ago
    At that point why not just use the HMAC and drop the weak hash entirely?

by antirez 15y ago

pja 15y ago

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 http://en.wikipedia.org/wiki/Avalanche_effect

antirez 15y ago
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.
- jacquesm 15y ago
  Only in that special case where the input <= the output of the hash function, as in your example earlier in the thread.
  - antirez 15y ago
    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.

thinkbohemian 15y ago

antirez, can you recommend some good hashing resources?

antirez 15y ago
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 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/ http://www.cacr.math.uwaterloo.ca/hac/).
- xtacy 15y ago
  Would you recommend this source as well? http://burtleburtle.net/bob/hash/ http://burtleburtle.net/bob/hash/
- zohebv 15y ago
  He did muddle around the definition of one way functions, but the information provided is useful. http://home.comcast.net/~bretm/hash/8.html 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/ http://burtleburtle.net/bob/hash/ before and it has worked very well for all the use cases I have thrown at it.

JoshTriplett 15y ago

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.

antirez 15y ago
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.
- JoshTriplett 15y ago
  At that point why not just use the HMAC and drop the weak hash entirely?